【汉诺塔问题】汉诺塔问题系列

汉诺塔游戏：

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

分析：

最基本的情况，即n为1，需要1步即可。

假设F(n-1)是把n-1个盘子集体挪动的最小步数，我们要证明F(n)是把n个盘子集体挪动的最小步数。

1）在把n个盘子从A移动到C的过程中，必然存在一步，是把最大的盘子从A拿出来。要想把最大的盘子从A移动到别的某个柱子上（B或C），就必须保证剩下的n-1个盘子不能碍事，得好好堆在剩下那个柱子（C或B）上。要保证n-1个盘子都在剩下那个柱子上，至少得付出F(n-1)次移动。

2）在把n个盘子从A移动到C的过程中，必然存在一步，是最大的盘子被放到了C上，而且此后再也没动过。在这步实行之前，最大的盘子要么在A要么在B上，而相应地别的n-1个盘子要么在B要么在A上。在这步实施之后，我们只要花至少F(n-1)的步数把n-1个盘子从要么B要么A挪动到C上就行了。这些步数必然和1）中的步数不重叠，因为这时候最大盘子在C上，而1）中最大盘子在A上。

3）最大的盘子至少被挪动了一次。而且这一次肯定没被算在1）或2）的“至少F(n-1)步”中，因为后者只挪动较小的那n-1个盘子。

把1），2），3）加起来，就是至少F(n-1) + F(n-1) + 1步。不能再少了。

步骤为：肯定是把A上面n-1个盘子移动到柱子B上，然后把A剩下的那最大块放在C上，最后再把B上的所有盘子移动到C上。

（作者：Tim Shen
链接：https://www.zhihu.com/question/24385418/answer/107761723
来源：知乎）

Solution 1 递归版

#include <iostream>
#include <stack>
#include <string>

using namespace std;

int cnt;

void Move(int num, string from, string to) {
    cnt++;
    cout << "第 " << cnt << " 次移动 Move " << num << " from " + from + " to " + to << endl;
}
void hanoi(int num, string left, string mid, string right) {
    if (num == 1) {
        Move(num, left, right);
    } else {
        hanoi(num - 1, left, right, mid);
        Move(num, left, right);
        hanoi(num - 1, mid, left, right);
    }
}

int main()
{
    int n;
    cin >> n;
    hanoi(n, "left ", "mid  ", "right");
    system("pause");
    return 0;
}

Solution 1 迭代版

现在我们更改游戏规则，限制不能从最左侧移动到最右侧或者从最右侧移动到最左侧，必须经过中间的柱子。

分析：

Solution 2 递归版

#include <iostream>
#include <stack>
#include <string>

using namespace std;

int cnt;

void Move(int num, string from, string to) {
    cnt++;
    cout << "第 " << cnt << " 次移动 Move " << num << " from " + from + " to " + to << endl;
}

void hanoi(int num, string left, string mid, string right) {
    if (num == 1) {
        if (left == mid || right == mid) {
            Move(num, left, right);
            return;
        } else {
            Move(num, left, mid);
            Move(num, mid, left);
            return;
        }
    }
    hanoi(num - 1, left, mid, right);
    Move(num, left, mid); 
    hanoi(num - 1, right, mid, left);
    Move(num, mid, right);
    hanoi(num - 1, left, mid, right);
}

int main()
{
    int n;
    cin >> n;
    hanoi(n, "left ", "mid  ", "right");
    system("pause");
    return 0;
}

Solution 2 迭代版（栈）