关于斐波那契数列

╰半夏微凉° 2022-09-24 00:23 95阅读 0赞

# 斐波那契数列 #

## 代码1 ##

// 分分钟写出来的代码
    int fib(int n)
    {
            if (n == 0 || n == 1)
                    return n;
    
            return fib(n-1) + fib(n-2);
    }

## 分析代码1 ##

递归使整个代码非常简洁，然而代码是有问题的

1.  考虑n值特别大的情况，上万的一个值，递归可能使栈溢出（OOM），
2.  递归调用是非常耗时的操作，可是函数调用开销大，递归层次非常多时，整个进程就卡死了。
3.  考虑过返回值两个int值之和可能溢出的问题吗？

## 代码2 ##

// 考虑1和2的问题，通常递归都能写成迭代循环的方式
    int fib2(int n)
    {
            if (n == 0 || n == 1)
                    return n;
            // 斐波那契数列 0,1,1,2,...,prev1,prev2,cur,...
            int prev1 = 0, prev2 = 1;
            int cur;
    
            for (int i = 2; i <= n; i++) {
                    cur = prev1 + prev2;
                    prev1 = prev2;
                    prev2 = cur;
            }
    
            return cur;
    }

## 代码2分析 ##

迭代的方式解决了代码1中1和2 的问题，计算机执行迭代非常快，而且栈的使用也非常少。  
然而并没有解决3，整型变量之和溢出的问题？

// 据测试n = 49就溢出了
    [renwotao@localhost workspace]$ ./fib
    100
    fab2(100) = -980107325
    [renwotao@localhost workspace]$ ./fib
    50
    fab2(50) = -298632863
    [renwotao@localhost workspace]$ ./fib
    20
    fab2(20) = 6765
    [renwotao@localhost workspace]$ ./fib
    40

## 关于代码中问题3的解决 ##

无论是int和long还是long long ，只要是有符号整型，在相同符号相加或不同符号相减都有可能溢出，即结果超出有符号整型的表示范围。在科学计算中，采用[高精度算法][Link 1]来处理大数字的数学计算。

[Link 1]: http://baike.baidu.com/link?url=5DD1NruJDBRCySne-89DUVwFJrj6HwX6_hOl1ZEtYiR05JqG6i23OGvWqizy3dj-