Основи алгоритмізації та програмування Заняття 5. Базові структури алгоритмів. Типи алгоритмів. - презентация

1 Основи алгоритмізації та програмування Заняття 5. Базові структури алгоритмів. Типи алгоритмів

2 Exit Способи запису алгоритмів Ми знаємо, що таке алгоритм. Тепер нам необхідно домовитися, яким чином ми будемо його описувати.. Існує чотири способи запису алгоритмів, вибір яких залежить від того, хто його записує або на кого він орієнтований: словесний спосіб описування алгоритмів; описування алгоритмів за допомогою схем; описування алгоритмів мовою псевдокодів (не розглядатиметься); описування алгоритмів мовою програмування (розглядатиметься пізніше).

3 Exit Cловесний спосіб описування алгоритмів Словесний спосіб описування алгоритмів орієнтований на людину-виконавця. Мабуть, поки що важко уявити собі інший спосіб запису. Це найбільш проста і доступна форма представлення алгоритму. Словесна форма зазвичай використовується для алгоритмів, орієнтованих на виконавця- людину. Дійсно, цей спосіб є найбільш доступним будь- кому незалежно від його спеціальної підготовки.

4 Exit Приклад словесного способу описування алгоритму Розглянемо алгоритм Евкліда - процес знаходження найбільшого спільного дільника (НСД) двох цілих додатних чисел. 1) Візьмемо два цілих додатних числа. Якщо вони рівні, то перше з них і є найбільшим спільним дільником, якщо ж ні, то перейдемо до наступного пункту. 2) Порівняємо два числа і виберемо більше з них. 3) Більше з двох чисел замінимо різницею більшого і меншого. 4) Перейдемо до пункту 1. Зверніть увагу, що у першому пункті конкретно сказано, яке саме число необхідно вибрати у випадку співпадання двох чисел. Саме це і є характерною рисою алгоритму, виконавцем якого може бути навіть не підготовлена в даній галузі людина.

5 Exit Описування алгоритмів за допомогою схем Схеми дозволяють зобразити алгоритм в наочній графічній формі. Цей спосіб вже вимагає деяких знань. Вони полягають у знайомстві зі спеціальними стандартами графічних зображень блоків, в середину яких поміщаються команди алгоритму. На малюнку зображена блок-схема алгоритму Евкліда.

6 Exit Призначення блоків Початок Введення даних Вибір напрямку виконання алгоритму в залежності від виконання умови Виконання операцій, в результаті яких відбувається зміна значення даних Виведення даних Кінець алгоритму При створенні схеми алгоритму блоки із записаними в них командами з'єднуються між собою стрілками, які визначають черговість виконання дій алгоритму. Для запису команд всередині блоків використовується природна мова з елементами математичної символіки.

7 Exit Початок та кінець алгоритму Блоки початку і кінця алгоритму використовуються при записі повного алгоритму задачі. Вони є пасивними блоками, що тільки вказують на початок та кінець алгоритму але не задають конкретних команд.

8 Exit Блоки введення та виведення Блок введення використовують для вказівки, значення для яких величин слід ввести в процес розв'язання алгоритму. Блок виведення використовують для вказівки, значення яких величин слід вивести (показати). Обидва блоки мають точку входу – вгорі блоку входу та точку виходу – унизу блоку.

9 Exit Блок розгалуження В результаті перевірки умови під час вибору напрямку виконання алгоритму виникають два можливі шляхи для його продовження. Ці шляхи зображуються стрілками з позначеннями «так» (+) та «ні» (-). Перехід по стрілці з позначенням «так» відбувається у випадку, коли умова виконується, а перехід по стрілці з позначенням «ні» - у протилежному випадку. Такий блок називають блоком розгалуження. Він має один вхід та два альтернативних (взавємовиключаючих) виходи.

10 Exit Арифметичний операторний блок Арифметичний операторний блок використовують для виконання математичних розрахунків за формулою, що наведена в середині блоку та призначення отриманих результатів вказаним змінним. Арифметичний операторний блок має один вхід та один вихід.

11 Exit Блок виклику допоміжного алгоритму У блок-схемах передбачена можливість виклику додаткових алгоритмів для виконання певних дій. Цьому слугує блок виклику допоміжного алгоритму. Блок виклику допоміжного алгоритму має одну точку входу та одну точку виходу. Наведений блок відсутній у алгоритмі Евкліда, але цей блок може бути використаний в іншому алгоритмі.

