Зміст матеріалу: 1. Поняття алгоритму. Приклади. 2. Виконавці алгоритмів. 3. Способи опису алгоритмів. 4. Властивості алгоритмів. 5. Схема алгоритму. 6. Основні конструкції алгоритмів (лінійні, розгалужені, циклічні). Приклади. А л г о р и т м и

Поняття алгоритму Термін алгоритм існував задовго до появи компютерів. Він походить від імені давнього філософа і математика з Хорезму (Узбекистан), що жив у 9 ст. Мухаммед аль-Хорезмі. Саме він у своїх трактатах описав правила (алгоритми) додавання, віднімання, множення і ділення багатозначних чисел, якими ми користуємося сьогодні. Алгоритм – це правило (інструкція), що задає (описує) послідовність команд (дій, вказівок), які потрібно виконати над вхідними даними (обєктами) для отримання результату. Приклади: 1)Завдання: Обчислити Алгоритм виконання: 1.Виконати віднімання 92 – 32 і запамятати результат Виконати ділення 360 : 60 і запамятати результат 6. 2)Завдання: Закипятити воду. Алгоритм Кипятіння води 1. Налити в чайник води.2. Запалити плитку. 3. Поставити чайник на плитку.4. Чекати поки вода закиппть. 5. Зняти чайник з плитки.6. Виключити плитку.

Виконавці алгоритмів Вчинки людей підпорядковані досягненню конкретної мети. Обдумуючи план на день, ми складаємо алгоритми розвязування побутових чи профе- сійних задач. Отже, людина є виконавцем алгоритмів. Для полегшення фізичної та інтелектуальної праці люди створили різні технічні пристрої: машини, роботи, автомати, компютери. Кожен виконавець може виконати певну кількість команд, які називають- ся допустимими командами виконавця. Розглянемо таких виконавців: людину, робота, компютер. 1. Людина здатна виконати практично необмежену кількість різних ко- манд: іти, лічити, шити, їсти, спати і т.д. Тому на дії людей розумні обмеже- ння накладаються законами, мораллю й сумлінням. 2. Кількість команд для робота є значно меншою. Наприклад, уперед, направо і т.д. – це допустимі команди робота. Але робот не виконає таких команд: їсти, пити, спати. 3. Додавати, віднімати, множити, ділити, малювати, грати – це команди для компютера, але він не може виконати команду, наприклад, переміще- ння у просторі, яка характерна для людини і робота. Команди, які не може виконати виконавець, називаються недопустимими командами виконавця.

Способи опису алгоритмів Є такі способи опису алгоритмів : 1) словесно-формульний (описували алгоритми при розгляді прикл. 1 і 2) 2) графічний у вигляді блок-схем; 3) алгоритмічною мовою або мовою програмування. Будемо вчитися описувати алгоритм мовою програмування, а не алго- ритмічною мовою, тому що правильність алгоритму (програми) записаної на мові програмування можна перевірити лише за допомогою компютера. Наведемо приклад словесного способу опису алгоритмів. Алгоритмові дає- мо назву, команди нумеруємо. Назву пишемо з великої літери. Приклад : 3) Завдання: Скласти алгоритм переходу вулиці. Алгоритм Перехід 1. Подивитися наліво. 2. Якщо немає перешкоди, то йти до середини вулиці, інакше пропусти- ти машини і йти до середини вулиці. 3. Подивитися направо. 4. Якщо немає перешкоди, то завершити перехід, інакше пропустити ма- шини і завершити перехід. Дайте відповіді на запитання: 1. Хто може бути виконавцем цього алгоритму? 2. Чи можна в алгоритмі поміняти будь-які дві команди місцями, чи буде новий алгоритм правиль- ний?

