Мне пришла в голову поистине дьявольская мысль: эти прекрасные монахи желали конца света, чтобы как можно скорее достичь вечного счастья, вот уж я его им обеспечу, В корпус компьютера я добавил выдвижной ящик, который окрестил «концом света». В нем были под видом блока питания толстые цилиндры, на корпусах которых была маркировка конденсаторов, но в которых находились пластиковые бомбы. Маленькое изменение программы должно было вызвать взрыв сразу же после того, как наименьший диск покидал свой стержень и перед тем, как он достигал места своего назначения. Таким образом, игра никогда не должна была кончиться. Что до монахов, то они будут с восторгом представлять себе конец света в тот момент, когда завершится игра. В тот момент чудовищность моего поступка меня не шокировала. Наоборот, я был в восторге: монахи будут счастливы, а я уберегу весь мир от конца. Я дошел до того, что смотрел на себя как на благодетеля человечества. Конечно, я брал на себя риск. Программу, без сомнения, нужно было испытать. Но, как я вам уже говорил, я прошел хорошую школу — Вашу школу — и я программировал правильно.

Когда все было закончено, я отправился вручить свое произведение сияющим монахам. Она была испытана на игре в 20 дисков. Затем аппарат был пущен в работу для игры с 50 дисками и 4 стержнями. Тут я попросил у монахов разрешения удалиться: ведь мне хотелось бы привести свои дела в порядок в то небольшое время, которое осталось нам жить, что они очень хорошо понимали. Я вое Братался с полными пригоршнями золота.

Через некоторое время сообщили, что ужасный взрыв неизвестного происхождения разрушил монастырь в Индии. В живых не осталось никого. Моя программа была правильной…

Уже позже меня стали одолевать сомнения. Не были ли монахи правы? Не я ли тот, кто помешал воле богов? Не воспрепятствовал ли я выполнению работы, которая была доверена людям? Не должен ли я сконструировать игру в 50 дисков, и не следует ли ее разыграть, чтобы искупить свою вину?

С этих пор я живу в ужасе. Если я ничего не делаю, я несу на себе груз того, что я препятствую воле богов. Если я сделаю игру, что для меня не составляет никакого труда, то именно я и приведу мир к гибели… Я никому не могу довериться. Я умоляю вас, помогите мне…»

Я не стал вмешиваться. Душа Паскаля Младшего не могла сопротивляться этому удару. Он впал в безумие и немного спустя умер…

Игра 31. Рекурсивная форма.

Письмо Паскаля Младшего ставит много задач по программированию. Я не осмеливаюсь предложить вам написать рекурсивную процедуру, которая перечисляет последовательность движений дисков в игре с тремя стержнями, помеченными номерами 0, 1 и 2 (например, в форме последовательности строк ДИСК 2 ИДЕТ С 1 НА 0, дающих номер перемещаемого диска, если наименьший диск имеет номер 1, номер стержня, с которого диск снимается, и номер стержня, на котором этот диск оказывается).

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

Можете ли вы вычислить число f(n) ходов, необходимое для проведения партии в игре с n дисками? Сколько веков потребуется для проведения игры в 50 дисков, если каждый ход делается за секунду?

Я использовал игру из дерева, в которой диски были обтесаны из двух разных пород дерева, поочередно светлых и темных. Проводя игру, можно убедиться, что два диска одного и того же цвета никогда не оказываются друг на друге. Сумеете ли вы показать это с помощью рассуждения, основанного на рекурсивной процедуре? Заметьте, что это сводится к вопросу четности. Если диски занумерованы так, как это было описано выше, то диски с номерами одинаковой четности никогда не попадают друг на друга.

* Игра 32. Рисунок игры.

Напишите простую рекурсивную процедуру, наиболее образно дающую возможность увидеть движение дисков. Очень общий способ состоит в том, чтобы изобразить три стержня в виде трех строк, на которых последовательно поставлены номера дисков. Таким образом, рис. 27 представляет начальное состояние и промежуточное состояние игры с 5 дисками.

Внимание: ваша программа работает слишком быстро, и вы не видите перемещений. Вставьте цикл ожидания, чтобы замедлить игру…

Более хитрый способ представляет стержни вертикально либо как последовательность номеров, либо — что еще лучше — если у вас есть графическая система, стилизованным образом, как на рис. 26. Это труднее…

? Игра 33. Итеративная стратегия.

Таких стратегий много. Сумеете ли вы предложить такую, которая позволила бы играть по ходу в. секунду, как у монахов…

??? Игра 34. Игра с 4 стержнями.

Составьте рекурсивную программу для игры с 4 стержнями, не занимаясь представлением дисков на экране каким-либо хитрым образом. Вам и бее этого будет достаточно работы. Даже если ваш компьютер не предоставляет вам возможности вычислять рекурсивные процедуры, это поможет вам ясно увидеть задачу и найти стратегию.

Найдите способ действовать, минимизируя число ходов, и найдите их необходимое число для малых значений n. Из письма Паскаля Младшего неясно, сколько времени нужно — если каждый ход совершается за секунду — для завершения игры с 4 стержнями и 50 дисками. Вычислите его.

??** Игра 35. Составьте итеративную программу для игры с 4 стержнями.

Если теперь добавить пятый стержень, то нужно все начинать сначала, или результаты, полученные для 4 стержней, допускают немедленную экстраполяцию на случай 5 стержней?