Алгоритмизация основных видов вычислительных процессов

В соответствии с наличием в алгоритмах управляющих структур композиции, альтернативы и итерации алгоритмы вычислительных процессов классифицируют на:

· линейный;

· ветвящийся;

· циклический.

Линейным называется такой вычислительный процесс, при котором все этапы решения задачи выполняются в естественном порядке следования записи этих этапов

Примером линейной алгоритмической структуры может служить алгоритм решения следующей задачи.

З адача 1. Вычислить и вывести результаты вычисления выражения

На рис. 6.2 представлена блок-схема алгоритма решения этой задачи.

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

Блоки 1 и 5 служат соответственно для обозначения начала и окончания вычислительного процесса.

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

Для того, чтобы можно было получить результат, который по условию задачи 1 должен располагаться в области памяти Y, необходимо до выполнения расчетов поместить числовые данные в области памяти a и b. Для указания процесса ввода данных в схеме используется блок 2. Процесс получения результата вычислений описывается в блоке 3.

Начало ввод a, b a²+b² y = 100 вывод y конец

Рис. 6.2. Блок-схема алгоритма решения задачи 1.

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

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

В качестве примера ветвящейся алгоритмической структуры рассмотрим процесс вычисления выражения задачи 2:

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

Блок-схема решения задачи 2 показана на рис.6.3.

Рассмотрим особенности построения этой схемы алгоритма. Блоки 3,4,5,6 представляют единую конструкцию “альтернатива“. Начинается эта конструкция с блока 3 (блока “решения”), из которого выходят две ветви алгоритма (два плеча альтернативы), определяющие отдельные направления обработки информации.

Блоки 4 и 5 расположены на ветви “ДА”, а блок 6 - на ветви “НЕТ”. Для данной алгоритмической структуры характерно, что в любой момент ее реализации осуществляется обработка только по какой - либо одной из ветвей. Общий вид управляющей конструкции “ветвление” приводится на рис. 6.4а. В некоторых случаях обработка может выполняться только по одной из веток, тогда конструкция “ветвление” является неполной (рис. 6.4б).

Рис. 6.3. Блок-схема алгоритма решения задачи 2.


Рис. 6.4. Управляющая конструкция: ветвление

Ветвление - это структура, обеспечивающая выбор между альтернативами. Альтернатив может быть больше двух, в этом случае из блока решения указывают несколько выходов: три (рис. 6.5a) или больше.



Рис. 6.5. Управляющая конструкция “ветвление” на множество веток – многоальтернативный выбор

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

Циклом называется многократно повторяемый участок вычислений

В алгоритмизации выделяют несколько основных видов циклов. Их классификация представлена на рис. 6.6.

Рассмотрим принцип работы цикла с параметром на примере задачи 3.

Задача 3. Получить результаты расчетов по формуле

при значениях - 5 <= a <= 5 с шагом +1

Блок - схема алгоритма решения задачи 3 представлена на рис. 6.7.

1 начало ввод b a = - 5 (a+b)² y = 1000 вывод y a = a + 1 да 7 a £ 5 нет конец Рис. 6.7. Блок-схема алгоритма решения задачи 3.

На схеме можно выделить компоненты, характерные для цикла с параметром. К таким компонентам относятся: 1. наличие стрелки возврата (к блоку 4); 2. наличие трех характерных блоков: · блок (процесс), в котором параметр цикла принимает начальное значение а= - 5 (в блоке 3); · блок (процесс), в котором параметр цикла изменяет свое значение на определенную величину a = a +1 (в блоке 6); · блок (решение), в котором параметр цикла сравнивается с последним возможным значением а<=5 (в блоке 7).

Три блока (3,6,7) называются заголовком цикла, а блоки (4 и 5), расположенные между блоками заголовка цикла, образуют тело цикла.

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


Рис. 6.8. Управляющая конструкция: цикл с параметром.

Рассмотрим использование цикла с предусловием при решении задачи 4, в которой требуется вывести все значения x >1, причем каждое последующее значение x получается делением предыдущего пополам.

Схема решения этой задачи приведена на рис.6.9. На этой схеме можно выделить условие, остающееся истинным при выполнении цикла (блок 3). Такое условие называется инвариантом цикла. Блоки 4 и 5 представляют тело цикла. Управляющая конструкция “цикл с предусловием” приведена на рис. 6.10. Она может быть записана двумя способами. В блок-схеме на рис. 6.10б для записи цикла использованы блоки “границы цикла”. Использование этих блоков целесообразно при записи алгоритмов решения сложных задач, использующих в вычислительном процессе много разных циклов, в том числе и вложенных друг в друга. При составлении алгоритмов решения простых задач будем использовать способ записи цикла, приведенный на рис. 6.10а.

1 начало ввод х да 3 нет x >1 4 6 вывод конец x x = x / 2
Рис. 6.9. Блок-схема алгоритма решения задачи 4 с использованием цикла с предусловием.

Рис. 6.10. Управляющая конструкция: цикл с предусловием.

Цикл с предусловием является циклом “пока” и в ряде случаев может быть не выполнен ни разу, что должно соответствовать задуманному алгоритму. Так например, если при решении задачи 4 (см. рис. 6.9) в качестве начального значения x мы введем значение 0.9, то тело цикла (4 и 5 блоки) не выполнится ни разу.

Рассмотрим использование цикла с постусловием при решении предыдущей задачи 4.

Схема решения этой задачи приведена на рис.6.11.

Рис. 6.11. Блок-схема алгоритма решения задачи 4 с использованием цикла с постусловием.

На этой схеме можно выделить условие, остающееся истинным при выполнении цикла (блок 5), инвариант цикла. Блоки 3 и 4 представляют тело цикла. В общем виде управляющая конструкция “цикл с постусловием” приведена на рис. 6.12.

Цикл с постусловием является циклом “до” и отличается от рассмотренных ранее видов циклов тем, что выполнится хотя бы один раз.


Рис. 6.12. Управляющая конструкция: цикл с постусловием

Так например, если при решении задачи 4 (см. рис.6.11) в качестве начального значения x мы введем значение 0.9, то тело цикла (3 и 4 блоки) выполнится один раз обязательно.