用C语言解答汉诺塔问题

汉诺塔相信很多人小时候都玩过这样的游戏，这是源于印度的古老传说，大家可千万不要小看这个游戏，里面体现了古人的大智慧，在这里我们能学到最直观的演示方法，本篇主要是针对汉诺塔的问题进行分析和代码展示。

一、前言

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

二、解题思路

思路很简单：有三根相邻的柱子，从左到右分别为：托盘A、托盘B、托盘C；

托盘A按照“从下到上、从大到小”叠放着3个不同大小的盘子；

第一步：将盘子1从托盘A移动至托盘C

第二步：将盘子2从托盘A移动至托盘B

第三步：将盘子1从托盘C移动至托盘B

第四步：将盘子3从托盘A移动至托盘C

第五步：将盘子1从托盘B移动至托盘A

第六步：将盘子2从托盘B移动至托盘C

第七步：将盘子1从托盘A移动至托盘C

动图演示

是不是很简单？

我们从上面移动的过程中，可以看到，托盘B始终作为一个过渡的存在，并且可以把它想象成中转柱；

那么我们就可以这样理解：

托盘A：起始柱A；

托盘B：中转柱B；

托盘C：目标柱C

三、代码实现

分析：那么我们怎么用代码来实现呢？

这是一个非常经典的递归问题。

假设有n个盘子，需要把这些盘子从第一根起始柱A移动到第三根目标柱C中。

（1）首先需要把n-1个盘子移动到第二根中转柱B上；

（2）再把最后一个也就是最大的那一个盘子移动到第三根目标柱C上；

（3）最后再把剩下的n-1个盘子移动到第三根目标柱C上。

我们定义f(n)是需要移动的次数； 

f(1)=1，f(2)=3，f(3)=7

…

f(n)=2f(n−1)+1 

代码如下：

#include <stdio.h>

void move(int n, char pos1, char pos3)
{
    //打印移动的过程
    // 1代表上面最小的盘子
    // 2代表中间位置的盘子
    // 3代表下面最大的盘子
    printf("盘子%d: 从 %c柱 移动到 %c柱\n", n, pos1, pos3);

}

void Hanoi(int n, char pos1, char pos2, char pos3)
{
    //如果是1个盘子，直接从起始柱A移动到目标柱C
    if (n == 1) 
    {
        move(n, pos1, pos3);
    }
    else
    {
        //如果盘子大于1个，需要把n-1个盘子，从起始柱pos1，通过目标柱pos3，移动到中转柱pos2
        Hanoi(n-1, pos1, pos3, pos2); 

        //此时pos1上的n-1个盘子全部移动pos2上去了，那么可以直接把pos1上剩下的1个盘子，直接移动到pos3上
        move(n, pos1, pos3);

        //把pos2剩下的n-1个盘子，通过中转位置pos1，移动到目标位置pos3
        Hanoi(n-1, pos2, pos1, pos3);
    }
}

int main()
{
    //盘子个数
    int n = 3;

    //起始柱A
    char pos1 = 'A';

    //中转柱B
    char pos2 = 'B';

    //目标柱C
    char pos3 = 'C';

    printf("移动%d个盘子的步骤如下↓\n", n);

    //汉诺塔函数
    Hanoi(n, pos1, pos2, pos3);

    return 0;
}

如果我们编译并运行上述程序，那么它应该产生以下结果：

移动3个盘子的步骤如下↓
盘子1: 从 A柱 移动到 C柱
盘子2: 从 A柱 移动到 B柱
盘子1: 从 C柱 移动到 B柱
盘子3: 从 A柱 移动到 C柱
盘子1: 从 B柱 移动到 A柱
盘子2: 从 B柱 移动到 C柱
盘子1: 从 A柱 移动到 C柱