我不是一个数学Geek,但是有时候也会玩玩课本上没有的东西....没学过数学奥赛.....所以弄出来这些东西也很有成就感了....
这周就玩了两道题.
1.斐波那契数列(Fibonacci)的通项公式:
稍微学过一点OI的同学都会知道斐波那契数列其实就是一个满足A[n+2]=A[n+1]+A[n]的递推式的数列(1,1,2,3,5,8,13,21.......)。
我们在编程的时候为了提高效率都选择用快速幂来写这个程序,但是我特别想直接用通项公式解决这个问题。在NOIp之前,我只是在百度百科上面查过Fibonacci的通项公式,却自己推不出来....这几天正好在复习数列这一章,我就顺便想了想Fibonacci,有了点灵感,就推出来了....下面是推导过程:
//===============================================================
由公式A[n+2]=A[n+1]+A[n] ---------[1]
我们可以构造一个数列B[n]=A[n+2]+x*A[n+1](其中x是未知数)
因为我们可以将公式通过移项变成这个样子:
A[n+2]+x*A[n+1]=y*(A[n+1]+x*A[n])(其中y和x都是未知数)----------[2]
带入B[n]得:B[n]=y*B[n-1] 由此观察B[n]是一个以y为公差的等比数列
将[2]展开后就得到了一个方程组: