算法之汉诺塔

汉诺塔

这是个著名难题, 虽然说起来简单, 如果不用递归, 就很难解决。

题目介绍: 有三个塔, 每个都堆放 n 个盘子。开始时, 所有盘子均在塔A上,并且,盘从上到下, 按直径增大的次序放置。此难题的目的是设计一个盘子移动的序列。使得塔 A 上的所有盘子借助于塔 B 移动到塔 C 上。
有两个限制: 1. 一次只能搬动一个盘子。2. 任何时候不能把盘子放在比它小的盘子的上面。

对于缺乏递归思维能力的人来说, 这个问题会令人迷惑不解。另一方面, 递归方法却是那样简单, 简直象有魔力一样。

解题方法如下进行. 若你只有一个盘子, 则是直接从 A 移到 C。若你有一个以上的盘子(设为 n 个), 则考虑三个步骤。

第一步, 把 n-1 个盘子从塔 A 搬到塔 B。第一步不违反说明的第一条限制(一次只能搬动一个盘子); 所有 n-1 个盘子不能作为一个整体一起搬动, 而是符合要求地从一个塔移到另一个塔上。注意尽管最终目标是把盘子从 A 搬到 C, 但是你可以用相同的算法把盘子从一个塔移到另一个塔上, 只要把源塔和目塔的名字改变一下即可。

第二步: 将剩下的一只盘 (也就是最大的一只) 直接从 A 塔搬到那个仍然空着的塔 C 。

第三步: 用第一步所说的方法, 再次将 B 塔上的盘搬到 C 塔。和第一步一样. 这一步实际上是由一序列更小的一次仅搬一个盘的操作组成。这一步是没有问题的, 因为 C 塔上仅有的一只盘是最大的盘。

这个算法达到了预期的目标, 即在 C 塔上按正确的顺序堆放了所有的盘。

注意: 前面的讨论是按照递归算法的标准形式表达的。显而易见的情形 (一只盘的情况)能够直接了当地解决。而其它情况, 将用一个"变简单"的参数(即减少一只盘)去调用函数。最终, 将到达仅有一个盘的情形, 这时, 递归就终止了。

这个例子的 C 语言程序如下。
main()
{
    int disks;
    void towers(int,char,char,char);
    printf("Number of disks: ");
    scanf("%d",&disks);
    towers(disks,'A','B','C');
}

void move_disk(char src, char dst)
{
    printf("%c ====> %c",src,dst);
}

void towers(int n, char src, char mid, char dst)
{
    void move_disk(char,char);
    if (n==1)
    {
        move_disk(src,dst);
        return;
    }
    towers(n-1,src,dst,mid);
    move_disk(src,dst);
    towers(n-1,mid,src,dst);
}

说明:
函数 main() 读入要搬动的盘的个数, 然后开始第一次调用 tower 函数。
函数 towers() 完成递归算法。
函数 move_disk() 打印盘从一个塔到另一个塔的搬动情形。

让我们看一看, 当盘数是 3 时, towers() 的执行情况。