斐波那契
斐波 那契
2023-09-27 14:25:00 时间
方法一:利用特征方程(线性代数解法)
斐波那契 f(n+1) = f(n)+f(n-1)
线性递推数列的特征方程为:
X^2=X+1
解得
X1=(1+√5)/2, X2=(1-√5)/2.
则F(n)=C1*X1^n + C2*X2^n
∵F(1)=F(2)=1
∴C1*X1 + C2*X2=C1*X1^2 + C2*X2^2=1
解得C1=1/√5,C2=-1/√5
∴F(n)=(1/√5)*{[(1+√5)/2]^n - [(1-√5)/2]^n}【√5表示根号5】
X^2=X+1
解得
X1=(1+√5)/2, X2=(1-√5)/2.
则F(n)=C1*X1^n + C2*X2^n
∵F(1)=F(2)=1
∴C1*X1 + C2*X2=C1*X1^2 + C2*X2^2=1
解得C1=1/√5,C2=-1/√5
∴F(n)=(1/√5)*{[(1+√5)/2]^n - [(1-√5)/2]^n}【√5表示根号5】
缺点是计算机中浮点数不准确
方法二:矩阵
(f_n,f_n-1) = (f_n-1,f_n-2)*A
1 1
A ={ } 这个矩阵太丑了。。。
1 0
所以 (f_n,f_n-1) = (f_1,f_0) * A^n-1
然后就是矩阵的幂乘法,,,利用快速幂可求
如果是f(k) = f(k-1)+f(k-2)+f(k-3)
那么
1 1 0
A = { 1 0 1 }
1 0 0
这种注意观察就可以了。
相关文章
- 斐波那契数列
- 【禅与计算机程序设计艺术】使用 16 门编程语言实现斐波那契数列:循环控制指令与函数递归思想
- LeetCode_斐波那契数列_简单_509.斐波那契数
- 斐波那契数列的几种写法 2021-02-23
- 剑指 Offer 10- I. 斐波那契数列
- 斐波那契数列
- LeetCode------斐波那契数列(2)
- 1303. 斐波那契前 n 项和
- 717. 简单斐波那契
- 2019牛客多校第五场 generator 1——广义斐波那契循环节&&矩阵快速幂
- AcWing 205. 斐波那契
- 斐波那契数列的和
- 【ybt高效进阶6-1-2】斐波那契数列(矩阵乘法)
- 变形斐波那契数列的和 II
- [Amazon] Program for Fibonacci numbers 斐波那契数列
- 剑指offer【07】- 斐波那契数列(java)
- 【算法递归】斐波那契数列