#1
-
- 我假設移動戒指的基本規則是眾所周知的。
- 如果環數為奇數,您只需 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 次最小移動)
(已翻譯) [顯示原文]
2020-02-13 08:10:02
讚好
回覆