Файл: Рекурсивные и итерационные алгоритмы: особенности и примеры использования.pdf

Оператор цикла while в Паскаль имеет следующий формат записи:

while выражение do

оператор;

Рисунок 2.2 - Блок-схема цикла while

Рассмотрим работу оператора цикла while.

1. Вычисляется значение выражения (т. е. условие, стоящее после ключевого слова while), которое должно быть логическим выражением.
2. Если результат вычисления выражения равен true (истина), то выполняется тело цикла (простой или составной оператор, расположенный после ключевого слова do). Затем, снова проверяется условие и т. д.
3. Если результат равен false (ложь), то происходит выход из цикла и управление передается на первый оператор, следующий за циклом.

2.1.3. Цикл с постусловием. Оператор repeat

Цикл while может не выполниться ни разу, если логическое выражение в заголовке сразу вернуло false. Однако такая ситуация не всегда может быть приемлемой. Бывает, что тело цикла должно выполниться хотя бы один раз, не зависимо оттого, что вернет логическое выражение. В таком случае используется цикл repeat – цикл с постусловием.

В цикле repeat логическое выражение стоит после тела цикла. Причем, в отличие от цикла while, здесь всё наоборот: в случае true происходит выход из цикла, в случае false – его повторение.

Оператор repeat имеет следующий формат записи:

repeat

тело цикла

until выражение

Рисунок 2.3 - Блок-схема цикла repeat

Работа оператора цикла repeat происходит следующим образом:

1. Выполняется последовательность операторов, заключенная между ключевыми словами repeat и until (поэтому тело цикла выполнится хотя бы один раз).
2. Производится проверка продолжения цикла: если значение выражения, записанного после ключевого слова until, равно false (ложь), то тело цикла выполняется снова.
3. Если значение выражения равно true (истина), то происходит выход из цикла.

Чтобы рассмотренные выше операторы цикла выполнялись конечное число раз, при построении цикла необходимо предусмотреть, чтобы среди выполняемых операторов обязательно был оператор, который изменял бы значение условия, таким образом, чтобы когда-нибудь значение условия принимало бы false(для оператора while-do)или true(для оператора repeat- until). В противном случае цикл будет повторяться бесконечное число раз и программа "зациклится".[2]

2.1.4. Вложенные циклы

Основная идея использования вложенных циклов состоит в том, что даже когда некий процесс, требует цикла -- повтора действий (т.н. "внешний цикл"), то даже внутри отдельного действия можно запустить свой цикл (т.н. "внутренний" или "вложенный цикл") для решения какой-то "местной" задачи. То есть: внутри витка внешнего цикла, можно запустить цикл внутренний, тогда на один виток внешнего цикла, внутренний цикл будет каждый раз выполнять все свои витки.

Рассмотрим классический пример задачи с выводом таблицы умножения.

var i, j: integer;

begin

for i := 1 to 9 do // цикл по строкам таблицы, счетчик как левый множитель

begin

for j := 1 to 9 do // выводим равенства очередной строки, счётчик как правый множитель

write(i, '*', j, '=', i*j:2, #9);

writeln(); // переносим строку

end;

end.

Пример работы программы представлен на рисунке 2.4.

Рисунок 2.4 - Результат работы программы вывода таблицы умножения

2.2. Применение итерационных алгоритмов

Огромное количество различного рода задач решается с применением алгоритмов циклической структуры:

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

Рассмотрим более подробно один из возможных практических вариантов применения алгоритмов практических задач - сортировку данных - на примере алгоритма сортировки методом пузырька.

Данная задача решается с использованием вложенных циклов.

Алгоритм:

1) Последовательно бежим по массиву и сравниваем два соседних элемента, если порядок не верный то меняем их местами.

2) Повторять проходы на один меньше, чем кол-во элементов в массиве или пока не окажеться, что за проход не произведено ни одной замены.

Просмотрим алгоритм на примере:

Отсортируем массив: 524613 где каждая цифра это элемент массива.

Начало цикла, в массиве 524613 нет отсортированных чисел:

1) Первый проход:

524613->254613->245613->245613->245163->245136

Мы бежим по массиву и меняем элементы местами, которые находятся рядом друг с другом и не соответствуют порядку сортировки. Первый шаг это цифры 5 и 2, второй 5 и 4, третий 6 и 5, четвёртый 6 и 1, пятый 6 и 3.

