练习17，L题，汉诺塔问题

题目如下：

汉诺塔是一个源于印度古老传说的益智玩具。据说大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘，大梵天命令僧侣把圆盘移到另一根柱子上，并且规定：在小圆盘上不能放大圆盘，每次只能移动一个圆盘。当所有圆盘都移到另一根柱子上时，世界就会毁灭。

请编写程序，输入汉诺塔圆片的数量，输出移动汉诺塔的步骤。假定圆盘从小到大编号为1, 2, ...

输入描述:

输入为一个整数(小于20），后面跟三个单字符，用空格分隔。整数为盘子的数目，后三个字符表示三个柱子的编号。

输出描述:

移动汉诺塔的步骤：

每行显示一步操作，具体格式为：

圆盘号：起始柱 -> 目标柱子

其中圆盘号从 1 开始由小到大顺序编号。

解决该问题，我们只拿三个盘来举例，会更清晰，我们的目的是把最底层挪到目标柱上，在此之前，我们应该先是把最上面的盘挪到最右面，第二个盘是放在借力柱上，如下图：

拿n个盘来举例，那就是首先第n个盘放在最右面，然后n-1号盘是放在借力柱上，所以就有了递归关系，假设起始柱子是A，目标柱子是C，借力柱子是B，那应该就是定义一个函数进行递归，flag（int n,char a,char c,char b），如果n == 1直接输出，n如果不等于1，进行flag(n-1,a,b,c);然后再进行输出，再递归，flag（n-1,c,a,b），以此类推，代码如下：

#include <iostream>

using namespace std;
void flag(int n, char a, char b, char c)
{
    if (n == 1)
    {
        cout << "1: " << a << " -> " << c << endl;
        return;
    }
    flag(n - 1, a, c, b);
    cout << n << ": " << a << " -> " << c << endl;
    flag(n - 1, b, a, c);
}
int main()
{
    int n;
    char a, b, c;
    cin >> n >> a >> b >> c;
    flag(n, a, b, c);
    return 0;
}