Как сделать ханойскую башню

Обновлено: 04.07.2024

Высоко в горах Тибета монахи перекладывают 64 золотых диска, нанизанных на 3 алмазные стержня. Когда их работа будет окончена, наступит конец света.

Есть 3 стержня. На первый надеты n дисков увеличивающегося сверху вниз диаметра. Эти диски необходимо по одному переложить с первого стержня на второй. Можно использовать все стержни, но диски большего диаметра должны всегда находиться ниже дисков меньшего диаметра (на картинку можно кликать, а также менять число дисков: и стержней: )

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

Рекурсивное решение

Пусть есть 3 башни (x, y, z) и, благодаря магическим способностям, мы умеем перекладывать n дисков с одной башни на другую. Применим эти способности, переложив n-1 дисков с x на z. Затем тривиальным образом перенесём оставшийся (самый большой) диск с x на y. Наконец, снова, применив магию, переложим n-1 дисков с z на y (поверх того, самого большого диска). Всё, задача по переносу n дисков с x на y решена, а её код на JavaScript имеет вид: Несмотря на ощущение надувательства, всё работает и вызов функции Hanoi1(3, "0", "1", "2") (башни нумеруем с нуля) приведёт к следующему результату (который стоит проверить, перекладывая диски мышкой):
.

Аналогичен алгоритм, на вход которого подаётся номер (по размеру) перкладываемого диска (их также нумеруем с нуля: d=0. n-1) и направление его сдвига s=1 (вправо) или s=-1 (влево). Сдвиг предполагается цикличным и при переносе с 0-го стрержня влево (s=-1) диск попадает на 2-й стержень, а при переносе со второго вправо (s=1) - попадает на 0-й. Пусть необходимо сдвинуть самый большой (нижний) диск (d=n-1) вправо (s=1). Для этого мы должны сдвинуть чуть меньший диск d-1 влево -s, затем переложить большой диск вправо, и затем на него положить меньший, снова сдвигая его влево (цикл через 3 тоже что 2 раза вправо): Этот, ещё более волшебный код, приводит к: , что означает: "перенести маленький диск под номером 0 вправо, затем следующий по размеру диск влево (окажется на последнем стержне), и т.д."

Разделяй и властвуй

Подсчитаем число ходов M(n,3)=M_n, которые необходимо сделать для решения задачи с n дисками и 3-мя башнями. Каждый вызов функции Hanoi1приводит к одному перекладыванию и двум выззовам с перекладыванием на единицу меньше. Поэтому справедливо рекурентное уравнение: M_n=1+2·M_n-1 с начальным условием M₁=1. Прямой подстановкой несложно проверить, что ему удовлетворяет следующее решение: M_n = 2 n - 1.

Если натренированные монахи тратят секунду на один диск, то конца света следует ждать не ранее чем через 584 миллиарда лет (M₆₄ = 2 64 - 1 = 1.8·10 19 секунд). Впрочем, когда они начали, нам неведомо.

Количество состояний системы (рассположений n дисков по t башням) вычисляется следующим образом. Первый диск может находиться на одной из t башень. Независимо от этого, второй диск, при каждой из t возможностей первого диска, также может находиться на t башнях, что даёт t·t возможностей и т.д.: N(n,t) = t n .

В таблице приведены значения функций M_n=M(n,3), N_n=N(n,3) и их отношение:

n	3	4	5	10	15	20
M_n	7	15	31	1023	32767	1048575
N_n	27	81	243	59049	14348907	3486784401
M_n/N_n	0.26	0.19	0.12	0.02	0.002	0.0003

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

Структура данных

В задачах поиска решений, часто приходится сохранять в памяти различные состояния решаемой задачи. Поэтому необходимо обеспечить максимально компактное описание состояния системы. Введём массив disks[i] размерности n, в котором будем хранить номер (начиная с 0) башни, где находится i-тый диск (также отсчет ведем с нуля): Эта функция объявляет класс Hanoi, экземпляры которого будут хранить число дисков nDisks, башен nTowers и массив disks принадлежностей каждого диска к конкретной башне. При помощи директивы prototype определим два метода класса Hanoi. Первый устанавливает диск под номерм disk на башню под номером tower, а второй выводит массив disks как строку: Теперь для 5 стержней и 3-х башен можно написать следующий код, который, при помощи оператора new, создаёт экземпляр han класса Hanoi, перемещает 0-й диск на 3-ю башню, а 4-й диск на 1-ю башню и затем результат выводится на страницу: что приведёт к появлению строки: .

Почти за всё приходится платить. Компактность представления информации замедляет доступ к ней. Например, чтобы получить номер диска, лежащего наверху башни tower, необходимо пробежаться по всем дискам: Аналогично выгдядит функция, возвращающая номер диска в стопке на башне (считая снизу от нуля):

Рисуем башни

