Анотація: Алгоритм є базовим поняттям для тих, хто хоче почати програмувати на будь-якій мові програмування. Будь-яке завдання може бути формалізована алгоритмічно. Щоб зрозуміти, з чого почати, розглянемо основні види алгоритмів. Мета даної лекції - ознайомити студентів з поняттям алгоритму; показати, що така абстрактна річ як алгоритм оточує нас у повсякденному житті.
Існує кілька визначень поняття алгоритму. Наведемо два найпоширеніших.
Алгоритм - послідовність чітко визначених дій, виконання яких веде до вирішення завдання. Алгоритм, записаний на мові машини, є програма рішення задачі.
Алгоритм - це сукупність дій, що призводять до досягнення результату за кінцеве число кроків.
Взагалі кажучи, перше визначення не передає повноти сенсу поняття алгоритм. Використовується слово "послідовність" звужує це поняття, тому що дії не обов'язково повинні слідувати один за одним - вони можуть повторюватися або містити умову.
- Дискретність (від лат. Discretus - розділений, переривчастий) - це розбиття алгоритму на ряд окремих закінчених дій (кроків).
- Детермінованість (від лат. Determinate - визначеність, точність) - будь-яка дія алгоритму має бути строго і недвозначно визначено у кожному випадку. Наприклад, алгоритм проїзду до одного, якщо до зупинки підходять автобуси різних маршрутів, то в алгоритмі має бути вказаний конкретний номер маршруту 5. Крім того, необхідно вказати точну кількість зупинок, яке треба проїхати, скажімо, три.
- Кінцівка - кожна дія окремо і алгоритм в цілому повинні мати можливість завершення.
- Масовість - один і той же алгоритм можна використовувати з різними вихідними даними.
- Результативність - алгоритм повинен призводити до достовірного вирішення.
Основна мета алгоритмізації - складання алгоритмів для ЕОМ з подальшим вирішенням завдання на ЕОМ.
- Будь-який прилад, куплений в магазині, забезпечується інструкцією щодо його використання. Дана інструкція і є алгоритмом для правильної експлуатації приладу.
- Кожен шофер повинен знати правила дорожнього руху. Правила дорожнього руху однозначно регламентують поведінку кожного учасника руху. Знаючи ці правила, шофер повинен діяти за певним алгоритмом.
- Масовий випуск автомобілів став можливий тільки тоді, коли був придуманий порядок складання машини на конвеєрі. Певний порядок складання автомобілів - це набір дій, в результаті яких виходить автомобіль.
Існує кілька способів запису алгоритмів. На практиці найбільш поширеним є такі форми подання алгоритмів:
- словесна (запис на природній мові);
- псевдокоду (напівформалізоване опису алгоритмів на умовному алгоритмічній мові, що включають в себе як елементи мови програмування, так і фрази природної мови, загальноприйняті математичні позначення та ін.);
- графічна (зображення з графічних символів - блок-схема);
- програмна (тексти на мовах програмування - код програми).
Розглянемо докладніше кожен варіант запису алгоритмів на прикладі наступної задачі. Потрібно знайти приватне двох чисел.
Словесний спосіб записи алгоритмів є опис послідовних етапів обробки даних. Алгоритм поставив у довільному викладі природною мовою. Відповідь при цьому отримує людина, яка виконує команди відповідно до словесної записи.
Приклад словесної записи:
- задати два числа, які є діленим і дільником;
- перевірити, чи дорівнює дільник нуля;
- якщо дільник не дорівнює нулю, то знайти приватне, записати його у відповідь;
- якщо дільник дорівнює нулю, то у відповідь записати "немає рішення".
Словесний спосіб немає поширення, бо такі описания: строго не формалізуються; страждають багатослівність записів; допускають неоднозначність тлумачення окремих приписів.
Наведемо основні керуючі структури псевдокоду в табл. 1.1.
Таблиця 1.1. Базові керуючі структури псевдокоду
В даному прикладі використовується три змінні: ділене, дільник і приватне. Ділене і дільник задаються виконавцем довільними числами. Приватне вважається лише в тому випадку, якщо дільник не дорівнює нулю.
Графічна реалізація алгоритму є блок-схему. Блок-схема складається з блоків певної форми, з'єднаних стрілками. Відповідь при цьому отримує людина, яка виконує команди відповідно до блок-схемі. Більш докладно про блок-схемах буде розказано в Лекції 2.
Програмна реалізація алгоритму - це комп'ютерна програма, написана на якій-небудь алгоритмічній мові програмування, наприклад: С ++, Pascal, Basic і т.д. Програма складається з команд певної мови програмування. Відзначимо, що одна і та ж блок-схема може бути реалізована на різних мовах програмування. Відповідь при цьому отримує ЕОМ, а не людина. Більш докладно про складання програм на мові програмування С ++ дивитися Лекцію 3.
Розрізняють три основних види алгоритмів:
- лінійний алгоритм,
- розгалужується алгоритм,
- циклічний алгоритм.
Лінійний алгоритм - це алгоритм, в якому дії виконуються одноразово і строго послідовно.
Найпростіший приклад реалізації лінійного алгоритму - шлях з університету додому.
Словесний спосіб записи даного алгоритму:
- вийти з університету на зупинку;
- почекати потрібний автобус;
- сісти на потрібний автобус;
- оплатити проїзд;
- вийти на необхідної зупинці;
- дійти до будинку.
Очевидно, що даний приклад відноситься до лінійного алгоритму, тому що всі дії слідують одне за іншим, без умов і повторень.
Розгалужується алгоритм - це алгоритм, в якому в залежності від умови виконується або одна, або інша послідовність дій.
Найпростіший приклад реалізації разветвляющегося алгоритму - якщо на вулиці йде дощ, то необхідно взяти парасольку, інакше не брати парасольку з собою.
Наведений вище приклад псевдокоду по знаходженню приватного двох чисел також відноситься до розгалужується алгоритму.
Циклічний алгоритм - це алгоритм, команди якого повторюються певну кількість разів поспіль.
Найпростіший приклад реалізації циклічного алгоритму - при читанні книги будуть повторюватися одні й ті ж дії: прочитати сторінку, перегорнути і т.д.
Більш докладно про лінійному, розгалужуються і циклічних алгоритмах дивитися Лекцію 2.
короткі підсумки
Будь-яке завдання може бути розбита на елементарні дії. Для будь-якої математичної задачі або ситуації з життя можна скласти алгоритм рішення. Алгоритм може бути описаний словесно, псевдокодом, графічно або програмно. Завдання завжди вирішується за допомогою базових типів алгоритму - лінійного, разветвляющегося або циклічного.
- Що таке алгоритм?
- В чому полягає завдання алгоритмізації?
- Якими властивостями володіє алгоритм?
- Які види алгоритму бувають?
вправи
- Складіть алгоритми по походу в магазин за яблуками. Використовуйте лінійний і розгалужується алгоритми. Реалізуйте їх словесно.
- Складіть алгоритм по знаходженню коренів квадратного рівняння через дискримінант. Використовуйте розгалужується алгоритм. Реалізуйте його псевдокодом.