菲波那契数列

打破惨案 · 2019-01-20 19:37:20 · 个人记录

在编程中，有一种很经典的题目，这就是以菲波那契数列为原形的题目。这种题目，解法很多，可以用递推，可以用递归，可以用公式。

菲波那契数列：1 1 2 3 5 8 13 21······

菲波那契数列递推式：F_n=F_{n-1}+F_{n-2}

菲波那契数列公式：(1/√5)*{[(1+√5)/2]^n - [(1-√5)/2]^n}

推导过程： 设常数r，s

使得F(n)-rF(n-1)=s[F(n-1)-r*F(n-2)]。

则r+s=1， -rs=1。

……

则F(n)=（√5/5)*{[(1+√5)/2]^n - [(1-√5)/2]^n}。 内容过长，不全列出

这就引出一个问题，即之后方法的取舍，显而易见，我们原来的方法非常好写，而且速度也不错，但如果推出公式，虽然困难，但速度不止要快多少。所以，再编程中，加入数学的思想会大大优化代码，这也指明了学习相关数学的重要性。