1.3. Разновидности структур алгоритмов

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

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

Пример 1.1 Найти значение функции

при значении аргумента x=1,5 и заданных а, b, с.

Очевидно, что функцию Y целесообразно вычислять в такой последовательности: предварительно введя исходные данные а, b, с и присвоив значение переменной х, вначале найдем значение выражения (ах²+b)/с, которое обозначим переменной z. и далее определим выражение arctg(+ ln z). Используя общепринятые символы блоков (рис.1.1), изобразим схему разрабатываемого алгоритма (рис. 1.2).

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

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

Рассмотрим пример разветвляющегося алгоритма с простым логическим условием.

Пример 1.2. Даны два числа а и b.

Найти

Очевидно, что для определения ветви , по которому необходимо производить процесс вычисления значения х, достаточно проверить выполнение одного из условий, например а>b. Если условие а>b не выполняется, то очевидно и без дополнительной проверки, что будет выполнено условие а < b. Следовательно, вариант схемы алгоритма будет выглядеть следующим образом (рис 1.3).

Рис 1.3. Схема простого разветвляющегося алгоритма

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

a / b, если а > 0

Пример 1.3. Даны два числа а и b. Найти х = - а - b, если а = 0.

а + b, если а < 0

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

При этом алгоритм может быть представлен в одном из двух вариантов: с разветвлением по сложному логическому условию (рис 1.4а) и с разветвлением при разложении сложного логического условия на простые (рис. 1.46).

Пример 1.4. Вычислить значение Y при заданных значениях а, х.

Рис 1.4, Схемы алгоритмов разветвляющейся структуры: а) - со сложным логическим условием; б) - при разложе­нии сложного логического условия на простые

Несмотря на то что в примере предлагаются четыре логических условия, два из которых сложные, при составлении алгоритма достаточно организовать только три простых сравнения. Остальные сравнения необязательны, поскольку соответствующие условия и так являются единственно возможными при невыполнении предложенных сравнений (рис. 1.5). Например, проверка логического условия х<=0 (блок 5) возможна только при невыполнении условия х< -2 (ветка "нет" блока 3), что в свою очередь возможно только при х>= -2.

Рис /5. Схема разветвляющегося алгоритма решения примера 1.4

Пример 1.5. Даны три неравных между собой числа а, b, с. Определить наибольшее из них.

В алгоритме (рис. 1.6) вначале сравним между собой два первых числа а и b (блок 3). Затем большее из них сравним с оставшимся третьим числом с (блок 4 или блок 5). Большее число в этом сравнении и является наибольшим из трех.

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

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

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

Пример 1.6. Заданы четыре неравные между собой величины а, b, с, d. Определить наибольшую из них.

В алгоритме (рис. 1.7) переменной max операто­ром присваивания зада­ется первоначальное значение, равное значе­нию переменной а (блок Рис 3). Если при сравнении значения переменной max со значением остальных переменных b, с, d (блоки 4,6 и 8 соответственно) найдется большее max число, то его значение станет новым значением переменной max (блоки 5, 7, 9). Блок 10 осуществляет вывод наибольшего из чисел а, b, с, d, присвоенного в качестве значения переменной max. Пример 1.7. Даны три неравных между собой числа а, b, с. Вывести эти числа на печать в порядке убывания их значений.

Из анализа возможных вариантов ответа решения поставленной задачи следует, что на первом месте может стоять любое наибольшее из трех исходных чисел. Очевидно, что на втором месте должно следовать наибольшее из двух оставшихся. Тогда возможно шесть вариантов ответа: а b с; а с b; b а с; b с а; с а b; с Ь а.

1.7. Схема алгоритма нахождения наибольшего из 4 заданных чисел

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

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

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

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

Пример 1.8. Дано натуральное число N. Найти сумму первых N членов натурального ряда.

Варианты схемы алгоритма циклической структуры решения поставленной задачи приведены на рис. 1.9. При этом в схеме на рис. 1.9а цикл организован с использованием блока модификации, а на рис. 1.96 - блока проверки условия. В обоих алгоритмах операция нахождения суммы, при предварительном обнулении значения переменной S (блок 3), повторяется N раз.

Рис. 1.9. Схема алгоритма циклической структуры для на­хождения суммы N первых членов натурального ряда:

а) — с использованием блока модификации; б) — с использо­ванием блока проверки условия

   В теле цикла использована операция присваивания S = S + I, по которой и осуществляется вычисление суммы путем прибавления к предыдущему значению переменной S всё новых значений переменной I.

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

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

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

Пример 1.9. Дан ряд натуральных чисел 1,2,3,..., ∞ и число N. Требуется найти сумму первых членов ряда. Вычисление суммы прекратить, как только ее значение будет равно или превысит заданное N.

Вариант схемы алгоритма решения задачи, включающей итерационный цикл с постусловием, приведен на рис. 1.10а. Цикл организован в виде итерационного потому, что число его повторений заранее неизвестно. В алгоритме выход из цикла или его продолжение определяется выполнением (или невыполнением) условия S>=N в блоке 6. Если условие не выполняется, то вычисление суммы продолжается путем прибавления к предыдущему значению суммы (переменной S) значения очередного члена ряда, отслеживаемого переменной цикла I. Однако приведенный алгоритм дает неверное решение при N=0, так как в этом случае не будет выполнено первое по порядку сравнение S=N=0. Правильный алгоритм решения этой задачи с использованием итерационного цикла с предусловием приведен на рис. 1.106. В этом алгоритме тело цикла расположено после проверки условия выхода из него. В нем в начале цикла осуществляется проверка S>=N (блок 5) и если N задано равным нулю, то тело цикла не будет выполняться ни разу.

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

Рис. 1.10. Схема итерационного алгоритма на­хождения суммы первых членов натурального ряда:

а) – с постусловием;

б) - с предусловием

Пример 1.10. Дано натуральное N и первый член бесконечного ряда: Y₁=1. Вычислить сумму членов бесконечного ряда, образованного по следующему рекуррентному соотношению: Y₁ =2 • Y_I-1, (то есть S = 1+2+4+8+16+...). Вычисление суммы продолжать до тех пор, пока соблюдается условие | Y₁ - Y_I-1| <N.

Схема алгоритма представлена на рис. 1.11. В задаче число Учитываемых при суммировании членов ряда заранее не задано, следовательно, применяем итерационный цикл. При решении задачи обходимся без образования одномерного массива Y,, Y₂, Y₃, ..., вычисляя в цикле только значения суммы предыдущего а и последующего b членов ряда. Как только разница между предыдущим а и последующим b членами ряда по абсолютному значению станет равна значению N или превысит его, вычисление суммы прекращаем.

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

Рис.1.11 Вариант схемы алгоритма решения примера 1.10