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

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

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

· слідування;

· галуження;

· цикл.

Особливість будь-якої базової структури – наявність одного входу і одного виходу.

Розглянемо ці структури детальніше.

1. Базова структура слідуванняутворюється з послідовності дій, що слідують одне за іншим. По-іншому слідування називають лінійним типом алгоритму (рис.3.2):

 

Рис.3.2.

2. Базова структура галуженнязабезпечує залежно від результату перевірки логічної умови вибір одного з альтернативних варіантів роботи алгоритму. Кожен з варіантів повинен вести до загального виходу, тупикові шляхи не допустимі.

Прикладом алгоритму з галуженням може служити алгоритм знаходження НЗД, розглянутий у попередній лекції.

До тих, що розгалужуються відносять такі типи алгоритмічних структур:

- якщо – то;

- якщо – то – інакше;

- вибір;

- вибір – інакше.

Розглянемо їх зображення в блок-схемах алгоритмів:

 

1) Алгоритмічна структура якщо – то:

 

 

 

Ні

 

 

Так

 

Рис.3.3.

2) Алгоритмічна структура якщо - то – інакше:

 

Так Ні

 

Рис.3.4.

 

3) Алгоритмічна структура вибір:

Так

 

 

Ні

 

 

Так

 

 

Ні

 

 

Так

 

 

Ні

 

Рис.3.5.

3) Алгоритмічна структура вибір – інакше:

Так

 

 

Ні

 

 

Так

 

 

Ні

 

 

Так

 

 

Ні

 

 

Рис.3.6.

 

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

Розглянемо два основні різновиди циклів.

1) Цикл «для». Предписує виконувати тіло циклу для всіх значень параметра циклу в заданому діапазоні. Інша назва цього типа циклу – цикл з відомим числом повторень:

 

 

 

Рис.3.7.

 

Усередині блоку модифікація вказано початкове значення параметра циклу i1, його кінцеве значення i2 і крок зміни, Δi.

2) Цикл «доки» – предписує виконання тіла циклу до тих пір, поки виконується логічна умова, що входить до складу цієї алгоритмічної структури.

Цикли «доки» бувають 2-х типів – з передумовою і з постумовою залежно від того, де знаходиться умова по відношенню до тіла циклу.

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

 

 

 

Рис.3.8.

 

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

 

 

 

Рис.3.9.

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

Наведемо приклади блок-схем простих алгоритмів циклічної структури.

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

Приклад 2. Обчислення суми нескінченого ряду з точністю до члена, меншого, ніж задане значення:

 

 

з точністю до члена .

 

 

 

 

Рис.3.10.

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

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

Блок-схема алгоритму наведена на рис. 3.11.

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

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

 

 

 

Ініціалізація у

 

 

Параметр циклу

 

Накопичення суми

 

Ні

 

 

Так

 

 

Рис. 3.11.

 

 

Контрольні запитання

 

1. Які базові алгоритмічні структури Вам відомі?

2. Які типи галужень застосовуються в алгоритмах? Як реалізується в алгоритмах багатоальтернативний вибір?

3. Що таке цикл? Назвіть типів циклів, вживаних в алгоритмах.

4. Як зображається в блок-схемах алгоритмів цикл з відомим числом повторень? Що в цьому випадку вказується усередині блоку «модифікація»?

5. У яких випадках застосовуються ітераційні цикли? У чому відмінність ітераційного циклу з передумовою від циклу з постумовою?