阶乘与斐波那契数的理解

在算法导论第三章中，提到了阶乘和斐波那契数，颠覆或者说是加深了我以前对这两种数的理解。以前是无法想象这个数有多大，但现在是有了一个概念。

阶乘
阶乘的定义为

[plain]
n!= n>0?1:n*(n-1)!

n!= n>0?1:n*(n-1)! 根据斯特林公式Stirling有：

[plain]
n!=sqrt(2pi*n)*(n/e)^n*(1+THETA(1/n))

n!=sqrt(2pi*n)*(n/e)^n*(1+THETA(1/n))
由这个公式，数学中关于阶乘与其他函数大小的比较就了然了。

另一个关系式也有所帮助：

[plain]
n!=sqrt(2pi*n)*(n/e)^n*e^(an)
1/(12n+1)<an<1/(12n)

n!=sqrt(2pi*n)*(n/e)^n*e^(an)
1/(12n+1)<an<1/(12n)

斐波那契数
其定义为

[plain]
F0=0
F1=1
F(i)=F(i-2)+F(i-1),i>=2

F0=0
F1=1
F(i)=F(i-2)+F(i-1),i>=2
序列为：

[plain]
0，1，1，2，3，5，8，13，21…………

0，1，1，2，3，5，8，13，21…………
斐波那契数和黄金分割比例fai与^fai有密不可分的关系。

黄金分割比例为下面方程的两个解：

[plain]
x^2=x+1

x^2=x+1
解为：

[plain]
fai=(1+sqrt(5))/2=1.61803
^fai=(1-sqrt(5))/2=0.61803

fai=(1+sqrt(5))/2=1.61803
^fai=(1-sqrt(5))/2=0.61803
这样就有：

[plain
Fi=(fai^i-^fai^i)/sqrt(5)

Fi=(fai^i-^fai^i)/sqrt(5)
可以归纳法证明。

又由于：

[plain]
abs(^fai^i)/sqrt(5)<1/sqrt(5)<1/2
===>
Fi=floor((fai^i)/sqrt(5)+1/2)

abs(^fai^i)/sqrt(5)<1/sqrt(5)<1/2
===>
Fi=floor((fai^i)/sqrt(5)+1/2)
这样，斐波那契数就是指数增长的。

补充：综合编程 , 其他综合 ,