Головоломка Ханойская башня, рекурсивный алгоритм решения. Scratch 3.

Сегодня мы доработаем проект с головоломкой "Ханойская башня", рассмотренный ранее. Мы сделаем так, чтобы можно было управлять перемещением дисков при помощи мыши. Кроме того, наша программа будет способна продемонстрировать оптимальное решение этой головоломки для башни из произвольного количества дисков.

Описание алгоритма.

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

Собираем программу

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

• Откройте свой собственный проект, созданный на прошлом занятии.

• Создайте две глобальные переменные с именами "ход" и "размер_башни".

• Создайте блок "построить_башню_высотой" и отредактируйте основной программный скрипт по рисунку 1.

Рис. 1 Редактируем основной программный скрипт

• Добавьте в определение блока "переместить_верхний" команду "изменить ход на 1".

Рис. 2 Команда "изменить ход на 1"

• Запустите проект в режиме "Турбо" и убедитесь, что он работает как прежде. Но теперь удобнее будет менять желаемую высоту башни.

• Создайте блок "переместить_башню_из_элементов_с_на_с_помощью" по рисунку 3. Определение блока имеет рекурсивный характер.

Рис. 3 Определение блока перемещения башни

• Отредактируйте основной программный скрипт (рис. 4)

Рис. 4 Редактируем основной программный скрипт

• Запустите программу и понаблюдайте за процессом решения головоломки. Можно задавать ту или иную высоту башни (рис. 5).

Рис. 5 Проект в работе

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

• Замените заголовок скрипта с рисунка 6

Рис.6

Теперь следует реализовать управление перемещением блоков при помощи мыши.

• Создайте три глобальных переменных с именами "кнопка_1", "кнопка_2" и "кнопка_3".

• Поменяйте режим отображения содержимого списков и переменных на сцене. Уберите галочки у всех списков и переменных, кроме переменной "ход".

• Добавьте в проект три новых спрайта из библиотеки — "Glow-1", "Glow-2" и "Glow- 3". Для удобства желательно отредактировать костюмы спрайтов, чтобы они занимали большую площадь (примерно так, как на рисунке 7).

Рис. 7 Спрайты кнопок

• Дорисуйте костюмы спрайтов. Удобно будет копировать выделенный объект и затем вставлять его в костюм другого спрайта. Также понадобится кнопка "переместить на задний план".

• Создайте скрипт спрайта "Glow-1" (рис. 8).

Рис. 8 Скрипт спрайта "Glow-1"

• Создайте скрипты спрайтов "Glow-2" и "Glow-3" с нуля либо путём дублирования и редактирования (рис. 8 и 9).

Рис. 9 Скрипт спрайта "Glow-2"

Рис. 10 Скрипт спрайта "Glow-3"

• Выберите снова спрайт "Башня".

• Создайте блок "жест_из" и отредактируйте основной программный скрипт по рисунку 11.

Рис. 11 Редактируем основной скрипт

• Запустите программу и проверьте работу проекта. Для перемещения диска следует провести при нажатой кнопке мыши от одной цифры к другой.

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

Дополнительные задания

• Ознакомьтесь с содержимым статей Википедии о различных головоломках.

http://ru.wikipedia.org/wiki/Головоломка
http://ru.wikipedia.org/wiki/Механическая_головоломка
http://ru.wikipedia.org/wiki/Занимательная_математика
Какие из головоломок, о которых вы узнали, имеют рекурсивное решение?

Попытайтесь его описать словами.

Какие из головоломок вам интересно было бы реализовать в виде компьютерной игры?