首页 > 代码库 > 算法竞赛中常见的数学(一):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数列