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

Содержание:

Введение

Для решения многих задач и достижения целей мы составляем «план действий». Разбивая выполнение задания на этапы, мы оптимизируем наше время и силы, начинаем лучше понимать, чего мы хотим сделать и каким образом мы должны это сделать. Конечно, этот «план» должен быть записан на понятном для исполнителя языке.

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

Цель курсовой работы – сравнить основные структуры алгоритмов и определить сферу их применения.

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

• Раскрыть понятие алгоритма
• Выделить свойства алгоритма
• Определить основные структуры алгоритмов, провести их сравнительный анализ
• Выяснить сферу и способ применения основных структур алгоритмов для решения различных задач в программировании

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

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

В своей работе я использовал учебно-методические материалы таких авторов, как М.П. Белов (СЗТУ), И.А. Селиванова (УралГАХА), А.А. Ключарев (СПбГУАП). В них подробно и понятно раскрывается понятие алгоритма, его основные свойства, приводятся примеры структур алгоритмов и анализ их эффективности.

Глава 1. Понятие и свойства алгоритма

Термин алгоритм происходит от имени узбекского ученого IX века Аль-Хорезми, который в своем труде «Арифметический трактат», переведенном в XII веке с арабского на латынь, изложил правила арифметических действий над числами в позиционной десятичной системе счисления. Эти правила назывались алгоритмами.

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

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

Алгоритмизация задачи – процесс разработки (проектирования) алгоритма решения задачи с помощью ПК на основе ее условия и требований к конечному результату.

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

Итак, алгоритм – это понятное и точное предписание исполнителю совершить последовательность действий, направленных на достижение указанной цели или на решение поставленной задачи.^[2]

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

• Понятность для исполнителя – содержание предписания о выполнении только таких действий, которые входят в систему команд исполнителя, т.е. алгоритм должен быть задан с помощью таких указаний, которые исполнитель может воспринимать и выполнять по ним требуемые действия (операции).
• Дискретность (прерывность, раздельность) – алгоритм должен представлять процесс решения задачи как последовательное исполнение простых (или ранее определенных) шагов (этапов). Ими могут служить пункты инструкции, ввод различных типов данных с устройств ввода – текстовых, графических, аудиовизуальных, операторы языков программирования.
• Определенность – каждое правило алгоритма должно быть четким, однозначным и не оставлять места для произвола. Это свойство обеспечивает выполнение алгоритма механически, не требуя никаких дополнительных указаний или сведений о решаемой задаче.
• Результативность – алгоритм должен приводить к решению задачи за конечное число шагов. При этом в некоторых случаях число шагов устанавливается вручную и влияет на точность результата, а иногда число шагов заранее неизвестно, например, при выполнении алгоритма до остановки пользователем по достижении требуемого результата. В остальных случаях алгоритм может производить вывод о невозможности продолжения решения задачи по какой-либо из причин, что тоже является результатом.
• Массовость – алгоритм решения задачи производится в общем виде, т.е. его можно будет применять дня некоторого класса задач, различающихся лишь исходными данными. При этом исходные данные могут выбираться из некоторой области, которая называется областью применимости алгоритма.^[3]

Для решения любой задачи нам понадобятся начальные (входные) и конечные (выходные, результативные) данные. Они могут быть отнесены к одному из двух типов: основному (простому), форма представления которого определяется архитектурой ЭВМ, или сложному, конструируемому пользователем для решения конкретных задач.

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

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

• Словесный – в виде, например, нумерованного списка, на языке, понятном исполнителю.
• Графический (Блок-схема) – это вариант графической записи алгоритма, применяемый на этапе алгоритмизации задачи, выполняемой на программируемом вычислительном устройстве.
• Псевдокоды
• Программный^[4]

Основным способом записи алгоритмов в программировании является блок-схема. В ней каждому типу действий соответствует геометрическая фигура, представленная в виде блочного символа. Блочные символы соединяются линиями переходов, определяющими очередность выполнения действий. Для начертания этих схем используется набор символов, определяемых ГОСТ 19.701-90 (ИСО 5807-85) «Единая система программной документации». Наиболее часто употребляемые символы приведены в таблице 1. ^[5]

