Базові структури алгоритмів

Базові структури алгоритму — це структури, за допомогою яких створюється алгоритм для розв’язання певної задачі.

Існують три основні (базові) алгоритмічні структури, або три основні типи алгоритмів:

• лінійний,

• розгалужений

• циклічний.

Структурну схему їх логічних зв’язків зображено на рис. 8.

Рис. 8. Типи алгоритмічних процесів

Лінійні алгоритми.

Найпростішими для алгоритмізації є задачі, в яких перетворення інформації відбувається послідовно за певними формулами, які розкладаються на елементарні операції. Такі алгоритми називають лінійними.

Для представлення такого алгоритму використовується алгоритмічна конструкція слідування (послідовного виконання), яка передбачає лінійне виконання операцій програми (в тому порядку, в якому вони записані в тексті програми). Представлення цієї конструкції у блок-схемах здійснюється послідовністю блоків “процес”:

Типовим прикладом лінійного алгоритму є процедура обчислення за певними формулами, які розкладаються на елементарні операції.

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

Наприклад, обчислити Z = sin²(x² + y²) + cos³ln(x² + y²).

Розгалужені алгоритми.

У випадках, коли перетворення інформації може здійснюватись за різними схемами, залежно від властивостей вхідних даних або проміжних результатів, використовуються розгалужені алгоритми. В таких алгоритмах передбачаються всі можливі варіанти обробки інформації, кожний з яких розробляється як окрема гілка алгоритму, а вибір однієї з них для виконання здійснюється за допомогою перевірки деякої умови, що відображає властивості інформації, яка використовується у процесі перетворення.

Для представлення таких алгоритмів використовуються алгоритмічні конструкції вибору (розгалуження), які бувають повними і неповними.

Повне галуження — це розгалуження, у якому дії визначені і у разі виконання, і у разі невиконання заданої умови. Графічне представленням такої структури у блок-схемах має наступний вид:

Неповне галуження — це розгалуження, в якому дії визначені тільки у разі виконання (або у разі невиконання) умови, тобто, одна із гілок взагалі не передбачає ніяких дій. Графічне представленням таких структур у блок-схемах:

Наприклад, обчислити max(x, y).

Алгоритм розв’язання:

Залежно від того, на скільки гілок розгалужується алгоритм, він може бути простим або складним. Для простого розгалуженого процесу перевіряється одна умова, для складного — дві чи більше умов, кожна з яких відокремлює одну гілку. Умова формулюється таким чином, щоб відповідь перевірки була «так» чи «ні». Наприклад,

Складне розгалуження відбувається послідовно, з відокремленням гілок за наведеною схемою:

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

Нехай k - змінна вибору варіантів, яка може приймати значення а₁, а₂, ..., а_n, і існують варіанти обробки інформації, відповідні деяким переліченим значенням змінної чи їх сукупностям. Обов’язково необхідно передбачити варіант обробки, коли значення змінної не належить до перелічених значень. Тоді розгалужений алгоритм матиме вигляд: