斐波那契数列

article/2025/8/30 2:36:05

斐波那契数列来源于兔子繁殖问题，所以也叫兔子序列。
在这里插入图片描述
最开始我一直不能理解兔子问题怎么和斐波那契数列联系在一起的，然后画了这个图之后，就明白了。
第一年有一对小兔子，一年后成年。成年的兔子又可以生出一对小兔子，如此循环往复，每年的兔子数就构成了一个斐波那契数列。
斐波那契数列有很多马甲：

爬楼梯问题，一次可以爬一级，也可以爬两级；
用1个2 * 1个小矩形覆盖8个2*1的小矩形问题（剑指offer）。

有四种解决方法：

1. 递归

这是最简单，也是效率最差的一种：

    public long recursive(int n) {if (n <= 0) return 0;if (n == 1) return 1;return recursive(n - 1) + recursive(n - 2);}

时间复杂度指数级，他的递归通项公式可以转换为一个齐次二阶常系数差分方程：
设f(n)为参数为n时的时间复杂度，很明显：f(n)=f(n-1)+f(n-2) ，且f(0)=0; f(1)=1;
特征方程为：x^2-x-1=0
得 x=(1±√5)/2
因而f(n)的通解为:
在这里插入图片描述
由f(0)=0; f(1)=1可解得c_1，c_2
最终可得，时间复杂度为：

真是没想到，高数里的差分方程在这里用到了，说真的，我刚看到这里还挺惊喜的。

2. 数学公式法

有了上述时间复杂度的分析，就可以直接套用最后得出的公式，直接利用给的n计算x，时间复杂度O（logn）。因为涉及到幂运算。

3. 动态规划

利用动态规划的思想，利用递归分析问题，找到状态转移方程，然后从第一个状态开始迭代到最终状态。

这里的状态转移方程是：f(n) = f(n - 1) + f(n - 2) (n > 2)
初始状态：f(0) = 0; f(1) = 1;

    public long addition(int n) {int[] result = {1, 2};if (n < 2) {return result[n];}long n1 = 0;long n2 = 1;long n3 = 0;for (int i = 2; i <= n; i++) {n3 = n1 + n2;n1 = n2;n2 = n3;}return n3;}

4. 矩阵乘法

在这里插入图片描述
根据这个公式写代码算就完事了。

let matrix22_mul = (x, y) = >{[x[0][0] * y[0][0] + x[0][1] * y[1][0], x[0][0] * y[0][1] + x[0][1] * y[1][1],x[1][0] * y[0][0] + x[1][1] * y[1][0], x[1][0] * y[0][1] + x[1][1] * y[1][1]]
}
let matrix22_pow = (x, n) =>{var r = [[1,0],[0,1]];var v = x;while (n) {if (n % 2 == 1) {r = matrix22_mul(r, v);n -= 1;}v = matrix22_mul(v, v);n = n / 2;}return r;
}
let fibnacci = n => n <= 0 ? 0 : matrix22_mul([[0,1],[0,0]], matrix22_pow([[0,1],[1,1]], n - 1))[0][1];