5. Лінійні алгоритми. Базові структури алгоритмів

Алгоритм зветься лінійним, якщо всі його дії виконуються послідовно, одна за одною, від початку до кінця¹.

У лінійному алгоритмі не може бути команди, яка б передбачала різну послідовність виконання алгоритму. Приклад лінійного алгоритму «Як перевезти по одному через річку без втрат вовка, козу і капусту»:

1. Переправити на той берег козу, вовка залишити з капустою;

2. Повернутись, взяти вовка, переправитись з ним до кози;

3. Забрати козу і повернутись назад до капусти;

4. Залишити козу, забрати і перевезти капусту до вовка;

5. Повернутись і забрати козу.

У цьому прикладі дії алгоритму виконуються послідовно одна за одною до закінчення алгоритму. Наведемо приклад побудови блок-схеми лінійного алгоритму «Обчислити шлях за швидкістю і часом руху» (рис. 6).

Словесний запис алгоритму задачі буде таким:

1. Ввести швидкість v і час руху t.

2. Обчислити шлях за формулою

S = v·t

3. Вивести шлях S.

Рис. 6. Приклад побудови лінійного алгоритму «Обчислити шлях за швидкістю і часом руху»¹

Ще один приклад:

Алгоритм «Обчислити площу трикутника за трьома сторонами».

Словесний запис алгоритму:

1. Ввести сторони трикутника а, b, с.

2. Обчислити півпериметр трикутника

р = 0.5 * (a + b + c).

3. Обчислити площу S за формулою Герона

.

4. Вивести площу трикутника S. Запис алгоритму у вигляді блок-схеми буде таким, як на рис. 7.

Рис. 7. Приклад алгоритму «Обчислити площу трикутника за трьома сторонами»

Наступний приклад:

Відомі щільність і геометричні розміри циліндричного зливка, отриманого в металургійній лабораторії. Знайти об'єм, масу і площу основи зливка.

Вхідні дані: R - радіус основи циліндра, h - висота циліндра, ρ- щільність матеріалу зливка.

Вихідні дані: m - маса зливка, V - об'єм, S - площа основи.

Блок-схема представлена на рис. 8.

Рис. 8. Алгоритм «Знайдення об'єму, маси і площі основи зливка»¹

Ще один приклад:

Задані довжини двох катетів в прямокутному трикутнику. Знайти довжину гіпотенузи, площу трикутника і величину його кутів.

Вхідні дані: a, b - довжини катетів.

Вихідні дані: с - довжина гіпотенузи, S - площа трикутника, α, β - кути.

Блок-схема представлена на рис.1.9.

Рис. 9. Алгоритм прикладу «Знайдення довжини гіпотенузи, площі трикутника і величини його кутів»

За структурою алгоритми можна класифікувати на три базові різновиди: лінійні, розгалужені, циклічні¹.

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

Реальні алгоритми, як правило, включають усі три типи алгоритмів у різноманітних комбінаціях.

Структурний підхід до конструювання (розробки) алгоритмів полягає в тому, що спочатку продумується і фіксується загальна структура алгоритму без деталізації окремих його частин. Блоки, що потребують подальшої деталізації, позначаються пунктиром. На наступних кроках ці блоки уточнюються. Коли завершено деталізацію всіх блоків, одержимо алгоритм розв’язку задачі в цілому. Це простіше, ніж відразу розробляти детально весь алгоритм. Такий підхід до конструювання алгоритмів ще називають розробкою «зверху вниз». Структурний підхід до конструювання алгоритмів забезпечує легкість розуміння алгоритму, простоту його перевірки і редагування.