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

Содержание:

ВВЕДЕНИЕ

Понятие алгоритм появилось в средних веках, и его авторство приписывают математику Муххамеду бен Аль-Хорезми. Считается, что звучание слова алгоритм - это результат произношения слова Аль-Хорезми. Первоначально термин алгоритм применяли только к выполнению арифметичес­ких действий над десятичными числами [4]. В дальнейшем это понятие получило более широкое применение, и, в общем смысле, алгоритм представляет собой некоторую, однозначно определенную последовательность действий, предназначенную исполнителю для решения поставленной задачи за обозримый промежуток времени. Алгоритмы используются людьми повсеместно, и практически каждый из нас знаком с ними. Например, рецепт яблочного пирога - это линейный алгоритм. Исполнителем этого алгоритма является человек. Но термин "алгоритмическая конструкция" уже ассоциируется с вычислительной техникой. В качестве исполнителя такого алгоритма, как правило, выступает электронное вычислительное устройство.

Цель работы. Рассмотреть основные структуры алгоритмов и на практических примерах провести их сравнительный анализ.

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

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

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

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

Дискретность – это свойство подразумевает, что алгоритм делится на простые шаги [3,4].

Массовость – это свойство показывает, что алгоритм представляет собой универсальную последовательность действий, которая применяется для решения всех задач данного типа [3,4].

Определенность – это свойство ал­горитма свидетельствует, что шаги инструкции алгоритма должны быть однозначны и не допускать двусмысленности [3,4].

Результативность – свойство состоит в том, что алгоритм должен завершаться за конечное число шагов [3,4].

Формальность – это свойство указывает, что инструкции алгоритма должны быть понятны любому исполнителю, для которого они предназначены [3,4].

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

На второй ступени по качеству разработки находятся алгоритмы, описанные в открытой печати, предназначенные для решения стандартных типовых задач, которые приходится решать программистам. Это такие задачи, как сортировка массивов (пузырьковая сортировка), поиск наикратчайшего пути (задача коммивояжера), быстрый поиск и многие другие [1, 3]. Эти стандартные алгоритмы тоже очень эффективны, так как в их создании участвовали группы специалистов, обладающие высокой квалификацией. Библиотека таких алгоритмов опубликована в известном труде "Искусство программирования" Дональда Кнута [1].

В практике специалиста по информационным системам могут встречаться задачи, для решения которых стандартных алгоритмов не существует, поэтому ему самостоятельно придется их разрабатывать. Любые сложные алгоритмы состоят из простых структур - алгоритмических конструкций. Основные алгоритмические конструкции представляют собой базовые кирпичики, из которых строятся большие алгоритмы. Сочетание базовых конструкций позволяет задать сложную цепочку действий для решения поставленной задачи. Основные алгоритмические конструкции подразделяются на 3 типа: линейные структуры, разветвляющиеся структуры и циклические [2-4]. Все они будут рассмотрены в данной курсовой работе.

1. Линейные алгоритмы

1.1. Способы описания алгоритмов

Распространены четыре основные способа описания алгоритмов: словесное описание, псевдокод, блок-схема и программа [4].

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

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

Блок-схема — это язык описания алгоритмов с помощью геометрических фигур, соединенных линиями, показывающими порядок выполнения команд алгоритма. Этот способ представления алгоритма очень наглядный и, как правило, используется в отчётах и презентациях [3,4].

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

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

1.2. Применение линейных алгоритмов

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

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

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

Блок схема алгоритма приведена на рисунке 1

Рисунок 1 – Блок-схема алгоритма сложения двух чисел

Пример использования псевдокода для описания алгоритма.

Начало алгоритма

Ввод двух чисел а, b.

Вычислить сумму S = а + b.

Вывод S.

Конец алгоритма.

Пример. Составить компьютерную программу для вычисления общей поверхности и объема конуса. Заданы значения радиуса основания R и длины образующей L.

Решение.

