Види алгоритмів.

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

Алгоритми найпростішого виду – лінійні. Це такі алгоритми, в яких дії виконуються послідовно, одна за одною. Кожна дія лінійного алгоритму обов'язково виконується, і виконується тільки один раз:

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

Якими б не були вхідні дані, лінійний алгоритм приписує виконання однієї й тієї самої послідовності дій.

Прикладом лінійного алгоритму може бути наведений вище алгоритм завершення роботи з комп'ютером.

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

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

“якщо умова виконується, то виконати дію 1, інакше виконати дію 2” (див. рисунок а),

а коротку – так:

“якщо умова виконується, то виконати дію” (див. рисунок б).

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

Приклад алгоритму з розгалуженням: У крамниці пара шкарпеток коштує 2 гривні, а в'язка (дванадцять пар) – 19 гривен. Визначити, скільки в'язок та пар шкарпеток вигідніше придбати, якщо потрібно Х пар.

За таких умов очевидно, що замість 11 пар шкарпеток (22 гривні) і навіть 10 пар (20 гривень) вигідніше придбати в'язку (19 гривень) – буде затрачено менше грошей, і ви ще отримаєте додаткові шкарпетки. Але для дев'яти пар (18 гривень) знижка на в'язку вже не спрацює.

Розв'язання задачі ґрунтується на такому міркуванні. Треба порівняти за ціною всього два варіанти придбання шкарпеток:

перший – з округленням кількості шкарпеток до в’язки в менший бік і додаванням, якщо потрібно, окремих пар;

другий – з округленням кількості окремих пар, якщо такі є, до цілої в’язки.

Наприклад, якщо треба придбати 45 пар шкарпеток, то обов’язково треба купувати 3 в’язки і, порівнявши ціну 9 пар з ціною цілої в’язки, зробити висновок, що вигідніше докупити - потрібну кількість окремих пар чи цілу в’язку. У нашому прикладі дешевше докупити 9 пар.

Наведемо алгоритм розв’язування задачі:

1. Обчислити кількість цілих в'язок (N), які треба придбати:

N = Х поділити націло на 12.

2. Обчислити кількість окремих пар (M) :

M = Х – 12 N

3. Обчислити ціну окремих пар (С):

С = 2 M

4. Якщо значення С менше за ціну цілої в’язки (С < 19), то придбати N в'язок та M пар, інакше N + 1 в'язку.

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

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

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

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

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

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

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

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

Для розробки алгоритму позначимо через a та b задані числа, r – остачу від ділення першого числа на друге.

Якщо a менше за b , то остача дорівнює a; якщо ж a більше чи дорівнює b, то треба зменшити a на величину b і перевірити, чи нове значення a менше за b. Якщо так, то останнє значення a і є остачею, якщо ні – потрібно повторити дії.

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

Зважуючи на те, що для випадку a < b остача r дорівнює заданому значенню а і цикл не потрібно виконувати жодного разу, скористаємося для складання алгоритму циклом з передумовою.

Блок-схему алгоритму знаходження остачі від ділення двох натуральних чисел a, b подано на рис. а. На рис. б наведено кроки виконання алгоритму для випадку a = 15, b = 7.

Питання до лекції:

1. Підходи до визначення поняття «алгоритм».

2. Виконавець алгоритму та система його команд. Наведіть приклади.

3. Властивості алгоритму. Розкрийте їх сутність.

4. Наведіть приклади способів подання алгоритмів.

5. Вили алгоритмів. Наведіть приклади їх конструкцій.

Читайте також:

<== попередня сторінка	\|	наступна сторінка ==>
Способи подання алгоритмів.	\|	Основні принципи структурного підходу до побудови алгоритмів.

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.005 сек.