BASIC-программа «Ханойские башни»
Суть головоломки. Имеется три стержня, на первый из которых (у нас в программе на рис. 6.14 он маркирован как A) нанизаны диски на манер детской пирамидки: самый большой диск внизу – самый маленький наверху. Предлагается переложить эти диски на второй стержень (C), беря их по одному и не кладя большой диск на маленький. Для временного складирования разрешается использовать третий диск (B). Программе на рис. 6.14 достаточно сообщить только число дисков в пирамиде N. После запуска программа будет возвращать порядок перекладки дисков:
N=2: A-B, A-C и B-C (три хода)
N=3: A-C, A-B, C-B, A-С, В-A, B-C и, наконец, A-C (семь ходов)
N=4: …(15 ходов) и т.д.
Число перестановок в общем случае равно 2N-1. Задача с N дисками легко сводится к задаче с N-1 дисками, а задача с N-1 дисками легко сводится к задаче с N-2 дисками и т.д. до задачи с двумя дисками, которая решается просто – A-C (см. на рис. 6.14 фрагмент программы If N = 1 Then Print X; "-"; Z). Отсюда и рекурсия в программе на рис 6.14.
Задание читателям[29]
– переписать BASIC-программу на рис. 6.14 для Mathcad. Подводный камень: BASIC-программа оператором Print выдает результат из подпрограммы. В языке Mathcad это сделать невозможно – там допустимо сначала полностью заполнить матрицу, и только потом вывести ее на дисплей.
По легенде тибетские монахи уже несколько тысячелетий перекладывают 64 золотых диска, нанизывая их на алмазные стержни. Когда головоломка будет решена и на стержне C окажутся все диски, наступит конец света. Спасает нас лишь то, что при 64 дисках для решения головоломки потребуется:
Это без учета ложных ходов и времени, необходимого на ручной или компьютерный расчет порядка перестановки дисков.
