裴波那契数列的递归和动态规划算法

裴波那契数列的递归和动态规划算法

一、    概论

通过对裴波那契数列的例子，分析了递归和动态规划算法的本质。并且说明了两种算法的区别。

裴波那契数列：800年前，意大利的数学家斐波纳契出版了惊世之作《算盘书》。在《算盘书》里，他提出了著名的“兔子问题”：假定一对兔子每个月可以生一对兔子，而这对新兔子在出生后第二个月就开始生另外一对兔子，这些兔子不会死去，那么一对兔子一年内能繁殖多少对兔子？

答案是一组非常特殊的数字：1，1，2，3，5，8，13，21，34，55，89……不难发现，从第三个数起，每个数都是前两数之和，这个数列则称为“斐波纳契数列”，其中每个数字都是“斐波纳契数”。

斐波纳契数列还暗含着许多有趣的数字规律，如从第3个数开始每隔两个必是2的倍数，从第4个数开始每隔3个必是3的倍数，从第5个数开始每隔4个必是5的倍数……另外，这个数列最具有和谐之美的地方是，越往后，相邻两项的比值会无限趋向于黄金比0.61803……即[5^(1/2)-1]/2。

但这个伟大的发现在当时一直不受数学们的青睐与认可，直到19世纪，斐波纳契数列才在该领域占有一席之地并引发出了许多重要的应用。像斐波纳契方块，斐波纳契螺旋以及斐波纳契数，在生活中都可以见到类似的图案，譬如说海螺和蜗牛壳等等。

----------------------------以上来自360百科

这个数列感觉还是非常有意思的。感兴趣的同学可以多多研究一下。另外本文只是本人一个简单的分享感悟，有很多不正确的地方，请大家指正。

二、    裴波那契数列的递归分析

由上面的介绍可以得出裴波那契数列的递归算式：

也很容易写出下面的递归算法：

#include <iostream>
 using namespace std;
 //采用递归的方式求解裴波纳契数列
 int f(int n)
 {
 if(n==0)return 1;
 if(n==1)return 1;
 return f(n-1)+f(n-2);
 }
 int main()
 {
 //输出数列的前20项
 for(int i=0;i<20;i++)
 {
 cout<<"第i项："<<f(i)<<endl;
 }
 return 0;
 }

输出结果如图：

递归算法时间复杂度分析：

由上面的递归树可以分析，最右边是每次减少2，因此右边的层次数是最低的，因此可以通过右边的层次来计算最少的时间复杂度。

每次个节点都产生两个子节点，因此子节点的个数，就是要计算的复杂度，即总共需要计算：

c是一个常数，即两个数相加需要的时间。

根据上述等比数列，可以知道时间复杂度为指数级别（具体多少读者可以根据上面的算式计算）。

因此采用递归会导致大量的重复计算，例如在图中的f(n-3)就会被计算两次。同时，由于计算机本身的性质，递归次数不能过多，否则会导致栈溢出，导致程序崩溃。因此这里采用递归算法不仅造成时间复杂度很大，同时还造成栈溢出的可能。

本例中，当采用递归求解第40项的时，速度已经很慢，求解第50项的时，已经没有响应了。

三、    裴波那契数列的动态规划分析

动态规划的主要两个步骤：

a)         最优解的结构

f(i)=f(i-1)+f(i-2)，这就是最优解的结构，只不过不像一般的问题，这里的子结构都是固定的

b)         递归定义最优解

这里的递归定义和递归算法中的公式是一样的。

c)         自底向上

从底向上的求解，这里是最大的区别。递归算法是从上到下的计算，即将大问题分别分解成若干个小问题，然后递归求解小问题，直到达到原子问题，然后开始逐步返回，计算每个大的问题。即存在某些问题会反复计算多次。

而从底向上的解法，则是从小问题开始，计算完成后就记录下小问题的解，然后通过小问题的解，构造出大问题的解，如此重复。即每个问题只需要计算一次即可。

d)         由结果构造最优解

动态规划算法：

#include <iostream>
 using namespace std;
 //采用递归的方式求解裴波纳契数列
 int f(int n)
 {
 if(n==0)return 1;
 if(n==1)return 1;
 return f(n-1)+f(n-2);
 }
 //采用动态规划思想求解裴波纳契数列
 static int record[40]={0};
 void count(int n)
 {
 record[0]=1;
 record[1]=1;
 for(int i=2;i<n;i++)
 {
 record[i]=record[i-1]+record[i-2];
 }
 }
 int main()
 {
 //输出前20项
 count(20);
 for(int i=0;i<20;i++)
 {
 cout<<record[i]<<endl;
 }
 return 0;
 }

输出结果：

时间复杂度分析：

比较容易知道，上面的算法只是到n的一个简单循环，因此时间复杂度是o(n)，即n的线性时间复杂度。

本例中，当采用递归求解第40和第50项项的时，速度很快。

四、    结合了动态规划和递归两种方法的思想求解裴波纳契数列

结合两种方法的优点，即采用递归容易理解的结构，同时加入动态规划中的记录表，防止递归中的重复计算。即记录递归过程中产生的每一个值，如果遇到已经曾经计算过的小问题的值，则不再重复递归，直接返回即可。

算法如下：

#include <iostream>
 using namespace std;
 //采用递归的方式求解裴波纳契数列
 int f(int n)
 {
 if(n==0)return 1;
 if(n==1)return 1;
 return f(n-1)+f(n-2);
 }
 //采用动态规划思想求解裴波纳契数列
 static int record[40]={0};
 void count(int n)
 {
 record[0]=1;
 record[1]=1;
 for(int i=2;i<n;i++)
 {
 record[i]=record[i-1]+record[i-2];
 }
 }
 //结合了动态规划和递归两种方法的思想求解裴波纳契数列
 static int c[40]={1,1,0};
 int f_count(int n)
 {
 if(n==0)return c[0];
 if(n==1)return c[1];
 //如果两个子问题已经存在解 则直接返回这个解，并且记录当前问题的解
 if(c[n-1]!=0 && c[n-2]!=0)
 {
 c[n]=c[n-1]+c[n-2];
 return c[n];
 }
 //如果不存在，则递归求解
 else
 {
 return f_count(n-1)+f_count(n-2);
 }
 }
 int main()
 {
 //输出前20项
 f_count(20);
 for(int i=0;i<20;i++)
 {
 cout<<c[i]<<endl;
 }
 return 0;
 }

算法输出：

时间复杂度分析：

由于记录了曾经计算过的值，因此导致很多点不再被重复计算，仅仅是一个简单的一重递归，即时间复杂度为o(n)，即为n的线性时间。

本例中，当采用递归求解第40和第50项项的时，速度同样很快。

五、    总结

个人感觉，其实在某种程度上来说，动态规划和分治法是有着相同的思想。分治法的思想是将大问题分解为小问题。而动态规划思想是取最优子结构。但是从计算方法上来说，分治法是自顶向下的分解问题，然后自底向上返回问题的解。而动态规划一开始就直接从底向上的将小问题的解综合成大问题的解。动态规划相对分治法中的递归算法时间上是采用了以空间换时间的方式。即在计算小问题的过程中记录下小问题的值。而递归是不会记录小问题的值，每次都是重复计算。

而采用两种方法相结合的方式也同样可以提高运行速度。其内在原因就是是否重复计算的问题。

文档下载地址：http://pan.baidu.com/share/link?shareid=531539743&uk=2903070410

源代码下载地址：http://pan.baidu.com/share/link?shareid=535428463&uk=2903070410