斐波那契数列算法分析报告
桌面上的图标不见了怎么办-
斐波那契数列算法分析
背景：
假定你有一雄一雌一对刚出生的兔子，它们在长到一个月大小时开始交配，在第二月
结束时，雌兔子产下另一对兔子，过了一个月后它们也开始繁殖，
如此这般持续下去
。
每只雌兔
在开始繁殖时每月都产下一对兔子，假定没有兔子死
亡，在一年后总共会有多少对兔子？
在一月底，最初的一对兔
子交配，但是还只有
1
对兔子；在二月底，雌兔产下一对兔子，
共有
2
对兔子；在三月底，最老的雌兔
产下第二对兔子，共有
3
对兔子；在四月底，最老的雌兔
产下第三对兔子，两个月前生的雌兔产下一对兔子，
共有
5
对兔子；……如此这般计算下去，
兔
子对数分别是：
1, 1, 2, 3, 5, 8, 13, 21,
34, 55,89, 144, ...
看出规律了吗？从第
3
个数
目开始，每个数目都是前面两个数目之和。这就是著名的
斐波那契（
Fibonacci
）数列。
有趣问题：
< br>1
，
有一段楼梯有
10
级台阶
,
规定每一步只能跨一级或两级
,
要登上第
10
级台阶
有几种不同
的走法
?
答：
这就是一个斐波那契数列：登上第一级台阶有一种登法；登上两级台阶，有
两种登法；
登上三级台阶，有三种登法；登上四级台阶，有五种方法……所以，
1
，
2
，
3
，
5
，
< br>8
，
13
……登
上十级，有
89
种。
2
，
数列中相邻两项的前项比后项的极限是多
少，
就是问，
当
n
趋于无穷大时，
F(n)/F(n+1)
的极限是多少？<
/p>
答：
这个可由它的通项公式直接得到，
极限是
(-1+
√
5)/2
，这个就是所谓的黄金分割点，
也是代表大自然的和谐的一个数字。
数学表示：
F(n) = F(n-1) + F(n-2)
F(1) = 1
F(2) =
1
Fibonacci
数列的数学表
达式就是：
递归程序
1
：
Fibonacci
数列可以用很直观的二叉递归程序来写，用
C++
语言的描述如下：
long fib1(int n)
{
if (n <= 2)
{
}
else
{
return
1;
}
}
return fib1(n-1) +
fib1(n-2);
看上去程序的递归使用很恰当，可是在
用
VC2005
的环境下测试
n=37
的时候用了大约
3s
，
而
n=45
的时候基本下楼打完饭也看不到结果……显
然这种递归的效率太低了！！
递归效率分析：
例如，用下面一个测试函数：
long fib1(int n, int* arr)
{
}
这时，可以得到每个
fib(i)
被计算的次数：
fib(10) = 1
fib(9) = 1
fib(8) = 2
fib(7) =
3
fib(6) = 5
fib(5) = 8
fib(4) = 13
fib(3) = 21
fib(2) = 34
fib(1) = 55
fib(0) = 34
可见，计算
次数呈反向的
Fibonacci
数列，这显然造成了大量重复
计算。
我们令
T(N)
为函数
fib(n)
的运行时间，当
N>=2
的时候我们分析可知：
arr[n]++;
if (n <= 2)
{
}
else
{
}
return
fib1(n-1, arr) + fib1(n-2, arr);
return 1;
T(N) =
T(N-1) + T(N-2) + 2
而
fib(n) = fib(n-1) +
fib(n-2)
，所以有
T(N) >=
fib(n)
，归纳法证明可得：
fib(N) < (5/3)^N
当
N>4
时，
fib
< br>（
N
）
>=
(3/2)^N
标准写法：
显然这个
O
（
(3/
2)^N
）
是以指数增长的算法，基本上是最坏的情况。
其实，这违反了递归的一个规则：合成效益法则。
合成效益法则（
Compound interest rul
e
）：在求解一个问题的同一实例的时候，切勿在
不同的递归调
用中做重复性的工作。
所以在上面的代码中调用
fib(N-1)
的时候实际上同时计算了
fib(
N-2)
。
这种小的重复计算
在递归过
程中就会产生巨大的运行时间。
递归程序
2
：
用一叉递归程序就可以得到近似线性的效率，用
C++
语言的描述如下：
long fib(int
n, long a, long b, int count)
{
}
if (count == n)
return b;
return fib(n, b, a+b,
++count);
long fib2(int
n)
{
}
这种方法虽然是递归了，但是并不
直观，而且效率上相比下面的迭代循环并没有优势。
return fib(n, 0, 1, 1);
迭代解法：
Fibonacci
数列用迭代程序来写也很容易，用
C++
语
言的描述如下：
//
也可以用数组将
每次计算的
f(n)
存储下来，用来下次计算用（空间换时间）
long fib3 (int
n)
{
}
这时程序的效率显然为
O
（
N
）
，
N = 45
的时候
<1s
就能得到结果。
< br>
long x = 0,
y = 1;
for (int j = 1; j <
n; j++)
{
}
return y;
y = x +
y;
x = y - x;
矩阵乘法：
我们将数列写成：
Fibonacci[0] =
0
，
Fibonacci[1] =
1
Fibonacci[n] =
Fibonacci[n-1] + Fibonacci[n-2] (n >=
2)
可以将它写成矩阵乘法形式：
将右边连续的展开就得到：
下面就是要用
O(log(n))<
/p>
的算法计算：
显然用二分法来求，结合
一些面向对象的概念，
C++
代码如下：
class
Matrix
{
public
:
Matrix(
const
Matrix&rhs);
Matrix(
long
a,
long
b,
long
c,
long
d);
Matrix&
operator
=(
const
Matrix&);
friend
Matrix
operator
*(
const
Matrix& lhs,
const
Matrix& rhs)
{
Matrix ret(0,0,0,0);
[0][0]
= [0][0]*[0][0] +
[0][1]*[1]
long
matr[2][2];
[0];
[0][1] = [0][0]*[0][1] +
[0][1]*[1]
[1];
[1][0] = [1][0]*[0][0] +
[1][1]*[1]
[0];
[1][1] = [1][0]*[0][1] +
[1][1]*[1]
[1];
};
M
atrix::Matrix(
long
a,
long
b,
long
c,
long
d)
{
}
Ma
trix::Matrix(
const
Matrix
&rhs)
{
this
->matr[0][0] = [0][0];
this
->matr[0][0] = a;
this
->matr[0][1] = b;
this
->matr[1][0] = c;
this
->matr[1][1] = d;
}
return
ret;