By

Contents

斐波那契数列是有一个传奇的数学家基于一对非常能生的兔子提出的（喜欢数学游戏的卖兔子的商人？）：一对兔子每个月能生出一对小兔子来。如果所有兔都不死，那么一年以后可以繁殖多少对兔子？每个月兔子数量最终构成了一个了一个神奇的数列，这数列中除了第零项和第一项，其他所有的项都等于前面两项之和：F(n) = F(n-1) + F(n-2)

这里我先不讨论斐波拉契数列的各种事神奇的特性，比如它和黄金分割的关系，比如自然界的花瓣或者树叶或者数字与斐波拉契数列的巧合，比如晶体原子排列和斐波拉契数列的关联，比如研究股票的某些坑神尝试使用斐波拉契数列去探索跌涨规律等等。总之，看到斐波拉契数列你就会怀疑我们的世界是不是就是某个更高级的文明根据一堆奇奇怪怪数学原理来设计的呢……
在这里我就简单研究下怎么使用java实现计算斐波拉契数列的第N个数。
首先斐波拉契数列的特性就是一种递归的实现，所以我们可以简单的使用递归的方式求解它。代码结构优雅简洁：

int calculateRecursion(int n){
        if(n < 2){
            return n;
        }
        return calculateRecursion(n -1) + calculateRecursion(n -2);
}

但是递归算法终究是会导致资源的浪费和堆栈占用的暴增，但计算数值一旦变大，最终会导致堆栈溢出。并且这个递归算法中对同样的位数的斐波那契数进行了重复计算和存储也导致了计算资源的浪费。
代码结构简洁并不一定代码代码效率好，那么我们尝试把递归计算过程的数字保存下来，当发现已经计算过的就直接使用：

Integer[] fibs = new Integer[n+1];
int calculateRecursion(int n){
    if(fib[n] == null && n < 2){
        fibs[n] = n;
    }else if(fib[n] == null){
        fibs[n] = calculateRecursion(n -1) + calculateRecursion(n -2);
    }
    return fibs[n];
}

这样我们递归终于可以省掉一些额外的计算消耗了，但是代码好像看起来越来越臃肿了。那么我们尝试下不使用递归来实现另外一种求解斐波拉契数列的方式。

int calculateLinear(int n){
    if(n < 2){
        return n;
    }
    int f = new int[n + 1];
    f[0] = 0; f[1] = 1;
    for(int i = 2; i< n; i++){
        f[i]= f[i-1] + f[i-2];
    }
    return f[n];
}

这个段代码我们还可以继续简化它的存储占用。因为斐波拉契数列第N个数只和它的前两个相邻数相关，所以在计算过程中，其实我们只需要存储相关两个数，就可以计算出第N个数了，完全没有必要存储每一位的数值。

int calculateLinear(int n){
    //看，我们连数值界限判断都可以省掉了，真是太优雅了！
    int f0 = 0, f1 = 1;
    for(int i = 0; i< n; i++){
        f1 = f1 + f0;
        f0 = f1 - f0;
    }
    return f0;
}

嗯，这段代码实现也很简洁，并且成功的减少了内存堆栈的消耗。Good！
那么下一个问题来了，斐波拉契数列值是指数增长的，但是java中int类型的最大值是

1
2^{31} -1 = 2147483647

当使用上面实现的代码计算就可以发现计算到F[47]的时候就出现溢出了……那么我们换成long类型呢？

long calculateLinear(long n){
    
    long f0 = 0, f1 = 1;
    for(long i = 0; i< n; i++){
        f1 = f1 + f0;
        f0 = f1 - f0;
    }
    return f0;
}

结果是只能计算到前92个……那只好用上BigInteger了：

BigInteger calculateLinear(BigInteger n){
    BigInteger big1 = new BigInteger("1");
    BigInteger f0 = new BigInteger("0"), f1 = big1;
    for(BigInteger i = new BigInteger("0"); i.compareTo(n) == -1; i = i.add(big1)){
        f1 = f1.add(f0);
        f0 = f1.subtract(f0);
    }
    return f0;
}

这样我们就可以计算任意大小的斐波拉契数列的数值了么？
至少我跑了一晚上，计算到了182324，都没有出现什么错误，只不过是越到后面，计算消耗的时间越长就是了……

    fib(182324):    1297286608306366788170744137779958588200611866878942632507224818788883057962361182304458754935156188970882290447672
    ……
Contents