-1

右のペグをスペアとして使用して、タワーを左のペグから中央のペグに転送する必要がある、ハノイの塔の問題用に作成した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だけになるように実装することを望んでいます。他のすべてのルールは同じです。

4

1 に答える 1

4

この問題ではいつものように、帰納的に考える必要があります。移動できる最小の塔から始めて、次のことを自問してください。

サイズ 1 のタワーを移動するのは簡単なので、サイズ 2 のタワーから始めましょう。

規範事例

サイズ 2 のタワーを 1 ペグ右に移動します。

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

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

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

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

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

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

これは、タワーを 1 ペグ右に移動する方法を示しています。もちろん、これはタワーを2番目から3番目に、または3番目から最初のペグに移動するためにも使用できます。

ステップ

サイズnのタワーを1 ペグ右に移動する方法を知っているとしましょう。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:

|         |    -    |         | 
|         |   ---   |         |
|         |  -----  |         |
|         | ------- |         |
-------------------------------
于 2012-11-24T15:17:18.317 に答える