Виды алгоритмов

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

Линейный

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

Рассмотрим простой пример линейного алгоритма.  Допустим, перед нами стоит задача написать алгоритм собирания портфеля. Представим данный алгоритм в словесной форме:

1. Взять дневник, и выяснить расписание на завтра.
2. Положить в портфель учебники по нужным предметам.
3. Положить в портфель тетради по нужным предметам.
4. Положить в портфель пенал.
5. Положить в портфель дневник.
6. Закрыть портфель.

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

Разветвляющийся

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

Рассмотрим задачу:

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

1. Дойти до дома Кролика.
2. Поздороваться и зайти в дом.
3. Спросить у Кролика, есть ли у него дома мед.
4. Если мед есть, вежливо попросить Кролика угостить гостя медом. Если же меда нет, попросить угостить гостя сгущенным молоком.
5. Поблагодарить Кролика за угощение.

Выполняя этот алгоритм, Винни может попробовать только один десерт, либо мед, либо сгущенное молоко. Что именно ему достанется, зависит от выполнения условия, то есть от того, есть ли у Кролика дома мед.

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

Винни Пух решил прогуляться в гости к Кролику. У Винни был план подкрепиться у Кролика медом. Он точно знал, что у Кролика всегда есть сгущенное молоко, а иногда бывает и мед.  Но сгущенного молока Винни наелся у Кролика на прошлой неделе, и теперь он согласен только на мед. Составьте алгоритм действий для Винни.

1. Дойти до дома Кролика.
2. Поздороваться и зайти в дом.
3. Спросить у Кролика, есть ли у него дома мед.
4. Если мед есть, вежливо попросить Кролика угостить гостя медом.
5. Попрощаться с Кроликом.

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

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

 

Циклический

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

Циклические алгоритмы бывают двух типов — циклы со счетчиком и циклы с условием.

Циклы со счетчиком

Этот вид цикла используется в тех случаях, когда точно известно количество повторений цикла. Для того, чтобы считать эти повторения, вводится специальная переменная — счетчик цикла.

Рассмотрим задачу.

Винни Пух с утра был очень голоден. Для утоления голода Винни необходимо съесть 8 пончиков, намазанных медом. Составьте алгоритм действий для Винни.

1. Сесть за стол.
2. Достать пончик.
3. Намазать пончик медом.
4. Съесть пончик.
5. Задуматься, не восьмой ли пончик был съеден только что. Если это не так — перейти к пункту 2, иначе перейти к следующему действию.
6. С сожалением вылезти из-за стола.

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

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

Для начала определим начальное значение суммы (сумму обозначим переменной S). До того, как к сумме прибавили первое число, значение ее было равно нулю (S=0). Так же необходимо определить начальное значение счетчика (обозначим его переменной i). Определим значение счетчика равным нулю (i=0). Каждое введенное число (поместим его в переменную a) будет последовательно прибавляться к сумме. Новое значение суммы при этом становится равным сумме старого значения суммы и числа a (S=S+a). Такие формулы называются рекуррентными, в них и в правой, и в левой части выражения встречается одна и та же переменная.

При помещении в переменную нового значения, старое значение просто исчезает, происходит как бы вытеснение старого значения новым. После того, как первое число добавлено к сумме, нужно обязательно увеличить значение счетчика i на единицу. Для этого используем уже знакомый нам прием – рекуррентную формулу. Новое значение переменной i будет равно сумме старого значения и единицы (i=i+1). После этого проверим, не пора ли заканчивать выполнение цикла. Если счетчик цикла равен десяти (т. е. цикл выполнен уже 10 раз и все 10 чисел прибавлены к сумме), то выполнение алгоритма можно закончить. В противном случае необходимо вернуться и проделать шаги заново, начиная с ввода числа в переменную а (старое значение а при этом исчезает, но оно уже было использовано программой, и никакой проблемы его пропажа не создаст). Выполнение алгоритма будет ходить по кругу до тех пор, пока значение счетчика не станет равным 10. Ниже приведена блок-схема этого алгоритма.

Циклы с условием

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

Рассмотрим задачу. Винни Пух очень давно не ел сладкого, и решил зайти в гости к Кролику. Винни был так голоден, что нечаянно съел у Кролика все запасы меда. Он требовал добавки до тех пор, пока мед у хозяина не закончился. Опишите алгоритм действий Винни.

1. Дойти до дома Кролика.
2. Вежливо поздороваться и войти в дом.
3. Вежливо попросить Кролика угостить друга баночкой меда.
4. Съесть угощение.
5. Поинтересоваться, есть ли еще мед. Если мед есть, вернуться к пункту 3. Если нет — перейти к следующему действию.
6. Поблагодарить за угощение.
7. Покинуть дом Кролика.

Сколько раз будет выполняться цикл зависит от того, сколько банок меда было в шкафу у Кролика.

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