原题：http://bailian.openjudge.cn/practice/4147/

描述

一、汉诺塔问题

  有三根杆子A，B，C。A杆上有N个(N>1)穿孔圆盘，盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至C杆： 每次只能移动一个圆盘； 大盘不能叠在小盘上面。 提示：可将圆盘临时置于B杆，也可将从A杆移出的圆盘重新移回A杆，但都必须遵循上述两条规则。

  问：如何移？最少要移动多少次？

输入

输入为一个整数后面跟三个单字符字符串。
整数为盘子的数目，后三个字符表示三个杆子的编号。

输出

输出每一步移动盘子的记录。一次移动一行。
每次移动的记录为例如3:a->b 的形式，即把编号为3的盘子从a杆移至b杆。
我们约定圆盘从小到大编号为1, 2, ...n。即最上面那个最小的圆盘编号为1，最下面最大的圆盘编号为n。

样例输入

3 a b c

样例输出

1:a->c
2:a->b
1:c->b
3:a->c
1:b->a
2:b->c
1:a->c

解法

思路一：直接递归，这是递归入门经典题了

 1 #include <iostream>
 2 using namespace std;
 3 void move(int n, char nows, char uses, char targets,int pan) {
 4     if (n == 1) {
 5         cout << pan << ":" << nows << "->" << targets << endl;
 6         return;
 7     }
 8     move(n - 1, nows, targets, uses, pan - 1);
 9     move(1, nows, uses, targets, pan);
10     move(n - 1, uses, nows, targets, pan - 1);
11     return;
12 }
13 int main()
14 {
15     int n;
16     char a, b, c;
17     cin >> n >> a >> b >> c;
18     move(n, a, b, c, n);
19     return 0;
20 }
21 */

思路二：用栈实现递归，注意入栈的顺序

 1 #include <iostream>
 2 #include <stack>
 3 using namespace std;
 4 class Move {
 5 public:
 6     int n;
 7     char nows, uses, targets;
 8     int pan;//目前最大的盘子编号
 9     Move(int inn,char innows,char inuses,char intargets,int inpan):n(inn),nows(innows),uses(inuses),targets(intargets),pan(inpan){}
10 };
11 stack<Move>mystack;
12 int main()
13 {
14     int n;
15     char a, b, c;
16     cin >> n >> a >> b >> c;
17     mystack.push(Move(n, a, b, c, n));
18     while (!mystack.empty()) {
19         Move topn = mystack.top();
20         mystack.pop();
21         if (topn.n == 1) {
22             cout << topn.pan << ":" << topn.nows << "->" << topn.targets << endl;
23             continue;
24         }
25         //注意放入栈的顺序和上面的递归是倒过来的
26         mystack.push(Move(topn.n - 1, topn.uses, topn.nows, topn.targets, topn.pan - 1));
27         mystack.push(Move(1, topn.nows, topn.uses, topn.targets, topn.pan));
28         mystack.push(Move(topn.n - 1, topn.nows, topn.targets, topn.uses, topn.pan - 1));
29     }
30     return 0;
31 }