概述

你能写出多少个斐波那契数列的解法？递归？
如果有一个问题要你去求一个斐波那契数列的前n项乘积（n<=99989）！！！
怎么办？
你还去递归求解，然后再去算乘积！那你的有可能就TLE了，所以接下来给大家推荐几个好的算法。

C（C++函数）代码

递归算法实现

uint64_t fibonacci1(unsigned int n) {
    if (n == 0) return 0;
    if (n <= 2) return 1;
    return fibonacci1(n - 1) + fibonacci1(n - 2);
}

循环迭代算法实现

uint64_t fibonacci2(unsigned int n) {
    if (n == 0) return 0;
    if (n == 1 || n == 2) return 1;
    uint64_t f1 = 1, f2 = 1, fn;
    for (unsigned int i = 3; i <= n; i++) {
        fn = f1 + f2;
        f1 = f2;
        f2 = fn;
    }
    return fn;
}

原始矩阵算法实现

uint64_t fibonacci3(unsigned int n) {
    uint64_t m[2][2] = { 1,1,1,0 }; // 1次矩阵
    uint64_t result[][2] = { 1,0,0,1 }; // 单位矩阵
    uint64_t temp[2][2];
    // 计算n次矩阵
    for (unsigned int i = 1; i <= n; i++) {
        temp[0][0] = result[0][0] * m[0][0] + result[0][1] * m[1][0];
        temp[0][1] = result[0][0] * m[0][1] + result[0][1] * m[1][1];
        temp[1][0] = result[1][0] * m[0][0] + result[1][1] * m[1][0];
        temp[1][1] = result[1][0] * m[0][1] + result[1][1] * m[1][1];
        memcpy(result, temp, sizeof(uint64_t) * 4);
    }
    return result[1][0] * 1;
}

矩阵快速幂优化算法

uint64_t fibonacci4(unsigned int n) {
    uint64_t m[2][2] = { 1,1,1,0 }; // 1次矩阵
    uint64_t result[][2] = { 1,0,0,1 }; // 单位矩阵
    uint64_t temp[2][2];
    while (n) {
        if (n & 1) {
            temp[0][0] = result[0][0] * m[0][0] + result[0][1] * m[1][0];
            temp[0][1] = result[0][0] * m[0][1] + result[0][1] * m[1][1];
            temp[1][0] = result[1][0] * m[0][0] + result[1][1] * m[1][0];
            temp[1][1] = result[1][0] * m[0][1] + result[1][1] * m[1][1];
            memcpy(result, temp, sizeof(uint64_t) * 4);
        }
        // 2、4、8...次幂矩阵
        temp[0][0] = m[0][0] * m[0][0] + m[0][1] * m[1][0];
        temp[0][1] = m[0][0] * m[0][1] + m[0][1] * m[1][1];
        temp[1][0] = m[1][0] * m[0][0] + m[1][1] * m[1][0];
        temp[1][1] = m[1][0] * m[0][1] + m[1][1] * m[1][1];
        memcpy(m, temp, sizeof(uint64_t) * 4);
        n >>= 1;
    }
    return result[1][0] * 1;
}

矩阵快速幂查表算法

