Файл: Основные структуры алгоритмов: сравнительный анализ и примеры их использования (Линейные алгоритмы).pdf

Реализация алгоритма, использующего цикл с параметром на языке Паскаль, представлена следующим программным кодом.

program tabul;

Var

х, y, a, n : integer;

Begin

{ Ввод исходных данных}

ReadLn (a, n);

{ Цикл с параметром}

For x := a to n do

{Выполняется тело цикла}

begin

y := 5*x+4;

Writeln('y[',x,']=', y)

end;

{Конец тела цикла}

End.

При программной реализации цикла с параметром необходимо, чтобы переменная цикла x и переменные a и n были целого типа. Это создает ограничение для применения на практике алгоритмической конструкции "цикл с параметром". Хотя это ограничение легко обходится введением в тело цикла других переменных вещественного типа, но работу с ними и изменение их параметров программисту необходимо организовать.

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

3.2 Цикл с предусловием

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

Блок-схема, определяющая цикл с параметром в общей структуре алгоритма, представлена на рисунке 10.

Рисунок 10 - Алгоритмическая конструкция, определяющая цикл с
предусловием

Структура алгоритмической конструкции "цикл с предусловием" на языке Паскаль записывается следующим образом [2]:

while <логическое выражение> do

begin

<тело цикла, состоящее из нескольких операторов >

<счетчик, обеспечивающий выход из цикла >

end;

Служебное слово while свидетельствует, что этот программный код реализует алгоритмическую конструкцию "цикл с предусловием". Если логическое выражение истинно, то выполняется тело цикла, в противном случае происходит выход из цикла. Я решил в теле цикла отразить важный элемент цикла с предусловием: счетчик цикла, который со временем обеспечивает нарушение логического условия, что и позволяет завершить работу цикла и избежать бесконечного зацикливания. Синтаксис оператора не включает эту переменную, но в общей структуре я привел ее как элемент, отражающий особенности применения на практике этой алгоритмической конструкции.

Пример, иллюстрирующий практическое применение цикла с предусловием. Задача. Необходимо вычислить сумму чисел, чередующихся последовательно от 1 до n с заданным шагом.

Решение. Блок-схема алгоритма приведена на рисунке 11.

Рисунок 11 - Блок-схема алгоритма вычисления суммы целых чисел, чередующихся с заданным шагом

На первом этапе работы алгоритма вводится последнее число последовательности (n) и величина шага (h). До начала работы цикла инициируются начальные значения суммы s и числа х. На следующем этапе начинает свою работу цикл с предусловием. Сначала проверяется логическое условие xn. Если это логическое условие нарушается, то происходит выход из цикла, и тело цикла не выполнится ни разу. Когда условие истинно, значение суммы увеличивается на величину x. После этого переменная x возрастает на величину шага h, и начинается следующая итерация цикла. Вновь проверяется условие, и в зависимости от результата происходит выход из цикла или итерационный процесс продолжается. Переменная x на каждой итерации все время увеличивает свое значение и рано или поздно превысит величину n. Количество итераций заранее неизвестно и определяется величинами n и h. После выхода из цикла выводится значение суммы s, и алгоритм завершает свою работу.

Реализация алгоритма, использующего цикл с предусловием на языке Паскаль.

program summa;

Var

x, y, n, h, s : real;

Begin

{ Ввод исходных данных}

ReadLn ( n, h);

{ Инициализация начальных значений}

x:=1;

s:=0;

{ Цикл с предусловием}

while x <= n do

{Выполняется тело цикла}

begin

s := s+x;

x := x+h

end;

{Конец тела цикла}

Writeln('s=', s:8:4);

End.

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

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

3.3 Цикл с постусловием

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

Блок-схема, определяющая цикл с параметром в общей структуре алгоритма, представлена на рисунке 12.

Рисунок 12 - Блок-схема цикла с постусловием

Оператор цикла с постусловием на языке Паскаль имеет следующую структуру [2]:

repeat

