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

Содержание 15
ОСНОВЫ АЛГОРИТМОВ И СТРУКТУР ДАННЫХ
A B C
Рис. 7. Перемещение одного кольца с основания A на основание B
A B C
Рис. 8. Перемещение (n-1) кольцо с основания C на основание B
Алгоритм № 5.
HANOY (n, x, y, z)
{
if n > 0 then
{
HANOY (n-1, x, z, y)
print(x, “->”, y)
HANOY (n-1, z, y, x)
}
else return;
}
Для рекурсивных алгоритмов, оперирующих с натуральными числами,
поиск тривиального случая очень похож с “инициализацией” доказательства с
помощью индукции. Декомпозиция общего случая соответствует
доказательству Pn+1 , исходя из Pn. Таким образом рекурсия оказывается
простым обобщением метода математической индукции на информационные
процессы.