|
Согласно легенде, у жрецов храма Брахмы в горах Тибета есть медная платформа с тремя алмазными стержнями A, B и C. На одном стержне А нанизано 64 золотых диска, каждый из которых немного меньше того, что под ним. Конец света наступит, когда жрецы переместят диски со стержня А на стержень С. Задача имеет следующие условия:
• за один раз можно перемещать только один диск,
• больший диск нельзя класть на меньший,
• снятый диск нельзя отложить, его необходимо сразу же надеть на другой стержень.
Несомненно жрецы все еще работают, т.к. задача включает в себя 264 – 1 ходов. Если тратить по одной секунде на ход, то потребуется примерно 500 миллиардов лет.
Решение данной задачи носит рекурсивный характер. Задача разбивается на последовательность подзадач одного и того же типа, но меньшей размерности. Условием завершения является выполнение простой задачи перемещения одного диска.
Сформулируем алгоритм решения данной задачи для N дисков. Обозначим стержни: начальный (start), промежуточный (temp), конечный или целевой (destination). На начальный стержень нанизано N дисков в порядке возрастания размера, т.е. самый большой диск лежит внизу. Цель задачи – переместить все N дисков с начального стержня на конечный, следуя определенным выше условиям, и распечатать перечень ходов. Предполагается, что промежуточный стержень будет использоваться для временного хранения дисков.
Если N = 1, выполняется условие завершения (базисное условие рекурсивного алгоритма), которое может быть обработано путем перемещения единственного диска с начального стержня на конечный и распечатки соответствующего хода.
Для N > 1 выполняется трехшаговый процесс перемещения N дисков с начального стержня на конечный, причем стержень А является начальным (A – start), стержень В – промежуточным (B – temp), стержень С – конечным (C – dest).
На первом шаге алгоритма перемещаются N – 1 дисков с начального стержня на промежуточный с использованием конечного стержня для временного хранения. При этом стержень А выполняет роль начального (A – start), стержень В выполняет роль конечного (B – dest). Конечный стержень С используется как промежуточный (C – temp).
На втором шаге самый большой диск просто перемещается с начального стержня на конечный: start -> dest.
На третьем шаге N – 1 дисков перемещаются со среднего стержня на конечный с использованием начального стержня для временного хранения. При этом стержень B выполняет роль начального (B – start), стержень C выполняет роль конечного (C – dest). Начальный стержень А используется как промежуточный (A – temp).
|
