#1
5
(由 Microsoft 翻譯)
-
- 我假設移動戒指的基本規則是眾所周知的。
- 如果環數為奇數,您只需 1 步,就將頂部環直接放在所需的環的頂部。
- 如果是均勻的,則需要兩個步驟才能移動。讓我們假設從左到右掛鉤 A、B 和 C。例如,如果在 B 上,我們有一個帶環 1,2,3,4 的堆,並且想要將它們放在 C 上的環 5 上,則第一步是 1 到 A 和 2 到 C,下一步是 1 到 C。.和總共 15 個動作, 我們將有 1, 2, 3, 4 環超過 5 在釘 C 。
- 在最初的佈局有較大的戒指頂部較小的戒指(這是這個遊戲的第一版的主要區別),但當你開始玩,你不能把一個更大的戒指在一個較小的一個頂部,如在河內塔一。
- 我認為解決遊戲的最佳方法是從快速查看 9 號、8 號環和 7 號圈的位置開始。重要的是要看看環 9 是否已經位於挂鉤的基座上。如果不是,最好的方法是什麼(少移動)把它放在那裡。在這種情況下,它經常發生(特別是如果7和8在不同的挂鉤),一個人需要放置7超過8有一個自由挂鉤9。此外,我們可能需要把6對9,7移動到自由挂鉤后移動6,然後6超過7。 結果將是一堆從1到7和需要127個額外的動作,把這7環的頂部8,9(在河內塔一的情況解決遊戲的最小數量是:最小移動= 2\n - 1其中n是環的數量,所以,3環將需要7個動作,4環將需要15...7 環將需要127等)。
- 無論情況如何,目的是,在可能移動的最小數量的情況下,將初始佈局更改為河內一號塔的情況。這意味著你將永遠提前知道,如果遊戲可以解決,而不必實際完成它。當戒指在河內塔 I 的情況下 (一堆在上升順序開始與戒指 1, 2...在一個挂鉤上,一個自由挂鉤,和一個挂鉤與剩餘的環,也按升序,完成在挂鉤的基礎,其中9是),只需添加已經作出的動作,由上述方程給出的必要移動,結果應等於所需的最小移動(每當我這樣做,控制只是添加最後一個數位)。
- 三個例子(全部來自本網站)。
- 初始佈局 (需要 145 次最小移動)
佩格 A - 1,8,2,9。
佩格 B - 7,3。
佩格 C - 6,5,4。
步驟 1 - 最好的策略是將 9 放在挂鉤 C 的基座上,將 6 放在掛鉤 B 的 7 個上面。
第一步是: 環 3 在 A 上 9 的頂部, 然後 4 在 B 上 7...
從 初始佈局移動 18 次後,我們得到:
佩格 A - 1。
Peg B - 7,6,5,4,3,2 18 移動。
佩格 C = 9,8。
第 2 步 – 如果我們仔細查看此布局,我們會注意到,這相當於 B 上 7 環的 6 環,前提是下一步是將環 1 放在 C 上的 8 個環的頂部。我們說的是6環(6,5...1,甚至,在挂鉤B和2個步驟是必需的)。因此,要將這六個環放在 A 上,我們需要先採取行動,將 1 放在另一個掛鉤上,在此例中為 C。
正如我們已經知道的, 要移動 6 環到另一個掛鉤 (peg A), 我們需要 63 個動作。這些移動后,有一個額外的放置7,現在免費,在9,8的頂部。
因此,在此步驟 2 中,移動將是 63 + 1 = 64, 我們得到的佈局是:
A - 6,5,4,3,2,1。
B - 63×1 × 64 移動。
C - 9,8,7。
到目前為止, 我們在步驟 1 上有 18 個動作, 第 2 步有 64 個動作。
第 3 步 – 上述布局對應於我所說的河內 I 塔的情況。
為了完成比賽,我們需要移動6環(6,5,...1) 在挂鉤 A 到 9, 8, 7 的頂部在挂鉤 C。 這將需要另外63個動作。
總移動 = 18 = 64 = 63 = 145,這是所需的最小移動。 - 初始佈局(需要 256 次最小移動)
A - 5,3,9。
B - 8,1,6,4。
C - 2,7。
要將 9 放在底座上, 因為 8 和 7 在不同的掛鈎上, 我們需要在 B 上放置 7 個 8。
第 1 步 - 我們的目標是將 9 放在 C 上,在 B 上放置 7 個。為了達到這個目的,我們首先需要將 6,4 移至 A 上的 9 的頂部,以釋放 C 才能接收 9。
前五個動作是 4 在 7, 6, 除了 9 在 A, 4 到 6, 1 到 4 和 7 到 8 在釘 B。
20 次移動后,佈局將。
A = 5,3。
B = 8,7,6,4,2,1 20 次移動。
C = 9。
步驟 2 將 6 超過 9 放在挂鉤 C 上。為了做到這一點,我們需要4在5頂部的5完成這個步驟2與5,4,3,2,1的釘 A 。這是完成13個動作和佈局是。
A = 5,4,3,2,1。
B = 8, 7 13 移動。
C - 9,6。
步驟 3 = 將 5,4...,1(5 環)移動到 6 個掛鉤 C 的頂部。這對應於 31 個移動加上 1,將 7 放在挂鉤 A 上。 因此,步驟 3 31+1=32 中的移動數和佈局將。
A = 7。
B = 8 32 移動。
C = 9,6,5,4,3,2,1。
第四步 - 移動 6,5,...1 到 7 的頂部在掛鈎 A 將需要 (6 環) 63 移動加上另一個把 8 放在 9 的頂部 C. 總移動在步驟 4 63 +1 +64 和佈局。
A = 7,6,5,4,3,2,1。
B - 63×1 × 64 移動。
C - 9,8。
步驟 5。
我們有一個河內塔一的情況。最後一步是將 7 環從釘 A 移動。
在挂鉤 C 上 9,8 的頂部。這意味著 127 個移動。
總移動 - 20 × 13 × 32 × 64 × 127 × 256 最小移動需要。 - 初始佈局(需要 303 次最小移動)
A = 4,9,7,5,8。
B = 6,2。
C = 3,1。
此示例比前兩個要難一些。
請注意,9 卡在 A 上,頂部有三個環(7,5,8)。此外,B 和 C 不是自由掛鈎。很顯然, 需要把 8, 7 放在自由掛鈎上, 否則我們將沒有 9 個自由挂鉤。
最好的方法就是把 8,7 放在挂鉤 C 上,把 6 放在 C 上的 8,7 的頂部。
完成之後,Peg B 將免費接收 9。但是請注意,在釋放 7 之前,我們需要在 B 上放置 5 個 6。
步驟 1 - 放置 8,在 C 上,在 B 上放置 6,5,3,2,1。
前七個動作是:
2 對 A。
1 對 A。
3 在頂端 B (在 6 的頂部)
1 對 C。
2 對 B。
1 對 B。
8 在 C 上。
開始後 23 次移動, 我們得到佈局。
A = 4,9。
B = 6,5,3,2,1 23 次移動。
C = 8,7。
第 2 步 – 將 6,5,3,1(5 環)放在 C 上,放在 8,7(peg B 將可自由放置 9) 上。
將 5 個環移至另一個掛鉤需要 31 個移動加上另一個移動,以放置 9 個 B,因此,在此步驟中, 我們需要 31+1 +32 移動 。
佈局為。
A = 4。
B = 9 31+1= 32 次移動。
C = 8,7,6,5,3,2,1。
第 3 步 – 現在的目的是釋放掛鉤 A 來接收 7 (否則我們不能將 8 放在 9 的頂部) 。要做到這一點,需要將 6,5,3,2,1 移動到 B,在 9 個上面。
但是, 由於移動是交替放置 6 在 B 上, 我們以前需要把 5 放在 A 和 4 在 B...
在 步驟 2 的開始 57 次移動后,我們將具有以下佈局。
A = 7。
B = 9,6,5,4,3,2,1 57 次移動。
C = 8。
很明顯,這57個動作必須遵循邏輯。事實上,它們可以分解為以下操作。
行動。 移動數。 4 對 B。 1。 3,2,1 (3 環) 前 4 名 B。 7。 5 到 A。 1。 4,3,2,1(4 環)至 A。 15。 6 到 B。 1。 5,4,3,2,1(5 環)到 B 頂部 6。 31。 7 到 A。 1。 總。 57。
步驟 4 - 將 6,5...2,1(6 環)移動到頂部 7 的 A。這需要63個動作。 現在,可以將 8 放在 B 上 9 個上面,這意味著額外的移動。
因此,在此步驟 4 中,共有 63+1 = 64 個移動。
完成此功能后,佈局為。
A = 7,6,5,4,3,2,1。
B = 9,8,63×1=64( 河內一號塔的情況)
C |。
第 5 步 – 最後一步是移動 7,6,...2,1 到挂鉤 B 到頂部 9,8 。
要移動 7 圈,需要 127 個移動。
因此,總移動為 23×32×57×64×127×303 移動 最少。
- 初始佈局 (需要 145 次最小移動)
(原文) Solving Tower of Hanoi II
-
- I assume the basic rules for moving the rings are well known.
- If the number of rings is odd you only need 1 step to place the top ring straight on top of the ring you want.
- If it’s even, there is a need for two steps to make the move. Let’s assume pegs A,B and C from left to right. If, for example, on B we have a pile with rings 1,2,3,4 and want to place them over ring 5 on C , the first step will be 1 to A and 2 to C, and next, 1 to C.. .and with a total of 15 moves we will have the 1,2,3,4 rings over 5 on peg C.
- In the initial layout there are larger rings on top of smaller rings (that’s the main difference from version I of this game) but when you start playing you can’t put a larger ring on top of a smaller one as in Tower of Hanoi I.
- I think the best approach to solve the game is starting with a quick look at the positions of rings 9, 8 and 7. It’ s important to see if ring 9 is already on the base of a peg. And if it isn’t, what the best way is (less moves) to put it there. In this case it often happens (especially if 7 and 8 are on different pegs) that one needs to place 7 over 8 to have a free peg for 9. Moreover we may have to place 6 on 9, 7 moving to the free peg after moving 6 and then 6 over 7 . The result will be a pile from 1 to 7 and the need of 127 additional moves to place these 7 rings on top of 8,9 (the minimal number of moves to solve a game in Tower of Hanoi I situation is : minimal moves = 2^n - 1 where n is the number of rings so, 3 rings will need 7 moves, 4 rings will need 15… 7 rings will need 127 and so on).
- Whatever the case, the purpose is, with the minimal number of moves possible, to change the initial layout to a Tower of Hanoi I situation. This means you will always know in advance if the game can be solved without having to actually finish it. When the rings are in a Tower of Hanoi I situation (a pile in ascending order starting with rings 1,2… on one peg, a free peg, and a peg with the remaining rings, also in ascending order, finishing on the base of the peg where 9 is), just add the moves already made to the necessary moves given by the above equation and the result should be equal to the minimal moves needed (whenever I do that control just add the last digit).
- Three examples (all from this website).
- Initial layout (145 minimal moves needed)
Peg A - 1,8,2,9
Peg B - 7,3
Peg C - 6,5,4
Step 1 - The best strategy is to place 9 on the base of peg C and 6 on top of 7 on peg B.
First move is: ring 3 on top of 9 on A, then 4 on top of 7 on B…
After 18 moves from the initial layout we get:
Peg A - 1
Peg B - 7,6,5,4,3,2 18 moves
Peg C – 9,8
Step 2 – If we look at this layout carefully, we’ll note this is equivalent to 6 rings on top of 7 on B, provided the next move is to place ring 1 on top of 8 on C. We are speaking of 6 rings (6,5 …1 that is, even, on peg B and 2 steps are required). So to place these six rings on A we need a first move to place 1 on the other peg, in this case C.
As we already know, to move 6 rings to another peg (peg A) we need 63 moves. After these moves there is an addtional one to place 7, now free, on top of 9,8.
So, in this Step 2 the moves will be 63 + 1= 64 and the layout we get is:
A - 6,5,4,3,2,1
B - 63+1 = 64 moves
C - 9,8,7
So far, we have 18 moves on Step 1 plus 64 on Step 2
Step 3 – The above layout corresponds to what I call a Tower of Hanoi I situation.
To finish the game we need to move the 6 rings (6,5,…1) on peg A to the top of 9,8,7 on peg C. This will require another 63 moves.
Total moves= 18 + 64 + 63 = 145 which is the minimal moves needed. - Initial layout (256 minimal moves needed)
A - 5,3,9
B - 8,1,6,4
C - 2,7
To place 9 on the base, as 8 and 7 are on different pegs, we need to place 7 on top of 8 on B.
Step 1 - Our goal is to place 9 on C and 7 on top of 8 on B. To achieve this we first need to move 6,4 to the top of 9 on A to free C to receive the 9.
The first five moves are 4 on top of 7,6 on top of 9 on A ,4 to 6,1 to 4 and 7 to 8 on peg B.
After 20 moves the layout will be
A – 5,3
B – 8,7,6,4,2,1 20 moves
C – 9
Step 2 place 6 over 9 on peg C. To achieve this we need 4 on top of 5 on A finishing this Step 2 with 5,4,3,2,1 on peg A . This is done with 13 moves and the layout is
A – 5,4,3,2,1
B – 8, 7 13 moves
C - 9,6
Step 3 – Move 5,4…,1 (5 rings) to the top of 6 on peg C. This corresponds to 31 moves plus 1 to place 7 on peg A. So, the number of moves in Step 3 31+1=32 and the layout will be
A – 7
B – 8 32 moves
C – 9,6,5,4,3,2,1
Step 4 - Moving 6,5,…1 to the top of 7 on peg A will require (6 rings) 63 moves plus another one one to put 8 on top of 9 on C. Total moves on Step 4 63+1=64 and the layout
A – 7,6,5,4,3,2,1
B - 63+1 = 64 moves
C - 9,8
Step 5
We have a Tower of Hanoi I situation. The final step is moving the 7 rings from peg A
to the top of 9,8 on peg C. This means 127 moves.
Total moves- 20 + 13 + 32 + 64 + 127 = 256 minimal moves needed. - Initial layout (303 minimal moves needed)
A – 4,9,7,5,8
B – 6,2
C – 3,1
This example is a bit harder than the previous two.
Note that 9 is stuck on A with three rings on top (7,5,8). Also, B and C are not free pegs. It’s clear the need to place the 8,7 on a free peg otherwise we will not have a free peg for 9.
The best way to do this is to place 8,7 on peg C and move 6 to the top of 8,7 on C.
After this is done Peg B will be free to receive 9. Note however, before freeing 7 we need to place 5 on top of 6 on B.
Step 1 - Place 8, on C and 6,5,3,2,1 on B
The first seven moves are:
2 on A
1 on A
3 on top B (on top of 6)
1 on C
2 on B
1 on B
8 on C
23 moves after the start we get the layout
A – 4,9
B – 6,5,3,2,1 23 moves
C – 8,7
Step 2 – Place the 6,5,3,2,1 (5 rings) on C on top of 8,7 (peg B will be free to place the 9).
Moving 5 rings to another peg requires 31 moves plus another one to place 9 on B so, in this step we need 31+1 =32 moves .
The layout is
A – 4
B – 9 31+1= 32 moves
C – 8,7,6,5,3,2,1
Step 3 – The purpose now is to free peg A to receive 7 (otherwise we can’t place 8 on top of 9). To acheive this it’s needed to move 6,5,3,2,1 to B on top of 9.
But as the moves are alternate to place 6 on B we previously need to place the 5 on A and 4 on B…
After 57 moves from the start on Step 2 we will have the following layout.
A – 7
B – 9,6,5,4,3,2,1 57 moves
C – 8
It’s obvious these 57 moves must follow a logic. In fact they can be decomposed on the following actions
Action Number of moves 4 on B 1 3,2,1 (3 rings) on top 4 on B 7 5 to A 1 4,3,2,1 (4 rings) to A 15 6 to B 1 5,4,3,2,1 (5 rings) to B on top of 6 31 7 to A 1 Total 57
Step 4 - move 6,5…..2,1 (6 rings) to A on top of 7. This needs 63 moves. Now it’s possible to place 8 on top of 9 on B which means an additional move.
So in this Step 4 there is a total of 63+1 = 64 moves
After this is done the layout is
A – 7,6,5,4,3,2,1
B – 9,8, 63+1=64 (Tower of Hanoi I situation)
C –
Step 5 – The final step is to move 7,6,…2,1 to peg B to the top of 9,8 .
To move 7 rings, 127 moves will be needed.
So, the total moves are 23+32+57+64+127= 303 moves minimal moves needed
- Initial layout (145 minimal moves needed)
作者 Slb
2020-02-13 16:10:02
讚好
回覆