Решение "Ханойская башня" Когда все диски не в

Question

Как вы знаете, есть несколько способов решить Ханойскую башню, но они требуют, чтобы все диски были в одной башне в начале.

Теперь я хочу знать, есть ли способ ее решить, гдедиски уже случайно распределены между вышками при запуске.

Answer 1

Да, это все еще разрешимо (при условии, что нет больших дисков поверх меньших дисков). Например:

        1
  4     2
  6     5     3
  -------------

Найдите самый большой непрерывный стек, содержащий 1. Здесь это {1,2}. Переместите этот стек на следующий по величине диск, игнорируя все остальные. Для этого шага вы можете использовать стандартный алгоритм Ханойской башни.

              1
  4           2
  6     5     3
  -------------

Повторите шаги выше. Следующий непрерывный стек, содержащий 1, теперь {1,2,3}. Переместить его на 4

  1
  2
  3           
  4           
  6     5  
  -------------

То же самое - переместить {1,2,3,4} на 5.

        1
        2
        3     
        4     
  6     5    
  -------------

Переместитесь {1,2,3,4,5} на 6 сейчас, и все готово. Если вам нужно переместить весь стек в определенный колышек, используйте стандартное решение еще раз.

Answer 2

Ваш вопрос разрушил мою производительность!

Я просто потратил свое драгоценное время, пытаясь ответить на него, и вот результат:

Сначала вы должны рассчитать место, куда хочет пойти каждый дискот самого большого до самого маленького.Есть 3 простых правила:

1. Самый большой диск хочет идти вправо.
2. Если диск чуть большего размера перемещается, диск хочет уйти с дороги"(если N+1 хочет перейти от LEFT к MIDDLE, то N хочет перейти к RIGHT).
3. Если диск большего размера не перемещается, диск хочетчтобы перейти в это же место (если N+1 остается в RIGHT, N хочет перейти в RIGHT).

Затем переместится в нужное место на самый маленький дисккоторый не хочет оставаться на своей привязке .( edit: альтернативно, вы можете переместить первый диск, с которым вы столкнулись, который хочет выполнить законное перемещение, но это подразумевает, что ваш код имеет представление о том, что является допустимым перемещением )

Повторять дорешено.

Пример

Давайте рассмотрим пример Джастина.

Начальная башня

| | |
| | |
| | |
| 1 |
4 2 |
6 5 3

• 6 хочу перейти от LEFTRIGHT (правило 1).
• 5 хотите перейти от CENTER до CENTER (правило 2).
• 4 хотите перейти от LEFTдо CENTER (правило 3).
• 3 хотите перейти от RIGHT до RIGHT (правило 2).
• 2 хотите перейти от CENTERна RIGHT (правило 3).
• 1 хотите перейти с CENTER на LEFT (правило 2).

Первым шагом должно быть размещение диска1 на левом колышке (самый маленький диск, который не хочет оставаться на месте).

Next

Следующие шаги будут выглядеть следующим образом:

| | |
| | |
| | |
1 | |
4 2 |
6 5 3

| | |
| | |
| | |
1 | |
4 | 2
6 5 3

| | |
| | |
| | |
| | 1
4 | 2
6 5 3

| | |
| | |
| | |
| | 1
| 4 2
6 5 3

| | |
| | |
| | |
| 1 |
| 4 2
6 5 3

| | |
| | |
| | |
| 1 |
2 4 |
6 5 3

etc.

// TODO : commenting

IРеализованы эти правила, они работают для любой начальной башни (включая обычную все-левую башню).Кроме того, они всегда выбирают кратчайший путь.

YAY!Безрекурсный способ разгадать Ханойскую башню!

Answer 3

Решение для любого юридического соглашения следует той же схеме. В решении есть только два вида шагов:

• Переместить данный диск в привязку
• Переместить данный диск и все, что меньше его, в привязку

Чтобы переместить диск в привязку, либо диск уже находится в привязке, и все готово, или диск не находится в привязке, и есть только один способ выполнить этот шаг:

• Переместить все меньшие диски на третий оставшийся колышек
• Переносить данный диск из текущей привязки в целевую привязку

Чтобы переместить данный диск и все меньшие диски к определенной колышке, единственный способ достичь этой цели - выполнить оба следующих шага в порядке

• Переместить данный диск в целевой колышек
• Переместить все меньшие диски на целевой колышек

Answer 4

Я тоже не эксперт, но смотрю на эту проблему, рассматривая три стека A B и C и в качестве предпосылки, что 6 дисков должны финишировать в стеке C, как и большинство обычных башен Ханоя, решили эту проблему с 43 движениями. Я не знаю, является ли это оптимальным решением, но есть очень интересный сайт, который можно увидеть здесь