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

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

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

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

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

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

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

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

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

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

а)

б)

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

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

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

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

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

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

а)

б)

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

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