C++汉诺塔递归实现

程序背景：

汉诺塔（Tower of Hanoi）又称河内塔，问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

 1 #include<iostream>
 2 using namespace std;
 3 
 4 void hanoi(int n, char A, char B, char C,int &count)    //把n个圆盘从A借助B按原顺序移动到C上
 5 {
 6     if (n == 1) 
 7     {
 8         count++;
 9         cout << count << ":" << A << " " << B << endl;
10     }
11     else
12     {
13         hanoi(n - 1, A, C, B, count);        //把上边的n-1个圆盘借助C从A移动到B上
14         count++;
15         cout << count << ":" << A << " " << C << endl;    //将A上剩下的那个圆盘移到C上
16         hanoi(n - 1, B, A, C, count);    //再把B上的n-1个圆盘通过A移到C上
17     }
18 }
19 
20 int main()
21 {
22     int n, count = 0;
23     cout << "输入圆盘数:";
24     cin >> n;
25     cout << "结果为:" << endl;
26     hanoi(n, 'A', 'B', 'C', count);
27     cin.get();
28     cin.get();
29     return 0;
30 }

作者：耑新新，发布于博客园

转载请注明出处，欢迎邮件交流：zhuanxinxin@aliyun.com