Таблица 1

Название символа	Обозначение	Пояснение
Процесс		Вычислительное действие или последовательность вычислительных действий
Решение	Условие нет да	Проверка условий
Модификация	i = 1, 20, 2	Начало цикла
Предопределенный процесс		Вычисления по подпрограмме, стандартной подпрограмме
Документ	Печать x,y	Вывод, печать результатов на бумаге
Ввод-вывод	Ввод переменных	Ввод-вывод данных в общем виде
Соединитель	или	Разрыв линий потока
Пуск, остановка		Начало, конец, остановка, вход и выход в подпрограммах
Комментарий	Текст комментария	Пояснения, содержание подпрограмм, формулы[6]

Существует три основных структуры алгоритмов:

• Линейная структура - предполагает выполнение действий последовательно. Алгоритм с такой структурой не зависит от условий и происходит единожды.
• Разветвляющаяся структура – имеет логическое условие, от которого зависит, по какой ветви будет происходить в дальнейшем вычислительный процесс. Структура ветвление существует в четырех основных вариантах: если – то; если – то – иначе; выбор; выбор – иначе. Оператор выбора используется в тех случаях, когда возникает необходимость выбора альтернативы из трех возможностей и более.
• Циклическая структура – содержит многократно выполняемые участки, называемые циклами. Эта структура имеет особое значение для построения алгоритмов, т.к. только на их основе можно добиться компактной записи алгоритмов, требующих выполнения большого числа действий. При выполнении этого оператора серия, включающая одну или несколько команд, повторяется несколько раз подряд до тех пор, пока условие соблюдается. Как только условие нарушается, выполнение серии прекращается. Если условие изначально неверно, то серия не выполняется.^[7]

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

При использовании различных структур в одном алгоритме, мы получим смешанную структуру.

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

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

Таблица 2

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

Линейная структура	Ветвящаяся структура (если)	Циклическая структура (параметрический цикл)

По основной характеристике все три структуры одинаковы – все они имеют один вход и один выход.

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

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

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

Примеры трех основных структур, записанных в виде блок-схемы, представлены в таблице 2.

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

Глава 2. Сравнительный анализ основных структур алгоритмов

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

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

• быть простым для понимания, перевода в программный код и отладки;
• эффективно использовать вычислительные ресурсы и выполняться по возможности быстро.^[9]

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

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

Таким образом, будем различать временную T(n) и пространственную V(n) сложности алгоритма. Чаще при рассмотрении оценок сложности используется только временная сложность.

Временная сложность алгоритма определяется количеством входных данных. Для простоты входные данные представляются параметром n. Этот параметр пропорционален величине обрабатываемого набора данных и может обозначать:

• размер массива или файла при сортировке или поиске;
• степень полинома;
• количество символов в строке;
• другую абстрактную меру объема рассматриваемой задачи.^[10]

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

Например, если число тактов (действий), необходимое для работы алгоритма, выражается как 1,5n2 + 7n·log n + 3n + 4, то это алгоритм, для которого T(n) имеет порядок O(n2). Фактически, порядок представляет собой показатель старшей степени многочлена.

При использовании обозначения O(.), имеют в виду не точное время исполнения, а только его предел сверху — верхнюю асимптотическую границу. Если, например, алгоритму требуется время порядка O(n2), имеют в виду, что время исполнения задачи растет не быстрее, чем квадрат количества элементов. Для примера приведем числа, иллюстрирующие скорость роста для нескольких функций, которые часто используются при оценке временной сложности алгоритмов (табл. 3).

Таблица 3

Скорость роста часто используемых функций оценки

временной сложности алгоритмов

n	log n	n∙log n	n2
1	0	0	1
16	4	64	256
256	8	2 048	65 536
4 096	12	49 152	16 777 216
65 536	16	1 048 565	4 294 967 296
1 048 476	20	20 969 520	1 099 301 922 576
16775616	24	402 614 784	281 421 292 179 456

