斐波那契数列几种算法分析.doc
版权申诉
36 浏览量
2022-05-06
12:17:47
上传
评论
收藏 70KB DOC 举报
斐波那契数列算法分析
背景：
假定你有一雄一雌一对刚出生的兔子，它们在长到一个月大小时开始交配，在第二月
结束时，雌兔子产下另一对兔子，过了一个月后它们也开始繁殖，如此这般持续下去。每
只雌兔在开始繁殖时每月都产下一对兔子，假定没有兔子死亡，在一年后总共会有多少对
兔子？
在一月底，最初的一对兔子交配，但是还只有 1 对兔子；在二月底，雌兔产下一对兔
子，共有 2 对兔子；在三月底，最老的雌兔产下第二对兔子，共有 3 对兔子；在四月底，
最老的雌兔产下第三对兔子，两个月前生的雌兔产下一对兔子，共有 5 对兔子；……如此
这般计算下去，兔子对数分别是：1, 1, 2, 3, 5, 8, 13, 21, 34, 55,89, 144, ...看出规律
了吗？从第 3 个数目开始，每个数目都是前面两个数目之和。这就是著名的斐波那契
（Fibonacci）数列。
有趣问题：
1，有一段楼梯有 10 级台阶,规定每一步只能跨一级或两级,要登上第 10 级台阶有几
种不同的走法?
答：这就是一个斐波那契数列：登上第一级台阶有一种登法；登上两级台阶，有两种
登 法 ； 登 上 三 级 台 阶 ， 有 三 种 登 法 ； 登 上 四 级 台 阶 ， 有 五 种 方 法 … … 所 以 ，
1，2，3，5，8，13……登上十级，有 89 种。
2，数列中 相邻两项的前项比后项的极限是 多少，就是问，当 n 趋于 无穷大时，
F(n)/F(n+1)的极限是多少？
答：这个可由它的通项公式直接得到，极限是(-1+√5)/2，这个就是所谓的黄金分割
点，也是代表大自然的和谐的一个数字。
数学表示：
Fibonacci 数列的数学表达式就是：
F(n) = F(n-1) + F(n-2)
F(1) = 1
F(2) = 1
递归程序 1：
Fibonacci 数列可以用很直观的二叉递归程序来写，用 C++语言的描述如下：
long b1(int n)
{
if (n <= 2)
{
return 1;
}
资源评论
