#1
5
(翻訳者 Microsoft)
-
- 私はリングを動かするための基本的なルールはよく知られていると仮定します。
- リングの数が奇数の場合は、あなたが望むリングの上にまっすぐにトップリングを配置するために1ステップだけ必要です。
- 偶数の場合は、移動を行うための2つのステップが必要です。左から右にペグA、B、Cを仮定しましょう。たとえば、B にリング 1,2,3,4 の山があり、C のリング 5 の上に置きたい場合、最初のステップは 1 から A、2 から C、次は 1 から C になります。15の動きの合計で、我々はペグC上の5以上の1,2,3,4リングを持つことになります。
- 最初のレイアウトでは、小さなリングの上に大きなリングがありますが(これはこのゲームのバージョンIとの主な違いです)、あなたがプレイを開始すると、ハノイの塔のように小さなリングの上に大きなリングを置くすることはできません。
- 私はゲームを解決するための最良のアプローチは、リング9、8、7の位置を簡単に見て始めていると思います。リング9がすでにペグのベースにあるかどうかを確認することが重要です。そうでなければ、そこに置く最善の方法(動きが少ない)は何ですか?この場合、多くの場合、9の無料ペグを持つために7オーバー8を配置する必要がある(特に7と8が異なるペグにある場合)発生します。さらに、私たちは9に6を配置する必要があるかもしれません, 7は6を移動した後、フリーペグに移動し、6オーバー7 . 結果は1から7までの山になり、これらの7つのリングを8,9の上に置くために127の追加の動きが必要になります(ハノイIの塔でゲームを解決するための動きの最小数は: 最小限の動き = 2^n - 1 はnがリングの数なので、3リングは7つの動きを必要とします、4リングは15..7つのリングは127などを必要とします)。
- どのような場合でも、目的は、可能な限り最小限の移動数で、ハノイIの塔の状況に初期レイアウトを変更することです。これは、ゲームを実際に終了することなく解決できるかどうか、常に事前に知っていることを意味します。リングがハノイ1の塔の状況にある場合(リング1,2.で始まる昇順の山。1つのペグ、フリーペグ、残りのリングを持つペグ、さらに昇順で、9があるペグのベースで終わるだけで、上記の方程式によって与えられた必要な動きに既に行われた動きを追加するだけで、結果は必要最小限の動きに等しくする必要があります(コントロールが最後の数字を追加するだけです)。
- 3つの例(すべてこのウェブサイトから)。
- 初期レイアウト(145の最小限の移動が必要)
ペグA - 1,8,2,9
ペグB - 7,3
ペグC - 6,5,4
ステップ1 - 最良の戦略は、ペグCのベースに9を置き、ペグBの7の上に6を置く。
最初の動きは、Aの9の上にリング3、Bの7の上に4です。
最初のレイアウトから 18 の移動後、私たちは得る:
ペグA - 1
ペグB - 7,6,5,4,3,2 18の動き
ペグC – 9,8
ステップ 2 – このレイアウトを注意深く見ると、次の動きが C の 8 の上にリング 1 を配置する場合、これは B の 7 の上に 6 つのリングに相当することに注意してください。私たちは6つのリング(6,5..)について話しています。1 すなわち、ペグBおよび2ステップ上であっても必要である)。したがって、これらの6つのリングをAに配置するには、もう一方のペグ(この場合はC)に1を配置する最初の動きが必要です。
すでに知っているように、6つのリングを別のペグ(ペグA)に移動するには、63の動きが必要です。これらの動きの後、9,8の上に7、今は無料で配置する追加のものがあります。
したがって、このステップ2では、移動は 63 + 1 = 64 になり、レイアウトは次のようになります。
A - 6,5,4,3,2,1
B - 63+1 = 64移動
C - 9,8,7
これまでのところ、ステップ2のステップ1と64で18の動きがあります
ステップ3 - 上記のレイアウトは、私はハノイIの状況の塔と呼ばれるものに対応しています.
ゲームを終了するには、6つのリング(6,5,...を移動する必要があります1)ペグCの9,8,7の上部にペグAに。 これには別の63の動きが必要です。
総移動数= 18 + 64 + 63 = 145 必要最小限の移動です。 - 初期レイアウト(256の最小限の移動が必要)
A - 5,3,9
B - 8,1,6,4
C - 2,7
8と7が異なるペグにあるので、ベースに9を置くためには、Bの8の上に7を置く必要があります。
ステップ1 - 私たちの目標は、Cに9、Bの8の上に7を置く。これを達成するには、最初にAの9のトップに6,4を移動し、Cを解放して9を受け取る必要があります。
最初の5つの動きは、Aの9の上に7,6の上に4、6、1〜4とペグBで7〜8です。
20移動後、レイアウトは
A – 5,3
B – 8,7,6,4,2,1 20 の動き
C - 9
ステップ2はペグCの上に6オーバー9を置きます。これを達成するためには、ペグAの5,4,3,2,1でこのステップ2を終える5の上に4が必要です。これは13の移動で行われ、レイアウトは
A – 5,4,3,2,1
B – 8, 7 13移動
C - 9,6
ステップ 3 – ペグ C の 6 の上部に 5,4..,1 (5 つのリング) を移動します。これは、ペグAに7を配置するために31の動きプラス1に対応しています。 したがって、ステップ 3 31+1=32 の移動回数とレイアウトは
A - 7
B – 8 32の動き
C – 9,6,5,4,3,2,1
ステップ4 - 6,5を移動,...ペグAの7の上に1は(6リング)63の動きとCの9の上に8を置くために別のものを必要とします。
A – 7,6,5,4,3,2,1
B - 63+1 = 64移動
C - 9,8
ステップ 5
私たちはハノイ1の状況の塔を持っています。最後のステップは、ペグAから7リングを移動することです
ペグCの9,8の上に。これは127の動きを意味します。
総移動 - 20 + 13 + 32 + 64 + 127 = 256 最小の移動が必要です。 - 初期レイアウト(303の最小限の移動が必要)
A – 4,9,7,5,8
B – 6,2
C – 3,1
この例は、前の 2 つよりも少し難しいです。
9 は、上に 3 つのリング (7,5,8) を持つ A に貼り付けられていることに注意してください。また、BとCは無料のペグではありません。無料のペグに8,7を置く必要性は明らかです。そうでなければ9のための無料のペグはありません。
これを行う最善の方法は、ペグCに8,7を配置し、Cの8,7のトップに6を移動することです。
これが完了した後、ペグBは9を受け取って自由になります。ただし、7 を解放する前に、B の 6 の上に 5 を配置する必要があります。
ステップ 1 - C 上に 8 を配置し、6,5,3,2,1 を B に配置します。
最初の 7 つの移動は次のとおりです。
2 オン A
1 オン A
トップBの3(6の上)
1 オン C
2 オン B
1 オン B
8 on C
開始後23の動き は、我々はレイアウトを取得します
A – 4,9
B – 6,5,3,2,1 23の動き
C – 8,7
ステップ2 – 8,7の上にC上に6,5,3,2,1(5つのリング)を置きます(ペグBは9を自由に配置することができます)。
別のペグに5リングを移動するには、31の動きとBに9を配置する別の動きが必要なので、このステップでは 31 +1 =32の移動が 必要です。
レイアウトは
A – 4
B – 9 31+1= 32移動
C – 8,7,6,5,3,2,1
ステップ3 - 今の目的は、7を受け取るためにペグAを解放することです(そうでなければ、9の上に8を置くすることはできません)。これを達成するには、6,5,3,2,1を9の上にBに移動する必要があります。
しかし、動きはBに6を置くために交互に行われるので、以前は5をAに、4をB.に置く必要があります。
ステップ2の開始から 57 移動後、次のレイアウトになります。
A - 7
B – 9,6,5,4,3,2,1 57の動き
C – 8
これらの57の動きが論理に従わなければならないことは明らかです。実際、以下のアクションで分解することができます
アクション 移動数 4 オン B 1 Bのトップ4に3,2,1(3リング) 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 - 7の上にAに6,5.....2.1(6リング)を移動します。これには63の動きが必要です。 これで、B の 9 の上に 8 を配置することが可能になり、追加の移動が行われます。
したがって、このステップ4では合計63+1 = 64の動きがあります
これが完了すると、レイアウトは
A – 7,6,5,4,3,2,1
B – 9,8, 63+1=64 (ハノイ1の塔状況)
C –
ステップ5 - 最後のステップは、移動することです 7,6,...2,1は9,8の頂上にBをペグする。
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
いいね！
返信する