算法 - 递归实现汉诺塔（The Tower of Hanoi）

目录

引言：

分析：

分析两片汉诺塔的迁移过程：

 分析三片汉诺塔的迁移过程：

代码实现：

递归出口：

递归过程： 

完整程序代码：

运行结果：

参考资料：​​​​​

---

 

引言：

今天接触到了一个非常有意思的游戏，名字叫做汉诺塔（Tower of Hanoi），小时候没有玩过这个益智游戏，所以今天利用代码把这个益智游戏实现一下。在写汉诺塔的代码之前，我们先对汉诺塔的游戏规则、玩法、以及游戏过程进行了解：

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

分析：

分析两片汉诺塔的迁移过程：

假设我们现在在A支柱有两个片子，分别为蓝色方框和红色反框，这是他们的初始状态：

​​​​​​​ 

我们现在要将红色和蓝色方框按照原先的“大的在下面，小的在上面”的规则从A支柱迁移至C支柱，显然，我们要将蓝色方框先迁移至B支柱，然后将红色方框迁移至C支柱，然后再将蓝色方框从B支柱迁移至C支柱，这样就完成了迁移。

假设我们每次迁移的是支柱最上方的方框，迁移的顺序可以表示为：

A -> B

A -> C

B -> C

至此，两片的汉诺塔已经迁移完成。

 分析三片汉诺塔的迁移过程：

假设我们现在要迁移3片的汉诺塔，分别为红色方框、蓝色方框、黄色方框，这是他们的初始状态：

按照上面每次迁移支柱最上面方框的规则，顺序可以表示为：

A -> C

A -> B

C -> B

A -> C

B -> A

B -> C

A -> C 

至此，三片汉诺塔已经迁移完成。

那么接下来我们应该思考，从两片汉诺塔到三片汉诺塔我们能得出什么规律呢？ 

我们发现，从三片汉诺塔的迁移过程来看，首先我们需要的就是将除了底部以上的方框先迁移到B支柱，将底部最大的方框释放并迁移至C方框，然后再将上面的两个方框依次放到最大方框的上面。也就是说，无论多少片的汉诺塔，我们都能把大的问题转化为小的问题。

例如，我现在要迁移四片的汉诺塔，首先我要考虑的就是如何将底部方框以上的三片进行正确的迁移且将底部方框迁移至目标支柱；

那么我在迁移三片汉诺塔的时候，要考虑的是不是将底部方框以上的两片进行正确的迁移且将底部方框迁移至目标支柱；

同样，我在迁移两片汉诺塔的时候，当然就是将上面的一片先迁移到目标支柱以外的B支柱，然后再将底部方框迁移至目标支柱，再继续将B支柱的方框迁移至C支柱从而完成整个迁移的过程。

我们可以用树状图来模拟这个将四片汉诺塔这个大问题逐步分解成三片、两片汉诺塔这种小问题的过程：

注：这里合并过程中的2，3，4 分别代表的是每一步对应的底部方框。 

代码实现：

经过上面对汉诺塔迁移过程的分析，大体的思路我们已经清楚，现在我们以递归方式实现汉诺塔的代码：

首先我们来设计递归函数，汉诺塔问题中涉及到的无外乎就是：汉诺塔上面的片子和三个支柱（分别为A、B、C），所以我们以这两个东西作为函数的形参：

void Hanoi(int n, char A , char B , char C);

递归出口：

既然要递归，我们首先应该考虑的就是递归出口，也就是当汉诺塔待迁移支柱上面的片数为1的时候，我们直接将这一片从待迁移支柱迁移至目标支柱，用代码来表示也就是：

if(n == 1){
        printf("%c -> %c\n",A,C);
    }

递归过程： 

我们假设现在有一个n片的汉诺塔待迁移，根据上面分析的分解和合并的过程，我们首先要做的就是将除了底层方框以外上面的所有方框迁移至B支柱，也就是将n - 1个方框绕过C支柱迁移至B支柱，用代码来表示就是：

Hanoi(n - 1,'A','C','B');

当我们将n - 1个方框成功迁移至B支柱的时候，下面我们应该考虑的就是将编号为n的底层方框迁移至目标支柱(C支柱)，也就是 A -> C，用代码来表示就是：

printf("%c -> %c\n",'A','C');

接下来我们应该考虑的就是将B支柱上的方框依次迁移至C支柱，也就是将n - 1片绕过A支柱迁移至C支柱，用代码来表示就是：

Hanoi(n - 1,'B','A','C');

至此，n个方框的汉诺塔已经迁移完成。

完整程序代码：

#include
void Hanoi(int n,char A,char B,char C)
{
    if(n == 1){
        printf("%c -> %c\n",A,C);
    }
    else{
        Hanoi(n - 1 , A,C,B);
        printf("%c -> %c\n",A,C);
        Hanoi(n - 1,B,A,C);
    }
}
int main()
{
    int n = 0;
    printf("Please enter the number of slice :");
    scanf("%d",&n);
    Hanoi(n,'A','B','C');
    return 0;
}

运行结果：

例如我在这里输入汉诺塔的方框数为3：

运行结果的迁移过程和我们上方分析的三片汉诺塔的迁移过程完全一致，结果正确。 

参考资料：​​​​​​​​​​​​

百度百科 - 汉诺塔​​​​​​​