Властивості алгоритмів Існують такі властивості алгоритмів : - Визначеність алгоритму Алгоритм визначений, якщо він складається з допустимих команд виконавця, які можна виконати для зазначених вхідних даних. Невизначеність, наприклад, виникне в алгоритмі прикладу 1, якщо в знаменнику буде записано (ділення на 0 не допустиме). - Скінченність алгоритму Послідовність команд, які потрібно виконати, має бути скінченною. Алгоритм прикладу 1 – скінченний. Він складається з трьох дій. Нескінченний, наприклад, алгоритм обчислення ділення 5 : 3. - Результативність алгоритму Алгоритм результативний, якщо він дає результати. Наведені вище алгоритми є результативними. - Правильність алгоритму Алгоритм правильний, якщо його виконання забезпечує досягнення мети. Якщо в алгоритмі прикладу 3 поміняти місцями пункти 1 і 2 або 3 і 4, то отримаємо неправильний алгоритм. - Формальність алгоритму Якщо алгоритм можуть виконати не один, а декілька виконавців і одержати однакові результати. - Масовість алгоритму Алгоритм масовий, якщо він придатний для розвязування не однієї задачі, а низки подібних задач. Алгоритм прикладу 1 немасовий, а прикладу 3 (перехід вулиці) – масовий. Приклад масовості алгоритму: Написати алгоритм розвязування лінійного рівняння ах+в=с, де а, в та с – будь-які числа і а0.

Схема алгоритму Зясували, що одним із способів опису алгоритмів є графічний, тобто за допомогою блок-схем. На такій схемі операції виконавця подаються блоками і зєднані між собою стрілками. Є різні позначення блоків в залежності від конкретних дій. прямокутник - арифметичний блок, в який записується математична формула, наприклад, а=b+с; D=b 2 -4ac і т.д. В таких блоках знак = – це знак присвоєння, іноді його записують так :=. ромб – логічний блок, в який записується умова. Наприклад, а>b, D0 і т.д. паралелограм - в який записуються дані, які вводяться і виводяться з алгоритму. еліпс - записують початок і кінець алгоритму. шестикутник - запис умови циклу для

Основні конструкції алгоритмів Існують такі алгоритмічні конструкції: 1) лінійна (послідовність простих команд); 2) розгалужена (розгалужені алгоритми); 3) циклічна (циклічні алгоритми).

Лінійні алгоритми Якщо алгоритм складається лише з послідовності простих команд, то його називають лінійним. Наприклад: Знайдіть значення виразу z = x-5y+10, де y = 3x+4 Блок-схема має вигляд:

Розгалужені алгоритми 1) Повна форма команди розгалуження: якщо умова то серія 1 інакше серія 2 Блок-схема повної форми команди розгалуження має вигляд: 2) Скорочена форма команди розгалуження: якщо умова то серія 1 Блок-схема скороченої форми команди розгалуження має вигляд: Якщо в алгоритмі крім простих команд є ще і умовна команда, то такий алгоритм називають розгалуженим. Умовну команду утворюють за допомогою деякої умови та трьох службових слів: якщо, то, інакше. Алгоритм розгалуження має вигляд:

Умовна команда – це вказівка виконати одну з двох команд: команду 1 (серія 1), якщо умова справджується, або команду 2 (серія 2), якщо умова не справджується. Замість однієї команди може бути серія команд. Приклад : Знайти корені квадратного рівняння a x 2 +bx+c=0, де a, b, c > 0. Словесний спосіб опису алгоритму: Алгоритм Розвязки квадратного рівняння 1. Обчислити D=b 2 -4ac 2. Якщо D<0, то рівняння розвязку немає 3. Якщо D>0, то 4. Якщо D=0, то x 1 =x 2 =b/2a Блок-схема має вигляд:

Циклічні алгоритми Циклічні алгоритми забезпечують повторне виконання команд скінченну кількість разів. Існує два види циклічних алгоритмів: 1) цикл поки ; 2) цикл для. 1) Цикл поки має вигляд: поки умова пц серія команд кц Зазначені команди (чи одна команда) виконується поки справджується умова. Тут поки, пц, кц – службові слова. Приклад: Скласти алгоритм наповнення водою 10-літрового відра, користуючись 3-літровою банкою. Словесний спосіб опису алгоритму: Алгоритм Наповнення 1. Наповнити банку водою. 2. Поки відро неповне, перелити воду з банки у відро, і наповнити банку водою. Виконавець алгоритму виконає в циклі команди 4 рази. Відро наповниться, але при цьому 2л води розілється на землю.

2) Цикл для має вигляд: для і від А до В крок С пц серія команд кц Приклад: Знайти значення функції y=x 2 для х від -5 до 5 з кроком 0,5 Словесний спосіб опису алгоритму: Алгоритм Значення 1. Для х від -5 до 5 з кроком 0,5 виконати y=x Вивести значення відповідно х та у. Блок-схема має вигляд:

Приклад: Скласти блок-схему алгоритму знаходження максимального з трьох чисел а, в, с. Блок-схема має вигляд: