- •Основи алгоритмізації обчислювальних процесів Алгоритми та форми їх подання Поняття алгоритму
- •Властивості та характеристики алгоритмів
- •Оцінка ефективності алгоритму
- •Способи опису алгоритмів
- •Базові алгоритмічні структури
- •Лінійні алгоритми
- •Розгалужені алгоритми
- •Циклічні алгоритми
- •Логічні основи алгоритмізації
Базові алгоритмічні структури
Алгоритми, як процеси перетворення інформації, мають певну класифікацію, що відображає особливості їх реалізації. Загалом існує три типи алгоритмів:
лінійний,
розгалужений,
циклічний.
Структурну схему їх логічних зв’язків зображено на рис. 7.
Рис. 7. Типи алгоритмічних процесів
Алгоритми можна представляти як деякі структури, що складаються із окремих базових (тобто основних) елементів – базових алгоритмічних структур. Кожен такий елемент відповідає певному типу алгоритмічного процесу.
Логічна структура будь-якого алгоритму може бути представлена комбінацією трьох базових алгоритмічних структур:
слідування,
розгалуження,
циклу.
Характерною особливістю базових алгоритмічних структур є наявність в них одного входу і одного виходу.
Лінійні алгоритми
Найпростішими для алгоритмізації є задачі, в яких перетворення інформації відбувається послідовно за певними формулами. Такі алгоритми називають лінійними.
Для представлення такого алгоритму використовується алгоритмічна конструкція слідування (послідовного виконання), яка передбачає послідовне виконання дій в тому порядку, в якому вони записані в тексті програми. Представлення цієї конструкції у блок-схемах здійснюється послідовністю блоків “процес”:
Типовим прикладом лінійного алгоритму є процедура обчислення за певними формулами.
Слід зауважити, що обчислення виразів є досить складним процесом, який потребує багато часу та спеціальної додаткової пам’яті для збереження проміжних результатів. Порядок обчислень у кожній мові визначається за пріоритетом операцій та скобками, використаними у записі виразу. Ці вирази можуть бути настільки складними, що можуть викликати збої в рооботі програми. Тому доцільно розбивати складний вираз на декілька більш простих, пам’ятаючи, що запис виразу будь-якої складності повинен бути лінійним.
Якщо є якісь вирази, що використовуються у загальному виразі декілька разів, то доцільно їх знайти один раз і запам’ятати в окремих змінних.
Наприклад, алгоритм обчислення виразу z = sin2(x2 + y2) + cos3(x2 + y2).
Розгалужені алгоритми
У випадках, коли перетворення інформації може здійснюватись за різними схемами, залежно від властивостей вхідних даних або проміжних результатів, використовуються розгалужені алгоритми. В таких алгоритмах передбачаються всі можливі варіанти обробки інформації, кожний з яких розробляється як окрема гілка алгоритму, а вибір однієї з них для виконання здійснюється за допомогою перевірки деякої умови, що відображає властивості інформації, яка використовується у процесі перетворення.
Для представлення таких алгоритмів використовуються алгоритмічні конструкції вибору (розгалуження). Дана алгоритмічна структура в залежності від результату перевірки певної умови здійснює вибір одного з альтернативних шляхів роботи алгоритму. Кожен із шляхів веде до спільного виходу, так що робота алгоритму триватиме незалежно від того, який шлях буде обраний.
Структура розгалуження існує в чотирьох основних варіантах:
«якщо-то-інакше» (повне розгалуження);
«якщо-то» (неповне розгалуження);
«вибір-інакше» (повний багатоваріантний вибір);
«вибір» (неповний багатоваріантний вибір).
Повне розгалуження. Дана алгоритмічна структура передбачає виконання дій і у разі виконання, і у разі невиконання заданої умови. Графічне представленням такої структури у блок-схемах має наступний вид:
При цьому умова формулюється таким чином, щоб відповідь перевірки була «так» чи «ні» (рис. 8 а, б). Наприклад,
а) |
|
б) |
|
Рис. 8. Блок-схеми повного розгалуження
Неповне рогалуження. Дана алгоритмічна структура передбачає виконання дій тільки у разі виконання, або у разі невиконання заданої умови. Тобто, одна із її гілок взагалі не передбачає ніяких дій. Графічне представленням таких структур у блок-схемах має наступний вид:
Залежно від того, на скільки гілок розгалужується алгоритм, він може бути простим або складним. Для простого розгалуженого процесу перевіряється одна умова, для складного — дві чи більше умов, кожна з яких відокремлює одну гілку (рис. 9).
Рис. 9. Блок-схема складного розгалуження
Багатоваріантний вибір. Збільшення кількості умов робить алгоритм більш заплутаним, він втрачає наочність, перевірити його правильність досить складно. У таких випадках необхідно перехід до будь-якої гілки розгалуженого алгоритму пов’язати з деякою змінною, кожне значення якої відповідатиме одній із гілок розгалуження, тобто одному з варіантів обробки інформації. Це можуть бути не тільки окремі значення, а й проміжки значень, до яких належатиме конкретне значення змінної. Тоді всі логічні блоки алгоритму об’єднуються в один блок аналізу цієї змінної, який матиме не два виходи, а стільки, скільки існує варіантів обробки. Таке розгалуження називають багатоваріантним.
Якщо для такого розгалуження передбачений варіант обробки, коли значення змінної не належить до перелічених значень, то таке розгалуження є повним багатоваріантним вибором (рис. 10 а), інакше - неповним багатоваріантним вибором (рис. 10 б).
а) |
|
б) |
|
Рис. 10. Блок-схеми багатоваріантного вибору
Наприклад, алгоритм ров’язання квадратного рівняння ax2+bx+c = 0.