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

Содержание:

ВВЕДАНИЕ

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

Объектом исследования данной курсовой работы является алгоритмы.

Предметом исследования данной курсовой работы являются основные алгоритмические структуры.

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

Задачами данной курсовой работы являются:

Во-первых, рассмотреть определение алгоритма, его свойства и способы записи.

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

В-третьих, привести примеры использования данных структур алгоритмов на языке Pascal как по отдельности, так и всех вместе на языке C++.

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

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

В качестве источников для данной курсовой работы были использованы учебные пособия таких авторов как Голиков В.А., Макаров В.Л., Кирнос В.Н., Белов М.П., Кадырова Г.Р.

В качестве алгоритмического языка был выбран Pascal и С++, а в качестве сред программирования были выбраны среды PascalABC.NET и Arduino ide (так как у меня имеются роботы, собранные на Arduino, их мы и будем программировать).

Теоретическая часть

1.1. Понятие алгоритма, его свойства и способы записи

Что такое алгоритм? Алгоритмом называется строго определенная последовательность действий, определяющих процесс перехода от исходных данных к искомому результату [3, Стр.8]. Термин «алгоритм» происходит от латинской формы имени среднеазиатского математика Аль-Хорезми – Algorithmi [4, Стр.8]. Алгоритм – это понятие, которое является основным в программировании, информатике, а также математике.

Алгоритм обладает характерно определённым набором свойств. К таким свойствам относятся дискретность, результативность, детерминированность (или же однозначность), массовость и конечность. Разберём эти свойства:

1. Дискретность (от лат. discretus — разделенный, прерывистый) – это разбиение алгоритма на ряд отдельных законченных действий (шагов).
2. Детерминированность (от лат. determinate — определенность, точность) – любое действие алгоритма должно быть строго и недвусмысленно определено в каждом случае.
3. Конечность – каждое действие в отдельности и алгоритм в целом должны иметь возможность завершения.
4. Массовость – один и тот же алгоритм можно использовать с разными исходными данными.
5. Результативность – алгоритм должен приводить к достоверному решению [1, Стр.4-5].

Как записать алгоритм? Существует несколько способов это сделать. Наибольшее распространение получили следующие способы: графическая (блок-схема), словесная и псевдокоды. В данной курсовой работе будет использована в примерах графическая запись в виде блок-схем.

Словесный способ записи алгоритмов представляет собой последовательное описание основных этапов обработки данных и задаётся в произвольном изложении на естественном языке [5, Стр.10]. Например, любой прибор бытовой техники (утюг, электропила, и т.п.) имеет инструкцию по эксплуатации, т.е. словесное описания алгоритма, в соответствии которому данный прибор должен использоваться. Никаких правил составления словесного описания не существует. Запись алгоритма осуществляется в произвольной форме на естественном, например, русском языке. Этот способ описания не имеет широкого распространения, так как строго не формализуем (под «формальным» понимается то, что описание абсолютно полное и учитывает все возможные ситуации, которые могут возникнуть в ходе решения); допускает неоднозначность толкования при описании некоторых действий; страдает многословностью.

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

Блок-схема алгоритма – это графический способ записи алгоритма, представляющий собой систему определённым образом связанных блоков, изображаемых в виде плоских геометрических фигур [7, Стр.9]. Этот способ имеет ряд преимуществ. Благодаря наглядности, он обеспечивает «читаемость» алгоритма и явно отображает порядок выполнения отдельных команд. В блок-схеме каждой формальной конструкции соответствует определенная геометрическая фигура или связанная линиями совокупность фигур. Вот простой пример элементов блок-схемы (Рис.1):

Рис.1

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

Программа — это описание структуры алгоритма на языке алгоритмического программирования.

Подводя итог, можно выделить следующее моменты:

1. Понятие алгоритма. Алгоритм – это строго определенная последовательность действий, определяющих процесс перехода от исходных данных к искомому результату.
2. У алгоритма есть свойства. Это дискретность, результативность, детерминированность, массовость и конечность.

3. Существует несколько способов записи алгоритмов. Наибольшее распространение получили следующие способы: графическая (блок-схема), словесная и псевдокоды.

4. Самая простая, понятная, универсальная и наглядная запись алгоритма – это блок-схема.

1.2. Основные структуры алгоритмов, их сравнительный анализ

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

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

Линейные алгоритмы описывают линейный вычислительный процесс, этапы которого выполняются однократно и последовательно один за другим [8, Стр.6]. Линейные алгоритмы принято называть также следованием. Простой пример линейного алгоритма (Рис.1):