Общая площадь поверхности вычисляется по формуле:

S = R² + RL.

Объем конуса вычисляется по формуле:

,

где H - высота конуса, определяемая по формуле:

.

Блок схема алгоритма представлена на рисунке 2.

Рисунок 2 - Блок-схема линейного алгоритма вычисления общей поверхности и объема конуса

Словесное описание алгоритма. На первом этапе работы алгоритма вводятся исходные значения: длина образующей (L) и радиус окружности (R). Затем следуют три вычислительные формулы, в которых последовательно вычисляются высота конуса (Н), площадь его поверхности (S) и объем (V). Завершается алгоритм выводом на экран вычисленных величин: площади S и объема V.

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

Program SandV;

Var

L, R, H, S, T, V : real;

{Основной код программы}

Begin

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

ReadLn(R); ReadLn(L);

{Основные вычисления}

H : = Sqrt(L*L-R*R);

S : = PI*Sqr(R) +PI*R*L;

V := PI* Sqr(R)*H/3;

{Вывод результатов}

WriteLn('V=', V:8:4);

WriteLn('S=' , S:8:4);

End.

В код добавлены комментарии, которые делают понятными все этапы работы алгоритма. Добавление комментариев - это один из важных элементов представления алгоритмов на языке программирования.

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

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

2. Разветвляющиеся алгоритмы

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

2.1. Способы построения разветвляющегося алгоритма

Порядок выполнения разветвляющийся конструкции следующий. На первом этапе проверяется истинность логического выражения, которое представляет собой условие. Если условие выполняется (истинно), то реализуется оператор 1, иначе (ложь) - оператор 2 [2].

Рисунок 3 - Блок-схема оператора ветвления, предусматривающего выполнения двух операторов

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

if логическое выражение then

Оператор 1

else

Оператор 2

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

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

if x>0 then

y:=x+4

else

y:=x*5;

В разветвляющейся структуре может быть и не предусмотрена последовательность действий в случае, если логическое условие не выполняется (ложь). Блок-схема такой конструкции представлена на рисунке 4.

Рисунок 4 - Блок-схема оператора ветвления, предусматривающего выполнения одного оператора

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

if логическое выражение then Оператор 1;

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

if x>10 then y:=x+7;

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

Пример. Даны три числа a, b, c. Найти наибольшее их этих трех чисел.

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

Рисунок 5 - Блок-схема поиска максимального числа из трех заданных

Описание алгоритма решения задачи. На первом этапе работы алгоритма вводятся три числа. Так как количество чисел больше двух, а операция сравнения чисел предусматривает только два варианта, то на втором этапе работы алгоритма для анализа всех возможных вариантов используются последовательно один за другим два условных перехода. Сначала сравниваются между собой два числа: a и b. Если величина числа a больше b, то в промежуточной переменой z сохранятся число a (z=a). Если условие (a>b) нарушается, то в промежуточной переменой z сохранятся число b (z=b). Таким образом, в результате выполнения первой операции сравнения будет найдено наибольшее из двух чисел a или b. Затем выполняется еще одна операция сравнения, где производится сопоставление переменной z с величиной числа с. Если условие (c>z) выполняется, то число c больше чисел a или b, и в этом случае за наибольшее принимается число c. В противном случае за наибольшую принимается величина, записанная в переменную z.

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

Program maximum;

Var

a, b, с, z : real;

Begin

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

ReadLn(a);

ReadLn (b);

ReadLn(c);

{Сравнение чисел a и b}

if a > b then

z := a

else

z := b;

{Проверка числа с}

if c>z then z := c;

WriteLn(z:8:2);

End.

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

2.2. Сложное ветвление

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

Пример алгоритма, включающего сложное ветвление. Заданы переменные х и у. Необходимо выполнить три различных действия в зависимости от условий. При х = у необходимо вывести на экран значения этих переменных без изменения. Когда х > у, величины переменных необходимо уменьшить в 3 раза. При условии х < у величины х и у увеличиваются на 12. Блок-схема алгоритма для решения поставленной задачи имеет вид, приведенный на рисунке 6.

