作者：夜阑人静1314coolgirl | 来源：互联网 | 2023-05-17 13:26
求fibonacci数列的第n项的算法用非递归的形式 求解其通项公式 并且分析时间复杂度
13 个解决方案
a[0]=1;
a[1]=1;
for(c=2;c<=n;c++)
{
num=a[c-2]+a[c-1];
}
google "线性差分方程"
通项为：
f(n)=(((1+Sqrt(5))/2)^n - ((1-Sqrt(5))/2)^n)／Sqrt(5)
small=1;
big=1;
for(c=3;c <=n;c++)
{
tmp=big;
big += small;
small = tmp;
}
return big;
o(n)
1) 解方程 ... 1 + x = x^2 得解 x1 , x2
2) 令 Fib(n) = A*x1^n + B*x2^n , 代入 Fib(0) = 0 , Fib(1) = 1 ,解二元一次方程组得 A,B
---------------------------------------------
同样如果是 F(n) = F(n-1) + F(n-2) + F(n-3) , F(0) = 0 , F(1) = 0 , F(2) = 1 则这样求通式:
1) 解方程 ... 1 + x + x^2 = x^3 得解 x1 , x2 , x3
2) 令 F(n) = A*x1^n + B*x2^n + C*x3^n 代入 F(0) = 0 , F(1) = 0 , F(2) = 1 解三元一次方程得 A,B,C
谢谢mLee79
敢问楼主
题目难道不是编程"求解其通项公式"么?
找一本讲递归方程解法的教材，都是用费波纳其数列做例子的。
建议搂主看看，知道解题方法，比知道结果好，呵呵。
看不起那9楼的小子,我希望如果谁有算法或在计算机专业方面有什么好的意见,应多拿出来交流,这样使我们走的更快更远,还要什么得分才干.
解:你想想,要是n=1时sum=1,当n=2时,sum也等于,当n>2时,数学函数sum=F(n-1)+F(n-2);(我们用函数作为反回值,Fn来代替)
所以有通项式:n=1 Fn=1;
n=2 Fn=1;
n>2 Fn=F(n-1)+F(n-2);
嗯,好好体会一下!
![[译]技术公司十年经验的职场生涯回顾](https://img8.php1.cn/3cdc5/24912/711/b6574f3292f9dc00.png)
京公网安备 11010802041100号