Рис.1

Разветвляющийся алгоритм описывает вычислительный процесс, реализация которого происходит по одному из нескольких заранее предусмотренных направлений. Направления, по которым может следовать вычислительный процесс называются ветвями. Выбор конкретной ветви вычисления зависит от результатов проверки выполнения некоторого логического условия. Результатами проверки являются: «истина» (да), если утверждение выполняется, и «ложь» (нет), при невыполнении условия [8, Стр.6]. Простой пример разветвляющегося алгоритма (Рис.2):

Рис.2

Разветвляющийся алгоритм может быть двух видов. Это полный и неполный (Рис.3):

Рис.3

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

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

Алгоритм циклической структуры – алгоритм, содержащий многократно выполняемые участки вычислительного процесса, называемые циклами. Если алгоритм содержит цикл, внутри которого размещен один или несколько других циклов, то такой алгоритм называется алгоритмом со структурой вложенных циклов [2, Стр.4].

Различают несколько видов алгоритмов циклической структуры. Прежде всего это цикл «до», цикл «пока». Существует еще одна важная разновидность цикла: цикл по счетчику. Для него существует специальное обозначение и специальный оператор в различных алгоритмических языках программирования (оператор цикла). Для организации цикла по счетчику используется управляющая переменная цикла, изменяющаяся в заданных пределах с постоянным шагом [6].

Цикл «до» и цикл «пока» различаются тем, что в одном цикле функциональный блок размещён до проверки выполнения условия, а в другом после. Иное название цикла «пока» – это цикл с предусловием, а иное название цикла «до» - это цикл с постусловием [7, Стр.11-12]. Вот простые примеры циклов «до» и «пока» (Рис.4):

Рис.4

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

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

Примером использования циклов, число повторений которых не задано, могут послужить интерационные вычислительные процессы. Они реализуют решение задачи через последовательное приближение к цели (искомому результату). Процесс заключается в многократных вычислениях и является циклическим. Начальное приближение Yo выбирается заранее или задаётся по определённым правилам. Заканчивается итерационное выражение при выполнении условия Yi-Yi-1 ≤d (где d – это допустимая ошибка вычисления) [8, Стр.8].

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

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

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

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

В некоторых случаях стремление во что бы то ни стало остаться в рамках структурного подхода приводит к необоснованному усложнению программы и потере ее наглядности и естественности. Если учесть, что структурное программирование имеет целью не подчинить программы каким-то правилам, а сделать их более удобными для восприятия, то в ряде случаев оказывается целесообразным отдать предпочтение ясности и естественности программы [6].

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

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

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

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

Подводя итог, можно выделить следующее моменты:

1. Выделяют три вида структур: линейная (следование), разветвляющаяся и циклическая.
2. Линейные алгоритмы описывают линейный вычислительный процесс, этапы которого выполняются однократно и последовательно один за другим.
3. Разветвляющийся алгоритм описывает вычислительный процесс, реализация которого происходит по одному из нескольких заранее предусмотренных направлений.
4. Алгоритм циклической структуры – алгоритм, содержащий многократно выполняемые участки вычислительного процесса, называемые циклами.
5. Все перечисленные структуры имеют один вход и один выход. Их всех также можно соединить друг с другом в любых последовательностях. Любая структура может содержать в качестве одного из блоков любую структуру другого вида.

2. Практическая часть

2.1. Использование линейной структуры на алгоритмическом языке Pascal

Возьмём для примера простую и наглядную задачу. Требуется сложить два любых простых числа и получить результат. Составим блок схему для данного алгоритма (Рис.5):

Рис.5

Собственно, сам алгоритм в Pascal:

program sum;

var

a,b,s:integer;

begin

writeln('Нахождение суммы чисел ');

write('Введите первое число ');readln(a);

write('Введите второе число ');readln(b);

s:= a+b;

writeln('Сумма чисел = ', s);

end.

Выполнение алгоритма в среде PacalABC.NET (Рис.6):

Рис.6

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

2.2. Использование разветвляющейся структуры алгоритма на языке Pascal

Теперь, для примера, рассмотрим такую задачу. Эта задача является классической в своём роде. Требуется решить квадратное уравнение D = b² - 4ac. Составим блок схему для данного алгоритма (Рис.7):

Рис.7

Собственно, сам алгоритм в Pascal:

program ifthenelse;