Рисунок 6 - Блок-схема алгоритма, предусматривающего сложенное ветвление

Словесное описание алгоритма. Алгоритм начинается с ввода исходных данных - чисел x и y. На первом этапе выполняется проверка внешнего логического условия. Если оно ложно, то на экран монитора выводятся числа x и y без изменений.

Если логическое выражение внешнего условия истинно, то проверяется вложенное условие (x>y), которое позволяет завершить логическую цепочку выбора действий над числами. Когда величина x больше y, значения переменных величин (x и y) уменьшаются в 3 раза соответственно. Результаты выводятся на экран, и алгоритм завершает работу.

Если же логическое условие x>y нарушается, то в этом случае значения x и y увеличиваются на постоянное число 12. После выполнения вложенного условия на экран выводятся полученные результаты.

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

program usvovoperat;

Var

х, у : real;

Begin

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

ReadLn (х, у);

{ Проверяем внешнее условие}

if х < > у then

{Проверяем вложенное условие}

if х > у then

begin

х : = х/3;

y : = у/3;

end

else

begin

х := х+12;

у : = у+12

end;

WriteLn ('x= ', х:8:4, 'у= ', у:8:4) ;

End.

В представленном алгоритме, использующем для решения задачи сложное ветвление, сочетаются условные операторы, предусматривающие выполнение двух типов ветвлений. Внешнее ветвление построено согласно схеме с одной исполняемой ветвью (рисунок 4), а вложенное - с двумя ветвями (рисунок 3).

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

2.3. Ветвление с выбором варианта

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

Существует обобщенный оператор условного перехода - это "оператор варианта", который не ограничен двумя исполняемыми ветвями, а позволяет задать их количество и выбирать одну из многих, в зависимости от значения выражения, которое называется селектор [3].

Пример. Определить остаток от деления на 4 следующего выражения c=k*(a+b) и в зависимости от полученного результата выполнить следующие действия. Если остаток от деления равен нулю, то число с увеличить на 1, если остаток равен 1, то значение a увеличить на 4, а если остаток равен 2 или 3, то b увеличить на 2.

Блок-схема алгоритма имеет вид, приведенный на рисунке 7.

Рисунок 7 - Блок-схема алгоритма, использующая конструкцию с оператором
варианта

Алгоритм начинается с ввода переменных a, b, k. Далее вычисляется значение переменной c. На следующем шаге определяется значение селектора и в зависимости от полученного результата дальнейшая последовательность действий определяется одной из трех веток. Если остаток от деления равен нулю, то вычисляется значение с по формуле c:=c+1, и результат выводится на экран. При значении селектора равном единице выполняется другая ветвь, которая предусматривает совсем иную операцию a:=a+4, а затем вывод на экран переменной a. Для случая, когда значение селектора равно двум или трем, выполняется один и тот же оператор b:=b+2 с последующим выводом на экран переменной b. После выполнения последовательностей действий из выбранной ветки алгоритм завершает свою работу.

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

Program variantr;

Var

a, b, k, c : longint;

Begin

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

ReadLn(a,b,k);

{Вычисление значения переменной с}

c:=k*(a+b);

{Реализация оператора выбора варианта}

case c mod 4 of

0: begin

c:=c+1;

writeln(c:8)

end;

1: begin

a:=a+4;

writeln( a:8 )

end;

2, 3: begin

b:=b+2;

writeln( b:8)

end

end;

end.

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

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

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

3. Циклические алгоритмы

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

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

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

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

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

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

For <имя > := <нач. значение> to (или downto) <конечное значение> do

begin

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

end;

