Procedure fibonacci;

Begin

F[0]:= 1;

F[1]:= 1;

for i:= 2 to max do

F[i]:= F[i-1]+F[i-2];

End;

Эта программа вычисляет первые max чисел Фибоначчи, используя массив размера max. Этот метод называет итерационным.

Какой же метод лучше? Точных правил для выбора между рекурсивной и нерекурсивной версиями алгоритма решения задачи не существует. Краткость и выразительность большинства рекурсивных процедур упрощает их чтение и сопровождение. С другой стороны, выполнение рекурсивных процедур требует больших затрат и памяти, и времени процессора нежели их итерационные аналоги.

Пример: Вывод всех делителей натурального числа.

Сначала рассмотрим программу:

Var n, d: longint;
BEGIN
...
For d:= 1 To n div 2 Do
If n div 2 = 0 Then write(n div d, ' ')
write(n)
...

В ней находятся и выводятся все делители числа n. Например, для n = 30 будут выведены числа 1, 2, 3, 5, 6, 10, 15, 30.

Далее надо заметить, что для того чтобы найти делители числа n, достаточно обнаружить делители, не превышающие , — все остальные делители получаются в результате деления n на найденные делители.

Фрагмент программы, учитывающий это обстоятельство:

For d:= 1 To Trunc(Sqrt(n)) — 1 Do
If n mod d = 0 Then write(d, ' ', n div d, ' ');
If Sqr(Trunc(Sqrt(n))) = n then write(Trunc(Sqrt(n)));

Последний оператор используется для того, чтобы в случае, когда n — точный квадрат,делитель, равный ,не выводился дважды. В результате, когда n = 100,будут выведены числа:

1, 100, 2, 50, 4, 25, 5, 20, 10.

А как сделать так, чтобы делители были напечатаны в порядке возрастания?

Ответ — надо использовать рекурсию.Процедура, решающая рассматриваемую задачу,имеет вид:

Procedure Dived(n, d: longint);

Var dd: longint;

{dd — делитель, 'симметричный' найденному делителю}

Begin

If n mod d = 0 Then

{Встретился делитель числа n}

Begin

{Выводим его}

write(d, ' ');

{Запоминаем 'симметричный' делитель}

dd:= n div d;

If d <> dd Then

Begin

{Переходим к проверке следующего числа d}

Dived(n, d + 1);

{После 'возврата' из процедуры Dived печатаем делитель dd}

write(dd, ' ')

End

End

Else {n mod d <> 0}

{Переходим к проверке следующего числа d}

Dived(n, d + 1);

End;

Вызов процедуры из основной программы осуществляется следующим образом:

Dived(n, 1);

Здесь используется форма рекурсивной процедуры с выполнением действий как до, так и после рекурсивного вызова (или с выполнением действий как на рекурсивном спуске, так и на рекурсивном возврате).

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

Решение будем получать в строковом виде, аналогичном следующему (для n = 12):

2*2*3

2*6

…

Можем рассуждать так. Проверим все числа, которые могут быть множителями числа n,начиная с двойки. Если среди них окажется множитель, то учтем его в записи разложения (как— опишем ниже), а затем решим задачу разложения на множители числа, равного частному от деления nна этот множитель. Итак, мы вышли на использование рекурсии.

Параметрами создаваемой рекурсивной процедуры (ее имя — R) будут:

k — число, разлагаемое на множители (не только заданное);

first — первый возможный множитель числа k;

s — величина строкового типа,представляющая собой запись разложения,полученного до вызова процедуры R.

Искать возможные множители можно не до целой части от k/2, а до целой части квадратного корня из k (см. обсуждение предыдущей задачи).

Что делается в процедуре R?

Необходимо проверить, являются ли множителями числа k числа m, равные first, first + 1, ( — целая часть квадратного корня из k). Если множитель (очередной) встретился, то необходимо:

1) его строковое представление sm“добавить” к уже полученной ранее записи s с учетом символа “*” — полученная величина (s2)будет передана в качестве параметра при очередном рекурсивном вызове процедуры R;

2) вызвать процедуру R с параметрами k div m, m, s2.

После проверки всех чисел m необходимо учесть в записи разложения также число k и вывести полученный результат на экран.

Процедура R, решающая задачу:

Procedure R(k, first: longint; s: string);

Var m: word;

sm, s2: string; {sm — строковое представление очередного множителя}

Begin

For m:= first to Trunc(Sqrt(k)) Do

{Если m — множитель числа k}

If k mod m = 0 Then

Begin {то: — получаем строковое представление m,}

Str(m, sm);

{— добавляем его к ранее полученной записи разложения}

s2:= s + sm + '*'

{— вызываем (рекурсивно) процедуру R с новыми параметрами}

R(k div m, m, s2)

End;

{После рассмотрения всех возможных множителей учитываем в разложении также число k}

Str(k, s2);

s:= s + s2;

writeln(s)

End;

Вызов разработанной процедуры из основной части программы должен выглядеть следующим образом: R(n, 2, '');

ВОПРОСЫ ДЛЯ САМОКОНТРОЛЯ:

1. Стек: определение, свойства.

2. Основные алгоритмы с использованием стека.

3. Задача о сбалансированности скобок в тексте.

4. Задача Джозефуса.

5. Рекурсивные и не рекурсивные алгоритмы.

6. Задача Ханойские башни.

ИСПОЛЬЗУЕМАЯ ЛИТЕРАТУРА:

1. Вирт Н. Алгоритмы и структуры данных. –М.: Мир, 2001.

2. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы. Построение и анализ. –М.: МЦНМО, 2000.

3. Ахо А., Хопкрофт Д., Ульман Д. Структуры данных и алгоритмы. –М.: Вильямс, 2000.

4. Голицына О.Л., Попов И.И. Основы алгоритмизации и программирования. –М.: Форум, 2008.

Дата добавления: 2015-07-11