var

a,b,c,d,x1,x2:real;

Begin

writeln('Решение квадратных уравнений ');

writeln('Введите коэффициенты квадратного уравнения ');

write('a = '); readln (a);

write('b = '); readln (b);

write('c = '); readln (c);

d:= b*b - 4*a*c;

if d < 0 then writeln('Корней нет')

else

begin

x1:=(-b + sqrt(d))/(2*a);

x2:=(-b - sqrt(d))/(2*a);

writeln(' x1= ',x1);

writeln(' x2= ',x2);

end;

end.

Выполнение алгоритма в среде PacalABC.NET (Рис.8):

Рис.8

2.3. Использование циклической структуры на языке Pascal

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

Собственно, сам алгоритм в Pascal:

program fortodo;

var

a,i,max:integer;

begin

writeln('Нахождение наибольшего числа ');

writeln('Введите 10 целых чисел ');

for i:=1 to 10 do

begin

readln(a);

if i = 1 then max:= a;

if a > max then max := a;

end;

writeln('Наибольшее число = ', max);

end

Выполнение алгоритма в среде PacalABC.NET (Рис.9):

Рис.9

2.4 Использование нескольких разных структур в одном алгоритме на языке C++ в среде разработки Arduino ide

Сформулируем задачу. Требуется, чтобы робот двигался по треку из чёрной линии. Оговорюсь сразу, что блок схему для данной задачи я составлять не буду потому, что она получилась бы чересчур громоздкой и потеряла бы свою наглядность. Для удобства я всё закомментировал. Сам алгоритм при этом является полностью рабочим и готовым к использованию в среде Arduino.

Собственно, сам алгоритм движения робота:

int r = 24; //Вводим переменную для определения состояния массива ir датчиков (датчики, отвечающие за ориентацию относительно линии)

int rm = 2; //Вводим переменную предыдущего состояния предыдущего состояния массива ir датчиков

int v = 140; //Максимальная скорость движения (до 255)

int vl = v; //Скорость левого двигателя

int vr = v; //Скорость правого двигателя

int v0 = 0; //минимальная скорость движения

int v1 = int(v*0.515); //скорость умножается на коэффициент квадратичной зависимости

int v2 = int(v*0.699);

int v3 = int(v*0.821);

int v4 = int(v*0.903);

int v5 = int(v*0.958);

int v6 = int(v*0.989);

int v7 = int(v*1); //Максимальная скорость движения

void detect(){ //Функция формирует значения переменной r (состояния массива ir датчиков)

r=0;

if (analogRead(A7) > 1000) r=r+1; //Датчик находится над чёрной линией

if (analogRead(A6) > 1000) r=r+2; //Датчик находится над чёрной линией

if (analogRead(A5) > 1000) r=r+4; //Датчик находится над чёрной линией

if (analogRead(A4) > 1000) r=r+8; //Датчик находится над чёрной линией

if (analogRead(A3) > 1000) r=r+16; //Датчик находится над чёрной линией

if (analogRead(A2) > 1000) r=r+32; //Датчик находится над чёрной линией

if (analogRead(A1) > 1000) r=r+64; //Датчик находится над чёрной линией

if (analogRead(A0) > 1000) r=r+128; //Датчик находится над чёрной линией

}

void touchon(){

while (digitalRead(2) != HIGH); //Включение сенсорной кнопки (запуск движения робота)

}

void setup() {

pinMode(2, INPUT);//touch Устанавливает режим работы заданного входа (2 pin)

pinMode(5, OUTPUT); //Устанавливает режим работы заданного выхода(5 pin) левый двигатель

pinMode(6, OUTPUT); //Устанавливает режим работы заданного выхода(6 pin) правый двигатель

touchon();

}

void loop() {

detect(); //проверка датчиков массива ir, и включение двигателей в соответствии с значением переменной r

if (r == 0 && rm == 1) {vl = v0; vr = v7;} //Возвращение на линию, если линия находится с левой стороны

if (r == 1) {vl = v0; vr = v7;}

if (r == 3) {vl = v1; vr = v7;}

if (r == 2) {vl = v2; vr = v7;}

if (r == 6) {vl = v3; vr = v7;}

if (r == 4) {vl = v4; vr = v7;}

if (r == 12) {vl = v5; vr = v7;}

if (r == 8) {vl = v6; vr = v7;}

if (r == 24) {vl = v7; vr = v7;}

if (r == 16) {vl = v7; vr = v6;}

if (r == 48) {vl = v7; vr = v5;}

if (r == 32) {vl = v7; vr = v4;}

if (r == 96) {vl = v7; vr = v3;}

if (r == 64) {vl = v7; vr = v2;}

if (r == 192){vl = v7; vr = v1;}

if (r == 128){vl = v7; vr = v0;}

if (r == 0 && rm == 128) {vl = v7; vr = v0;} //Возвращение на линию, если линия находится с правой стороны

analogWrite(5, vl); //Задаётся скорость левого двигателя

analogWrite(6, vr); //Задаётся скорость правого двигателя

if (r != 0) rm = r;

}

