Линейная структура алгоритмов

Под понятием «действие», можно понимать любую операцию. Если это операция в области математики, то это может быть какая либо формула, если это операция в жизни человека, то это какое либо его действие. Например положить монету в телефон-автомат это действие или вычислит выражение c=a+b это тоже действие. Рассмотрим структуру алгоритма вычисления выражения C=A+B, приведенную на рисунке 16.

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

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

Для более детального понимания шага, классифицируемого как действие, рассмотрим структуру алгоритма, состоящую не из одного, а из двух последовательных действий. Для примера возьмем следующую последовательность вычислений: C=A+B, E=C*D, графическое представление алгоритма которой представлено на рисунке 17. Проанализируем наши исходные данные. В первом выражении объекты(в данном случае числа) являющиеся исходными данными имеют символическое представление A и B, во втором выражении исходные данные имеют символическое представление C и D, однако объект, имеющий символическое представление C является результатом первого выражения, а соответственно не является исходными данными для алгоритма в целом. Следовательно исходными данными алгоритма в целом являются объекты, имеющие символическое представление A, B и D. Теперь разберемся с результатами работы алгоритма. В первом выражении результатом работы является объект, имеющий символическое представление C, а во втором объект, именуемый как E, однако объект C, является промежуточным результатом работы алгоритма. Отсюда делаем вывод, что результатом работы алгоритма является объект с символическим именем E. И последним этапом, идет анализ шагов, которые необходимо проделать для получения конечного результата. В нашей задачи предусмотрено два математических выражения, это C=A+B и E=C*D. Соответственно у нас должно быть два последовательных шага типа «действие» первый это C=A+B, а второй E=C*D. Обращаемся к общей структуре алгоритма, описывающий любой процесс. В блок «ввод данных» подставляем символические представления объектов, используемых в качестве исходных данных задачи это A, B и D, в качестве «процесса» вводим два последовательных действия это C=A+B и E=C*D. И наконец в блок «результаты» подставляем символическое представление результирующих объектов, в нашем случае это E. На этом процесс построения алгоритма решения задачи можно считать завершенным. Структуры алгоритмов, имеющие только последовательные действия имею общее название - линейные алгоритмы.

Структура развилки

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

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

Итак начинаем строить алгоритм решения поставленной задачи, рисунок 18. За основу как обычно берем общую структуру алгоритма, в блок «ввод данных» вводим символическое представление объектов, определенных как исходные данные, в нашем случае это A и B. Далее идет блок выполнения алгоритма. Поскольку поставленная задача может иметь два пути решения, вводим в блок процесса структуру развилки, и записываем в нее условие, которое является причиной различных путей решения, в нашем случае это A<B.Теперь у нас получилось два возможных пути решения, в случае выполнения условия, мы можем организовать один вычислительный процесс, а в случае его невыполнения другой, так и поступаем в случае выполнения условия организуем процесс, в котором будет выполняться шаг, выполняющий действие C=A, а в случае его невыполнения шаг на котором выполняется выражение C=B. После выполнения одного из возможных действий мы объединяем пути и организуем вывод результатов, для этого записываем в блок «результат» символическое название объекта, являющегося результирующим, в нашей задаче это объект C. На этом процесс построения алгоритма решения задачи можно считать завершенным.

Возможны варианты задач, в которых используется структура развилки, не имеющая шагов, в случае невыполнения условий, например: C=A+B, если C<10, то C=C+10, графическое представление алгоритма приведено на рисунке 19. Как и в предыдущих примерах, определяемся с исходными данными, здесь они имеют символические названия A и B, и с результатами работы алгоритма, это объект, имеющий символическое название C. Теперь рассмотрим непосредственно процесс выполнения алгоритма. У нас имеется два выражения, это C=A+B и C=C+10, однако, первое выражение выполняется всегда, а второе, только при определенных исходных данных, в нашем случае условием C<10. Следовательно, нам необходимо внедрить развилку, но с одним условием, что дополнительный шал алгоритма, появляется только при выполнение условия развилки. В случае его невыполнения, дополнительные шаги не предусматриваются. Итак, анализ задачи проведен, теперь обращаемся к общей структуре алгоритма. В блок «ввод данных», как и в предыдущих примерах вносим список символических представлений объектов, являющихся исходными данным, в блок процесса, первым шагом, вычисление выражения C=A+B, далее идет блок развилки C<10, в случае выполнения которого, вводим дополнительный шаг C=C+10, и последним нашим действием, будет запись в блок «результаты» символического представления результатов работы алгоритма, в нашем случае это объект C. Процесс разработки алгоритма завершен.