Если считать, что числа соответствуют микросекундам, то для задачи с 1048476 элементами алгоритму со временем работы O(log n) потребуется 20 микросекунд, а алгоритму со временем работы O(n2) — более 12 дней.^[11]

Если операция выполняется за фиксированное число шагов, не зависящее от количества данных, то принято писать O(1). Следует обратить внимание, что основание логарифма здесь не пишется. Причина этого весьма проста. Пусть есть O(log₂n). Но log₂n = log₃n/log₃2, а log₃2, как и любую константу, символ О() не учитывает. Таким образом, O(log₂n) = O(log₃n). К любому основанию можно перейти аналогично, а значит, и писать его не имеет смысла. Практически время выполнения алгоритма зависит не только от количества входных данных, но и от их значений, например, время работы некоторых алгоритмов сортировки значительно сокращается, если первоначально данные частично упорядочены, тогда как другие методы оказываются нечувствительными к этому свойству. Чтобы учитывать этот факт, полностью сохраняя при этом возможность анализировать алгоритмы независимо от данных, различают:

– максимальную сложность T_max (n), или сложность наиболее неблагоприятного случая, когда алгоритм работает дольше всего;

– среднюю сложность T_mid (n) – сложность алгоритма в среднем;

– минимальную сложность T_min (n) – сложность в наиболее благоприятном случае, когда алгоритм справляется быстрее всего. ^[12]

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

1) время выполнения операций присваивания, чтения, записи обычно имеют порядок O(1). Исключением являются операторы присваивания, в которых операнды представляют собой массивы или вызовы функций;

2) время выполнения последовательности операций совпадает с наибольшим временем выполнения операции в данной последовательности (правило сумм: если T₁(n) имеет порядок O(f(n)), а T₂(n) – порядок O(g(n)), то T₁(n) + T₂(n) имеет порядок O(max(f(n), g(n)) );

3) время выполнения конструкции ветвления (if-then-else) состоит из времени вычисления логического выражения (обычно имеет порядок O(1) ) и наибольшего из времени, необходимого для выполнения операций, исполняемых при истинном значении логического выражения и при ложном значении логического выражения;

4) время выполнения цикла состоит из времени вычисления условия прекращения цикла (обычно имеет порядок O(1) ) и произведения количества выполненных итераций цикла на наибольшее возможное время выполнения операций тела цикла.

5) время выполнения операции вызова процедур определяется как время выполнения вызываемой процедуры;

6) при наличии в алгоритме операции безусловного перехода, необходимо учитывать изменения последовательности операций, осуществляемых с использованием этих операции безусловного перехода.^[13]

Таблица 4

Классы сложности алгоритмов

в зависимости от функции трудоемкости

Вид f (n)	Характеристика класса алгоритмов
1	Большинство инструкций большинства функций запускается один или несколько раз. Если все инструкции программы обладают таким свойством, то время выполнения программы постоянно
log n	Такое время выполнения обычно присуще программам, которые сводят большую задачу к набору меньших подзадач, уменьшая на каждом шаге размер задачи на некоторый постоянный фактор. Изменение основания не оказывает заметного влияния на изменение значения логарифма: при n = 1 000, log10 n = 3, log2 n ≈ 10
n	Когда время выполнения программы является линейным, это обычно значит, что каждый входной элемент подвергается небольшой обработке
n log n	Время выполнения, пропорциональное n logn, возникает тогда, когда алгоритм решает задачу, разбивая ее на меньшие подзадачи, решая их независимо и затем объединяя решения
n2	Когда время выполнения алгоритма является квадратичным, он полезен для практического использования при решении относительно небольших задач. Квадратичное время выполнения обычно появляется в алгоритмах, которые обрабатывают все пары элементов данных (возможно, в цикле двойного уровня вложенности)
n3	Похожий алгоритм, который обрабатывает тройки элементов данных (наиболее часто в цикле тройного уровня вложенности), имеет кубическое время выполнения и практически применим лишь для малых задач
2n	Лишь несколько алгоритмов с экспоненциальным временем выполнения имеют практическое применение, хотя такие алгоритмы возникают естественным образом при попытках прямого решения задачи, например полного перебора[14]

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

