1.4 Опис алгоритму

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

Наприклад, план обчислення при заданому значенні х можна описати наступною послідовністю інструкцій (алгоритм очевидний з самого формулювання завдання):

1) ввести (у ЕОМ) конкретне значення х; перейти до виконання наступної по порядку інструкції;

2) обчислити перейти до наступної інструкції;

3) вивести (з ЕОМ) y в, тобто результат; перейти до наступної інструкції;

4) припинити обчислення (кінець).

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

Зручно представити алгоритм в графічній формі у вигляді блок-схеми. Умовимося змальовувати:

- процедуру вводу—виводу у вигляді паралелограма

- обчислювальну процедуру у вигляді прямокутника;

- початок і кінець алгоритму у вигляді овалу.

Усередині кожної фігури (їх називають блоками; звідси і назва "блок-схема алгоритму"- (БСА) записуватимемо конкретний зміст процедури, а самі фігури з'єднаємо між собою лініями зв'язку, що показують послідовність виконання процедур. На рисунку 1, представлена блок-схема алгоритму розглянутого вище завдання.

Рисунок 1-Блок-схема лінійного обчислювального процесу

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

1.5 Процеси, що гілкуються

Р озглянемо завдання: обчислити

y= x2+1, якщо х≤0 при заданому значенні х

3x2-х1, якщо х≥0 при заданому значенні х

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

Якщо процедуру аналізу х (х — ?) позначити ромбом, то блок-схема матиме вигляд рисунок 2а.

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

Зазвичай процедуру аналізу записують у вигляді процедури перевірки якоїсь умови (наприклад, х > 0?), і залежно від того, виконується ця умова чи ні, обчислювальний процес спрямовують по тій або іншій гілці. Об'єднавши дублюючі процедури, отримаємо блок-схему, представлену на рисунок 2б,

а б

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

Пригадаємо, що алгоритм — це строга послідовність кроків (процедур, інструкцій, операцій) обчислювального процесу.

Для лінійного процесу порядок їх виконання видно з блок-схеми і стає зовсім ясним, якщо блоки пронумерувати в порядку їх виконання (див. рисунок 1).

У таких випадках говорять, що інструкції виконуються в природному порядку (в порядку зростання номерів інструкції).

Спробуємо пронумерувати блоки рисунок 2,б. Всього блоків 6. Нумерація перших два (1 і 2) і два останніх (5 і 6) не викликає сумнівів. Пронумеруємо останні блоки так, як показано на рисунок 2, б.

Розташуємо блоки послідовно один за одним в порядку зростання їх номерів (рисунок 2б). Відразу видно, що природний порядок (із зростанням номера) виконання блоків тут не дотримується (адже після 2-го виконується 4-й, а після 3-го — 5-й) і це треба якось описати в інструкціях.

Рисунок 5, в і г. Варіант блок схеми процесу, що розгалужується .

Процедуру, що виконується блоком 2, можна описати такою інструкцією: «якщо х > 0, то перейти до виконання блоку (інструкції) 4, інакше до наступного по порядку блоку (інструкції), тобто до «3».

Якщо умовитися, що при невиконанні умови потрібно завжди переходити до наступної по порядку інструкції, то тоді інструкцію 2 можна записати коротко: «якщо х > 0, то йти до 4».

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

Отже, ми описали одну (праву) гілку рисунок 2в.

Як же описується ліва гілка? Стрілка між блоками 3 і 5 вказує на обов'язкове, не обумовлене жодними умовами порушення природного порядку виконання блоків, і наказує перейти до блоку виводу. Це розпорядження записують після блоку 3 зазвичай у вигляді інструкції «йти до ...», для якої введемо особливе графічне позначення (усічений зверху і знизу ромб). Вочевидь, цьому блоку потрібно привласнити номер 4 (рисунок 2,г). Поява нового блоку 4 приведе до зсуву номерів подальших блоків на одиницю, і ми отримаємо остаточно блок-схему рисунок 5, г, яку можна описати наступною послідовністю інструкцій:

1. Введення х

2. Якщо х > 0, йти до 5

3. Обчислити в = х2 + 1

4. Йти до 6

5. Обчислити в = 3х2-х

6. Вивід в

7. Кінець

Інструкцію «йти до 6» називають операцією безумовного переходу. Вона означає обов'язкове (безумовне) порушення природного порядку виконання інструкції і перехід до виконання тієї інструкції, номер якої вказаний в цій операції.

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