|
发表于 2009-11-3 02:32:41
|
显示全部楼层
IP:江苏扬州
wfpb,
汉诺塔的算法其实是很简单的.
首先你必须清楚什么是汉诺塔问题.
汉诺塔的问题是这样的.
在一块板上竖立着三根柱子, 给这三根柱子做个标记,分别为 A, B, C.
最初, 所有的盘都位于A, 并且是按大小排好序的, 确切讲, 小的盘位于大的盘上面. 现在你的任务是将所有位于A 的盘 移动到 目的柱子上, 假定C为我们的目的柱子. 并且无论如何, 大盘位于小盘上都是不允许的.
那么解法是什么呢? 我不马上告诉你, 我想告诉你的是如何去寻找解法, 知道解决问题的途径比知道解法更为重要, 因为你看到了思维的过程, 而不仅仅是一个结果. 好, 那么如何去发现解法呢? 有一个很重要的方法, 那就是假设法, 然后你要实现自圆其说. 如果你的假设法能够成功, 那么我们可以说,我们找到了一个解法, 至于这个解法是不是唯一的解法,是另外一个话题.
那么关于这个问题, 什么是我们的假设呢? 其实很简单. 我们假设, 已经找到了某个解法, 到目前为止,这个所谓的假设是虚的, 也就是说, 我们并不知道这个解法, 但是没有关系. 我们清楚一个非常重要的一点, 这一点也是游戏规则所决定的, 即大盘不允许放在小盘的上面. 那么好, 如果我们要将所有的盘从A移到C, 必须将那个最大的盘从A移到C, 然后才能将其余的盘放到那个最大的盘上面. 那么这意味着什么? 这意味着, 那个最大的盘的上面的所有盘必须先移到B上面, 这样才能使得那个最大的盘有可能被移到C. 由于我们有了一个假设, 就是我们有能力将所有的盘从A移到C, 那么我们当然有能力将所有除去那个最大盘的盘移到B上面来. 好了, 也就是说, 我们进一步假设, 我们实现了, 将所有最大盘上面的所有盘先移到了B, 然后将那个位于A 最下面的那个最大的盘移到了C, 接着就是实现,将B 上面的所有盘移到C上面了。 这个问题和原问题其实是一回事, 只不过起始柱子现在为B,盘的数目也少掉一个了。那么方法和前面的是一样的。这样一直推理下去, 就逐步变成将5个盘移到目标柱子, 那么你就要先移掉最上面的4个盘,然后将最下面的盘移到目标柱子,然后问题就变成那4个盘移到目标柱子。要移4个盘,当然必须先移掉上面的3个盘,一直这样进行下去,你看一下你是否能够实现移3个盘啊。要移3个盘, 你必须看一下,你能不能移两个盘啊?问题越来越清楚了,我们的假设得到了自圆其说。也就是说,我们可以这样假设的。那么我们就找到了问题的解法了。这就是逆推理的过程。我们设法从目的地回到起点,如果我们能够从目的地回到起点,那么我们当然能够从起点走到目的地啊。
希望上面的解释够清楚了。 |
|