Урок по информатике 6 класс

Задача о Ханойских башнях является классической алгоритмической задачей. Формулируется она следующим образом. На одном из трех алмазных шпилей надето 64 круглых золотых диска. Диски имеют разные радиусы и расположены на шпиле в порядке убывания радиусов от основания к вершине. В одном из буддийских монастырей монахи уже тысячу лет занимаются перекладыванием колец. Они располагают тремя пирамидами, на которых надеты кольца разных размеров. Монахи должны переложить все кольца с первой пирамиды на вторую, выполняя единственное условие кольцо нельзя положить на кольцо меньшего размера. При перекладывании можно использовать все три пирамиды. Монахи перекладывают одно кольцо за одну секунду. Как только они закончат свою работу, наступит конец света.

Эту известную игру придумал французский математик Эдуард Люка, в 1883 году её продавали как забавную игрушку. Первоначально она называлась «Профессор Клаус (Claus) из Коллеж Ли-Су-Стьян (Li-Sou- Stian)» но вскоре обнаружилось, что таинственный профессор из несуществующего колледжа не более чем анаграмма фамилии изобретателя игры профессора Люка (Lucas) из коллежа Сен-Луи (Saint Louis).

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

1. Разборка двухэтажной башни: первый диск снимается с вершины и переносится на требуемый стержень. 2. Построение основания двухэтажной башни: второй диск переносится на соответствующий стержень. 3. Завершение строительства двухэтажной башни: первый диск переносится на второй диск. 4. Укладка нового фундамента: более крупный диск перекладывается на освободившееся место, или переносится диск, ранее находившийся под первым диском