понеділок, 27 лютого 2017 р.

Лінійний алгоритм


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

Приклад 1. Прикладом лінійного алгоритму може служити розглянуте в главі 2 рішення задачі про знаходження площі стін кімнати. У цьому алгоритмі послідовно виконуються наступні розпорядження:
1.     Ввести довжину кімнати, привласнити змінній А введене значення.
2.     Ввести ширину кімнати, привласнити змінній В введене значення.
3.     Ввести висоту кімнати, привласнити змінній H введене значення.
4.     Зробити обчислення за формулою: S= 2 (А + В) H.
5.     Вивести (надрукувати) результат — значення змінної S — площа стін кімнати.
За допомогою лінійних алгоритмів вирішуються найпростіші задачі. У них число дій виконавця в точності дорівнює числу операторів програми.                                      Прикладами таких програм можуть служити коди, наведені в попередніх главах.
На практиці ж усі більш-менш серйозні задачі вирішуються за допомогою більш складних алгоритмів, у яких виконавцю іноді доводиться відступати від того порядку, у якому записуються оператори програми. Наприклад, виконавець може повертатися до вже виконаних операторів для того, щоб виконати їх знову. Деякі частини програми можуть взагалі не виконуватися, хоч задача при цьому вирішуватиметься успішно.
Лінійна структура передбачає, що тіло алгоритму являє собою послідовність команд, виконуваних одна за одною.

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



Малюнок 1. Приклад лінійного алгоритму

Приклад. Обчислити значення виразу


     
Етапи розв’язування задач
-       постановка задачі;
-       формальна (математична) постановка задачі;
-       вибір методу розв’язку задачі;
-       побудова блок-схеми алгоритму;
-       перевірка алгоритму;
-       розробка тексту програми;
-       тестування і відлагодження програми;
-       розв’язок задачі, аналіз результатів;
-       експлуатація програми
При постановці задачі потрібно вказати, які вхідні дані будуть оброблятись, що з ними  необхідно зробити і в якому вигляді повинні бути результати.
Формальна постановка задачі – це представлення задачі у вигляді формул, рівнянь, співвідношень, обмежень.
Вибір методу полягає у виборі того чи іншого способу розв’язування задачі.
Побудова блок-схеми  - це графічний запис алгоритму на основі  вибраного методу.
Перевірка алгоритму полягає в ручній перевірці розв’язку задачі.
Розробка тексту програми – це запис алгоритму на алгоритмічній мові програмування.
Алгоритмічна мова програмування — це мова, призначена для запису алгоритмів розв'язування задач і вихідних даних для ЕОМ. Це певна сукупність символів, слів, команд і правил, за допомогою яких можна у формальному вигляді записувати послідовність дій для розв'язування даної задачі. Цю послідовність дій називають прог­рамою на алгоритмічній мові. Якщо розробка алгоритму виконана добре, то програмування принципових труднощів не викликає.
В обчислювальних машинах завдання автоматичного перетворення алгоритмів з алгоритмічних мов у машинні виконують спеціальні програми, які називаються трансляторами. Людина пише програму на алгоритмічній мові, зрозумілій людині, а транслятор цю програму перетворює в мову із 0 і 1, зрозумілу комп'ютеру. Таким чином, алгоритмічна мова відіграє роль посередника між людиною і комп'ютером.
Тестування і відлагодження програми — це перевірка правильності роботи програми і виправлення знайдених помилок.  
 Для виконання тестування необхідно підготувати тести.
Тест — це спеціально підібрані вхідні дані разом з результатами, які повинні бути отримані за цими даними.
При тестуванні перевіряється, чи отримуються програмою ті самі результати, які вказано в тесті.
Налагодження (відладка) програми полягає у виявленні й усуненні помилок у розробленій програмі.
У програмі, складеній вперше, як правило, містяться помилки. Деякі із цих помилок (так звані синтаксичні) виявляються трансляторами. Інші помилки (названі логічними) трансляторами не виявляються. Ці помилки повинен виявити та усунути програміст.
Розв'язування задачі та аналіз результатів — це остаточна перевірка правильності реалізації всіх попередніх етапів.  
Після налагодження програми здійснюється її запуск при різних вхідних даних. Цей етап є підсумком виконання всіх попередніх етапів і служить підтвердженням (або запереченням) їх правильності. Після цього етапу, буває, доводиться переглянути сам підхід до розв'язку задачі і повернутися до першого етапу для повторного виконання всіх етапів з оглядом на набутий досвід. Упевнившись, що в заданому діапазоні вхідних даних програма функціонує правильно, програміст передає розроблену ним програму для експлуатації, для розв'язування заданого класу задач.
Експлуатація програми — це використання програми людьми, які її замовляли.     

Розглядання лінійних алгоритмічних задач
У Марусі є маленький робот. Одного разу Маруся дала йому команди:
1. Піди на кухню
2. Налий воду в маленьку лієчку
3. Повернись до кімнати
4. Полий квіти у горщиках
Виконавши послідовно ці команди, робот полив квіти в кімнаті. Наступного дня до Марусі завітав у гості Василько. Маруся вирішила пригостити його яблуком. Робот отримав такі команди:
1, Піди на кухню
2, Візьми яблуко
3, Помий яблуко
4, Повернись у кімнату
5, Дай помите яблуко Василькові
Кожного разу робот послідовно виконував команди. Послідовність команд називають лінійним алгоритмом.
Алгоритм посадки дерева:
1)  викопати в землі ямку;
2)  вилучити в ямку саджанець;
3)  засипати ямку із саджанцем землею;
4)  полити саджанець водою.