какая алгоритмическая структура представлена на рисунке

algoritmkgu

Страницы

Календарь

Ноябрь 2021

Пн	Вт	Ср	Чт	Пт	Сб	Вс
1	2	3	4	5	6	7
8	9	10	11	12	13	14
15	16	17	18	19	20	21
22	23	24	25	26	27	28
29	30

Основные алгоритмические структуры

Основными алгоритмическими структурами являются:

«Следование» — это часть алгоритма, в которой все команды исполняются одна за другой в порядке их записи.

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

«Ветвление» — это часть алгоритма, в которой выполняется либо одна, либо другая последовательность действий в зависимости от результата проверки условия.

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

Различают две формы ветвления:

Конструкция полного ветвления:

Конструкция неполного ветвления:

«Цикл» — это часть алгоритма, в которой некоторую последовательность действий необходимо повторить несколько раз.

Алгоритм циклической структуры — алгоритм, в котором предусмотрено выполнение одной и той же последовательности действий.

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

Конструкция цикла «до»:

В цикле «пока» тело цикла выполняется до тех пор, пока выполняется условие.

Конструкция цикла «пока»:

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

Для организации цикла необходимо предусмотреть:

задание начального значения параметра цикла — переменной, которая будет изменяться при повторениях цикла;

изменение значения этой переменной перед каждым новым повторением цикла;

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

Существует два вида циклов:

В цикле «до» тело цикла выполняется определенное количество раз.

Источник

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

Содержание:

ВВЕДЕНИЕ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

For := to (или downto) do

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

zatrat, limit, stoim : real;

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

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

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

zatrat:= zatrat + stoim

Until zatrat > limit;

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

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

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

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

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

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

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

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

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

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

При копировании любых материалов с сайта evkova.org обязательна активная ссылка на сайт www.evkova.org

Сайт создан коллективом преподавателей на некоммерческой основе для дополнительного образования молодежи

Сайт пишется, поддерживается и управляется коллективом преподавателей

Whatsapp и логотип whatsapp являются товарными знаками корпорации WhatsApp LLC.

Cайт носит информационный характер и ни при каких условиях не является публичной офертой, которая определяется положениями статьи 437 Гражданского кодекса РФ. Анна Евкова не оказывает никаких услуг.

Источник