133. Види алгоритмів.

Будь-який алгоритм містить опис команд і визначає послідовність їх виконання. На перший погляд здається, що всі команди алгоритму завжди виконуються одна за одною, проте це не так. Для забезпечення такої властивості алгоритму, як масовість, його будують з огляду на будь-який набір допустимих вхідних даних. Через це в багатьох випадках не можна завчасно передбачити, яким саме має бути наступний крок алгоритму. Звідси виникає потреба в таких інструкціях виконавцеві, які дозволяли б управляти його діями згідно із ситуацією, що складається в процесі виконання алгоритму.

За характером управління розрізняють три основні види алгоритмів: лінійні, з розгалуженням і з повторенням.

У найпростішому випадку алгоритм приписує одноразове виконання всіх по черзі заданих дій незалежно від значень вхідних даних задачі. Наприклад, для знаходження об’єму призми потрібно знайти площу її основи, визначити висоту призми, знайти їх добуток. Ці дії потрібно виконати для обрахування об’єму будь-якої призми.

Алгоритм, який приписує одноразове виконання однієї і тієї самої послідовності дій при будь-яких допустимих вхідних даних задачі, називається лінійним.

Складнішими за управлінням є алгоритми, які передбачають два можливі варіанти дій. Вибір варіанта пов’язується з деякою умовою. Наприклад, алгоритм розв’язання квадратного рівняння приписує спочатку знайти значення дискримінанта, а потім, залежно від його знаку, або повідомити про відсутність дійсних коренів (якщо значення дискримінанта від’ємне), або знайти їх за відповідними формулами (у протилежному випадку). Алгоритм, який приписує виконання тих чи інших дій у залежності від результату перевірки умови, називається алгоритмом із розгалуженням, або розгалуженим. Хоча такий алгоритм містить опис дій для обох можливих варіантів, при кожному його виконанні реалізується тільки один з них, який саме — залежить від заданого набору вхідних даних. Отже, на відміну від лінійного алгоритму, алгоритм із розгалуженням приписує виконання не всіх без винятку дій, а тільки тих, які вибрані за умовою. Третій вид алгоритмів складають такі, що передбачають можливість повторного виконання певної послідовності дій.

Наприклад, для підрахування суми двох цілих чисел (у стовпчик) потрібно спочатку обчислити суму останніх цифр чисел-доданків, записати останню цифру результату й перенести, якщо потрібно, одиницю в наступний розряд. Далі за аналогічним правилом потрібно обчислити суму передостанніх цифр чисел-доданків і т. д. Процедура повторюється, доки всі цифри чисел-доданків не будуть вичерпані. Кількість повторень залежить від кількості цифр у заданих числах.

Алгоритм, який приписує повторне виконання дій, називається алгоритмом із повторенням, або алгоритмом із циклом. Повторювана дія або група дій називається тілом циклу. Кількість повторень тіла циклу визначається поставленою умовою, яка називається умовою циклу. За результатом перевірки умови здійснюється вибір: ще раз повторити тіло циклу чи перейти до інших дій. Наявність повернення до раніше виконаних дій є характерною відмінністю алгоритмів із циклами від лінійних і розгалужених.