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

Програмування - це записування чогось з використанням чужого малознайомого мови. З розвитком цієї галузі знання розробники пішли ще далі і навчилися записувати "щось", навіть не розуміючи, як воно звучить російською мовою. Новачки вчаться писати код відразу на C++ чи php, використовуючи безліч бібліотек, і навіть не розуміють, як те, що вони створюють, звучить на їх рідній мові. Алгоритмізація займається роз'ясненням і доведенням до зрозумілого цього "щось".

Алгоритмізація

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


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

Поняття алгоритму

Комп'ютер не вміє вирішувати завдання, він здатний виконувати прості дії в зазначеному порядку. "Як же калькулятор?" - запитаєте ви. Він теж є плодом праці програмістів, які створили програму, що використовує певні алгоритми для одержання необхідних результатів. Розглянемо абстрактну ситуацію. Що слід зробити, якщо попросити знайти корені квадратного тричлена людини, яка не знайома з методами рішення рівнянь?

Очевидно, що його необхідно навчити вирішувати квадратні рівняння. Відбувається це за наступною схемою:

Вибрати спосіб вирішення.

Вивчити всі деталі обраного способу.

Пояснити перші два пункти майбутньому виконавцю на зрозумілій йому мові.

Потім можна буде давати виконавцю завдання на розв'язування квадратного рівняння. І якщо перші два кроки прості і зрозумілі - всі способи вирішення описані у відповідній літературі, то третій крок представляє складність. Як можна гарантувати, що ідеї, які використовуються при розв'язанні задачі, будуть сприйняті виконавцем так само, як ви це розумієте? Тут ми впритул підходимо до поняття алгоритму. Практика показує, що для правильного пояснення чого-то кому-то необхідно дотримуватися наступні кроки:

визначити вихідні дані (змінна і коефіцієнти квадратного рівняння);

розбити процес рішення однозначно відомі компоненти для виконавця (формули дискримінанта та знаходження коренів);

вказати порядок виконання етапів (спочатку обчислити дискриминант, потім коріння);

встановити умова, при якому рішення вважається завершеним (перевірити знайдені коріння, підставивши їх у рівняння на місце змінних);

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

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

Основні властивості алгоритму

Дискретність. Процес рішення задачі завжди складається з суворо відокремлені один від одного дій, званих кроками, що мають певний порядок. Визначеність. Кожен крок повинен бути зрозумілим і однозначним як за змістом, так і в ключі дії, які належить вчинити. Результативність. Алгоритм повинен давати результат. При цьому кількість кроків може обчислюватися тисячами або мільйонами, але вони завжди повинні приводити до результату. Масовість. Будь-який алгоритм, розроблений для вирішення якої-небудь задачі, повинен бути застосовний до всім завданням цього типу для всіх допустимих вихідних даних.

Можливості комп'ютера

Для правильного створення алгоритмів під комп'ютери важливо розуміти їх можливості. Розглянемо спочатку величини, з якими працює ЕОМ. У загальному випадку їх можна розділити на числові та текстові, постійні і змінні.
Під постійними числами розуміються всі числа: 31510010 5 їх особливістю є незмінність протягом всієї роботи програми. Змінні величини змінюють своє значення в ході виконання коду і позначаються, як правило, літерами: x, y, max, min і т. д. Текстові змінні аналогічно числовим бувають постійними або змінними. У першому випадку це просто текст: "добре", "a і b" та ін. У другому - таке ж символьне позначення, як і числових змінних: name, city і т. п. Відмінність між ними полягає головним чином у виділюваної пам'яті комп'ютера під зберігання змінної. Операції, які здатний виконувати комп'ютер:

Зчитувати дані з пристроїв введення (клавіатура, миша, файли).

Обчислення значень з використанням математичні функції: додавання, віднімання, sin, cos, ln тощо - в кожній мові програмування свій набір вбудованих функцій.

Висновок даних на екран, папір, мережний інтерфейс).

Перехід між етапами виконання програми.

Порівняння двох величин (більше, менше, дорівнює).

