Язык программирования Pascal. Процедуры и функции. Рекурсия. Васильев В.В - 23 стр.

UptoLike

ВУЗ: 

ВГУ | Воронеж

Составители: 

Рубрика: 

23
then begin read(c); Rec; write(c) end;
end; {Rec}
Begin
Rec; readkey
End. {Text}
Познакомимся с красивой задачей , связанной с легендой , решение кото-
рой приводит к рекурсивному алгоритму. Говорят, что когда- то в Ханое стоял
храм , а рядом с ним – три башни (стержня ). На первую башню надеты 64 дис-
ка различного диаметра. Сложенные диски на стержне похожи на детскую иг-
рушку – пирамиду. Монахи этого храма должны переместить все диски с пер -
вого стержня на третий, соблюдая следующие правила :
1. можно перемещать лишь по одному диску;
2. больший диск нельзя класть на меньший;
3. снятый диск нельзя отложить – его необходимо сразу же надеть на дру-
гой стержень.
Легенда утверждает , что когда монахи закончат свою работу – а они пере-
мещают диск за одну секунду! – наступит конец света. Когда дисков много,
решение этой задачи оказывается слишком долгим.
Задача 2. «Ханойские башни». Пусть имеются три
столбика А , В , С и n дисков разного размера, перенуме-
рованных от 1 до n в порядке возрастания их размеров .
Сначала все диски надеты на столбик А в виде
пирамиды . Требуется перенести все диски со столбика А на столбик С , соблю -
дая следующие правила : диски можно переносить только по одному, диск
большего размера нельзя ставить на меньший. Диск B можно использовать в
качестве промежуточного.
♣ Задачу можно решить, составив рекурсивный алгоритм. Решение задачи
для n дисков можно сформулировать через решение задачи для n-1 дисков и
т . д . Для случая n=1 решение сводится к перемещению единственного диска с
исходного столбика на целевой столбик. Составим рекурсивный алгоритм:
Если n>0, то
переместить верхние n-1 диск со столбика А на столбик В,
используя столбик С как вспомогательный,
переместить оставшийся нижний диск со столбика А на
столбик С,
переместить n-1 диск со столбика B на столбик С,
используя столбик А как вспомогательный.
Параметрами рекурсивной процедуры move являются переменные n (число
перемещаемых дисков на текущем уровне рекурсии), Source (буква исходного
столбика), Help (буква вспомогательного столбика), Res (буква целевого стол-
бика). В глобальной переменной k накапливается число сделанных ходов . ♠
Program Hanoi;
Uses crt;
Var n,k:integer;

Страницы