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

В блок-схемах разветвленные алгоритмы изображаются так, как показано на рис. 8 [3, с. 10].

Рис.8. Полный и неполный разветвленный алгоритм

Рассмотрим пример разветвленного алгоритма.

Даны три числа а, b, с. Найти наибольшее из них.

Блок-схема алгоритма представлена на рис. 9 [3, с. 11].

Рис.9. Алгоритм поиска наибольшего из трех чисел

Пример 2. Составить алгоритм решения для функции F(x) = 1 при x > 0 и F(x) = 0 при x < 0. Блок - схема разветвляющегося алгоритма показана на рис.10 [1, с. 16].

Рис.10. Нахождение функции F

2.3 Циклический алгоритм

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

Существует два типа алгоритмов циклической структуры. На рис. 11 изображен цикл с предусловием, а на рис. 12 – цикл с постусловием [3, с. 11-12].

Рис.11. Алгоритм цикла с предусловием

Рис.12. Алгоритм цикла с постусловием

Эти циклы взаимозаменяемы и обладают некоторыми отличиями:

• в цикле с предусловием условие проверяется до тела цикла, в цикле с постусловием – после тела цикла;

• в цикле с постусловием тело цикла выполняется хотя бы один раз, в цикле с предусловием тело цикла может не выполниться ни разу;

• в цикле с предусловием проверяется условие продолжения цикла, в цикле с постусловием – условие выхода из цикла.

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

Обязательные блоки для организации цикла:

1. Установка начального значения параметра цикла.

2. Проверка условия достижения конечного значения параметра цикла.

3. Изменение параметра цикла.

Рассмотрим пример циклического алгоритма на рис 13 [3, с. 11-13]:

Рис.13. Пример циклического алгоритма

Пример 2. Составить алгоритм решения задачи вычисления N первых членов геометрической прогрессии, используя формулу b_n+1 =b_n *q для любых b и q, где n - текущий член геометрической прогрессии.

Блок-схема алгоритма решения данного примера показана в двух вариантах: с использованием цикла "ДО" (рис. 14, а) и цикла "ПОКА" (рис. 14, б) [1, с. 18].

Рис.14. Вычисление членов геометрической прогрессии

Пример циклов с неизвестным числом повторений.

Примером циклов, число повторений которых не задано, являются итерационные вычислительные процессы. В них решение задачи реализуется путем последовательного приближения к искомому результату. Процесс является циклическим, поскольку заключается в многократных вычислениях. Начальное приближение Y0 выбирается заранее или задается по определенным правилам. Заканчивается итерационное вычисление при выполнении условия |Yi -Yi-1| <d , где d - допустимая ошибка вычисления.

Типовая структура алгоритма итерационных вычислений имеет вид, показанный на рис. 15 [1, с. 19]:

Рис.15. Типовая структура алгоритма итерационных вычислений

Пример. Составить алгоритм вычисления функции y=√x c точностью d,

используя рекуррентную формулу yi+1=0.5*(x/yi +yi).

Если начальное приближение y1=x, тогда на первом цикле вычисления будем иметь y=0.5*(x/y1 +y1).

Блок - схема алгоритма решения примера 4 приведена на рис. 16 [1, с. 20]:

Рис.16. Алгоритм вычисления функции y= √x c точностью d

Сложные циклы

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

Пример. Составить алгоритм вычисления и вывод на печать функции

y = x*z / (A + B) при изменении аргументов 1< x < 10 c шагом ∆x = 2 и

1< z <4 с шагом ∆z = 0.5.

Решение данного примера показано на рис. 17.

Внутренний цикл организован по переменной z , а внешний - по переменной x . На каждом шаге изменения переменной x (переменной внешнего цикла) переменная z (переменная внутреннего цикла) проходит весь заданный диапазон изменения от 1 до 4 с шагом 0.5.

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

Первая цифра внутри фигуры (рис. 19) определяет начальное значение переменной, вторая ее конечное значение, а третья - шаг изменения переменной. По умолчанию (при отсутствии последней цифры) шаг изменения переменной принимается равным 1 [1, с. 21-22].

Рис.17. Вычисление функции y [1, с. 21]

Рис.18. Вычисление функции y (модифицированная блок-схема) [1, с. 21]

Рис.19. Упрощенная блок-схема цикла [1, с. 22]

ЗАКЛЮЧЕНИЕ

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

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

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

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

1. Аузяк А.Г., Богомолов Ю.А., Маликов А.И., Старостин Б.А. Программирование и основы алгоритмизации (учебное пособие) / А.Г. Аузяк, Ю.А. Богомолов, А.И. Маликов, Б.А. Старостин. – Казань: Изд-во Казанского национального исследовательского технического ун-та - КАИ, 2013. – 153 с.
2. Голицина О.Л., Попов И.И. Основы алгоритмизации и программирования / О.Л. Голицина, И.И. Попов – М: Форум, 2008. – 432 с.
3. Кадырова Г. Р. Основы алгоритмизации и программирования (учебное пособие) / Г. Р. Кадырова. – Ульяновск: УлГТУ, 2014. – 95 с.
4. Семакин И.Г., Шестаков А.П. Основы алгоритмизации и программирования: учебник для студ. учреждений сред. проф. образования / И.Г. Семакин, А.П. Шестаков. – М: Издательский центр «Академия», 2012, 400 с.
5. Семакин И.Г., Шестаков А.П. Основы программирования: учебник / И.Г. Семакин, А.П. Шестаков. – М: Мастерство, 2002, 432 с.