曲径通幽论坛

标题: 汉诺塔问题 [打印本页]

作者: beyes 时间: 2009-9-12 03:09
标题: 汉诺塔问题
汉诺塔问题是递归中的经典问题，但以前却没仔细的去体会过这个问题。网上所找的一些资料，要么说得模糊，要么就认为太简单。这里，就这个问题，做一个仔细的总结以及推导过程。

下面是 3层和 4层汉诺塔的玩法示意图。

3 层玩法：

4 层玩法：

解决汉诺塔问题的手段是递归。递归方法的思想是追根溯源，通俗的讲就是顺藤摸瓜。

以 4 层(假设上图中红色盘为1号盘，黄色盘子是2号盘子，蓝色盘子是 3 号盘，橙色盘是 4 号盘；塔位从左到右分别称为为1，2，3))玩法来仔细分析并推导出汉诺塔的 C 语言的算法，为了直观起见，这里设汉诺塔函数为 hanoi(4, 1, 2, 3)，其中第 1 个参数 4 表示是 4 个盘子，1，2，3 分别代表塔位-1，塔位-2，塔位-3 ---- 整个函数的意思就是，塔位-1(第 2 个参数) 上有 4 个盘(第 1 个参数)，这 4 个盘要搬到塔位-3(第 4 个参数)上，此间需要的中间的辅助塔位为塔位-2(第 2 个参数)。下面是推导函数过程：

如果需要把 4 个盘子从塔位-1 移到塔位-3，需要塔位-2 作为辅助塔位，那么可以设想中间必经：
先让 1，2，3号盘依次叠在 2 号塔位上，则 4 号盘子就可搬移到 3 号塔位上，其中塔位 3 为辅助塔位； ---- 这一步对应的函数为 hanoi (3, 1, 3, 2)

当上面的第 1 步实现后，那么只需要将塔位-2 上的 3 个盘子都移动塔位-3 上即可完成任务，此间塔位-2 为辅助塔位； --- 这一步对应的函数为 hanoi(3, 2, 1, 3)

... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..

那么 hanoi (3, 1, 3, 2) 这一步是怎样实现的呢？到此，我们完全可以忽略 4 号盘的存在，因为已经对它移动完成，也就是说我们不会再去动它，所以现在需要分析的仅是如何实现从塔位-1 上把 1，2，3 号盘子搬到塔位-2 上。同样的分析方法，像上面一样需要经过 2 步组成：

先让 1，2 号两个盘从塔位-1 搬到塔位-3 上，中间的辅助塔位是塔位-2 ---- 这一步对应的函数是 hanoi (2, 1, 2, 3)
在上面的一步后，再把 3 号盘搬到塔位-2 上，最后再把塔位-3 上的1，2号两个盘再挪到塔位-2 上即可实现 --- 这一步对应的函数是 hanoi (2, 3, 1, 2)

... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..

同理可分析如何实现 hanoi (2, 1, 2, 3) 这个函数。实现这个函数仍然需要两个步骤，也就是需要两个函数来组成，他们分别是：
hanoi (1, 1, 3, 2) 和 hanoi (1, 2, 1, 3)

此时，当第一个参数为 1 的时候，也就是说我们只需要移动 1 个盘，这种情况自然是最简单的。所以，递归到此就结束了。

现在列出各个函数的分解过程，并从这个过程中得出 hanoi() 这个函数的实现规律：
hanoi (4, 1, 2, 3) 分解为 hanoi(3, 1, 3, 2) 和 hanoi(3, 2, 1, 3) 这两个函数实现；
hanoi (3, 1, 3, 2) 分解为 hanoi(2, 1, 2, 3) 和 hanoi(2, 3, 1, 2) 这两个函数实现；
hanoi (2, 1, 2 ,3) 分解为 hanoi(1, 1, 3, 2) 和 hanoi (1, 2, 1, 3) 这两个函数实现。

从上面函数中的蓝色数字中看到，规律为每隔一个分解函数后重复，而第一个参数递归一层就递减 1！同样可以证明每一次分解中的第 2 个函数的后 3 个参数的交替规律。为了明了期间，将 hanoi() 后面 3 个参数分别用 x, y , z 来代替，那么就有：

int hanoi(int dishs, int x, int y, int z)
{
        if (dishs == 1)
                printf ("盘子从 %d 移到 %d\n", x, z);
        else {
                hanoi (dishs - 1, x, z, y); /*第一步骤*/
                printf ("盘子从 %d 移到 %d\n", x, z);
                hanoi (dishs - 1, y, x, z); /*第三步骤*/
        }
}

欢迎光临曲径通幽论坛 (http://www.groad.net/bbs/)