斐波那契数列

兔子繁殖问题与斐波那契

　　裴波那契（Fibonacci leonardo，约1170-1250）是意大利著名数学家． 他最重要的研究成果是在不定分析和数论方面，他的“裴波那契数列”成为世人们热衷研究的问题．

　　保存至今的裴波那契著作有5部，其中影响最大的是1202年在意大利出版的《算盘书》，《算盘书》中许多有趣的问题中最富成功的问题是著名的“兔子繁殖问题”． 如果每对兔子每月繁殖一对子兔，而子兔在出生后第二个月就有生殖能力，试问一对兔子一年能繁殖多少对兔子？可以这样思考：第一个月后即第二个月时，1对兔子变成了两对兔子，其中一对是它本身，另一对是它生下的幼兔． 第三个月时两对兔子变成了三对，其中一对是最初的一对，另一对是它刚生下来的幼兔，第三对是幼兔长成的大兔子． 第四个月时，三对兔子变成了五对，第五个月时，五对兔子变成了八对，这组数可以用图来表示，这组数从三个数开始，每个数是两个数的和，按此方法推算，第六个月是13对兔子，第七个月是21对兔子……，裴波那契得到一个数列，人们将这个数列前面加上一项1,成为“裴波那契数列”，即：1,1,2，3,5,8,13…． 数列用 表示有： 出人意料的是，这个数列在许多场合都会出现，在数学的许多不同分支中都能碰到它． 如果把普遍目前数列邻项之比作为一个新数列的项，我们得到： ，可以证明这个数列的极限是： ，这是非常有名的黄金分割率，大自然中许多现象总是力求接近黄金比 ，这个黄金比在科学中甚至艺术中也经常出现． 例如，宽比长的比等于黄金比 时最美：黄金比在古希腊建筑和陶瓷中可以经常见到埋在现代建筑设计等方面也越来越多地显示出黄金比的独特魅力． 裴波那契数列的许多有趣的性质和重要应用，引起了近800年数学历史上许多学者的兴趣，世界上有关裴波那契数列的研究文献多得惊人，裴波那契数列不仅是在初等数学中引人入胜，而且它的理论已广泛应用，特别是在数列、运筹学及优化理论方面为数学家们展开了一片施展才华的广阔空间．

　　后人从裴波那契数列得到一系列的辉煌成果，但是我们不能忘记，这些成果都是起因与裴波那契的《算盘书》中提到的兔子问题．

方法1：使用递归解，时间复杂度是n的指数级别

#include

#include

using namespace std;

//f(n)={0,1,1,2,3...} n>=0

int Fibonacci(int n)

{

 if(n<=0)

 return 0;

 if(n==1)

 return 1;

 return Fibonacci(n-1)+Fibonacci(n-2);

}

void main()

{

 int f=Fibonacci(30);

 cout<

 system("pause");

}

方法二：
循环