Решаемая башня Ханое II

1. • Я полагаю, основные правила для перемещения кольца хорошо известны.
     
   • Если количество колец странно вам нужно только 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), просто добавить движется уже сделал необходимые шаги, данные выше уравнения и результат должен быть равен минимальным движется необходимо (всякий раз, когда я делаю этот контроль просто добавить последнюю цифру).
     
2. Три примера (все с этого сайта).
   1. Начальная компоновка (необходимо 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, что является минимальными ходами, необходимыми.
      
      
   2. Первоначальная компоновка (необходимо 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 минимальных ходов.
      
      
   3. Первоначальная компоновка (необходимо 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 ходов минимальные ходы, необходимые

Как вы размещали на форумах вложенные списки, таблицы и подчеркивания?