Basic Pascal Tutorial/Chapter 4/Programming Assignment/zh CN

│ български (bg) │ English (en) │ français (fr) │ 日本語 (ja) │ 中文（中国大陆） (zh_CN) │

4G - 编程作业4: 汉诺塔 (原作者: Tao Yue, 状态: 未更改)

汉诺塔 是经典的递归应用，它也是计算机科学入门课程。在这个问题中，你有三根杆子，三个不同大小的圆盘，举例来说，四层楼高的塔看起来像：

   |       |       |
   |       |       |
   *       |       |
  ***      |       |
 *****     |       |
*******    |       |

方便起见，我们将三根杆分别称为杆一，杆二和杆三。现在的问题在于，怎么将一座（任意高的）塔从杆一转移到杆三。在整个过程中，大的圆盘不能放在小的圆盘上面，而且每次只能移动一个位于塔顶的圆盘。

The pegs are designated 1, 2, and 3 from left to right. The challenge is to move a tower (any height) from peg 1 to peg 3. In the process, no large disc may be placed on top of a smaller disc, and only one disc (the topmost disc on a peg) may be moved at any one time.

一共只有一两个圆盘时，这个问题很简单。对于只有一个圆盘的情况，你只需将它直接从杆一转移到杆三。对于有两个圆盘的情况，只需把杆一的两个圆盘依次移到杆二和杆三，再将位于杆二的圆盘移到杆三即可。

The problem seems trivial, and it is for one or two discs. For one disc, you simply move it from peg 1 to peg 3. For two discs, move the topmost disc from peg 1 to peg 2, then 1 to 3, and finally move the smaller disc from 2 to 3.

当圆盘的数目增加到三或以上时，这个问题就会变得比较复杂了。对于三个圆盘的情况，首先要把杆一顶的圆盘移到杆三，接着一到二，然后三到二。此时你已经将一座双层塔移到杆二了。现在把最大的圆盘由杆一移到杆三，再模仿之前的步骤将位于杆二的塔移到杆三即可。

The problem gets harder for three or more discs. For three discs, you'd move 1 to 3, then 1 to 2, then 3 to 2. This effectively creates a two-story tower on peg 2. Then move the largest disc: 1 to 3. Now move the two-story tower on top of the large disc: 2 to 1, 2 to 3, 1 to 3.

随着盘数增加，问题会越来越复杂。现在，你的使命是用递归的过程来解决有任意层数的汉诺塔问题。首先要从用户哪里获取塔的初始高度，然后输出具体的、精确到每一步的移动步骤。举例来说，如果用户让你解决一个3层的汉诺塔，他/她应该要收到如下的结果（'x to y'表示把杆x顶端的圆盘移到杆y顶端）：

Your mission, should you choose to accept it -- write a program using a recursive procedure to solve the Towers of Hanoi for any number of discs. First ask the user for the height of the original tower. Then, print out step-by-step instructions for moving individual discs from one peg to another. For example, a three-disc problem should produce the following output:

1 to 3
1 to 2
3 to 2
1 to 3
2 to 1
2 to 3
1 to 3

正如在递归章节所叙述的，递归是最难掌握的编程技术之一。一些人能很快的通过这个示例（汉诺塔）领会其中的真理，一些人则会感到十分困惑。然而，一旦你掌握了递归的技巧，作出解决汉诺塔问题的程序对你来说就是小菜一碟。

As stated in the section on recursion, recursion is one of the more difficult topics to grasp. Some people will look at this problem and find it extremely easy. Others will have a difficult time with it. However, once you get past the hurdle of understanding recursion, the actual coding of the program is relatively simple.

现在，如果你打算挑战自我，就先读到这里，打开你的fp或lazarus写代码吧！如果你遇到了困难，可以看看下文的小提示。

So, if you'd like to challenge yourself, stop reading right here. If you have a little trouble, keep reading for a small hint.

---

提示：这个问题就像所有递归问题一样，随着递归的进行不断地简化自身。还记得三层塔的问题吗，首先把二层塔移到杆二，然后将原本位于杆一最下层的圆盘移到杆三，然后再将位于杆二的双层塔移到杆三。

Hint: the problem, like all recursive problems, reduces itself, becoming simpler with each step. Remember the three-disc problem? You first create a two-disc tower on peg 2, which allows you to move the bottommost disc on peg 1 to peg 3. Then you move the two-disc tower on top of peg 3.

对于四层塔也是一样的，首先移动三层圆盘到杆二，再将最大的圆盘移到杆三，最后再将位于杆二的三层塔移到杆三。怎么移动三层塔？我们已经在上一文段学会了！唯一的不同，只是这次要将三层塔由杆一移到杆二，而非杆三。当最大的圆盘已经被移到杆三时，再将位于杆二的三层塔移到杆三。在整个过程中，我们可以无视最大的圆盘的存在（因为它不影响其他圆盘的移动）。利用三层塔和四层塔的例子学会举一反三吧！

It's the same with four discs. First create a three-disc tower on peg 2, then move the biggest disc over to peg 3 and move the three-disc tower to peg 3. How do you create the three-disc tower? Simple. We already know how to move a three-disc tower from peg 1 to peg 3. This time, you're just moving from peg 1 to peg 2, then when the biggest peg is in place, you're moving the tower from peg 2 to peg 3. In this whole procedure, we can act as though the big disc doesn't exist, since it's guaranteed to be bigger than the others and thus poses no problem. Just utilize the three-disc solution, switching the numbers around.

祝好运~！

Good luck!

上一页

目录

下一页