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

Например, необходимо найти объем цилиндра [3, с. 47]. Для решения используется линейная структура алгоритма:

алг Объем цилиндра (арг вещ r, h, рез вещ v)

нач

вещ pi = 3.1415926

ввод r, h

v = 2* pi* r* r* h

вывод v

кон

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

Алгоритмы разветвляющейся или циклической структуры используются при решении задач, где необходимо проанализировать условия, и только потом следующее действие выполняется. Это более сложные задачи. В их структуре обязательно присутствует логический блок. В разветвляющемся алгоритме логический блок имеет один вход и два выхода: ветвь «да» и ветвь «нет» [8, с. 14]. А для задач, где необходимо получить решение путем подбора верного значения (истины), путем команд повторения, используется циклический алгоритм.

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

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

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

1. Рассмотреть А как первое число, В как второе. Перейти к пункту 2.
2. Сравнить первое и второе число. Если они равны, перейти к пункту 5. Если нет, перейти к пункту 3.
3. Если первое число меньше второго, то поменять их местами. Перейти к пункту 4.
4. Вычесть из первого числа второе и рассмотреть полученную разность как первое число. Перейти к пункту 2.
5. Рассмотреть перовое число как результат. Закончить выполнение алгоритма.

Структура алгоритма в виде блок-схемы изображена на рис. 9 [4, с. 18].

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

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

Допустим ситуацию, перед выходным днем папа сказал своему сыну: «Давай спланируем свой завтрашний день. Если будет хорошая погода, то проведем день в лесу. Если же погода будет плохая, то сначала займемся уборкой квартиры, а во второй половине дня сходим в зоопарк». Что получится на выходе блок-схемы (рис. 10) [1, с. 18], если:

---

а) погода хорошая;

б) погода плохая?

Для определения результата воспользуемся трассировочными таблицами (а, б):

а) погода хорошая:

Шаг	1
Исходные значения	Погода хорошая
Результат выполнения	Прогулка в лесу
Вывод значений	Прогулка в лесу

б) погода плохая:

Шаг	1
Исходные значения	Погода плохая
Результат выполнения	Уборка квартиры Поход в зоопарк
Вывод значений	Поход в зоопарк

Рисунок 10. Пример разветвляющегося алгоритма

Наиболее простым способом отслеживания действий, предписанных алгоритмом, является его пошаговое исполнение.

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

1) пошаговое выполнения каждого действия с записью результата в строку таблицы;

2) выполнение группы действий с записью результатов в одну строку для всей группы.

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

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

Необходимо поменять значение двух переменных А и В. команды и результаты выполнения заносятся в таблицу (табл. 3)

Таблица 3. Трассировочная таблица

команда	А	Б
А: = 3	3
В: = 5		5
А: = В	5
В: = А		5
результат	5	5

По результату задачи видно, что она не решена, т.к. значение 3, находящееся в переменной А, утеряно. Его необходимо сохранить, а затем присваивать переменной А значение переменной В. Для временного хранения нужного значения вводится дополнительная переменная С, она называется буферной (табл. 4).

---

Таблица 4. Трассировочная таблица с дополнительной переменной

команда	А	Б	С
А: = 3	3
В: = 5		5
С: = А			3
А: = В	5
В: = С		3
результат	5	3

Теперь требуемый результат получен.

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

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

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

Заключение

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

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

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

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

Раскрывают понятие алгоритма его свойства. Ими являются: дискретность (прерывность, раздельность), определенность, результативность (конечность), массовость, элементарность или понятность, эффективность.

---

Решение задач на компьютере проходи определенные этапы:

- постановка задачи;

- математическая формализация;

- построение алгоритма;

- составление программы на языке программирования;

- отладка и тестирование программы.

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

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

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

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

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

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

Разветвляющийся алгоритм – это алгоритм, в котором то или иное действие выполняется после анализа условия. В структуре такого алгоритма есть две ветви «да» и «нет».

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

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

Список использованных источников

1. Алгоритмы. Основные алгоритмические конструкции [Текст]: сб. задач / сост. С.А. Рогозин. – Челябинск: Изд-во Челяб. гос. пед. ун-та, 2008. – 42 с.
2. Алгоритмы и структуры данных: учебное пособие / О.Б. Фофанов; Томский политехнический университет. – Томск: Изд-во Томского политехнического университета, 2014 – 126 с.
3. Белов М.П. Основы алгоритмизации в информационных системах: Учеб. пособие. – СПб.: СЗТУ, 2003. – 85 с.
4. Голицына О.Л., Попов И.И. Основы алгоритмизации и программирования: учеб. пособие. – 3-е изд., испр. и доп. – М.: ФОРУМ, 2008. – 432 с.
5. Калмыкова Е. А.. Информатика. - 2012. [Электронный ресурс] URL // https://lawbooks.news/informatika_960/informatika501.html
6. Основы алгоритмизации и программирования: учебное пособие /

---