Ханойская башня, или Один замечательный алгоритм

Одна легенда гласит: В джунглях находится храм бога Брахмы. В нем бронзовая плита с тремя алмазными стержнями. На один из стержней бог при сотворении мира нанизал 64 диска из золота. Они образуют пирамиду. Это башня Брамы, жрецы, работая день и ночь переносят с одного стержня диски на другой следуя некоторым законам Брамы. Когда все 64 диска будут перенесены с одного стержня на другой наступит конец света!

Законы Брамы: 1. Диски можно перемещать с одного стержня на другой только по одному 2. Нельзя класть больший диск на меньший 3. Нельзя откладывать диски в сторону, при переносе дисков с одного на другой можно использовать промежуточный стержень, на котором диски должны находиться тоже только в виде пирамиды, сужающейся кверху

Эта древняя легенда положена в основу задачи о Ханойской башне: переместить n дисков со стержня 1 на стержень 3, используя промежуточный стержень 2 и соблюдая законы Брахмы.

Для переноса башни из 1 диска, нужно 1 ход: 1-3 Для переноса 2 дисков, 3 хода: 1-2; 1-3; 2-3 Для переноса башни из 3 дисков нужно 7 ходов: 1-3;1-2;3-2;1-3;2-1;2-3;1-3 и т.д.

Алгоритм для решения задачи «Ханойская башня» имеет удивительное свойство: входе его выполнения для башни, состоящей из n колец, используется алгоритм для более простой ситуации: переноса башни, состоящей из n-1 кольца, в этом случае используется тот же алгоритм для n - колец и т.д.

Прием, когда некоторый процесс описывается через самого себя, называют рекурсией. Алгоритм решения задачи «Ханойская башня» - пример рекурсивного алгоритма

КОНЕЦ