Стр. 15 - Основы алгоритмов и структур данных

Содержание 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 колец.