2) Второй проход.

245136->245136->245136->241536->241356->241356

3) Третий проход.

241356->241356->214356->213456->213456->213456

4) Четвёртый проход.

213456->123456->123456->123456->123456->123456

После первого шага видно, что массив отсортирован, но условия выхода из сортировки ещё нет сказано, что не должно проходить ни одного изменения, или шаг должен быть на один меньше, чем кол-во элементов в массиве.

5) Пятый проход финальный.

123456->123456->123456->123456->123456->123456

Сразу удовлетворилось два условия выхода, не было произведено ни одного изменения и проход по счёту равен количеству элементов в массиве минус 1.

Ниже представлена код процедуры реализующей данный алгоритм на языке программирования Pascal.

Procedure Bubble_Sort (var a : array of real; LengthArray :Integer);

var i,i2:integer;

begin

for i:=1 to LengthArray-1 do

for i2:=1 to LengthArray-2 do

if a[i2+1]<a[i2] then

Swap(a[i2],a[i2+1]);

end;

Рассмотрим еще одну задачу решаемую с применением итерационных алгоритмов - вычисление определенного интеграла. Рассмотрим на примере метода трапеций. Блок-схема данного метода приведена на рисунке 2.5.

Рисунок 2.5 - Блок-схема алгоритма метода трапеций

Ниже приведен код программы на языке паскаль реализующий данный алгоритм.

function f(x: real): real;

begin

f := sqr(x) - x - 1;

end;

var

a, b, S, h, integ: real;

i, n: integer;

begin

readln(a, b, n);

h := (b - a) / n;

for i := 1 to n - 1 do

S := s + f(a + h * i);

integ := h * ((f(a) + f(b)) / 2 + S);

writeln('S=', integ);

end.

3. Сравнение рекурсивных и итерационных алгоритмов

Для сравнения итерационных и рекурсивных алгоритмов рассмотрим их на решении простых задач.

3.1. Вычисление N-го числа Фибоначчи

Числа Фибоначчи — элементы числовой последовательности в которой первые два числа равны либо 1 и 1, либо 0 и 1, а каждое последующее число равно сумме двух предыдущих чисел[3].

Ниже приведена программа на языке программирования Pascal вычисляющая n-е число Фибоначчи.

program Fibonacci;

function Recursion (n: word): longint;

begin

if (n = 0) or (n = 1) then

Recursion:= 1

else Recursion := Recursion(n - 1) + Recursion(n - 2); {рекурсивный вызов}

end;

function Iteration(n: word): longint;

var

x, y, t: longint;

k: integer;

begin

x := 1;

y := 1;

for k := 2 to n do

begin

t := y;

y := x + y;

x := t;

end;

Iteration := y; {итерация}

end;

Var

n:integer = 20;

begin

writeln('Рекурсивный алгоритм : F(', n, ')= ', Recursion(n));

writeln('Итерационный алгоритм : F(', n, ')= ', Iteration(n));

end.

Исходя из алгоритма можно сделать следующие выводы:

• итеративный алгоритм работает линейное время.
• рекурсивный алгоритм работает время, пропорциональное самому вычисляемому числу Фибоначчи, так как результат получается в результате сложения единиц.
• для рекурсивного алгоритма код более компактный, но на него затрачивается большее количество памяти.

3.2. Вычисление факториала

Слово факториал произошло от латинского factor (делающий, производящий). Факториал числа — это произведение натуральных чисел от 1 до самого числа (включая данное число).

Ниже приставлен код вычисления факториала на языке программирования Pascal.

function FacRecursive(n: Integer): Real;

begin

if n = 0 then

FacRecursive := 1

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

end;

function FacIteration(n: Integer): Real;

var

s, i: integer;

begin

s := 1;

for i := 1 to n do

S := S * i;

FacIteration:=s;

end;

var

n: integer;

begin

write('n: ');

readln(n);

writeln('Итерация: ',FacIteration(n));

writeln('Рекурсия: ',FacRecursive(n));

end.

Как и при вычислении числа Фибоначчи, рекурсивный код алгоритма более компактный, но на него затрачивается большее количество памяти.

Важнейшим достоинством рекурсивного подхода к программированию является краткость записи и прозрачность рекурсивных алгоритмов. Не следует также забывать об ориентации рекурсивного программирования на математическую форму записи, а следовательно, о возможности доказательства правильности построенных алгоритмов.

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