• класс Р — класс детерминированных полиномиальных алгоритмов, функция трудоемкости которых определяется от входных параметров как O (n), O (n²), O (n³) и т. д. Примеры задач, решаемых за полиномиальное время: умножение матриц, сортировка массива;
• класс L — класс детерминированных алгоритмов, использующих дополнительно O (log n) памяти;
• класс NL — класс недетерминированных алгоритмов, использующих дополнительно O (log n) памяти. Класс L  NL. Пример задачи NL — нахождение пути в графе. Задачи класса NL обычно решаются за полиномиальное время;
• класс NP — класс недетерминированных полиномиальных алгоритмов. Задача о равенстве классов Р и NP является одной из самых актуальных задач теории алгоритмов. Примером задач NP являются задача о мешке и задача коммивояжера.^[15]

Два самых больших класса алгоритмов – это алгоритмы с повторением и рекурсивные алгоритмы. В основе алгоритмов с повторением лежат циклы и условные выражения; для анализа алгоритмов требуется оценить число операций, выполняемых внутри цикла, и число итераций цикла. Рекурсивные алгоритмы разбивают большую задачу на фрагменты и применяются к каждому фрагменту по отдельности. Такие алгоритмы называются иногда «разделяй и властвуй», и их использование может оказаться очень эффективным. Термин «разделяй и властвуй», применимо к информатике, популяризовал в своей книге «Алгоритмы: построение и анализ» Томас Кормен (Thomas H. Cormen). В процессе решения большой задачи путем деления ее на меньшие создаются небольшие, простые и понятные алгоритмы. Анализ рекурсивного алгоритма требует подсчета количества операций, необходимых для разбиения задачи на части, выполнения алгоритма на каждой из частей и объединения отдельных результатов для решения задачи в целом. Объединяя эту информацию и информацию о числе частей и их размере, можно вывести рекуррентное соотношение для сложности алгоритма. Полученному рекуррентному соотношению можно придать замкнутый вид, затем сравнивать результат с другими выражениями.

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

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

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

Глава 3. Примеры использования алгоритмов

По типу задач мы можем выделить следующие разновидности алгоритмов:

Вычислительные алгоритмы

Целью данного вида алгоритма будет вычисление из исходных данных определенного результата. Эти алгоритмы работают с простыми типами данных – числами, векторами, матрицами. Но процесс вычисления может быть как простым, быстрым, так и сложным. Кроме того, в зависимости от задачи мы можем получить как точный результат, так и приблизительный – с указанной управляющим человеком точностью вычислений.

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

Информационные алгоритмы

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

Управляющие алгоритмы

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

Любой вид алгоритма строится на трех основных структурах: линейной, ветвящейся и циклах.^[16]

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

Построим линейный алгоритм для вычисления значения переменных по заданным формулам, при заданных значениях переменных a,b,x.

А)

Б)

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

Для задания А

1. x+1 = A1
2. x+a = A2
3. x² = A3
4. sin A2 = A4
5. A3*A1 = A5
6. A²4 = A6
7. A5/b = A7
8. A7-A6 = R

Для задания Б

1. x*b=A1
2. A1/a=A2
3. x+b=A3
4. √A2 = A4
5. A²3= A5
6. cos A5=A6
7. A²6=A7
8. A4+A7=S

Запишем блок-схему для задания А: Запишем блок-схему для задания Б:

x*b=A1

Конец

Начало

Вывод S

Ввод a,b,x

Начало

Ввод a,b,x

x+1 = A1

A1/a=A2

x+a = A2

x+b=A3

x² = A3

√A2 = A4

sin A2 = A4

A²3= A5

A3*A1 = A5

cos A5=A6

A²4 = A6

A²6=A7

A5/b = A7

A4+A7=S

A7-A6 = R

Вывод R

Конец

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

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

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

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

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

Вычислим значения функции при заданных значениях переменных a, x

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

ЕСЛИ x>1 ТО ИНАЧЕ

Запишем блок-схему решения задачи с использованием блока ветвления:

Начало

Ввод a,x

да

нет

x>0 0

Вывод

Конец

Начало

Ввод a,x

да

нет

X=0 0

На ноль

делить нельзя!

Вывод Z

Конец

Условную структуру удобно использовать в случае, если мы проводим проверку вводимых данных. Например, при решении задач, требующих проверки значений входных переменных (деление на ноль и т.п.), мы можем задать условный фильтр (рис. 1).

Рисунок 1

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

Существуют две схемы циклических вычислительных процессов:

IF

Тело цикла

Нет

Да

Выход из цикла

Тело цикла

IF

Да

Нет

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

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

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

Составим алгоритм для решения задачи:

Заполнить массив X размерностью 40 простыми числами; заменить отрицательные числа в массиве нулями.

Зарисуем блок-схему:

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

Задание:

1. Заполнить двумерный массив Mas случайными простыми положительными двузначными числами;
2. Найти среднее арифметическое элементов каждой строки;
3. Найти минимальный и максимальный элемент массива.
4. Организовать удобный вывод результата работы

Нам потребуется ввести переменную массива Mas, индексы элементов массива i, j, переменные для поиска максимума и минимума max, min, а также переменную для записи значения среднего арифметического строк sred.

Данную задачу можно разделить на несколько этапов:

1. Заполнение массива
2. Поиск среднего арифметического построчно
3. Поиск минимального элемента
4. Поиск максимального элемента
5. Вывод результата в виде таблицы

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

Для того, чтобы эффективно решить эту задачу, мы можем снизить объемность нашего алгоритма, и реализуем решение через один вложенный цикл. Это сократит количество циклических структур в 5 раз (по количеству этапов решения).

Учитывая, что заполнение массива происходит автоматически, мы можем реализовать заполнение так, как нам удобно для решения задачи. В данном случае, для получения результата 1, 2 и 5 этапа, будет выгодно заполнять массив построчно. Таким образом мы сможем во вложенном цикле заполнять массив, выводить его элементы построчно, последовательно складывать элементы строки, записывая результат в переменную sred, а затем при переходе на внешний цикл производить расчет среднего арифметического, разделив сумму элементов на их количество, которое будет равно количеству итераций внутреннего цикла и хранится в переменной индекса j, а так же вывод полученного результата в конце каждой строки. Переменная sred будет обнуляться после вывода.

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

Для поиска максимума:

ЕСЛИ Mas[текущий элемент]>max ТО max=Mas[текущий элемент]

Для поиска минимума:

ЕСЛИ Mas[текущий элемент]<min ТО min=Mas[текущий элемент]

Для правильного поиска min и max мы должны присвоить им стартовые значения. Проанализировав условие задачи приходим к выводу, что элементы массива могут лежать в диапазоне от 10 до 99. Таким образом, в начале программы присвоим переменной max значение 10, а переменной min значение 99.

Итак, составим блок-схему алгоритма:

По блок-схеме напишем программу на языке Pascal с комментариями:

var i,j,max,min: byte; //выбранный тип уменьшает использование ОЗУ. Значения индексов, а также элементов массива не выходят за диапазон значений данного типа

sred: integer; //используем целочисленный тип, т.к. в переменной будет хранится только сумма элементов, и расчет конечного значения будет произведен на этапе вывода

Mas: array [0..9,0..9] of byte; //объявление массива Mas[]

begin

max:=10;//начальное значение переменной max

min:=99;// начальное значение переменной min

for i := 0 to 9 do //открываем внешний цикл перебора строк

begin

for j := 0 to 9 do //открываем вложенный цикл перебора столбцов

begin Mas[i,j]:=random(90)+10; //заполнение массива

write(Mas[i,j],' ');//вывод элементов с разделителем «пробел»

if mas[i,j]>max then max:=mas[i,j]; //поиск максимума

if mas[i,j]<min then min:=mas[i,j]; //поиск минимума

sred:=sred+Mas[i,j]; //поиск суммы элементов строки

end;

writeln('среднее арифметическое строки №',i+1,' = ',sred/(j+1)); //вывод среднего арифметического строки и переход на новую строку

sred:=0; //обнуление переменной sred

end;

writeln('максимум: ',max);//вывод максимума

writeln('минимум: ',min);//вывод минимума

end.

Результат работы программы в среде PascalABC.NET выглядит так:

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

Заключение

В данной работе было определено понятие алгоритма и его основные свойства. Были рассмотрены основные структуры алгоритмов – следование, ветвление и цикл; составлена графическая запись основных структур в виде блок-схемы.

В отдельной главе был рассмотрен вопрос анализа эффективности алгоритмов, выделены основные характеристики производительности – временная и объемная. Была дана классификация алгоритмов по сложности.

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

Библиография

1. Белов М.П. Основы алгоритмизации в информационных системах. - СПб.: СЗТУ, 2003. – 85 с.
2. Ключарев А.А., Матьяш В.А, Щекин С.В. Структуры и алгоритмы обработки данных. – СПб.: СПбГУАП, 2003. - 172 с.
3. Селиванова И.А., Блинов В.А. Построение и анализ алгоритмов обработки данных. – Екатеринбург: Изд-во Урал. ун-та, 2015. – 108 с.

1. Белов М.П. Основы алгоритмизации в информационных системах / М.П. Белов. - СПб.: СЗТУ, 2003. – С. 5-6 ↑

2. Белов М.П. Основы алгоритмизации в информационных системах. С. 5 ↑

3. Белов М.П. Основы алгоритмизации в информационных системах / М.П. Белов. - СПб.: СЗТУ, 2003. – С. 8-9 ↑

4. Селиванова И.А. Построение и анализ алгоритмов обработки данных / И.А. Селиванова, В.А. Блинов. – Екатеринбург: Изд-во Урал. ун-та, 2015. – С. 7 ↑

5. Белов М.П. Основы алгоритмизации в информационных системах / М.П. Белов. - СПб.: СЗТУ, 2003. – С. 10-11 ↑

6. Белов М.П. Основы алгоритмизации в информационных системах / М.П. Белов. - СПб.: СЗТУ, 2003. – С. 12-13 ↑

7. Белов М.П. Основы алгоритмизации в информационных системах / М.П. Белов. - СПб.: СЗТУ, 2003. – С. 31-32 ↑

8. Белов М.П. Основы алгоритмизации в информационных системах / М.П. Белов. - СПб.: СЗТУ, 2003. – С. 32 ↑

9. Селиванова И.А. Построение и анализ алгоритмов обработки данных / И.А. Селиванова, В.А. Блинов. – Екатеринбург: Изд-во Урал. ун-та, 2015. – С. 12-13 ↑

10. Селиванова И.А. Построение и анализ алгоритмов обработки данных / И.А. Селиванова, В.А. Блинов. – Екатеринбург: Изд-во Урал. ун-та, 2015. – С. 7 ↑

11. Селиванова И.А. Построение и анализ алгоритмов обработки данных / И.А. Селиванова, В.А. Блинов. – Екатеринбург: Изд-во Урал. ун-та, 2015. – С. 13-14 ↑

12. Ключарев А.А. Структуры и алгоритмы обработки данных / А.А. Ключарев, В.А. Матьяш, С.В. Щекин. – СПб.: СПбГУАП, 2003. - С. 9 ↑

13. Ключарев А.А. Структуры и алгоритмы обработки данных / А.А. Ключарев, В.А. Матьяш, С.В. Щекин. – СПб.: СПбГУАП, 2003. - С. 9-10 ↑

14. Селиванова И.А. Построение и анализ алгоритмов обработки данных / И.А. Селиванова, В.А. Блинов. – Екатеринбург: Изд-во Урал. ун-та, 2015. – С. 14 ↑

15. Селиванова И.А. Построение и анализ алгоритмов обработки данных / И.А. Селиванова, В.А. Блинов. – Екатеринбург: Изд-во Урал. ун-та, 2015. – С. 15 ↑

16. Алексеев Е.Г., Богатырев С.Д. Информатика / Е.Г. Алексеев, С.Д. Богатырев. – Саранск: Морд. гос. ун-т, 2009. – С. 6 ↑