#1
5
(Übersetzt von Microsoft)
-
- Ich gehe davon aus, dass die Grundregeln für das Bewegen der Ringe bekannt sind.
- Wenn die Anzahl der Ringe ungerade ist, benötigen Sie nur 1 Schritt, um den oberen Ring direkt auf den ring zu platzieren, den Sie wollen.
- Wenn es sogar ist, gibt es einen Bedarf für zwei Schritte, um den Umzug zu machen. Nehmen wir die Pegs A, B und C von links nach rechts an. Wenn wir z.B. einen Stapel mit den Ringen 1,2,3,4 haben und sie über Ring 5 auf C platzieren möchten, ist der erste Schritt 1 bis A und 2 bis C und als nächstes 1 bis C. .und mit insgesamt 15 Zügen haben wir die 1,2,3,4 Ringe über 5 auf Peg C.
- Im ursprünglichen Layout gibt es größere Ringe auf kleineren Ringen (das ist der Hauptunterschied zu Version I dieses Spiels), aber wenn du anfängst zu spielen, kannst du keinen größeren Ring auf einen kleineren wie in Tower of Hanoi I legen.
- Ich denke, der beste Ansatz, um das Spiel zu lösen, ist mit einem schnellen Blick auf die Positionen der Ringe 9, 8 und 7 zu beginnen. Es ist wichtig zu sehen, ob Ring 9 bereits auf der Basis eines Pflocks ist. Und wenn nicht, was der beste Weg ist (weniger bewegt), es dort zu setzen. In diesem Fall kommt es oft vor (besonders wenn 7 und 8 auf verschiedenen Pflöcken sind), dass man 7 über 8 platzieren muss, um einen freien Stift für 9 zu haben. Darüber hinaus müssen wir vielleicht 6 auf 9, 7 bewegen auf den freien Pflock nach dem Bewegen 6 und dann 6 über 7 . Das Ergebnis wird ein Haufen von 1 bis 7 und die Notwendigkeit von 127 zusätzlichen Zügen, um diese 7 Ringe auf oben auf 8,9 zu platzieren (die minimale Anzahl der Züge, um ein Spiel in Tower of Hanoi I Situation zu lösen ist : minimale Züge = 2n - 1 wo n ist die Anzahl der Ringe so, 3 Ringe benötigen 7 Züge, 4 Ringe benötigen 15... 7 Ringe benötigen 127 und so weiter).
- Wie dem auch sei, der Zweck ist, mit der minimalen Anzahl von Möglichen, das ursprüngliche Layout in einen Turm von Hanoi I Situation zu ändern. Das bedeutet, dass Sie immer im Voraus wissen, ob das Spiel gelöst werden kann, ohne es tatsächlich beenden zu müssen. Wenn die Ringe in einem Turm von Hanoi I Situation sind (ein Haufen in aufsteigender Reihenfolge beginnend mit Ringen 1,2... auf einem Pflock, einem freien Pflock und einem Stift mit den verbleibenden Ringen, ebenfalls in aufsteigender Reihenfolge, die auf der Basis des Pflocks endet, wo 9 ist), fügen Sie einfach die Bewegungen hinzu, die bereits zu den notwendigen Bewegungen gemacht wurden, die durch die obige Gleichung gegeben wurden, und das Ergebnis sollte gleich den minimalen Bewegungen entsprechen, die benötigt werden (wann immer ich diese Kontrolle tue, fügen Sie einfach die letzte Ziffer hinzu).
- Drei Beispiele (alle von dieser Website).
- Erstes Layout (145 minimale Verschiebungen erforderlich)
Peg A - 1,8,2,9
Peg B - 7,3
Peg C - 6,5,4
Schritt 1 - Die beste Strategie ist, Platz 9 auf der Basis von Peg C und 6 auf oben auf 7 auf Peg B.
Der erste Zug ist: Ring 3 oben auf 9 auf A, dann 4 auf 7 auf B...
Nach 18 Zügen aus dem ursprünglichen Layout erhalten wir:
Peg A - 1
Peg B - 7,6,5,4,3,2 18 Züge
Peg C – 9,8
Schritt 2 – Wenn wir uns dieses Layout genau ansehen, werden wir feststellen, dass dies 6 Ringen auf 7 auf B entspricht, vorausgesetzt, der nächste Zug ist, Ring 1 auf 8 auf C zu platzieren. Wir sprechen von 6 Ringen (6,5 ... 1, d.d. b., auf Peg B und 2 Stufen erforderlich). Um diese sechs Ringe auf A zu platzieren, brauchen wir einen ersten Zug, um Platz 1 auf dem anderen Stift, in diesem Fall C, zu platzieren.
Wie wir bereits wissen, brauchen wir 63 Züge, um 6 Ringe zu einem anderen Stift (Peg A) zu bewegen. Nach diesen Umzügen gibt es einen zusätzlichen Platz 7, jetzt frei, auf 9,8.
In diesem Schritt 2 werden die Züge also 63 + 1= 64 sein und das Layout, das wir erhalten, ist:
A - 6,5,4,3,2,1
B - 63+1 = 64 Züge
C - 9,8,7
Bisher haben wir 18 Züge auf Schritt 1 plus 64 auf Schritt 2
Schritt 3 – Das obige Layout entspricht dem, was ich einen Turm von Hanoi I Situation nenne.
Um das Spiel zu beenden, müssen wir die 6 Ringe (6,5,... 1) auf Peg A bis zur Spitze von 9,8,7 auf Peg C. Dies erfordert weitere 63 Züge.
Gesamtbewegungen = 18 + 64 + 63 = 145, was den minimalen Erforderlichen entspricht. - Erstes Layout (256 minimale Verschiebungen erforderlich)
A - 5,3,9
B - 8,1,6,4
C - 2,7
Um Platz 9 auf der Basis, da 8 und 7 auf verschiedenen Pflöcken sind, müssen wir 7 auf 8 auf B platzieren.
Schritt 1 - Unser Ziel ist es, Platz 9 auf C und 7 auf oben auf 8 auf B. Um dies zu erreichen, müssen wir zuerst 6,4 nach oben von 9 auf A bewegen, um C zu befreien, um die 9 zu erhalten.
Die ersten fünf Züge sind 4 auf 7,6 auf oben auf 9 auf A , 4 bis 6,1 bis 4 und 7 bis 8 auf Peg B.
Nach 20 Verschiebungen wird das Layout
A – 5,3
B – 8,7,6,4,2,1 20 Züge
C – 9
Schritt 2 Platz 6 über 9 auf Peg C. Um dies zu erreichen, benötigen wir 4 auf oben 5 auf A und beenden diesen Schritt 2 mit 5,4,3,2,1 auf Peg A . Dies geschieht mit 13 Zügen und das Layout ist
A – 5,4,3,2,1
B – 8, 7 13 Züge
C - 9,6
Schritt 3 – Bewegen Sie 5,4...,1 (5 Ringe) an die Spitze von 6 auf Peg C. Dies entspricht 31 Zügen plus 1 zu Platz 7 auf Peg A. Die Anzahl der Züge in Schritt 3 31+1=32
A – 7
B – 8 32 Züge
C – 9,6,5,4,3,2,1
Schritt 4 - Bewegen 6,5,... 1 an die Spitze von 7 auf Peg A erfordert (6 Ringe) 63 Züge plus einen weiteren, um 8 auf 9 auf C zu setzen.
A – 7,6,5,4,3,2,1
B - 63+1 = 64 Züge
C - 9,8
Schritt 5
Wir haben einen Turm von Hanoi I Situation. Der letzte Schritt ist das Verschieben der 7 Ringe aus Peg A
auf die Spitze von 9,8 auf Peg C. Das bedeutet 127 Züge.
Gesamtzüge - 20 + 13 + 32 + 64 + 127 = 256 minimale Bewegungen erforderlich. - Erstes Layout (303 minimale Verschiebungen erforderlich)
A – 4,9,7,5,8
B – 6,2
C – 3,1
Dieses Beispiel ist etwas schwieriger als die vorherigen beiden.
Beachten Sie, dass 9 auf A mit drei Ringen oben (7,5,8) klebt. Auch B und C sind keine freien Pflöcke. Es ist klar, dass die 8,7 auf einem freien Pflock platziert werden muss, sonst haben wir keinen freien Pflock für 9.
Der beste Weg, dies zu tun, ist 8,7 auf Peg C zu platzieren und 6 an die Spitze von 8,7 auf C zu bewegen.
Danach wird Peg B frei sein, 9 zu erhalten. Beachten Sie jedoch, bevor wir 7 befreien, müssen wir 5 auf 6 auf B platzieren.
Schritt 1 - Platz 8, auf C und 6,5,3,2,1 auf B
Die ersten sieben Züge sind:
2 auf A
1 auf A
3 oben B (oben auf 6)
1 auf C
2 auf B
1 auf B
8 auf C
23 Züge nach dem Start erhalten wir das Layout
A – 4,9
B – 6,5,3,2,1 23 Züge
C – 8,7
Schritt 2 – Platzieren Sie die 6,5,3,2,1 (5 Ringe) auf C auf 8,7 (Peg B ist frei, die 9 zu platzieren).
Das Verschieben von 5 Ringen auf einen anderen Stift erfordert 31 Züge plus einen weiteren, um Platz 9 auf B zu platzieren, also benötigen wir in diesem Schritt 31+1 =32 Züge.
Das Layout ist
A – 4
B – 9 31+1= 32 Züge
C – 8,7,6,5,3,2,1
Schritt 3 – Der Zweck ist jetzt, Peg A freizugeben, um 7 zu erhalten (sonst können wir 8 nicht auf 9 setzen). Um dies zu erreichen, müssen 6,5,3,2,1 nach B auf 9 verschoben werden.
Aber da die Züge abwechselnd Platz 6 auf B sind, müssen wir zuvor die 5 auf A und 4 auf B platzieren...
Nach 57 Zügen von Anfang an auf Schritt 2 haben wir das folgende Layout.
A – 7
B – 9,6,5,4,3,2,1 57 Züge
C – 8
Es ist offensichtlich, dass diese 57 Züge einer Logik folgen müssen. In der Tat können sie bei den folgenden Aktionen zersetzt werden:
Aktion Anzahl der Züge 4 auf B 1 3,2,1 (3 Ringe) auf Top 4 auf B 7 5 bis A 1 4,3,2,1 (4 Ringe) bis A 15 6 bis B 1 5,4,3,2,1 (5 Ringe) bis B auf 6 31 7 bis A 1 gesamt 57
Schritt 4 - bewegen 6,5.....2,1 (6 Ringe) nach A auf 7. Das braucht 63 Züge. Jetzt ist es möglich, Platz 8 auf 9 auf B, was eine zusätzliche Bewegung bedeutet.
In diesem Schritt 4 gibt es also insgesamt 63+1 = 64 Züge
Danach wird das Layout
A – 7,6,5,4,3,2,1
B – 9,8, 63+1=64 (Turm von Hanoi I Situation)
C –
Schritt 5 – Der letzte Schritt ist, 7,6 zu verschieben,... 2,1, um B an die Spitze von 9,8 zu binden.
Um 7 Ringe zu bewegen, werden 127 Züge benötigt.
Die Gesamtzüge sind also 23+32+57+64+127= 303 Züge, die minimal erforderlich sind.
- Erstes Layout (145 minimale Verschiebungen erforderlich)
(Original) 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)
von Slb
2020-02-13 16:10:02
Gefällt mir
Antworten
Eine Antwort posten
Wird übermittelt ...
Posten der Antwort ist fehlgeschlagen. Bitte noch einmal versuchen. Beenden