#1
5
(번역 - Microsoft)
-
- 나는 반지를 이동하기위한 기본 규칙이 잘 알려져 있다고 가정합니다.
- 링 수가 이상하면 상단 링을 원하는 링 위에 똑바로 배치하려면 1 단계만 필요합니다.
- 이 경우에도 이동하려면 두 단계가 필요합니다. 왼쪽에서 오른쪽으로 못 A, B, C를 가정해 봅시다. 예를 들어, B에서 우리는 반지 1,2,3,4가있는 더미가 있고 C에 링 5 위에 배치하려는 경우 첫 번째 단계는 1 에서 A및 2에서 C, 다음 단계는 1에서 C.가 됩니다. 총 15번의 동작으로 페그 C에 5개 이상의 1,2,3,4개의 링을 갖게 됩니다.
- 초기 레이아웃에는 작은 반지 위에 더 큰 반지가 있지만 (이 게임의 버전 I와 주요 차이점입니다) 재생을 시작할 때 하노이 1 의 탑에서와 같이 작은 반지 위에 더 큰 링을 넣을 수 없습니다.
- 나는 게임을 해결하기위한 가장 좋은 방법은 반지 9, 8, 7의 위치를 빠르게 보는 것으로 시작하는 것 같아요. 링 9가 이미 페그 의 밑에 있는지 확인하는 것이 중요합니다. 그리고 그렇지 않다면, 가장 좋은 방법은 거기에 넣어 (적은 움직임)입니다. 이 경우 종종 발생 (특히 경우 7 과 8 다른 못에) 하나는 배치 해야 7 이상 8 9에 대 한 무료 못을 가지고. 또한 우리는 6에 6을 배치해야 할 수도 있습니다, 7 이동 후 무료 못으로 이동 6 다음 6 이상 7. 결과는 1에서 7까지 더미가 될 것이며 8,9의 상단에이 7 개의 링을 배치하는 127 추가 이동의 필요성 (하노이 의 탑에서 게임을 해결하기 위한 최소한의 움직임은 : 최소 이동 = 2 ^n - 1 은 반지의 수이므로 3 개의 링이 필요하므로 3 개의 링이 필요합니다 15 ... 7 개의 반지는 127 등이 필요합니다).
- 어쨌든, 목적은, 가능한 이동의 최소한의 숫자로, 하노이 I 상황의 타워에 초기 레이아웃을 변경하는 것입니다. 즉, 실제로 게임을 완료하지 않고도 게임을 해결할 수 있는지 사전에 알 수 있습니다. 반지가 하노이 의 탑에있을 때 I 상황 (반지 1,2로 시작하는 오름차순더미 ... 하나의 못, 무료 못, 그리고 나머지 반지와 페그에, 또한 상승 순서로, 9인 페그의 기지에서 마무리), 그냥 위의 방정식에 의해 주어진 필요한 움직임에 이미 만든 움직임을 추가하고 결과는 필요한 최소한의 움직임과 같아야합니다 (내가 그 컨트롤을 할 때마다 그냥 마지막 숫자를 추가).
- 세 가지 예 (모두이 웹 사이트에서).
- 초기 레이아웃(145개의 최소한의 이동 필요)
페그 A - 1,8,2,9
페그 B - 7,3
페그 C - 6,5,4
1 단계 - 가장 좋은 전략은 페그 B에 7의 상단에 9와 6을 배치하는 것입니다.
첫 번째 움직임은 : A에 9의 상단에 링 3, 다음 4 의 상단에 7 B에 ...
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 단계가 필요합니다). 그래서 A에이 여섯 반지를 배치하려면 우리는이 경우 C, 다른 페그에 1을 배치하는 첫 번째 움직임이 필요합니다.
우리가 이미 알다시피, 다른 못 (페그 A)에 6 링을 이동하려면 우리는 63 움직임이 필요합니다. 이러한 이동 후 배치 하는 추가 1 7, 지금 무료, 위에 9,8.
따라서 이 단계 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단계 - 우리의 목표는 B에 8위에 C에 9, 7을 배치하는 것입니다. 이를 위해서는 먼저 6,4위를 A에서 9위로 이동하여 C를 무료로 받아 9를 받아야 합니다.
처음 5번의 움직임은 4위, A에서 9위, 4대 6,1대 4, 페그 B에서 7-8로 1위를 차지했습니다.
20 이동 후 레이아웃은
A – 5,3
B – 8,7,6,4,2,1 이동
C – 9
단계 2 단계 6 이상 9 페그 C에. 이를 위해서는 페그 A에서 5,4,3,2,1로 이 단계를 마무리하는 A에서 5 위에 4가 필요합니다. 이것은 13 개의 동작으로 수행되며 레이아웃은
A – 5,4,3,2,1
B – 8, 7 13 이동
C - 9,6
3단계 – 5,4...,1(5링)을 페그 C에서 6위로 이동합니다. 이는 페그 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의 상단에 (6 반지) 63 이동하고 다른 하나는 C. 단계 4 63 + 1 = 64 및 레이아웃에 9의 상단에 8을 넣어 이동
A – 7,6,5,4,3,2,1
B - 63+1 = 64 이동
C - 9,8
5단계
하노이 타워 상황. 마지막 단계는 페그 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
이 예제는 이전 두 예제보다 약간 어렵습니다.
9는 상단에 세 개의 반지와 A에 붙어 (7,5,8). 또한 B와 C는 무료 못이 아닙니다. 그것은 분명 8,7 무료 못에 그렇지 않으면 우리는 에 대한 무료 못이 없을 것입니다 9.
이 작업을 수행하는 가장 좋은 방법은 페그 C에 8,7을 배치하고 C에 8,7의 상단에 6을 이동하는 것입니다.
이 작업이 끝나면 페그 B는 9를 무료로 받을 수 있습니다. 그러나 7을 해제하기 전에 B에 6 위에 5를 배치해야합니다.
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,2,1 (5 링)을 8,7의 상단에 C에 놓습니다 (페그 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을 배치 하는 교대로 우리는 이전에 B에 A에 5와 4를 배치 해야...
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 링) 15 6 ~ B 1 5,4,3,2,1 (5 링) 6 의 상단에 B 31 7대 A 1 총 57
4단계 - 6,5....2,1(6링)을 7번 의 상단에 A로 이동합니다. 이렇게 하려면 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 페그 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
좋아요
댓글