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;
}
Для рекурсивных алгоритмов, оперирующих с натуральными числами,
поиск тривиального случая очень похож с “инициализацией” доказательства с
помощью
индукции.
Декомпозиция
общего
случая
соответствует
доказательству
P
n+
1
, исходя из
P
n
. Таким образом рекурсия оказывается
простым обобщением метода математической индукции на информационные
процессы.
1...,7,8,9,10,11,12,13,14,15,16 18,19,20,21,22,23,24,25,26,27,...106