Общая структура алгоритма, использующего условное определение пути решения приведена на рисунке 20.

Структура цикла

Очень часто в жизни встречаются повторяющиеся процессы, тое есть процессы, состоящие из определенных шагов, повторяющиеся до тех пор, пока не выполнится какое либо условие. Так например, повторять набор номера телефона, до тех пор, пока не будет установлено соединение. Различаются три основных вида циклических процессов. Первое, это циклический процесс со счетчиком.. Этот вид циклического процесса подразумевает повторение одних и тех же операций, определенное число раз. Например, телефонный номер состоит из 10 цифр, то есть для набора телефонного номера, нам необходимо ввести последовательность из 10 цифр. Получается, что для набора номера телефона, мы используем цикл со счетчиком, то есть по очереди набираем цифры с первой по десятую. Рассмотрим простой арифметический пример, вычисление суммы чисел последовательности M размерности N, рисунок 21. Как и в предыдущих примерах сначала определяемся с исходными данными. В данной задаче первым делом определяемся с исходными данными. В данном случае, это размерность N и сама последовательность M. И с результатами работы алгоритма. В данном случае это сумма S. Далее непосредственно с процессом, выполняемым внутри алгоритма. Для определения суммы всех элементов какой либо последовательности нам необходимо их всех сложить. Для складывания всех элементов любой последовательности M необходимо перебрать их всех. Для перебора всех элементов любой последовательности необходимо организовать цикл со счетчиком. Счетчик в данном случае необходим для определения текущего номера элемента, а так же определения конца последовательности, и при каждом повторении цикла прибавлять значение элемента к символическому объекту, определяющему сумму. Кроме того, поскольку мы определяем сумму элементов, необходимо начальное значение символического объекта S приравнять нулю, поскольку при определении суммы цифра «0» не меняет результата. Общая структура цикла со счетчиком приведена на рисунке 22.

Второй вид циклического процесса, это циклический процесс с предусловием. Этот вид циклического процесса применяется в ситуациях, когда процесс, повторяемый в цикле выполняется только в случае выполнения условия, причем перед началом цикла проверяется истинность этого условия. Цикл со счетчиком является частным случаем цикла с предусловием, однако в структуре цикла со счетчиком, за ранее известно сколько раз будет повторен процесс, а в общем случае цикла с предусловием нет. Цикл с предусловием, может не выполнится ни одного раза, если заранее заданы параметры невыполнимого условия, например, если телефон работает, то набирать номер пока не произойдет соединение. В этом примере видно, что для выполнения цикла должны выполниться условия «телефон работает» и «нет соединения», то есть если телефон не работает или соединение уже установлено цикл не выполниться ни одного раза. Рассмотрим алгоритм включающий в себя цикл с предусловием на примере. Найти сумму цифр от A_нач до A_кон с шагом dA, рисунок 23. Исходными данными для построения алгоритма решения задачи являются A_нач, A_кон и dA. Результатом работы алгоритма будет являться сумма, придадим ей символическое название S. Для решения этой задачи нам необходимо сложить все числа, которые входят в промежуток от A_нач до A_кон с шагом dA, то есть на первом шаге мы присвоим символическому объекту значение ноль S=0, на втором шаге мы прибавим к S=A_нач, далее S=S+dA,…, S=S+dA до тех пор, пока A_нач+n*A будет меньше или равно A_кон. Для того, чтобы не повторять одну и туже операцию некоторое количество раз и организуется цикл с предусловием, который будет выполнять этот процесс автоматически.

При выполнении циклического процесса, сначала проверяется условие, и если исходные данные заданы таким образом, что A_нач заранее больше A_кон, то при таких исходных данных процесс внутри цикла не выполнится ни разу. Общая структура алгоритма организации цикла с предусловием приведена на рисунке 24.

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