uint64_t fibonacci5(unsigned int n) {
    const static uint64_t cache[][2][2] = {
        { 1, 0, 0, 1 },// 0次幂(无用)
        { 1, 1, 1, 0 },// 1次幂(2^0,1)
        { 2, 1, 1, 1 },// 2次幂(2^1,2)
        { 5, 3, 3, 2 },// 4次幂(2^2,3)
        { 34, 21 ,21, 13 },// 8次幂(2^3,4)
        { 1597, 987, 987 ,610 },// 16次幂(2^4,5)
        { 3524578, 2178309, 2178309, 1346269 },// 32次幂(2^5,4)
        { 17167680177565, 10610209857723, 10610209857723, 6557470319842 },//64次幂(2^6,5)
        { 8102862946581596898, 18154666814248790725, 18154666814248790725, 8394940206042357789 }//128次幂(2^7,6)
    };
    uint64_t result[][2] = { 1, 0, 0, 1 }; // 单位矩阵
    uint64_t temp[2][2];
    int bit_pos = 1;
    while (n) {
        if (n & 1) {
            temp[0][0] = result[0][0] * cache[bit_pos][0][0] + result[0][1] * cache[bit_pos][1][0];
            temp[0][1] = result[0][0] * cache[bit_pos][0][1] + result[0][1] * cache[bit_pos][1][1];
            temp[1][0] = result[1][0] * cache[bit_pos][0][0] + result[1][1] * cache[bit_pos][1][0];
            temp[1][1] = result[1][0] * cache[bit_pos][0][1] + result[1][1] * cache[bit_pos][1][1];
            memcpy(result, temp, sizeof(uint64_t) * 4);
        }
        n >>= 1;
        bit_pos++;
    }
    // result[1][0] * 1 + result[1][1] * 0;
    return result[1][0] * 1;
}

通项公式直接求解

uint64_t fibonacci6(unsigned int n) {
    const double sqrt5 = 2.2360679774997896964091736687313;
    const double a = (sqrt5 + 1) / 2;
    const double b = (1 - sqrt5) / 2;
    const double sqrt1_5 = 1 / sqrt5;

    return (uint64_t)((pow(a, n) - pow(b, n))*sqrt1_5);
}

矩阵求解

void power_matrix(uint64_t m[][2], unsigned int exp) {
    uint64_t result[][2] = { 1,0,0,1 }; // 单位矩阵
    uint64_t temp[2][2];
    // 计算n次矩阵
    for (unsigned int i = 1; i <= exp; i++) {
        temp[0][0] = result[0][0] * m[0][0] + result[0][1] * m[1][0];
        temp[0][1] = result[0][0] * m[0][1] + result[0][1] * m[1][1];
        temp[1][0] = result[1][0] * m[0][0] + result[1][1] * m[1][0];
        temp[1][1] = result[1][0] * m[0][1] + result[1][1] * m[1][1];
        memcpy(result, temp, sizeof(uint64_t) * 4);
    }
    memcpy(m, result, sizeof(uint64_t) * 4);
}
void generate_matrix() {
    uint64_t m[2][2] = { 1,1,1,0 }; // 1次矩阵
    uint64_t temp[2][2];
    for (int i = 0; i < 8; i++) {
        memcpy(temp, m, 4 * sizeof(uint64_t));
        printf("{");
        power_matrix(temp, 1 << i);
        for (int j = 0; j < 2; j++) {
            for (int k = 0; k < 2; k++) {
                printf("%llu, ", temp[j][k]);
            }
        }
        printf("},\n");
    }
}

整数乘法的实现(使用加法和移位操作)

int quick_multi(int a, int b) {
    int bits, factor;
    if (a < b) {
        bits = a;
        factor = b;
    }
    else {
        bits = b;
        factor = a;
    }

    int result = 0;
    while (bits) {
        if (bits & 1)
            result += factor;
        bits >>= 1; // 除2
        factor <<= 1; // 乘2
    }
    return result;
}

整数快速幂运算

int quick_pow(int base, int exp) {
    int result = 1;
    while (exp) {
        if (exp & 1)
            result *= base;
        exp >>= 1;
        base <<= 1; 
    }
    return result;
}

比较测试

/* 计算时间间隔 */

double duration(struct timespec *end, struct timespec *start) {
    double d_sec = difftime(end->tv_sec, start->tv_sec);
    long d_nsec = end->tv_nsec - start->tv_nsec;
    return (d_sec*10e9 + d_nsec);
}