<тело цикла, состоящее из нескольких операторов >

<счетчик, обеспечивающий выход из цикла >

until <логическое выражение>

Отличительной особенностью при кодировании цикла с постусловием от двух предыдущих циклических конструкций: цикла с параметром и цикла с предусловием является то, что при использовании нескольких операторов в теле этого цикла не требуется ставить операторные скобки begin и end.

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

Решение. Блок-схема алгоритма приведена на рисунке 13. На первом шаге работы алгоритма осуществляется ввод общего количества средств (переменная limit). Далее задается начальное значение суммы затрат. Так как не совершено еще ни одной покупки, начальная сумма затрат задается равной нулю.

Рисунок 13 - Блок-схема алгоритма вычисления суммы затрат

На следующем шаге организуется цикл с постусловием. Цикл начинается с вывода текущих затрат. Затем необходимо ввести стоимость первой покупки. После того как будет задана сумма первой покупки, вычисляются общие затраты и проверяется условие выхода из цикла. Если величина затрат меньше заданного лимита, то тело цикла выполняется вновь. Выводится на экран сумма потраченных средств, и вводится стоимость новой покупки. Общая стоимость всех потраченных средств вычисляется прибавлением к уже потраченной сумме стоимости новой покупки. Снова проверяется условие выхода из цикла. Итерационный процесс завершается, когда количество потраченных средств превысит лимит. После выхода из цикла алгоритм завершает свою работу.

Реализация алгоритма, использующего цикл с постусловием на языке Паскаль.

Program pokupki;

Var

zatrat, limit, stoim : real;

Begin

{Ввод максимальной суммы средств}

WriteLn('Введите лимит средств');

ReadLn(limit);

{Задание начальных значений}

zatrat:=0.0;

{Начало цикла с постусловием}

repeat

WriteLn('Текущие затраты= ', zatrat:8:4);

WriteLn('Введите цену покупки');

ReadLn(stoim);

zatrat:= zatrat + stoim

Until zatrat > limit;

{Конец цикла }

End.

При программной организации цикла с постусловием необходимо обращать внимание на те же моменты, что и для цикла с предусловием. Это правильность выставления знака логического условия выхода из цикла и переопределение в теле цикла переменной, обеспечивающей выполнение или нарушения логического условия выхода из цикла. Чтобы не ошибиться, необходимо в процессе отладки программы выводить величину этой переменной на экран. Тогда можно избежать зацикливания или преждевременного выхода из цикла.

Вывод. Таким образом, в отличие от алгоритмической конструкции "цикл с предусловием" в цикле с постусловием тело цикла выполнится хотя бы один раз. Программная реализация для цикла с постусловием отличается от других циклических конструкций тем, что не требует использования операторных скобок при использовании нескольких операторов в теле цикла.

Вывод по главе. Циклические конструкции предназначены для организации итерационного процесса, обеспечивающего многократное повторение тела цикла. Для выбор типа цикла, который необходимо применять для решения поставленной задачи, нужно определится с двумя вопросами. Первый вопрос такой. Требуется ли использовать при решении задач заданное число итераций или число итераций неограниченно и меняется в процессе решения задачи? В первом случае необходимо выбрать цикл с параметром. В другом случае требуется ответить на второй вопрос. Необходимо ли, чтобы тело цикло было выполнено хотя бы один раз? Если ответ положительный, то используется цикл с постусловием, в другом случае - цикл с предусловием.

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

Алгоритмы, предназначенные для решения практических задач, строятся посредством комбинирования основных алгоритмических конструкций [2]. Далее разобран пример решения практической задачи, сочетающий три основные алгоритмические конструкции.

Пример. Найти корень уравнения y=f(x) с погрешностью  методом половинного деления.

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

Блок-схема этого алгоритма представлена на рисунке 14. На первом этапе работы алгоритма вводятся начальные значения переменных a и b, которые являются границами интервала, включающего корень уравнения. Величина  определяет заданную точность. Критерий остановки вычислений определяется зависимостью .