- •Программа решения задачи о ханойской башне
- •Алгоритм решения задачи:
- •Псевдослучайные числа. Функция, возвращающая значение и меняющая параметр
- •Процедура вычисления корней квадратного уравнения
- •Нахождение нод (наибольшего общего делителя) с помощью рекурсивной функции
- •Функции вычисления площади геометрических фигур
- •"Заем". Арифметические выражения, возведение в степеньАлгоритм решения задачи:
Программа решения задачи о ханойской башне
Алгоритм решения задачи:
В одной из древних легенд говорится следующее. «В храме Бенареса находится бронзовая плита с тремя алмазными стержнями. На один из стержней бог при сотворении мира нанизал 64 диска разного диаметра из чистого золота так, что наибольший диск лежит на бронзовой плите, а остальные образуют пирамиду, сужающуюся кверху. Это – башня Брамы. Работая день и ночь, жрецы переносят диски с одного стержня на другой, следуя законам Брамы:
1. диски можно перемещать с одного стержня на другой только по одному; 2. нельзя класть больший диск на меньший. Когда все 64 диска будут перенесены с одного стержня на другой, и башня, и храмы, и жрецы-брамины превратятся в прах, и наступит конец света».
Эта древняя легенда породила задачу о Ханойской башне: переместить m дисков с одного из трех стержней на другой, соблюдая «законы Брамы».
Назовем стержни левым (left), средним (middle) и правым (right). Задача состоит в переносе m дисков с левого стержня на правый.
Задача может быть решена одним перемещением только для одного (m = 1) диска. В общем случае потребуется 2m-1 перемещений.
Построим рекурсивное решение задачи, состоящее из трех этапов:
a) перенести башню, состоящую из m – 1 диска, с левого стержня на средний; b) перенести один оставшийся диск с левого стержня на правый; c) перенести башню, состоящую из m – 1 диска, со среднего стержня на правый.
Таким образом, задача о перемещении m дисков сводится к задаче о перемещении m – 1 диска. Обращаясь опять к этому же алгоритму, сведем задачу к перемещению m – 2 дисков. Продолжая этот процесс, получим, в конце концов, задачу о перемещении одного диска. Эта задача решается за один ход. Таким образом, в процессе решения возникают промежуточные задачи: переместить башню из нескольких nдисков с одного стержня на другой.
Обозначим тот стержень, с которого следует снять диски, через s1, на который надеть – через sk, а вспомогательный стержень через sw.
Оформим алгоритм решения задачи о переносе башни из n дисков сs1 на sk в виде процедуры move с 4-мя параметрами: n, s1, sw, sk; алгоритм для n = 1 выделим в отдельную процедуру step, которая перемещает один диск со стержня s1 на sk.
Программа на языке Паскаль:
type
st = (left, middle, right);
nat = 1..maxint;
var
m: nat; {m – число дисков}
procedure move(n: nat; s1, sw, sk: st);
{перемещение n дисков с s1 на sk}
procedure step;
{перемещение одного диска с s1 на sk}
procedure print(s: st);
begin
case s of
left: write(' лев. ');
middle: write(' средн. ');
right: write(' прав. ')
end;
end;
begin {step}
write(' снять диск с ');
print(s1);
write(' надеть на ');
print(sk);
writeln
end;
begin {move}
if n = 1 then
step
else begin
move(n - 1, s1, sk, sw);
step;
move(n-1, sw, s1, sk)
end
end;
begin
read(m); {число дисков}
writeln('для ', m:3, ' дисков следует произвести ',
'следующие действия:');
move(m, left, middle, right);
readln
end.