首页 > 代码库 > 算法竞赛中常见的数学(一):Fibonacci数列

算法竞赛中常见的数学(一):Fibonacci数列

最近做的题目有很多都是与Fabonacci数列有关的,身为信息组蒟蒻的我最近经常与数学组李中一大神(Orz)畅谈,其中包括Fabonacci数列的若干性质,此处做一个总结。

参考资料:

《组合数学(第5版)》、《具体数学(第2版)》

正文:

Fibonacci数列是形如0、1、1、2、3、5、8、13、21、34……的数列。递归形式定义为:

数列F[n]=F[n-1]+F[n-2],其中F[0]=0,F[1]=1。

当然也有这样的类Fibonacci数列,即形如:

G[n]=G[n-1]+G[n-2],但其中G[0]∈Z,G[1]∈Z的数列。

广泛应用于生产生活之中,所以在信息学竞赛中的作用不可小觑,这是一些常见的Fibonacci数列的应用问题:

兔子繁殖问题:呵呵,令人头疼的兔子;

骨牌满铺问题,也可以说是上台阶问题。

先给个小代码求Fibonacci数列的第n项吧:

 1 int fibonacci(int n) 2 { 3     int fh=0,ft=1,fs,temp; 4     if(n==0)return 0; 5     if(n==1)return 1;  6     for(int i=1;i<n;++i) 7     { 8         fs=fh+ft; 9         fh=fs;10         ft=fh;11     }12     return fs;13 }      

当然也可以用递归或递推算法,下面给出递推算法的求项代码:

1 int fibonacci(int n)2 {3      if (n==0) return 0;                     4      if (n==1) return 1;                         5      return (fibonacci(n-1)+fibonacci(n-2));            6 }

下面是最近看到的一些fibonacci数列的性质:

首先是通项公式:

以及它的推导:

还有一个重要性质:

gcd(F(n),F(m))=gcd(n,m);

这个性质要用数论证明,只可惜本蒟蒻还没有学习数论,不能亲自给出证明,不过这个网站里有证明方法,感兴趣可以去看看:

http://www.douban.com/group/topic/33566582/

 

于是生成fibonacci数列就很简单了;

虽然用其通项公式涉及到大量乘方和无理数,但至少当n较大时,用高精度还是可以确保其算法复杂度为线性阶O(n)的,

反正比递归、递推、循环版的生成要容易。

然后许多问题就能够迎刃而解。

 

算法竞赛中常见的数学(一):Fibonacci数列