python - 河内建议的循环(单向)塔？

Question

这是我为汉诺塔问题编写的 Python 代码，其中塔必须从左桩转移到中间桩，使用右桩作为备用:

def hanoi(n, origin = "1", destination = "2", spare = "3"):

    if n == 1:
        print ("Move disk from", origin, "to", destination)

    else:
        hanoi(n-1, origin, spare, destination)
        hanoi(1, origin, destination, spare)
        hanoi(n-1, spare, destination, origin)

hanoi(3)

现在我的教授希望我以一种合法的移动方式来实现它，其中合法的移动只有从塔 1 到 2、塔 2 到 3 和塔 3 到 1。所有其他规则都是相同的。

Answer 1

与此问题一样，您需要归纳思考。从尽可能小的塔开始移动，然后问问自己:如果我能做到这一点，我该如何移动更大的塔？

由于移动 1 号塔很简单，让我们从 2 号塔开始:

基本案例

将一个大小为 2 的塔向右移动:

|  -  |     |     |
| --- |     |     |
-------------------
Step 1:

|     |     |     |   
| --- |  -  |     |
-------------------
Step 2:

|     |     |     |
| --- |     |  -  |
-------------------
Step 3:

|     |     |     |
|     | --- |  -  |
-------------------
Step 4:

|     |     |     |
|  -  | --- |     |
-------------------
Step 5:

|     |  -  |     |
|     | --- |     |
-------------------

这演示了如何将塔向右移动一个桩。当然，这也可以用来将塔从第二个移到第三个，或者从第三个移到第一个。

步骤

假设您知道如何将一座 n 大小的塔向右移动一个木桩，下面是您如何将 n + 1 个圆盘移动:

|    -    |         |         | Move the small tower one peg to the right
|   ---   |         |         |
|  -----  |         |         |
| ------- |         |         |
-------------------------------
Step 1:

|         |         |         | Move it another step to the right
|         |    -    |         |
|         |   ---   |         |
| ------- |  -----  |         |
-------------------------------
Step 2:

|         |         |         | Let's move the n+1 disk one peg to the right
|         |         |    -    |
|         |         |   ---   |
| ------- |         |  -----  |
-------------------------------
Step 3:

|         |         |         | Move the small tower to the right
|         |         |    -    |
|         |         |   ---   |
|         | ------- |  -----  |
-------------------------------
Step 4: 

|         |         |         | Move the small tower another peg to the right
|    -    |         |         |
|   ---   |         |         |
|  -----  | ------- |         |
-------------------------------
Final step:

|         |    -    |         | 
|         |   ---   |         |
|         |  -----  |         |
|         | ------- |         |
-------------------------------