首页 > 代码库 > 汉诺塔问题的递归实现
汉诺塔问题的递归实现
汉诺塔问题的递归实现
汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。
1.汉诺塔（基本）
汉诺塔问题是典型的分治算法问题，首先我们来讨论最基本的汉诺塔问题。假设有n个圆盘，三根柱子，a，b，c，需要把n个盘子（从上往下从小到大摞着）从a柱移动到c柱，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。
解决办法;
采用分治法，分而治之，把大问题化解成小问题。故可以把n个盘子看成n-1个盘子，和第n个盘子，首先我们需要把n-1个盘子移动到b柱子上，然后把第n个盘子移动到c柱子上，最后把n-1个盘子用同样方法移动到c柱子上，这样就用最少的移动次数完成了任务。
代码
该程序显示全部步骤的移动方法。
1 #include <iostream> 2 using namespace std; 3 4 void move(int n, char a, char b){ 5 cout<<n<<" from "<<a<<"->"<<b<<endl; 6 } 7 8 void hanoi(int n, char a, char b, char c){//把n个盘子从a柱子移动到c柱子 9 if(n > 0) {10 hanoi(n - 1, a, c, b);// 将a上的n-1个盘子移到b，c做辅助11 move(n, a, c); // 把n从a移动到c12 hanoi(n - 1, b, a, c); // 把b上n-1个盘子移到c，a做辅助13 }14 }15 16 int main()17 {18 int n;19 while(cin>>n){20 char a=‘a‘,b=‘b‘,c=‘c‘;21 hanoi(n,a,b,c); //把n个盘子从a柱子移动到c柱子 b做辅助22 }23 return 0;24 }
计算移动次数：
如果要计算一共移动了多少次，找出规律即可。
假设移动n个盘子需要移动f(n)次，所以把n-1个盘子移动到b柱子上，需要移动f(n-1)次，然后把第n个盘子移动到c柱子上，需要移动1次，最后把n-1个盘子移动到c柱子上，需要移动f(n-1)次，综上所述，一共移动了
f(n) = 2 f(n-1) + 1
而：
f(1) = 1;
f(2) = 2*1+ 1;
f(3) = 2(2*1+ 1)+ 1;
.......
f(n) = 2^n -1
代码就不写了
2.汉诺塔（必须通过中间的柱子）
假设有n个圆盘，三根柱子，a，b，c，需要把n个盘子（上从下往上按照大小顺序摞着）从a柱移动到c柱，不允许直接从最左(右)边移到最右(左)边(每次移动一定是移到中间杆或从中间移出)，也不允许大盘放到下盘的上面。
参考acm题目： http://acm.hdu.edu.cn/showproblem.php?pid=2064
这道题和之前不同，约束了必须通过中间的柱子才可以，这也难不倒我们，我们只需要在递归的时候改变一下策略就可以完成任务。
解决方法：
第1步:初始状态:
第2步:把上面的n-1个盘移到第3号杆上:
第3步:把第n个盘从1移到2:
第4步:把前n-1个从3移到1，给第n个盘让路:
第5步:把第n个盘从2移到3:
第6步:把前n-1个从移到3，完成移动。
代码：
1 #include <iostream> 2 using namespace std; 3 4 void move(int n, char a, char b) 5 { 6 cout<<n<<" from "<<a<<"->"<<b<<endl; 7 } 8 9 void hanoi(int n, char a, char b, char c) //把n个盘子从a柱子移动到c柱子10 {11 if(n > 0)12 {13 hanoi(n - 1, a, b, c);//a到c14 move(n, a, b);15 hanoi(n - 1, c, b, a);//c到a16 move(n,b,c);17 hanoi(n - 1, a, b, c);//a到c18 }19 }20 21 int main()22 {23 int n;24 while(cin>>n)25 {26 char a=‘a‘,b=‘b‘,c=‘c‘;27 hanoi(n,a,b,c);28 }29 return 0;30 }
我们设f(n)为把n个盘从1移到3所需要的步数，当然也等于从3移到1的步数。
由上面的图我们可以看到,要想把第n个盘从1移到3，需要3个步骤 :
1.) 把前n-1个从1移动3 .
2.) 第n个盘要从1->2->3经历2步.
3.) 而前n-1个盘需要先 3->1 ( 这是为了给 第n个盘让路 ), 最后再 1->3。
∴f(n) = 3 × f(n-1) + 2;
f(1) = 2;
这样我们就得到了这一题的递推公式, 当然我们可以做进一步的优化 , 优化方法如下: f(n) = 3 × f(n-1) + 2 f(1) = 2 =>
f(n) + 1 = 3 × [f(n-1) + 1]
f(1) + 1 = 2 + 1 = 3
=>
f(n) + 1 = 3n =>
f(n) = 3n- 1
3汉诺塔（必须通过中间的柱子，允许最大的放在最上面）
假设有n个圆盘，三根柱子，a，b，c，需要把n个盘子（上从下往上按照大小顺序摞着）从a柱移动到c柱，不允许直接从最左(右)边移到最右(左)边(每次移动一定是移到中间杆或从中间移出)，也不允许大盘放到小盘的上面。如果我们允许最大的盘子放到最上面会怎么样呢？（只允许最大的放在最上面）当然最后需要的结果是盘子从小到大排在最右边。
参考acm题目：http://acm.hdu.edu.cn/showproblem.php?pid=2077
这道题和之前不同，约束了必须通过中间的柱子才可以，也放宽了对最大盘子的限制，所以肯定比第二种汉诺塔移动次数少，我们也是只需要在递归的时候改变一下策略就可以完成任务。
解决方法：
依然采用分治法，分而治之，把大问题化解成小问题。最开始在a柱子上有n个盘子，我们可以把n个盘子看成n-2个盘子，和第n-1，以及第n个盘子。首先我们需要把n-2个盘子移动到c柱子上（利用第二种类型的算法），然后把第n-1和n个盘子依次移动到b柱子上，再把n-2个盘子移动到a柱子上，再把第n和第n-1个盘子移动到柱子c上，这样就用最少的移动次数完成了任务。
#include <iostream>using namespace std;void move(int n, char a, char b){ cout<<n<<" from "<<a<<"->"<<b<<endl;}void hanoi(int n, char a, char b, char c){ if(n > 0) { hanoi(n - 1, a, b, c); move(n, a, b); hanoi(n - 1, c, b, a); move(n, b, c); hanoi(n - 1, a, b, c); }}void Hanoi_(int n, char a, char b, char c){ if(n > 0) { hanoi(n - 2, a, b, c); if(n > 1) move(n - 1, a, b); move(n, a, b); hanoi(n - 2, c, b, a); move(n, b, c); if(n > 1) move(n - 1, b, c); hanoi(n - 2, a, b, c); }}int main(){ int n; while(cin>>n) { char a=‘a‘,b=‘b‘,c=‘c‘; Hanoi_(n,a,b,c); } return 0;}
计算移动次数：
如果要计算一共移动了多少次，找出规律即可。
假设移动n个盘子需要移动F(n)次，用第二种算法把n-2个盘子移动到c柱子上（利用第二种类型的算法），需要f(n-2)次，然后把第n-1和n个盘子依次移动到b柱子上，需要2次，再把n-2个盘子移动到c柱子上，再把第n和第n-1个盘子移动到柱子c上，需要2次，综上所述，一共移动了
F(n) = 3 f(n-2) + 4
而：f(n-2) = 3^(n-2)-1,故F(n)=3^(n-1)+1
4.汉诺塔（加一根柱子）
假设有n个圆盘，三根柱子，a，b，c，需要把n个盘子（上从下往上按照大小顺序摞着）从a柱移动到c柱，再找来了一根一模一样的柱子d，通过这个柱子来更快的把所有的盘子移到第三个柱子上。
参考acm题目：http://acm.hdu.edu.cn/showproblem.php?pid=1207
这道题和之前都有很大的不同，加了一根柱子，意味着有的时候可用3根柱子，有的时候可用4根柱子，当把j个小盘子移动到d盘上时，有四根柱子可用，而当把n-j个盘子从a移动到c时，仅有三根柱子可用。这里我们就要找到j的值，使所有移动的次数和最小。
解决方法：
依然采用分治法。首先把j个盘子移动到d柱子上（通过四个柱子可用的算法），需要B[j]次移动，然后把n-j个盘子移动到c柱子上（通过三个柱子可用的算法），需要A[n-j]次移动，，然后把d中的j个盘子移动到c柱子上，需要B[j]次移动。我们可以用j的大小循环，找到移动次数最小的j。
首先我们先计算移动的次数：
核心公式为：flag=2*B[j]+A[i-j]; //j个盘子移动到第四个柱子，然后把剩下的i-j个在第四个不能用的情况下移到第三个
计算次数的c++实现：
#include <iostream>using namespace std;int main(){ int n; double a[65],b[65]; //数组a代表没加第四个柱子的结果，数组b代表加了第四个柱子的结果 a[1]=1; for(int i=2;i<=64;i++) a[i]=2*a[i-1]+1; b[1]=1; b[2]=3; for(int i=3;i<=64;i++){ double min=a[i],flag; for(int j=1;j<i;j++){ flag=2*b[j]+a[i-j]; //j个移动到第四个柱子，然后把剩下的i-j个在第四个不能用的情况下移到第三个柱子上 if(min>flag) min=flag; } b[i]=min; } while(cin>>n){ if(n>64||n<1){ cout<<"ERROR!"<<endl; continue; } cout<<b[n]<<endl; } return 0;}
此时利用上面的算法，我们就可以模拟出移动的步骤了，
模拟移动步骤的C++实现：
#include <iostream>using namespace std;void move(int n, char a, char b){ cout<<a<<"->"<<b<<endl;} void hanoi_basic_3(int n, char a, char b, char c){//把n个盘子从a柱子移动到b柱子 if(n > 0) { hanoi_basic_3(n - 1, a, c, b);// 把n-1个盘子移动到b柱子上 move(n, a, b); // 把a移动到b hanoi_basic_3(n - 1, c, b, a); // 把第n个盘子移动到b柱子上 }}void hanoi(int n, char a, char c, char b, char d, int C[]){ int j=C[n]; //j个盘子使用四个柱子的移动方式 if(n > 0) { hanoi(j, a, d, b, c, C);// 把j个盘子移动到d柱子上 hanoi_basic_3(n - j, a, c, b);// 把n-j个盘子移动到c柱子上（使用三个柱子的移动方式） hanoi(j, d, c, a, b, C); // 把j个盘子移动到c柱子上 }}int main(){ int n,flag_j; double A[65]; //未加第四个柱子时候的移动次数情况 A[1]=1; for(int i=2;i<65;i++) A[i]=2*A[i-1]+1; double B[65],flag,min; int C[65]; //把前 c[j]个元素用四个柱子的方法，后i-j 个元素用三个柱子的方法 C[1]=0; C[2]=0; for(int i=3;i<=64;i++){ min=A[i]; //数组A代表没加第四个柱子的结果次数，数组b代表加了第四个柱子的结果次数 B[1]=1; B[2]=3; flag_j=0; for(int j=1;j<i;j++){ flag=2*B[j]+A[i-j]; //j个移动到第四个柱子，然后把剩下的i-j个在第四个不能用的情况下移到第三个 if(min>flag) { min=flag; flag_j=j; } B[i]=min; C[i]=flag_j; } } while(cin>>n){ char a=‘a‘,b=‘b‘,c=‘c‘,d=‘d‘; hanoi(n,a,c,b,d,C); //把n个盘子从a柱子移动到c柱子 } return 0;}
汉诺塔问题的递归实现