Перейдём теперь к художествам при помощи библиотеки draw.js, которая позволяет рисовать как на канвасе, так и в создавать файлы векторной графики (svg-формат). Зададим внутри конструктора Hanoi геометрические параметры системы, добавив туда следующий код: (номер fly переносимого диска, его назначение flyDesи скорость flyV будут обсуждаться в следующем разделе). Теперь код метода рисования башен на объекте draw имеет вид: В библиотеке draw.js координаты ящиков - это их центр, а последний параметр функции box - радиус скругления углов.

В качестве теста создадим 3 башни и выведем их на html-страницу в виде svg-картинки:

Таймер

Для анимирования полёта перекладываемого диска нам потребуется 3 функции, при помощи которых диск берётся, бросается в направлении целевой башни и кладётся на неё, когда туда долетает: В этих функциях вводится переменная fly номера перекладываемого диска, его координаты, скорость, башня назначения и расстояние, которое он должен пролететь. Диск будет лететь, если в таймере вызывать функцию: Делается это следующим образом. На html странице помещается канвас: и пишется следующий скрипт:

Взаимодействие с мышкой

Для организации взаимодействия с мышкой напишем ещё одну функцию: Теперь необходимо подключть мышиное событие: Результат этих действий приведен в начале страницы.

Нерекурсивное решение

Чтобы анимировть перекладывание диска в процессе решения задачи компьютером, необходима нерекурсивная версия функций Hanoi1 или Hanoi2 Для её написания, понаблюдаем за действиями рекурсивной функции при различном числе дисков (компактная запись):

Hanoi2(2,1):
Hanoi2(3,1):
Hanoi2(4,1):
Hanoi2(5,1):

Видно, что через раз переносится самый маленький диск под номером 0 вправо (+0) для нечётного n или влево (-0) - для чётного. Несложно видеть, что после такой перестановки, существует только одна возможность переложить другой диск. Этим алгоритмом, как известно, и пользуются монахи:

Запуск скрипта (new Hanoi(4)).solveTXT(100) даёт:

Стековое решение

При помощи стека (массива "вызовов функций"), напишем ещё один нерекурсивный код, логика которого тождественна функции Hanoi1. Перед каждым рекурсивным вызовом, в стеке будем сохранять текущее состояние аргументов функции. Затем в стек запихнём рекурсивно вызываемую функцию. Кроме этого аргументов функции будем сохранять индекс pos, нумерующий "участки кода", куда необходимо вернуться по окончанию работы функции (в листинге Hanoi1 они помечены круглыми скобками): Запуск этой функции даёт результат аналогичный Hanoi1: . Нечто подобное функции Hanoi3 делает компьютер, когда запускает на выполнение рекурсивную функцию Hanoi1.

Финальный результат

Для запуска решателя следует нажать на кнопку и насладиться перемещением дисков: time = 0:0:0 moves = 0

Есть три стержня A, B, и C. На стержень A надето N дисков, наверху самый маленький, каждый следующий диск больше предыдущего, а внизу самый большой. На другие стержни дисков не надето.

Hеобходимо перенести диски со стержня A на стержень C, пользуясь стержнем B, как вспомогательным, так, чтобы диски на стержне C располагались в том же порядке, в каком они располагаются на диске A перед перемещением.

Рекурсивный метод

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

Всего получается 2 N-1 перекладываний.

Нерекурсивный метод

Стержню, на котором диски находятся в начале, дадим номер 0; стержню, на который их надо перенести - номер 2; и, соответственно, оставшемуся стержню - номер 1.

Пусть всего дисков N. Занумеруем диски в порядке увеличения радиуса числами 0,1,2. N-1.

Как известно, задача решается за 2 N-1 ходов. Занумеруем ходы числами 1,2. 2 N-1 .

Любое натуральное число i единственным образом представимо в виде i=(2t+1)*2 k , где t и k - целые (т.е. как произведение нечетного числа на некоторую степень двойки). Так вот, на i-ом ходе переносится диск номер k со стержня номер ((-1) N-k *t mod 3) на стержень номер ((-1) N-k *(t+1) mod 3).

если пpедставить что стержни, на котоpые одеваются диски, pасположены в yглах pавностоpоннего тpеyгольника, то самый маленький диск каждым нечетным ходом движется по (или пpотив, это от пеpвоначального кол-ва дисков зависит) часовой стpелки.

Все четные ходы опpеделяются однозначно. Какой диск меньше - тот и перекладывать (иначе противоречит условию). Т.к. тpогать диск 0 нельзя и класть больший на меньший тоже нельзя.

Hа каждом нечетном ходy происходит перенос наименьшего диска.
Hаименьший диск всегда переносится циклически: либо A-B-C-A-B-C-. (в слyчае четного количества дисков), либо A-C-B-A-C-B-. (в слyчае нечетного).

А посемy полyчаем алгоритм:

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

