题目 浅谈汉诺塔问题，以及对其递归的剖析

首先谈谈汉诺塔这个问题，这个问题是印度的一个古老的传说。开天辟地的神勃拉玛在一个庙里留下了三根金刚石的棒，第一根下面套着 64 个圆的金片，最大的一个在底下，其余一个比一个小，顺次叠下来，庙里的众僧不倦地把它们一个个地从这根棒搬到另一根棒上，规定可利用两头的一根棒作为帮忙，但每次只能搬一个，而且大的不能放在小的下面。面对宏大的数字 (挪动圆片的次数)18446744073709551615，看来，众僧们耗尽毕生精力也不可能实现金片的挪动。起初，这个传说就演变为汉诺塔游戏。

作为一个 green hand，拿到这题的时候我是有些茫然的，感觉无从下手，没有什么思路。而后我就顺手画了 3 个柱子，3 个盘子。没一会就胜利了，但这并没有真正的胜利，因为我的这次胜利是缓缓的尝试进去的。起初我就多画了几个盘子，缓缓尝试，总结其中的法则，通过一下午的摸索，也算有了一点肤浅的心得，上面我就来谈谈。

很显著，这个问题须要用到递归能力解决，而用到递归的问题，往往能够使其简单化，把一个简单的问题转化为一个个类似而简略的小问题。而这，也正是其中之一的难点，首先要想到怎么转化这个简单的问题。通过一系列的尝试后，我发现，要想解决这个问题，你总是要把最大的盘子上的小盘子想方法移到两头的柱子上，而后再将最大的那个移到最初的一根柱子上，至此，也就发现了其中的共性点。

上面给出图示，以便了解

**

这其中最重要的一步就是肯定要将最大的一个盘子移到 c 柱上，上面谈谈我对这一步重要性的了解。其实想到这时，我不禁想到了线性代数上行列式的计算，如果要计算一个 4 阶行列式，显然是很简单的，但咱们能够利用代数余子式将其转化为几个 3 阶行列式的和，这样就简便了运算。

这个问题中也是用到了同样的思维，当把最大的独自移到最初一个柱子上时，那样咱们就不须要思考那个盘子了，因为那个盘子是所有盘子中最大的，然它此时正在最上面，所以如图 5 个盘子的问题，当到图 2 那一步后，也就转化为 4 个盘子的问题.

此时也就成了这样

此时又能够转化一下思维，咱们无妨将 A,B,C 三个柱子换下程序，因为这样并不会影响后果。

此时 5 个盘子的问题就转化成 4 个盘子的问题了，以此办法类推，最初就能够解决汉诺塔的问题了。

以上是整个问题的算法，以及是如何想到的，接下来就是写程序了

`void move(char c1, char c2);
void hannuo(int n, char x, char y, char z)
{if (n == 1)move(x, z); // 递归截止条件
    else
    {hannuo(n - 1, x, z, y);// 将 n- 1 个盘子先放到 B 座位上
        move(x, z);// 将 A 座上地剩下的一个盘挪动到 C 盘上
        hannuo(n - 1, y, x, z);// 将 n - 1 个盘从 B 座挪动到 C 座上

    }
}
void move(char c1, char c2)
{printf("%c--->%cn", c1, c2);
}

int main()
{
    int n;
    printf("input your number");
    scanf("%d", &n);
    hannuo(n, 'a', 'b', 'c');
    return 0;
}` 

*   1
*   2
*   3
*   4
*   5
*   6
*   7
*   8
*   9
*   10
*   11
*   12
*   13
*   14
*   15
*   16
*   17
*   18
*   19
*   20
*   21
*   22
*   23
*   24
*   25

上面来剖析下这个代码外面的递归局部

而后我用代码运行了一下，验证了一下剖析，与剖析完全一致.