3. Класифікація алгоритмів.
Навіть ще не маючи досвіду в створенні алгоритмів, ми інтуїтивно розуміємо, що вони розрізняються за своєю структурою. Так є алгоритми, що виконуються за будь-яких обставин. Але таке трапляється нечасто, тому що людина завжди коригує свої плани в залежності від оточуючих умов і тому виникає ситуація "якщо трапиться...", "якщо зустрінуся...", "якщо встигну..." тощо. А іноді ми змушені повторювати якийсь процес кілька разів, доки не отримаємо бажаного результату. Найчастіше ж ми і умови враховуємо, і повторюємо щось. Ось так і виникають різні типи алгоритмів.
Всього існують чотири базових структури алгоритмів:
Алгоритми лінійної структури;
Алгоритми розгалуження;
Алгоритми повторення (циклічні);
Змішані.
Лінійні алгоритми. Правила виконання.
Найпростіша в написанні та виконанні перша з цих структур - лінійна. До неї відносяться алгоритми, що складаються лише з простих команд. Які ж команди можна назвати простими? Простими з точки зору комп'ютера являються ті команди, що виконуються виконавцем безумовно, тобто після першої команди виконується друга, потім третя і т.д.
Загальний вигляд лінійного алгоритму, поданий мовою блок-схем, наступний:
|
У лінійних алгоритмах результат виходить після виконання однієї послідовності дій. Початок — ряд операторів – кінець. Н а п р и к л а д:
|
|
П р и к л а д: Тут відображено алгоритм обчислення суми двох чисел а і b , які вводяться з клавіатури і виведення результату S на екран. Програма для такого алгоритму буде мати такий вигляд: PROGRAM LIN (INPUT, OUTPUT); VAR S, А, В:REAL; BEGIN WRITE ('Введи а і b') ; READLN (A, B); S:=A+B; WRITELN ('Результат S=', S) END. |
Алгоритмічна структура розгалуження:
Весь час людина аналізуєте ситуацію, змінюєте свою поведінку та свої плани, пристосовуєтесь до обставин. Тому набагато частіше зустрічається другий тип алгоритму - розгалужений. Цей алгоритм обов'язково містить в собі хоча б одну умову (як правило, їх набагато більше) і виконується він в залежності від цієї умови.
На блок – схемі структури розгалуження позначаються ромбами. Дві стрілки, які відгалужуються від ромба, позначені словами «Так» і «Ні». Якщо записане всередені ромба умовне твердження є істинним, виконуються дії, на які вказує стрілка, позначена словами «Так». Якщо це твердження є хибним, виконуються дії, на які вказує стрілка, позначена словом «Ні».
Мовою блок-схем розгалужений алгоритм подається наступним чином:
|
Для прикладу продемонструємо блок-схему алгоритму і напишемо програму для знаходження максимального серед двох чисел А і В. З блок-схеми видно, що в залежності від виконання умови А>В змінній max присвоюється значення а. Якщо умова не виконується, тобто вираз а>Ь має значення. FALSE змінній max присвоюється значення В. В програмі на мові Паскаль цей алгоритм відобразиться: PROGRAM ROZ (INPUT, OUTPUT); VAR A, B, MAX:REAL; BEGIN WRITE ('Введи а і b'); READLN (A, B); IF A>B THEN MAX:=A ELSE MAX:=B; WRITELN ('Результат МАХ=', MAX) END. |
Алгоритмічна структура повторення (цикл):
Однак, навіть маючи в своєму арсеналі команду розгалуження, важко реалізувати алгоритми, що потребують багаторазового повторення деякої послідовності однакових дій. В цих випадках нас виручає циклічний алгоритм. У нашому житті дуже часто зустрічаються алгоритми з повторами, причому чітко визначаються два типи повторів. В одному випадку ми чітко знаємо, скільки разів необхідно повторити задану послідовність команд, а в іншому - ні.
Алгоритмічна структура повторення дає виконавцеві алгоритму вказівку повторювати деякі дії, поки певне умовне твердження істинне.
Твердження, істинність якого перевіряється під час виконання циклічної структури, на блок – схемі записується всередині ромба (як і у випадку розгалуження). Особливістю зображення циклічної структури на блок – схемі є те, що одна із стрілок повинна «повертатися назад», тобто має утворюватися замкнений «цикл» із блоків та стрілок. Такий цикл має містити умовний блок, в якому записана умова продовження повторення. Одна зі стрілок, що відгалужуються від цього блоку, повинна брати участь у циклі, а інша – вказувати на блок поза циклом.
В залежності від того, чи знаємо ми скільки разів необхідно повторювати якусь послідовність команд розрізняють цикли з лічильником (кількість повторень відома заздалегідь) та цикли з умовою (цикл робиться доки не виконається якась умова).
Н а п р и к л а д, в першому класі вчителька дає завдання дітям: "Діти, напишіть, будь ласка, в зошитах десять цифр "1", а потім рядочок цифр "2". Чим відрізняються ці два завдання? В першому випадку дитина отримала чітку вказівку написати десять одиниць, а в другому - ця вказівка була не точною (рядочок двійок). Чому другий випадок не такий точний? Тому що кількість отриманих кожним учнем цифр буде залежати від їх власного почерку: одні учні пишуть охайно маленькими цифрами, інші - неохайно величезними кривулями.
Крім того, в циклах з умовою теж можна виділити два різних випадки:
цикл з передумовою - коли ми спочатку перевіряємо умову, а потім виконуємо деяку послідовність дій (так, ми спочатку перевіряємо, чи вимита підлога в тій класній кімнаті, де нам потрібно чергувати, а потім починаємо прибирання);
цикл с післяумовою - спочатку ми виконуємо хоч один раз необхідну послідовність дій, а потім перевіряємо, чи не досягли ми бажаного результату (коли ми хочемо пити, ми спочатку ковтаємо хоч глоток води, а потім починаємо контролювати, чи не вгамували ми свою спрагу).
Мовою
блок-схем обидва типи циклів виглядають
наступним чином:
|
Блок-схема алгоритму для виконання цієї задачі приведена Блок 2 - ввід значення N. Блок 3 - підготовка до виконання циклу. Блок 4 - перевірка умови виконання циклу.!' Блок 5 і 6 - тіло циклу. Тут сума S збільшується на біжуче значення гармонічного ряду, а параметр циклу І збільшується на 1 Програма буде мати такий вигляд:
PROGRAM SUM1(INPUT, OUTPUT); VAR I, N:INTEGER; S: REAL; BEGIN WRITE('Введи N'); READLN(N) ; S:=0; I:=l; WHILE K=N DO BEGIN S:=S+1/I; {тіло} I:=1+1 {циклу} END; WRITELN('Сума S=',S) END. |
Вкладені цикли – це, коли певний цикл повторюється багато разів в іншому циклі що охоплює даний.
Блок – схема алгоритму обчислення коренів квадратного рівняння.
