13
ОСНОВЫ АЛГОРИТМОВ И СТРУКТУР ДАННЫХ
3.3. Задача о Ханойской башне
Пример
.
Имеется три основания (фундамента)
А
,
В
,
С
. На основании
А
в порядке
убывания в диаметре лежат 64 кольца. Требуется переложить кольца на
основание
В
, пользуясь вспомогательным
С
. Причем за раз перекладывается
только одно кольцо и никогда большее кольцо не может оказаться на меньшем.
Рассмотрим решения для случая из четырёх колец.
1
2
3
4
3
4 2 1
3
4 2 1
1
4 2 3
1
4 2 3
1 2
4 3
A B C A B C A B C A B C A B C A B C
1
2
3
4
5
6
1
2
4 3
1
2 4 3
1 3
2 4
3
2 4 1
1
2
3
4
A B C A B C A B C A B C A B C
7
8
9
10
11
Пусть требуется написать программу, выдающую команды типа А
C –
пересылка кольца с основания А на основание С и т.д. В
С, С
В, С
А.
1-й этап. Параметризация:
HANOY (n, x, y, z)
x
– начальное основание;
y
– конечное основание;
z
– вспомогательное основание.
2-й этап. Поиск тривиального случая.
При
n
= 1 выводим на экран команду
x
y.
Случай из двух колец сводится к случаю из одного кольца.
Если
n
= 0, то ничего не выводится.
Случай из одного кольца сводится к случаю из 0 колец.
1...,5,6,7,8,9,10,11,12,13,14 16,17,18,19,20,21,22,23,24,25,...106