1.Поняття алгоритму. Властивості алгоритму.
2. Форми подання алгоритму.
3. Базова структура алгоритму.
Поняття алгоритму. Властивості алгоритмів
Алгоритм – це скінчена система вказівок, виконання яких одна за однією через скінчене число кроків призводить до мети (розв’язування задачі).
До них можна віднести такі завдання, як «Купити хліб», «Закрити двері на ключ» та ін.
Інші ж завдання, навпаки, такі важкі, що вимагають тривалих міркувань і зусиль для пошуку розв'язання й досягнення поставленої мети.
Наприклад, розв'язання завдань «Написати контрольну роботу на 5 балів» або «Вільно розмовляти іноземною мовою» вимагають виконання набагато більшої кількості складних дій, ніж розв'язання завдання «Купити морозиво». При цьому рішення навіть найпростішого завдання звичайно здійснюється за кілька послідовних кроків.
Процес покупки хліба можна представити так:
Виконавець алгоритму
Кожний алгоритм створюється з розрахунку на конкретного виконавця, тому можна сказати, що алгоритм — це точні розпорядження (указівки, команди, операції, інструкції) виконавцеві здійснити послідовність дій, спрямованих на розв’язання поставленої задачі.
Алгоритм складається із команд — окремих указівок виконавцеві виконати деякі конкретні дії.
Команди алгоритму виконуються одна за одною, і на кожному кроці відомо, яка команда повинна виконуватися. Почергове виконання команд за кінцеве число кроків приводить до розв’язання задачі.
Для того щоб виконавець міг розв’язати задачу за заданим алгоритмом, він повинен уміти виконувати кожну з дій, що вказується командами алгоритму.
Виконавцями алгоритмів можуть бути людина, тварини, автомати, тобто ті, хто розуміє та може виконати вказівки алгоритму.
Фрезерний станок з числовим програмним управлінням
Подання алгоритмів
Процес алгоритмізації — це визначення елементарних дій та порядку їх виконання для розв’язання поставленого завдання.
Існують різні способи запису алгоритмів (словесний, формульно-словесний, метод блок-схем, програмний та ін.), які застосовуються для представлення алгоритму у вигляді, що однозначно розуміється і розробником, і виконавцем алгоритму.
Для опису алгоритмів людина часто користується природною мовою, але для запису багатьох алгоритмів природна мова виявилась незручною, тому виникла необхідність у створенні штучних мов, наприклад мови математичних формул, хімічних процесів тощо.
1.Словесно-формульний – основний спосіб написання алгоритмів на етапі постановки задачі.
Задача:
Вказати послідовність дій, які необхідно виконати для обчислення виразу (αx+b)x+c при заданих значеннях α,b,x,c.
Помножити a на b;
До отриманого результату додати b;
Отриманий результат помножити на х;
До отриманого результату додати с.
2.У вигляді блок-схем – це таке графічне представлення алгоритму, при якому розв’язок задачі зображується у вигляді різних геометричних фігур.
так
ні
Існує спеціальна навчальна алгоритмічна мова, яка була створена для запису алгоритмів на папері; вона використовує слова природної мови, але має більш жорстку структуру. Найбільше поширення для запису логічної структури алгоритмів отримали графічні (структурні) схеми, які спрощують складання та аналіз алгоритму, полегшують перехід від запису алгоритму до написання програми.
алг <назва алгоритму> (<тип змінних>)
арг <імена змінних-аргументів>
рез <імена змінних-результатів>
поч <тип та імена проміжних змінних>
<тіло алгоритму>
кін
Базові структури алгоритму
Базові структури алгоритму — це структури, за допомогою яких створюється алгоритм для розв’язання певної задачі.
Основна особливість базових алгоритмічних структур — це їх повнота, тобто цих структур достатньо для створення найскладнішого алгоритму.
1. Лінійний алгоритм — це найпростіший тип алгоритму, що містить одну серію простих команд, які виконуються послідовно.
До неї відносяться алгоритми, що складаються лише з простих команд. Простими з точки зору комп'ютера являються ті команди, що виконуються виконавцем безумовно, тобто після першої команди виконується друга, потім третя і т.д.
S1
S2
Sn
Приклад
Наведемо приклад побудови блок-схеми лінійного алгоритму «Обчислити шлях за швидкістю і часом руху».
Словесний запис алгоритму задачі буде таким:
1. Ввести швидкість v і час руху t.
2. Обчислити шлях за формулою
S = v·t .
3. Вивести шлях S
Базова структура галуження
Структура галуження – це структура, яка передбачає виконання одного з декількох варіантів обчислювального процесу. Структура галуження реалізується через повну та неповну форми алгоритмів галуження та вибору.
Розгалужений алгоритм (галуження) – у класичному варіанті цей алгоритм розглядається як вибір однієї з двох альтернативних дій залежно від виконання заданої умови.
Повне галуження — це галуження, в якому визначені різні дії в разі виконання, і в разі невиконання заданої умови.
Неповне галуження — це розгалуження, в якому дії визначені тільки у разі виконання (або у разі невиконання) заданої умови.
Розвилка також називається, «як-що-то-інакше»,
Базова структура повторення
Циклічний алгоритм (цикл, структура повторення) — це алгоритм, у якому передбачено повторення деякої серії команд.
За допомогою цієї структури описуються однотипні дії, що повторюються декілька разів. Такі алгоритми забезпечують виконання довгої послідовності дій, записаних порівняно короткою послідовністю команд.
Саме використання циклів дозволяє у повній мірі реалізувати швидкодію комп’ютерів.
Основна особливість базових алгоритмічних структур — це їх повнота, тобто цих структур достатньо для створення найскладнішого алгоритму.
Третьою базовою структурою є Цикл, який передбачає повторне виконання певних дій, необхідне для більшості програм.
Цикл ДОКИ
а) У структурі цикл-ДОКИ (цикл з передумовою)для виконання вказівки спочатку треба визначити, істинне чи хибне твердження Р. Якщо Р істинне, ТО виконується вказівка S, і знову повертаються до визначення істинності твердження Р.
Якщо ж твердження Р хибне, то виконання вказівки вважається закінченим.
Цикл означає повторне виконання тієї самої дії або блока дій, що мають назву тіла циклу, доти, доки певний логічний вираз залишається істинним.
Цикл ДО
б) У структурі цикл-ДО (цикл з післяумовою) спочатку виконується вказівка S, а потім визначається істинність твердження Р.
Якщо твердження Р хибне, то знову виконується вказівка S і визначається істинність твердження Р.
Якщо ж твердження Р істинне, то виконання вказівки вважається закінченим.
Цикл з параметрами
Цикл з параметрами (цикл з покроковою зміною аргументу) – це цикл, у якому тіло циклу виконується відому кількість разів, що реалізовано через покрокову зміну параметра.
Цикл з параметром реалізується таким чином.
Параметру циклу надається початкове значення, і з ним виконується тіло циклу. Параметр змінюється на заданий крок, і знову виконується тіло циклу, і так, доки параметр не дістане кінцевого значення
ПЦ:=ПЗ; КЗ; К
Серія
Інтерактивна вправа
Інтерактивна вправа
Завдання 5
1. Закип'ятити воду.
2. У чашку покласти 1 чайну ложку кави.
3. Залити окропом.
4. Дати настоятися.
Задача
Завдання додому: