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

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

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

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

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

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

Любой вид алгоритма строится на трех основных структурах: линейной, ветвящейся и циклах.^[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 ↑

---