Занимательный компьютер

«Инь» и «ян»: рекурсия и итерация, «Ханойская башня» и «Китайские кольца»

А. К. ДЬЮДНИ

ХОРОШИЕ головоломки вводят нас в «царство абстрактной мысли, населенное математиками и другими теоретиками». Лучшие головоломки воплощают в себе интересные темы, которые, конечно, намного важнее самих головоломок.

Две классические головоломки — «Ханойская башня» и «Китайские кольца» — представляют две пары взаимно противоположных понятий: «рекурсия» — «итерация» и «единство» — «многообразие». Если не задумываться над такими серьезными проблемами, то головоломки — хорошее раз влечение. И хотя подчас они обескураживают новичка, каждый испытывает волнующее чувство удовлетворения, все глубже погружаясь в царство абстрактной мысли.

Задача «Ханойская башня» заключается в перемещении дисков, нанизанных на вертикальный стержень, с помощью двух других стержней (см. рисунок внизу). В исходном положении на один из стержней нанизано некоторое число дисков различного размера, так что наименьший диск находится сверху. Диски можно перемещать согласно следующим простым правилам:

1.  Перекладывать диски со стержня на стержень можно только по одному.

2.  Нельзя класть диск большего размера на диск меньшего размера.

Сначала нужно переложить наименьший диск, так как в исходном положении доступен только он. Затем для наименьшего диска возможны два перемещения (оба бессмысленные) и одно перемещение для диска следующего по величине размера. Его можно переложить на пустой стержень, потому что на диск наименьшего размера его класть нельзя (правило 2). На третьем шаге выбрать правильный вариант перемещения уже труднее: следует-ли второй диск вернуть на исходный стержень или нужно снова переместить

первый диск, а если так, то на какой стержень?

 

0 Коментариев

Вы можете быть первым =)

Оставить коментарий