/* 算法测试 */
void compare_and_test() {
    typedef uint64_t(*PFUNC)(unsigned int n);
    PFUNC pFuncs[] = { fibonacci2 ,fibonacci3, fibonacci4, fibonacci5, fibonacci6 };
    struct timespec start, end;
    for (int j = 0; j < sizeof(pFuncs) / sizeof(PFUNC); j++) {
        timespec_get(&start, TIME_UTC);
        // 93项后会发生溢出，这里测试计算时间，所以不关心溢出问题
        for (int i = 0; i < 95; i++) {
#           ifdef NDEBUG
            (*pFuncs[j])(i);
#           else
            printf("%llu ", (*pFuncs[j])(i));
#           endif
        }
        timespec_get(&end, TIME_UTC);
        printf("\t duration: %lf nanosecond\n", duration(&end, &start));
    }
}

void main() {
    compare_and_test();//比较时间
    generate_matrix();//调用
}

java

递归

public static long f1(int n) {
    if (n <= 0) {
        throw new RuntimeException("输入参数小于1");
    }
    if (n == 1 || n == 2) {
        return 1;
    }
    return f1(n - 2) + f1(n - 1);
}

递归2(HashMap)

static HashMap<Integer, Long> map = new HashMap<>();

public static long f2(int n) {
    if (n <= 0) {
        throw new RuntimeException("输入参数小于1");
    }
    if (n == 1 || n == 2) {
        return 1;
    }
    if (!map.containsKey(n)) {
        map.put(n, f2(n - 2) + f2(n - 1));
    }
    return map.get(n);
}

递归3(数组)

static long[] mArray = new long[8000 + 1];
public static long f3(int n) {
    if (n <= 0) {
        throw new RuntimeException("输入参数小于1");
    }
    if (n == 1 || n == 2) {
        return mArray[n] = 1;
    }
    if (mArray[n] == 0) {
        mArray[n] = f3(n - 1) + f3(n - 2);
    }
    return mArray[n];
}

公式

public static long f6(int n) {
    double result = 0;
    double temp = Math.sqrt(5.0);
    result = (Math.pow((1 + temp) / 2, n) - Math.pow((1 - temp) / 2, n)) / temp;
    return (long) result;
}

矩阵

static long[][] initMatirx = {{1, 1}, {1, 0}};
public static long f7(int n) {
    if (n <= 0) {
        throw new RuntimeException("输入参数小于1");
    }
    if (n == 1 || n == 2) {
        return 1;
    }
    long[][] tem = initMatirx;
    for (int i = 1; i < n - 2; i++) {
        tem = matirxMulti(tem, initMatirx);
    }
    return tem[0][0] + tem[1][0];
}
private static long[][] matirxMulti(long[][] a, long[][] b) {
    long[][] temp = new long[2][2];
    temp[0][0] = a[0][0] * b[0][0] + a[0][1] * b[1][0];
    temp[0][1] = a[0][0] * b[0][1] + a[0][1] * b[1][1];
    temp[1][0] = a[1][0] * b[0][0] + a[1][1] * b[1][0];
    temp[1][1] = a[1][0] * b[0][1] + a[1][1] * b[1][1];
    return temp;
}

矩阵加快速幂

static long[][] initMatirx = {{1, 1}, {1, 0}};
static long[][] unitMatrix = {{1, 0}, {0, 1}};//单位矩阵
public static long f8(int n) {
    if (n <= 0) {
        throw new RuntimeException("输入参数小于1");
    }
    if (n == 1 || n == 2) {
        return 1;
    }
    long[][] result = unitMatrix;
    long[][] tem = initMatirx;
    int m = n - 2;
    while (m != 0) {
        if ((m & 1) == 1) {
            result = matirxMulti(tem, result);
        }
        tem = matirxMulti(tem, tem);
        m >>= 1;
    }
    return result[0][0] + result[1][0];
}

顺序递推

public static long f5(int n) {
        if (n <= 0) {
            throw new RuntimeException("输入参数小于1");
        }
        if (n == 1 || n == 2) {
            return 1;
        }
        long a = 1;
        long b = 1;
        long c = 0;
        for (int i = 3; i <= n; i++) {
            c = a + b;
            a = b;
            b = c;
        }
        return c;
    }

看下来

----->【 详细解释 】