2. Смотрим номер хода: если нечетный - переносим наименьший диск в направлении, определенном в п.1. если четный - то возможный ход один единственный - берем наименьший из двyх верхних дисков и переносим его.

Можно написать немного по другому:

Для N от 1 до 2 k-1 выполнять
1. В двоичном представлении N найти самый правый ненулевой разряд. Обозначим номер этого разряда t.

2. Обозначим номер стержня, на котором находится диск t через i. Переместить диск t со стержня i на стержень (i+(-1) t ) mod 3.

Назовем стержни левым (left), средним (middle) и правым (right). Задача состоит в переносеm дисков с левого стержня на правый.

Задача может быть решена одним перемещением только для одного (m = 1) диска. В общем случае потребуется 2m-1 перемещений.

Построим рекурсивное решение задачи, состоящее из трех этапов:

a) перенести башню, состоящую из m – 1 диска, с левого стержня на средний;
b) перенести один оставшийся диск с левого стержня на правый;
c) перенести башню, состоящую из m – 1 диска, со среднего стержня на правый.

Таким образом, задача о перемещении m дисков сводится к задаче о перемещении m – 1диска. Обращаясь опять к этому же алгоритму, сведем задачу к перемещению m – 2 дисков. Продолжая этот процесс, получим, в конце концов, задачу о перемещении одного диска. Эта задача решается за один ход. Таким образом, в процессе решения возникают промежуточные задачи: переместить башню из нескольких n дисков с одного стержня на другой.

Обозначим тот стержень, с которого следует снять диски, через s1, на который надеть – через sk, а вспомогательный стержень через sw.

Оформим алгоритм решения задачи о переносе башни из n дисков с s1 на sk в виде процедуры move с 4-мя параметрами: n, s1, sw, sk; алгоритм для n = 1 выделим в отдельную процедуру step, которая перемещает один диск со стержня s1 на sk.

Недавно меня попросили решить тестовое задание: нужно было средствами 1С решить задачу с перемещением ханойской башни (и визуализировать в среде 1С). Возможно, мое решение этой задачи окажется кому-нибудь полезным.

Специальные предложения

Просмотры 1030

Загрузки 0

Рейтинг 5

Создание 04.01.22 12:00

Обновление 04.01.22 12:00

№ Публикации 1580259

Рубрики Игры

Конфигурация Конфигурации 1cv8

Операционная система Не имеет значения

Вид учета Не имеет значения

Доступ к файлу Абонемент ($m)

Код открыт Да

См. также

RoboZZle для управляемых форм

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

2 стартмани

22.12.2021 860 1 Caliban 4

Игра про крипового колобка из 80-х

Аркадный платформер в виде внешней обработки для 1С:Предприятие 8. Помоги колобку добраться до крыши общаги!

1 стартмани

16.12.2021 856 1 sa1m0nn 1

Игра "Тетрис"

Классическая игра в тетрис.

1 стартмани

12.08.2021 2231 2 van010190 0

Игра "Жизнь". Вариации на тему

Игра "Жизнь" Джона Конуэя (Conway's Game of Life). Очередная реализация с нестандартными "фишечками".

1 стартмани

11.08.2021 1598 0 tired_coder 2

Майнкрафт и 1С

Создай свой мир через 1С.

4 стартмани

16.07.2021 2251 0 SerVer1C 0

"Уголки" на 1С

Игра "Уголки" на 1С - ностальгия детства .

1 стартмани

09.06.2021 4233 6 royaljon 5

Игра "Змейка" на управляемых формах (клиент)

Пишем игру с динамическим обновлением игрового поля и управлением с клавиатуры на управляемых формах, отправляем на github.

1 стартмани

07.06.2021 2600 0 alexey_kurdyukov 0

Самые красивые шахматы для 1С на управляемых формах

Здравствуйте, представляем Вашему вниманию классическую игру – Шахматы! Написана игра средствами 1С, на управляемых формах. Программный код представляет собой с аккуратностью составленную систему, содержащую лаконичные логические приемы и описательные имена переменных, объектов и функций. Программа полностью отлажена и многократно протестирована. Оригинальный авторский дизайн фигур, иконок и кнопок приятен глазу. Игра содержит большое количество функций, настроек и режимов игры, включая сетевую игру, тренировку с ботом или игру на двоих. Не упустите возможность найти ряд технических решений, применимых для реализации различных задач, а также поиграть в вечную игру с отличным оформлением! Желающие научиться программировать на управляемых формах могут многое почерпнуть в этой конфигурации.

5 стартмани

18.02.2021 6573 14 compmir 30

Прототип игры Морской бой

Решенное тестовое задание при приеме на работу в крупный франч. Всё сделано строго по ТЗ. Обработка включена в конфигурацию, и может запускаться как внутри, так и как внешняя. Для правильной работы потребуется опубликовать веб-сервис. Использованы механизмы веб-сервисов, XDTO, запросов, управляемых форм.

Читайте также: