算法竞赛中常见的数学（1）：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 }