Служебное слово For однозначно определяет цикл с параметром. Служебные слова to или downto задают прямой или обратный отсчет параметра цикла. Если тело цикла содержит только один оператор, то операторные скобки begin и end можно не применять, их присутствие для одного оператора только загромождает программу, но логику алгоритма не нарушает.

Типичный пример применения цикла с параметром - это решение задачи табулирования функции.

Пример. Вычислить значение функции y(x)=5*x+4 при изменении аргумента на заданном отрезке [1..20] c шагом 1.

Решение. Блок-схема алгоритма решения поставленной задачи приведена на рисунке 9.

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

Рисунок 9 - Блок-схема алгоритма табулирования функции y(x)=5*x+4

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

На первой итерации значение переменной цикла равно единице, которая подставляется в функцию и вычисляется значение у равное 9. Затем 9 выводится на экран, и проверятся такое условие: значение переменной цикла меньше либо равно 20. Если условие истинно, то значение переменной цикла автоматически увеличивается на шаг, равный единице, и тело цикла выполняется снова. Итерационный процесс повторяется до тех пор, пока значение переменной цикла не превысит n=20. Тогда происходит выход из цикла, и алгоритм завершает свою работу.

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

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, которые являются границами интервала, включающего корень уравнения. Величина  определяет заданную точность. Критерий остановки вычислений определяется зависимостью .

Для реализации метода половинного деления вычисляется значение функции в точке a (y=f(a)). Далее вычисляется координата середины интервала (a,b) по формуле x=(a+b)/2, где точка x - найденная координата середины (a,b). Таким образом, исходный интервал будет разбит на два равных интервала: (a,x) и (x,b), где корень уравнения принадлежит одному из них. Проверяется основное условие принадлежности корня одному из этих интервалов (a,x), которое представляет собой произведение значений функции на его границах f(a)*f(x)<0. На следующем шаге используется ветвление для выбора интервала в зависимости от истинности условия f(a)* f(x)<0. Если это условие истинно, то корень принадлежит интервалу (a,x), и правая граница b интервала (a,b) смещается в точку x (b=x). В противном случае левая граница a интервала (a,b) смещается в точку x.

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

Многократное деление пополам интервала (a,b), содержащего искомый корень уравнения, осуществляется с помощью цикла с постусловием, который выполняется пока логическое условие ложно. При достижении заданной точности происходит выход из цикла и вывод полученных результатов на экран.

Реализация алгоритма, использующего цикл с постусловием на языке Паскаль. В качестве примера была выбрана функция y=x² - 5. Заданная точность 0.01.

Program metod;

Var a, b, eps, x, y, z : real;

Begin

{Ввод границ интервала и погрешности}

WriteLn('Ведите левую и правую границы a, b и погрешность eps');

ReadLn(a, b, eps);

{Вычисление значения функции на левом интервале}

y := sqr(a) - 5;

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

repeat

x : = ( a + b)/2;

z := sqr(x) - 5;

if y*z < 0 then b := x

else

begin

a:=x;

y:=z

end;

until abs(b-a) <= eps;

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

WriteLn('Корень уравнения', x:8:4);

end.

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

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

1. Кнут, Д. Искусство программирования / Д. Кнут; [пер. с англ.] — М.: Вильямс, 2006. — Т.1 — 682 с.
2. Павловская, Т.А. Паскаль. Программирование на языке высокого уровня Учебник для вузов / Т.А. Павловская. – Санкт-Петербург: Питер, 2007. – 393 с.
3. Панфилова Н.И. Информатика и программирование. Алгоритмизация и программирование: учебник для студентов высшего профессионального образования // А.В. Пруцков, А.Н. Пылькин, Б.Г. Трусов. - Москва.: Издательский центр "Академия", 2012. - 336 с.
4. Соболь, Б.В. и др. Информатика / Б.В. Соболь, А.Б. Галин, Ю.В. Панов, Е.В. Рашидова, Н.Н. Садовой. — Ростов-на-Дону : Изд-во "Феникс", 2007. — 446 с.