#1
5
(Перевод: Microsoft)
-
- Я полагаю, основные правила для перемещения кольца хорошо известны.
- Если количество колец странно вам нужно только 1 шаг, чтобы поместить верхнее кольцо прямо на верхней части кольца вы хотите.
- Если это даже, есть необходимость в двух шагах, чтобы сделать ход. Допустим, колышки A,B и C слева направо. Если, например, на B у нас есть куча с кольцами 1,2,3,4 и хотите разместить их над кольцом 5 на C , первый шаг будет 1 к A и 2 к C, а затем, 1 к C. .and в общей сложности 15 ходов мы будем иметь 1,2,3,4 кольца более 5 на колышек C.
- В первоначальном макете есть большие кольца поверх небольших колец (это главное отличие от версии I этой игры), но когда вы начинаете играть вы не можете поставить большее кольцо на вершине меньшего, как в башне Ханое I.
- Я думаю, что лучший подход к решению игры, начиная с быстрого взгляда на позиции кольца 9, 8 и 7. Важно, чтобы увидеть, если кольцо 9 уже на базе колышек. А если это не так, то, что лучший способ (менее движется), чтобы положить его там. В этом случае это часто происходит (особенно, если 7 и 8 находятся на разных колышек), что нужно разместить 7 более 8 иметь свободный колышек для 9. Кроме того, мы, возможно, придется разместить 6 на 9, 7 перехода к свободной колышек после перемещения 6, а затем 6 более 7 . Результатом будет куча от 1 до 7 и необходимость 127 дополнительных ходов, чтобы разместить эти 7 колец на вершине 8,9 (минимальное количество ходов, чтобы решить игру в башне Ханое I ситуации: минимальные ходы - 2 'n - 1, где это количество колец так, 3 кольца потребуется 7 ходов, 4 кольца потребуется 15... 7 колец потребуется 127 и так далее).
- В любом случае, цель состоит в том, с минимальным количеством ходов возможно, чтобы изменить первоначальный макет на башню Ханой I ситуации. Это означает, что вы всегда будете знать заранее, если игра может быть решена без того, чтобы на самом деле закончить его. Когда кольца находятся в башне Ханое я ситуации (куча в порядке возрастания, начиная с кольцами 1,2 ... на одной колышек, свободный колышек, и колышек с остальными кольцами, а также в порядке подъема, заканчивая на базе колышек, где 9), просто добавить движется уже сделал необходимые шаги, данные выше уравнения и результат должен быть равен минимальным движется необходимо (всякий раз, когда я делаю этот контроль просто добавить последнюю цифру).
- Три примера (все с этого сайта).
- Начальная компоновка (необходимо 145 минимальных ходов)
Пег А - 1,8,2,9
Пег Б - 7,3
Пег C - 6,5,4
Шаг 1 - Лучшая стратегия заключается в том, чтобы разместить 9 на базе колышек C и 6 на вершине 7 на колышек B.
Первый ход: кольцо 3 на вершине 9 на A, затем 4 на вершине 7 на B...
После 18 ходов от первоначального макета мы получаем:
Пег А - 1
Пег B - 7,6,5,4,3,2 18 ходов
Пег C - 9,8
Шаг 2 - Если мы посмотрим на этот макет внимательно, мы заметим, это эквивалентно 6 колец на вершине 7 на B, при условии, что следующий шаг заключается в том, чтобы поместить кольцо 1 на вершине 8 на C. Мы говорим о 6 кольцах (6,5 ... 1, то есть, даже на колышек B и 2 шаги не требуется). Таким образом, чтобы поместить эти шесть колец на A, нам нужен первый шаг, чтобы поместить 1 на другой колышек, в этом случае C.
Как мы уже знаем, для перемещения 6 колец на другую колышек (пег А) нам нужно 63 хода. После этих ходов есть еще один, чтобы разместить 7, теперь бесплатно, на вершине 9,8.
Таким образом, в этом шаге 2 ходы будут 63 и 1 "64 и макет мы получаем это:
A - 6,5,4,3,2,1
B - 63'1 и 64 хода
C - 9,8,7
До сих пор у нас есть 18 ходов на шаг 1 плюс 64 на шаг 2
Шаг 3 - Выше макет соответствует тому, что я называю Башня Ханое I ситуации.
Чтобы закончить игру, нам нужно переместить 6 колец (6,5,... 1) на колышек А к верхней части 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 находятся на различных колышек, мы должны поместить 7 на вершине 8 на B.
Шаг 1 - Наша цель состоит в том, чтобы разместить 9 на C и 7 на вершине 8 на B. Для достижения этой цели мы сначала должны переместить 6,4 в верхней части 9 на свободных C, чтобы получить 9.
Первые пять ходов 4 на вершине 7,6 на вершине 9 на , 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 на отделку этот шаг 2 с 5,4,3,2,1 на колышек . Это делается с 13 ходов и макет
A - 5,4,3,2,1
Б - 8, 7 13 ходов
C - 9,6
Шаг 3 - Перемещение 5,4...,1 (5 колец) в верхней части 6 на колышек C. Это соответствует 31 ход плюс 1 к месту 7 на колышек А. Таким образом, количество ходов в шаге 3 31'1'32 и макет будет
A - 7
B - 8 32 хода
C - 9,6,5,4,3,2,1
Шаг 4 - Перемещение 6,5,... 1 к верхней части 7 на колышек А потребует (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
У нас есть Башня Ханое I ситуации. Заключительным шагом является перемещение 7 колец из колышка А
в верхней части 9,8 на колышек C. Это означает 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 к вершине 8,7 на C.
После этого Peg B будет свободно получать 9. Обратите внимание, однако, перед освобождением 7 мы должны разместить 5 на вершине 6 на B.
Шаг 1 - Место 8, на C и 6,5,3,2,1 на B
Первые семь ходов:
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 колец) на C поверх 8,7 (пег 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 - Цель сейчас состоит в том, чтобы освободить колышек, чтобы получить 7 (в противном случае мы не можем разместить 8 на вершине 9). Для достижения этой цели необходимо переместить 6,5,3,2,1 на B на вершине 9.
Но, как движется чередуются с местом 6 на B мы ранее должны разместить 5 на A и 4 на B ...
После 57 ходов с самого начала на шаг 2 мы будем иметь следующий макет.
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 до А 1 4,3,2,1 (4 кольца) до А 15 от 6 до B 1 от 5,4,3,2,1 (5 колец) до B поверх 6 31 от 7 до А 1 Общая 57
Шаг 4 - переместить 6,5.....2,1 (6 колец) на A поверх 7. Для этого нужно 63 хода. Теперь можно разместить 8 на вершине 9 на B, что означает дополнительный ход.
Таким образом, в этом шаге 4 есть в общей сложности 63 '1 и 64 ходов
После этого макет
A - 7,6,5,4,3,2,1
B - 9,8, 63'1'64 (Башня Ханое I ситуации)
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
Нравится
Ответить