12 Exit Блок модифікації Блок модифікації використовують для організації арифметичних циклів. тобто, процесів, що повторюються задане число разів. (Детально на циклах зупинемося на наступних заняттях). Блок модифікації має точку початкового входу (1), точку виходу в цикл (2), точку входу із циклу (3) та точку виходу із циклу (4). (1) (2) (3)(4)

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

14 Exit Базові структури алгоритмів. Будь-який алгоритм можна уявити, собі як деяку структуру, що складається з окремих базових елементів. Зрозуміло, що при такому підході до алгоритмів вивчення основних принципів їх конструювання слід починати з ознайомлення з цими базовими елементами. Визначають три базових структурних елементи: лінійний, розгалужений, циклічний.

15 Exit Лінійний елемент алгоритму Лінійним елементом алгоритму називається така операція, яка визначає один елементарний крок обробки або відображення інформації. До таких операцій відносяться дії зміни значення деяких Величин, введення та виведення інформації тощо. Декілька лінійних елементів можуть об'єднуватися і утворювати складену лінійну структуру.

16 Exit Повна структура розгалуження Розгалуженим елементом алгоритму називається така операція, за допомогою якої здійснюється вибір однієї з двох можливих дій в залежності від сформульованої умови. При виконанні операції, яка є розгалуженим елементом, виконується лише одна з дій. В тому випадку, коли умова справджується, продовження виконання алгоритму відбувається за стрілкою "так", в протилежному випадку - за стрілкою "ні". Наведений приклад розгалуженого елемента є повним, тобто містить вибір однієї з двох передбачених дій. Нижче показаний фрагмент алгоритму присвоєння змінній c більшого із значень змінних a та b

17 Exit Скорочена структура розгалуження Скорочена форма розгалуження у випадку невиконання умови не передбачає ніяких дій. При цьому алгоритм переходить до виконання наступного базового елемента. Наведений приклад розгалуженого елемента є скороченим. Нижче показаний фрагмент алгоритму присвоєння змінній x значення її модуля.

18 Exit Структура повторення (циклу) Циклічним елементом алгоритму називається така операція, за допомогою якої здійснюється визначена кількість повторень однієї або декількох дій згідно сформульованої умови (ітераційні цикли). Більшість алгоритмів містить серії багатократно повторюваних дій. Для їх визначення використовують циклічну конструкцію, яка ще носить назву «повторення». Є два типи ітераційних циклів: з передумовою з післяумовою. Наведений прикладом циклічної конструкції. так ні

19 Exit Ітераційний цикл з передумовою В цьому випадку спочатку перевіряється умова і, якщо вона справджується, то вказана дія черговий раз повторюється, якщо ж ні, то повторення дії припиняється. Наведений прикладом циклічної конструкції з передумовою. ні так

20 Exit Ітераційний цикл з післяумовою У випадку повторення з післяумовою спочатку відбувається виконання вказаної дії, а після цього визначається, чи є потреба виконувати її знову. Причому в цьому випадку повторення відбувається в разі, якщо умова не справджується. Наведений прикладом циклічної конструкції з післяумовою.

21 Exit Типи алгоритмів Розрізняють наступні типи алгоритмів: лінійні розгалужені циклічні складні

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

23 Exit Розгалужені алгоритми Алгоритми, які містять хоча б одну умову, в результаті перевірки якої забезпечується перехід до одного з можливих кроків, називаються розгалуженими.

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

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

26 Exit Види допоміжних алгоритмів Стосовно допоміжних алгоритмів можна розглядати: внутрішні, локальні, що створюються в межах даного алгоритму і доступні для використання тільки у цьому алгоритмі; зовнішні, глобальні, які можна використовувати у різних незалежних алгоритмах. Такі допоміжні алгоритми частіше за все об'єднуються у так звані бібліотеки. Для користування цими бібліотеками повинні існувати інструкції з описом всіх допоміжних алгоритмів, які входять до них, та правила користування ними.

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

28 Exit Питання для самоконтролю: 1. Назвіть всі базові структури алгоримів і дайте їм визначення. 2. Який елемент алгоритму називається лінійним? 3. Який елемент алгоритму називається розгалуженим? Які є форми розгалуження? 4. Який елемент алгоритму називається циклічним? На які типи вони поділяються? 5. Які алгоритми називаються лінійними? 6. Які алгоритми називаються розгалуженими? 7. Які алгоритми називаються циклічними? 8. Які алгоритми називаються допоміжними? 9. Якими можуть бути допоміжні алгоритми? 10. Яким чином визначається тип великих за об'ємом і складністю алгоритмів?