Алгоритм движения робота в среде Arduino ide (Рис.10):

Рис.10

Ir датчики (Рис.11):

Рис.11

Движение робота по треку (Рис.12):

Рис.12

Как мы можем наблюдать, в этом алгоритме используются все три основные структуры алгоритмов. Чётко видно, что внутри циклической структуры присутствует такая структура как ветвление. Можно сделать вывод, что в больших и сложных алгоритмах используется всегда несколько структур. Исходя из своего опыта работы с Arduino могу сказать, что в нём практически всегда, за редким исключением, используются циклы.

ЗАКЛЮЧЕНИЕ

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

Во-первых, мы рассмотрели определение алгоритма, его свойства и способы записи. Алгоритмом называется строго определенная последовательность действий, определяющих процесс перехода от исходных данных к искомому результату [3, Стр.8]. Алгоритм обладает определёнными свойствами. К ним относятся дискретность, детерминированность, конечность, массовость и результативность. Существует несколько способов записи алгоритмов. Наибольшее распространение получили следующие способы: графическая (блок-схема), словесная и псевдокоды. Самая простая, понятная, универсальная и наглядная запись алгоритма – это блок-схема.

Во-вторых, перечислили основные структуры алгоритмов, дали им определения и провели сравнительный анализ. В научной и учебной литературе различают три вида структур: линейная, разветвляющаяся и циклическая. Линейные алгоритмы описывают линейный вычислительный процесс, этапы которого выполняются однократно и последовательно один за другим [8, Стр.6]. Линейные алгоритмы принято называть также следованием. Разветвляющийся алгоритм описывает вычислительный процесс, реализация которого происходит по одному из нескольких заранее предусмотренных направлений. Алгоритм циклической структуры – алгоритм, содержащий многократно выполняемые участки вычислительного процесса, называемые циклами. Если алгоритм содержит цикл, внутри которого размещен один или несколько других циклов, то такой алгоритм называется алгоритмом со структурой вложенных циклов [2, Стр.4]. Ветвление в алгоритме используется тогда, когда требуется очередную команду в зависимости от условия. Цикл в алгоритме задействуется тогда, когда есть действия, которые требуется выполнить несколько раз. Следование в алгоритме применяется тогда, когда требуется выполнить простое действие без условий и без повторений.

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

В-третьих, привели примеры использования данных структур алгоритмов на языке Pascal как по отдельности, так и всех вместе на языке C++.

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

1. Алгоритмизация. Введение в язык программирования С++: учебное пособие / И.Е. Белоцерковская, Н.В. Галина, Л.Ю. Катаева. – М.: Национальный Открытый Университет «ИТУИТ», 2016. –196с.
2. Основы алгоритмизации и программирования: Метод. указ. / Сост.: И.П. Рак, А.В. Терехов, А.В. Селезнев. - Тамбов: Изд-во Тамб. гос. техн. ун-та, 2004. -24с.
3. Основы алгоритмизации и программирования: учеб. пособие / Т.А. Жданова, Ю.С. Бузыкова. – Хабаровск: Изд-во Тихоокеан. гос. ун-та, 2011. -56с.
4. Кадырова Г.Р. Основы алгоритмизации и программирования: учебное пособие. – Ульяновск: УлГТУ, 2014. -95с.
5. Белов М.П. Основы алгоритмизации в информационных системах: Учеб. Пособие. – СПб.: СЗТУ, 2003 -85с.
6. Голиков В.А. Теория программирования. / Московская финансово-промышленная академия. – М., -48с.
7. Кирнос В.Н. Информатика II. Основы алгоритмизации и программирования на языке C++: учебно-методическое пособие Эль Контент, 2013. -160с.
8. Макаров В.Л. Программирование и основы алгоритмизации.: учеб. пособие – СПб.: СЗТУ, 2003. -110с.