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

Всего на перенос потребуется 15 ходов.

Рассуждая аналогичным образом, сосчитаем число ходов, необходимых для переноса башни из пяти дисков: 15 + 1 + 15 = 2 • 15 + 1 = 31.

Для башни из 6 дисков получаем: 2-31+1 = 63 и т. д. Рассмотренный нами алгоритм решения задачи «Ханойская башня» обладает одним удивительным свойством: в ходе его выполнения для башни, состоящей из n колец, мы используем алгоритм для чуть более простой ситуации — переноса башни, состоящей из n-1 кольца. В свою очередь, в алгоритме для башни из n-1 кольца используется этот же алгоритм для n-2 колец и т. д.

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

Самое главное

1. Проведите необходимые вычисления и заполните следующую таблицу:

Вопросы и задания

2. Назовите числа: 1 048 575, 1 073 741 823, 1 099 511 627 775. Что это за числа?

3. Для того чтобы переместить башню из 64 дисков, при безошибочной работе потребуется 18 446 744 073 709 551 615 перекладываний. Сколько уйдет на это времени, если считать, что на одно перекладывание уходит одна секунда? Для выполнения вычислений используйте приложение Калькулятор.

4. Переместите башню из пяти дисков, действуя по следующим правилам: на первом, третьем и других нечетных шагах переносите самый маленький диск «по кругу» (1-2, 2-3, 3-1); на четных шагах переносите диск между теми стержнями, где нет самого маленького кольца. Что вы можете сказать об этом алгоритме?

<<< К началу