Лабораторная работа №19

Тема: «Решение задач, реализуемых с помощью алгоритмов с возвращением».

Цель работы: получение навыков составления программ на языке Pascal с использованием рекурсии.

 

Задача на вычисление факториала натурального числа.

Для того, чтобы вычислить N!, надо значение (N-1)! умножить на N, при этом 1! =1. В общем виде это можно записать так:

Решение:

Для вычисления факториала опишем функцию:

function factorial (n: integer): Longint;

begin

if n=1

then factorial: =1

else factorial: =n*factorial (n-1)

end

end;

Рассмотрим последовательность вызовов этой функции для n=5.

ü Первый вызов функции происходит в основной программе. Отметим, что при каждом обращении к функции будет создаваться свой набор локальных переменных (в данном случае в функции факториал имеется всего одна локальная переменная n). Для каждой локальной переменной на время работы функции выделяется память. После завершения работы функции эта память освобождается и переменные удаляются.

Так как , то управление передается на ветку Else и функции factorial присваивается значение n*factorial (n-1), то есть 5*factorial (4).

Происходит второй вызов функции factorial, с параметром 4. Этот процесс повторяется до тех пор, пока значение параметра не станет равным 1. Тогда n=1, а поэтому значение функции factorial=1.

Таким образом n=1 – это условие окончания рекурсии.

Управление передается в точку вызова, то есть в предыдущую функцию для n=2: factorial: =n* factorial (n-1), значит factorial: =2*1, следовательно, factorial (2)=2. Возвращаемся назад, поднимаясь «вверх» по цепочке рекурсивных вызовов. Таким образом, получаем значение factorial (5)=120, (рис. 17).

 

 

function factorial (n: integer): Longint; begin if n=1 then factorial: =1 else factorial: =n* factorial (n-1) end;

1 вызов (n=5) 120

 

 

function factorial (n: integer): Longint; begin if n=1 then factorial: =1 else factorial: =n* factorial (n-1) end;

2 вызов (n-4)

 

 

function factorial (n: integer): Longint; begin if n=1 then factorial: =1 else factorial: =n* factorial (n-1) end;

3 вызов (n=3)

 

 

function factorial (n: integer): Longint; begin if n=1 then factorial: =1 else factorial: =n* factorial (n-1) end;

4 вызов (n=2)

 

 

function factorial (n: integer): Longint; begin if n=1 then factorial: =1 else factorial: =n* factorial (n-1) end;

5 вызов (n=1)

 

Рис. 17

 

Задача о «Ханойских башнях».

В большом храме Бенареса бронзовая плита поддерживает 3 алмазных стержня, на один из которых Бог нанизал во время сотворения мира 64 золотых диска, образующих пирамиду. С тех пор монахи каждую секунду перекладывают по одному диску согласно правилам:

o За один раз можно перекладывать только один диск;

o Нельзя класть диск на диск, меньший по размеру;

o Можно пользоваться только одним резервным стержнем.

Составить программу с использованием рекурсии.

Решение:

1.

 

 

 

1 шаг 3 шаг

 

Х У Z

 

2 шаг

 

 

2. Перенесем верхушку пирамиды, состоящую из (n-1)-го диска, с первого стержня на второй, затем перенесем один диск с первого стержня на третий, а потом перенесем верхушку пирамиды, состоящую из (n-1)-го диска, со второго стержня на третий.

3. Далее повторим алгоритм переноса, но уже для (n-1)-го диска, затем для (n-2)-го диска и так далее, пока не опустимся до одного диска.