Этот блог использует графическую форму для имитации процесса перемещения диска башни Ханоя и имеет полную реализацию кода. Из-за моих плохих знаний, неизбежно, что будут неправильные вещи. Я действительно надеюсь, что друзья, которые любят программирование и алгоритмы, выскажут ваши ценные мнения.
оглавление
1. Что такое Ханойская башня
Ханойская Башня: проблема Ханойской Башни (также известной как Ханойская Башня) — образовательная игрушка, происходящая из древней легенды в Индии. Когда Брахма сотворил мир, он создал три алмазных столба, на одном из которых были сложены 64 золотых диска по порядку снизу вверх. Брахма приказал Брамину переместить диск на другой столбец в порядке размера снизу. И оговаривают,Невозможно увеличить диск на маленьком диске, только один диск может быть перемещен между тремя опорами одновременно。
2. Перемещение процесса Ханойской башни
Ханойская башня Анимация: демонстрирует процесс движения диска
Python #15 Рекурсия: ХАНОЙСКИЕ БАШНИ, ЧИСЛА ФИБОНАЧЧИ, ПЕРЕВОД ЧИСЕЛ В ДВОИЧНУЮ СИСТЕМУ СЧИСЛЕНИЯ
(эта анимация поступает из сети)
Ниже показан процесс перемещения каждой пластины в трех случаях (n представляет количество дисков):
В-третьих, идея алгоритма Ханоты
Когда n равно 1, переместите диск из A в C напрямую;
Переместите (n-1) пластины выше столба A от A до B;
Переместите n-ую пластину над колонной A от A до C;
Переместите (n-1) пластин в столбце B первого шага из B в C
В реализации алгоритма мы используем идею рекурсии. Для имитации процесса движения и общего количества движений.
1. Пример кода
Результаты выполнения кода:
2. Расширенные проблемы
Если для перемещения диска требуется 1 секунда, сколько времени займет ожидание восстановления всех 64 дисков?
Когда используется диск, мощность 2 уменьшается на 1.
Когда два диска, мощность 2 уменьшается на 1
При наличии 3 дисков мощность 2 уменьшается на 1
При наличии 4 дисков мощность 2 уменьшается на 1
…
Когда n дисков, мощность 2 уменьшается на 1
Когда n = 64, это (от 2 до 64 степени минус 1) раз.
Результаты выполнения кода:
Для перемещения всех дисков потребуется около 584,9 миллиардов лет. Какое ужасное число!
Источник russianblogs.com