Це основні операції, які можуть виконуватися більшістю мов програмування.

Способи опису алгоритмів

Словесний. Це найпростіший спосіб. Його прикладом може служити кулінарний рецепт. Допускається використання простих математичних формул. Графічний. Опис з допомогою схем. Це особливий спосіб запису алгоритмів з використанням свого роду загальноприйнятого алгоритмічного мови - фігур і блоків, що мають певне значення: прямокутник - простий дію, похилий паралелограм - введення/виведення, ромб - умова і т. д. Використання алгоритмічної мови. Аналогічно графічному, це також особливий спосіб запису алгоритму. Існує безліч алгоритмічних мов. Їх правила не є строгими, інакше це був би мову програмування. Розглянемо приклад алгоритму розрахунку заробітної плати залежно від стажу, записаний за допомогою алгоритмічної мови.

алг заробітна плата (int ST, real ZP)
арг ST
рез ZP
початок
якщо ST < 5 то zp = 150
інакше
якщо ST <= 15 то ZP = 180
інакше ZP = 180 + (ST - 15)*10
кінець

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

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

Існує безліч алгоритмів, створених для вирішення самих різних завдань. Наприклад, будь-який підручник вищої математики містить сотні алгоритмів: рішення системи лінійних рівнянь, знаходження екстремумів функції, обчислення інтеграла і т. д. Однак при детальному розгляді їх структури виявляється, що всі алгоритми можна розділити на кілька видів. Розглянемо ці види алгоритмів з прикладами.

лінійний (обчислення результату додавання або множення, обмін значеннями декількох змінних);

розгалужений (визначення найбільшого з декількох чисел);

циклічний (сортування масиву, обчислення факторіала).

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

Принципи алгоритмізації

Визначити вихідні дані.

Вибрати спосіб вирішення.

Розбити вибрані спосіб на кроки виходячи з можливостей комп'ютера (мови програмування).

Виконати алгоритм у вигляді схеми, визначивши чіткий порядок кроків.

Висновок результатів обчислень.

Позначити перехід до виходу схеми.

Налагодження алгоритму

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

Лінійні алгоритми

Лінійним є алгоритм, в якому кроки йдуть послідовно один за одним. Будь-який алгоритм, який не містить розгалужень і циклів, є лінійним. Розглянемо приклад алгоритму, що вирішує таку задачу: в двох клітках сидять вовк і заєць, потрібно поміняти їх місцями. Ключем до вирішення цієї задачі є додаткова клітина temp, яку слід використовувати, щоб поміняти місцями тварин.

Розгалужуються алгоритми

Як і випливає з назви, алгоритм має кілька гілок. Суть роботи полягає у виборі одного з можливих варіантів обчислювального процесу в залежності від яких-небудь умов. Схематичне розгалуження зображується ромбоподібним блоком, всередині якого вказується умова, а по боках від нього розташовуються гілки вибору в залежності від того, умова істинно або хибно. Розгалужений алгоритм і приклади його застосування можна знайти повсюдно. У програмуванні це типова конструкція if-else, яка є майже в будь-якій мові. Наведемо приклад алгоритму для розв'язання задачі про знаходження найбільшого серед трьох чисел.

Циклічний алгоритм

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

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

Блок обчислення результатів. Це основне тіло циклу.

Перевірка умови закінчення циклічного процесу. Якщо забути вказати умову, при якому слід завершити цикл, алгоритм буде виконуватися нескінченно.

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

Існує кілька видів циклічних алгоритмів: з постумовою, передумовою і параметром. Побудуємо циклічний алгоритм на прикладі знаходження факторіала числа N.

Інші типи алгоритмів

Існує ще ряд алгоритмів, які відрізняються за класифікацією або походженням.

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

Імовірнісні алгоритми. Їх робота заснована на теорії ймовірності і математичній статистиці.

Евристичні алгоритми. Використовують практичні міркування у своїй роботі, без суворого математичного обґрунтування.

Генетичні алгоритми. Застосовують біологічні ідеї в своїй роботі.

Та інші.