汉诺塔问题的递归和非递归算法_程序员的那些事

（给程序员的那些事加星标）

来源：IT修道者

blog.csdn.net/computerme/article/details/18080511

汉诺塔问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。

大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

如果考虑一下把64片金盘，由一根柱子上移到另一根柱子上，并且始终保持上小下大的顺序。这需要多少次移动呢？

这里需要递归的方法。假设有n片，移动最少次数是f(n).显然f(1)=1,f(2)=3,f(3)=7,且f(k+1)=2*f(k)+1。此后不难证明f(n)=2^n-1。

在本文中，将讨论用递归和非递归的方法来解决汉诺塔问题。

1、 通过递归实现汉诺塔问题的求解

设f(n)为将n片圆盘所在塔全部移动到另一塔最少总次数；由递归算法可知：f(1) = 1;当n>1时，f(n)   = f(n-1) +  1 + f(n-1)。

f(n) = 把上面n-1片圆盘移动到中间塔最少总次数f(n-1) + 把第n片圆盘移动到目标塔+ 把中间盘的n-1片圆盘移动到目标塔最少总次数为f(n-1)。

由数学计算可得：f(n)=2^n-1。(n>0)。此算法的递归代码实现如下所示：

#include <fstream>#include <iostream>#include<time.h>using namespace std;void Move(int n,char x,char y){ cout<<"把"<<n<<"号从"<<x<<"挪动到"<<y<<endl;}void Hannoi(int n,char a,char b,char c){ if(n==1)     Move(1,a,c); else {        Hannoi(n-1,a,c,b);        Move(n,a,c);     Hannoi(n-1,b,a,c); }}int main(){ int n; cout<<"请输入要求解的汉诺塔的阶数："; cin>>n; clock_t start,finish; start = clock(); cout<<"以下是7层汉诺塔的解法:"<<endl; Hannoi(n,'a','b','c'); cout<<"输出完毕！"<<endl; finish = clock(); printf("解决此 %d 阶汉诺塔所需的时间为：%.2f ms\n",n,(double)(finish-start)); system("pause"); return 0;}

2、 通过非递归的思想来实现汉诺塔问题的求解

汉诺塔的非递归算法描述如下：

首先容易证明，当盘子的个数为n时，移动的次数应等于2^n - 1。

一位美国学者发现一种出人意料的方法，只要轮流进行两步操作就可以了。

首先把三根柱子按顺序排成品字型，把所有的圆盘按从大到小的顺序放在柱子A上。

根据圆盘的数量确定柱子的排放顺序：若n为偶数，按顺时针方向依次摆放 A B C；

若n为奇数，按顺时针方向依次摆放 A C B。

（1）按顺时针方向把圆盘1从现在的柱子移动到下一根柱子，即当n为偶数时，若圆盘1在柱子A，则把它移动到B；

若圆盘1在柱子B，则把它移动到C；若圆盘1在柱子C，则把它移动到A。

（2）接着，把另外两根柱子上可以移动的圆盘移动到新的柱子上。

即把非空柱子上的圆盘移动到空柱子上，当两根柱子都非空时，移动较小的圆盘

这一步没有明确规定移动哪个圆盘，你可能以为会有多种可能性，其实不然，可实施的行动是唯一的。

（3）反复进行（1）（2）操作，最后就能按规定完成汉诺塔的移动。

该算法的实现代码如下：

#include <iostream>#include<time.h>using namespace std;// 圆盘的个数最多为64const int MAX = 64;// 用来表示每根柱子的信息struct st { int s[MAX]; //柱子上的圆盘存储情况 int top; //栈顶，用来最上面的圆盘 char name; //柱子的名字，可以是A，B，C中的一个     int Top()//取栈顶元素     {      return s[top]; }     int Pop()//出栈     { return s[top--]; }     void Push(int x)//入栈     { s[++top] = x; }};long Pow(int x, int y); //计算x^yvoid Creat(st ta[], int n); //给结构数组设置初值void Hannuota(st ta[], long max); //移动汉诺塔的主要函数int main(void){     clock_t start,finish;     int n;     cout<<"请输入汉诺塔的阶数：";     cin >> n; //输入圆盘的个数     start = clock(); st ta[3]; //三根柱子的信息用结构数组存储 Creat(ta, n); //给结构数组设置初值 long max = Pow(2, n) - 1;//动的次数应等于2^n - 1     Hannuota(ta, max);//移动汉诺塔的主要函数     finish = clock();     printf("解决此 %d 阶汉诺塔所需的时间为：%.2f ms\n",n,(double)(finish-start)); system("pause"); return 0;}void Creat(st ta[], int n){ ta[0].name = 'A'; ta[0].top = n-1; //把所有的圆盘按从大到小的顺序放在柱子A上 for (int i=0; i<n; i++) ta[0].s[i] = n - i; //柱子B，C上开始没有没有圆盘 ta[1].top = ta[2].top = 0; for (int i=0; i<n; i++) ta[1].s[i] = ta[2].s[i] = 0; //若n为偶数，按顺时针方向依次摆放 A B C if (n%2 == 0) { ta[1].name = 'B'; ta[2].name = 'C'; } else //若n为奇数，按顺时针方向依次摆放 A C B { ta[1].name = 'C'; ta[2].name = 'B'; }}long Pow(int x, int y){ long sum = 1; for (int i=0; i<y; i++) sum *= x; return sum;}void Hannuota(st ta[], long max){ int k = 0; //累计移动的次数 int i = 0;    int ch; while (k < max)    {    //按顺时针方向把圆盘1从现在的柱子移动到下一根柱子    ch = ta[i%3].Pop();    ta[(i+1)%3].Push(ch);    cout << ++k << ": " << "Move disk " << ch << " from " <<ta[i%3].name <<        " to " << ta[(i+1)%3].name << endl;     i++;     //把另外两根柱子上可以移动的圆盘移动到新的柱子上     if(k < max)     {         //把非空柱子上的圆盘移动到空柱子上，当两根柱子都为空时，移动较小的圆盘         if (ta[(i+1)%3].Top() == 0 ||             ta[(i-1)%3].Top() > 0 &&              ta[(i+1)%3].Top() > ta[(i-1)%3].Top())         {             ch =  ta[(i-1)%3].Pop();             ta[(i+1)%3].Push(ch);             cout << ++k << ": " << "Move disk"             << ch << " from " << ta[(i-1)%3].name             << " to " << ta[(i+1)%3].name << endl;         }         else         {             ch =  ta[(i+1)%3].Pop();             ta[(i-1)%3].Push(ch);             cout << ++k << ": " << "Move disk" << ch << " from " << ta[(i+1)%3].name                  << " to " << ta[(i-1)%3].name << endl; } } }}

3、 实验结果及分析（测试时以7阶汉诺塔为例）

使用递归算法时运行的情况：

使用非递归算法时运行的情况：

从实验结果可以看出，与n皇后问题不同，对于汉诺塔问题的求解，当使用递归的方法来解决时它的时间复杂度比非递归的方法要好。

而且，使用递归算法写代码时更容易理解。通过对于汉诺塔问题非递归与递归方法的对比可以得出结论：有的时候使用的递归的方法对于问题的求解不仅更能使人容易理解，而且效率更高。我们在以后编代码时也应该注意递归方法的使用。

- EOF -

推荐阅读  点击标题可跳转

1、递归如何转换为非递归？

2、简单又常见的算法题：汉诺塔

3、面试题：1 到 1000 之间有多少个 7？

觉得本文有帮助？请分享给更多人

关注「算法爱好者」加星标，修炼编程内功

点赞和在看就是最大的支持??