斐波那契序列.pdfVIP

斐波那契序列(转的)

[定理1]标准Fibonacci序列（即第0项为0，第1项为1的序列）当N大于1时，一定有f(N)

和f(N-1)互质

其实，结合―互质‖的定义，和一个很经典的算法就可以轻松证明

对，就是辗转相除法

互质的定义就是最大公约数为1

数学归纳法是很有用的证明方法，我们接下来这个定理用数学归纳法就很好证明：

[定理2]若i为奇数，f(i)*f(i)=f(i-1)*f(i+1)+1，否则f(i)*f(i)=f(i-1)*f(i+1)-1

对，这个定理用数学归纳法可以轻松证明，大家有兴趣可以自己尝试

[定理3]f(n)=f(i)*f(n-i-1)+f(i+1)*f(n-i)

f(n)=f(1)*f(n-2)+f(2)*f(n-1)

=f(2)*f(n-3)+f(3)*f(n-2)

=f(3)*f(n-4)+f(4)*f(n-3)

看来没有错，证明方法就是这样

这个公式也可以用来计算较大的fibonacci数除以某个数的余数

设i=n/2不过，为了保证计算能延续下去需要每次保留三个值

这样，下一次计算就可以利用这三个值来求出两个值，再相加就可以得到第三个值

譬如，计算出f(5),f(6),f(7)，可以计算出f(11)、f(12)，然后推出f(13)

就是刚才洛奇的悲鸣(364738334)所提到的矩阵方法

我们知道我们若要简单计算f(n)，有一种方法就是先保存

a=f(0),b=f(1)，然后每次设：

a’=bb’=a+b

并用新的a’和b’来继续这一运算

如果大家熟悉利用―矩阵‖这一工具的话，就知道，如果把a、b写成一个向量[a,b]，完成上

述操作相当于乘以矩阵

01

11

也就是说，如果我们要求第100个fibonacci数，只需要将矩阵

[0,1]乘上

01

11

的一百次方，再取出第一项

因为我们知道，矩阵运算满足结合律，一次次右乘那个矩阵完全可以用乘上那个矩阵的N

次方代替，更进一步，那个矩阵的N次方就是这样的形式：

f(n-1)f(n)

f(n)f(n+1)

而求矩阵的N次方，由于矩阵乘法满足结合律，所以我们可以用log(N)的算法求出——这

个算法大家都会么？

一个是二分，一个是基于二进制的求幂

二分的原理：要求矩阵的N次方A(N)，设i=N/2若N%2==1，则A(N)=A(i)*A(i)*A(1)若

N%2==0，则A(N)=A(i)*A(i)

基于二进制的原理：将N拆为二进制数，譬如13=1101那么A^13=A^8*A^4*A^1（这里

^表示幂运算）

也就是说，由A^1开始，自乘得到A^2，然后自乘得到A^4，如果N对应位为1，则将这个

结果乘到目标上去

这样的话，将所有乘法改为模乘，就可以得到一个较大Fibonacci数除以M的余数

若不用递归，其实类似

这里用的fib矩阵略有不同，是

f(n+1)f(n)

f(n)f(n-1)

但实际上可以验证效果是一样的

这题是要求求F(n)的最后四位数，所有乘法过程增加一个模10000的步骤即可，大家可以收

藏稍候AC

关于矩阵我们告一段落，等下会回来继续探讨利用矩阵来解决复杂些的Fibonacci问题

我们来看这题，这题要求求出Fibonacci某项的前四位

当然，用矩阵也可以解决这道题——只要将乘法改为乘并保留前四位

我们采用double保留整数部分四位这题最好还是double吧

不过显然有更好的解法——如果我们知道Fibonacci序列的通项公式

F(n)=(((1+Sqrt(5))/2)^n–((1-Sqrt(5))/2)^n)*1/Sqrt(5)

不过组合数学里也有这一公式的推导方法叫做―线性齐次递推式‖

这个解法的核心是，通解是某个数的幂将f(n)=x^n代入递推方程，可以解出三个通解0和

(1+sqrt(5))/2

通常把―0称作平凡‖解，那么特解就是通解的某个线性组合

再代入f(0)=0f(1)=1，就可以得出我们刚才的公式

不过通常情况下，我们只需要记住那个公式就可以了

提醒大家，记忆公式的时候千万别忘记了系数1/sqrt(5)

因为(1-sqrt(5))/2的绝对值小于1

所以当i较大的时候，往往可以忽略掉这一项

f(i)≈((1+Sqrt(5))/2)^n/sqrt(5);

所以，刚才列举出的HDOJ的1568，可以很简单的30以内直接求解，30以上采用这个公式，

还是用log(