汉诺塔问题

汉诺塔

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

分析

当刚开始接触这个问题的时候，一时间不知道该如何下手，如果只是一步一步尝试，随便移，刚开始几步还好说，但要到了后面，要移的越来越多，若果还是毫无规律的移，最终只会离答案越来越远。上面的问题有64片，最终要移18,446,744,073,709,551,615步，一个人耗尽一生也不可能完成。

这时候我们就可以换一种思路，假如先把63片全部移到B上，这时候只需将A上剩的一片移到C上；然后就只需移动B上的63片了，我们再将B上的62片移到A上，最后将B上的一片移到C上…….以此类推

这就存在着某种规律：

1.将A上的63片移到B上，此时B作为辅助，A上的最后一片移到C上
2.将B上的62片移到A上，此时A作为辅助，B上的最后一片移到C上
3.将A上的61片移到B上，此时B作为辅助，A上的最后一片移到C上
…….
实际上这个问题就转化为了递归

表达式：

H(1) = 1;
H(n) = 2 * H(n-1)+1      n>1
一般式：
H(n) = 2^n - 1 (n>0)

程序实现：

    #include <stdio.h>
    int i = 0; //记录移动的次数

    int move(char a, char b)
    {
        printf("%c ---> %c\n", a, b);
        return i++;
    }

    void Hanoi(int n, char a, char b, char c)
    {
        if (1 == n)
        {
            move(a, c); // 如果只有一个，只需将a移到c上
        }
        else
        {
            Hanoi(n - 1, a, c, b); //将a柱子上的n-1个盘子移到b上
            move(a, c); // 将a仅剩的一个移到c上 
            Hanoi(n - 1, b, a, c); // 将b上暂时放的n-1个盘子移到c上
        }
    }

    int main()
    {
        int n = 0; 
        scanf("%d", &n);
        char a = 'a';
        char b = 'b';
        char c = 'c';
        Hanoi(n, a, b, c);
        printf("%d\n", i);
        return 0;
    }