Масштабирование итеративного, побитового алгоритма для решения Ханойских башен с использованием X дисков и Y башен

Question

Мне нравится алгоритм, упомянутый в этом вопросе: «Как это работает? Weird Towers of Hanoi Solution» Как это работает? Странная Башня Ханоя Решение

Есть ли способ масштабирования этого нерекурсивного решения Towers of Hanoi для использования X-дисков и Y-башен, причем башни представлены в виде стеков?

Answer 1

Итеративное решение для Ханойской башни с Y = 3 Towers и X дисками, которое можно найти в Wikipedia :

Для четного количества дисков:

• сделать законный ход между колышками A и B
• сделать законный ход между колышками A и C
• сделать законный ход между колышками B и C повторите до завершения

Для нечетного количества дисков:

• сделать законный ход между колышками A и C
• сделать законный ход между колышками A и B
• сделать законный ход между колышками B и C повторите до завершения

В каждом случае выполняется 2 ^ X-1 ходов. Число ходов по этому алгоритму составляет всего , минимально для Y = 3 .

Это решение игнорирует другие башни, поэтому оно работает с любым Y> = 3 и любым X.

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

Цитируется из Википедия .