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

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

• лінійний,

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

• циклічний.

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

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

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

Логічна структура будь-якого алгоритму може бути представлена ​​комбінацією трьох базових алгоритмічних структур:

• слідування,

• розгалуження,

• циклу.

Характерною особливістю базових алгоритмічних структур є наявність в них одного входу і одного виходу.

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

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

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

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

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

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

Наприклад, алгоритм обчислення виразу z = sin²(x² + y²) + cos³(x² + y²).

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

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

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

Структура розгалуження існує в чотирьох основних варіантах:

• «якщо-то-інакше» (повне розгалуження);

• «якщо-то» (неповне розгалуження);

• «вибір-інакше» (повний багатоваріантний вибір);

• «вибір» (неповний багатоваріантний вибір).

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

При цьому умова формулюється таким чином, щоб відповідь перевірки була «так» чи «ні» (рис. 8 а, б). Наприклад,

а)

б)

Рис. 8. Блок-схеми повного розгалуження

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

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

Рис. 9. Блок-схема складного розгалуження

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

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

а)

б)

Рис. 10. Блок-схеми багатоваріантного вибору

Наприклад, алгоритм ров’язання квадратного рівняння ax²+bx+c = 0.