Programming Assignment 4/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.
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.