Запис алгоритмів у вигляді блок-схем

Існують дві форми опису алгоритму: словесне природною мовою й графічне у вигляді так званих структурних схем, або блок-схем. При другому способі запису алгоритм представляється у вигляді послідовності спеціальних символів - блоків, кожному з яких відповідає певний етап рішення завдання. У табл. 1 дані позначення деяких блоків відповідно до ДЕРЖСТАНДАРТ 19002-80, 19003-80.

Таблиця 1

Блоки з'єднуються лініями потоку інформації. Усередині блоків записуються виконувані дії. Лінії визначають напрямок обчислень, причому зверху вниз і ліворуч праворуч. Якщо необхідно відбити інший напрямок (знизу нагору або праворуч ліворуч), то на лініях ставляться стрілки. Практично будь-який складний алгоритм являє собою комбінацію трьох типів структур: лінійного, що розгалужується й циклічного.

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

Прикладом лінійного алгоритму може служити алгоритм обчислення значення функції в = .

Процес рішення цього завдання можна розділити на етапи й записати алгоритм природною мовою в такий спосіб:

1. Обчислити z = ax³+b.

2. Обчислити

3. Обчислити t = lnz.

4. Обчислити г=s+ t.

5. Обчислити y = arctgr.

Всі перераховані етапи є чисто арифметичними. Крім них у процесі рішення завдання будуть

мати місце й деякі інші допоміжні етапи. Блок-схема алгоритму рішення цього завдання показана на мал. 3.

алгоритм, Що Розгалужується, містить блок (або блоки) перевірки деякої умови, і залежно від результату перевірки виконується та або інша послідовність операцій, називана галуззю. При цьому форма розгалуження може бути як повна, так і скорочена (мал. 2, б).

Розглянемояк приклад алгоритм знаходження квадрата найбільшого із трьох заданих чисел: а, b і с. Спочатку рівняються два числа: а й b. Більше з них приймається за максимальне. Потім виробляється порівняння отриманого результату із третім числом с. Якщо значення з виявляється більше, те воно приймається за максимальне й зводиться у квадрат. У противному випадку найбільшим уважається результат порівняння а й b.

Опишемо алгоритм природною мовою:

1. Зрівняти а й b. Якщо а>b, то прийняти в = а. У противному випадку прийняти в=b.

2. Зрівняти c й y. Якщо з>в, то замінити в=с. У противному випадку залишити в без зміни.

3. Обчислити z = y².

Схема алгоритму (мал. 4) містить два розгалуження: повне (блоки 3, 4, 9) і скорочене (блоки 5,10).

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

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

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

Опишемо алгоритм. Дано два числа: x>0 й в>0. Потрібно знайти найбільший загальний дільник d.

1. Прийняти а = х, b = в.

2. Зрівняти а й b. Якщо а = b, то прийняти найбільший загальний дільник d = a і закінчити обчислення. У противному випадку виконати крок 3.

3. Прийняти d = a - b.

4. Якщо d>0, прийняти a=d. У противному випадку прийняти b=-d. Виконати крок 2.

Алгоритм Евкліда (мал. 5) містить дві лінійних ділянки (блоки 2, 3 й 9, 10), одне розгалуження (блоки 6, 7, 8) і один цикл, що включає блоки 4 (перевірка умови виходу із циклу) і 5-8 (тіло циклу).