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

Термін «алгоритм» походить від назви середньоазіатського міста Хорезм. У цьому місті в IX ст. жив математик і астроном Мухамед, який сформулював правила чотирьох арифметичних дій. Арабський варіант його імені Аль-Хорезмі, що в Європі записувався латиною як Algorithmi, і став основою терміна "алгоритм". Однак пізніше під словом алгоритм стали розуміти правила знаходження найбільшого спільного дільника, які були викладені ще в працях великого давньогрецького математика Евкліда (III ст. до н.е.). За наших часів поняття алгоритму було узагальнено, і словом "алгоритм" стали позначати опис будь-якої послідовності дій. Поняття алгоритму є одним із фундаментальних у сучасній математиці й інформатиці.

Алгоритм - це точний і зрозумілий опис послідовності дій над заданими об'єктами, що дозволяє отримати кінцевий результат.

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

Словесний запис алгоритмів

Для зображення алгоритмів можна користуватися різними способами запису, які відрізняються ступенем наочності і точності. Деякі способи орієнтовані на виконавця - людину, інші - на виконання комп'ютером, треті є допоміжними (використовуються для полегшення міркувань). У цьому параграфі ми розглянемо три способи подання алгоритмів: за допомогою звичайної мови спілкування, із використанням блок-схем і за допомогою навчальної алгоритмічної мови.

Словесний спосіб запису заснований на тій чи іншій природній мові спілкування (див. алгоритм Евкліда). Однак словесний запис алгоритму відрізняється від звичайних мовних конструкцій ретельнішим добором слів і фраз, який не допускає повторень або двозначного тлумачення. Крім того, у запису алгоритму можуть використовуватися математичні символи і вирази.

Розглянемо словесний спосіб запису ще на одному простому прикладі. Маємо знайти модуль величини x (тобто значення | X |) і надати цього значення змінній Y. Під час побудови алгоритму скористаємося визначенням модуля: | x | =x при x> 0 і | x =-x при x<0. Алгоритм можна записати у такий спосіб.

1. Початок.

2. Ввести числове значення величини X.

3. Якщо X> 0, то Y надати значення X, інакше Y надати значення -X.

4. Вивести значення Y.

5. Кінець.

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

Блок-схеми алгоритмів

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

Ці елементи називаються блоками початку і кінця алгоритму. Стрілки вказують напрямок виконання алгоритму. Блок Початок має одну вихідну стрілку, а блок Кінець - одну вхідну стрілку.

У алгоритмах часто використовуються команди введення і виведення значень. Цим командам відповідають блоки введення-виведення:

Тут лівий блок означає введення величини x, а правий блок - виведення Y. За допомогою наведених вище блоків ви можете скласти найпростіший алгоритм введення величини X

Відповідно до цього алгоритму в програму вводиться значення величини X. Однак програма, що складається тільки з операції введення, навряд чи доціль­на. Звичайно над введеною величиною виконуються певні дії, що позначаються прямокутними (операторними) блоками:

У середині прямокутників записані вирази, що виконуються над величинами. Лівий блок означає присвоювання змінній X значення суми Х + 1 (про операції присвоювання йтиметься в наступному параграфі). Правий блок відповідає за знаходження різниці x-Y і надання значення різниці змінній z. Операторні блоки можуть мати кілька входів і лише один вихід.

Запишемо найпростіший алгоритм обчислення квадрата якогось числа:

Відповідно до цього алгоритму вводиться величина X, потім обчислюється квадрат цієї величини (добуток X*x) і виводиться отримане значення.

Усі наведені вище блоки дозволяють організувати послідовне виконання інструкцій алгоритму. Однак на практиці часто виникають ситуації, коли залежно від виконання будь-якої умови маємо змінити послідовний хід обчислень. Прикладом такої умови є нерівність X> 0 в алгоритмі знаходження модуля числа X (див. попередній пункт). У схему алгоритму логічна умова вводиться за допомогою умовного блока. Цей блок прийнято зображати у вигляді ромба з одним входом і двома виходами:

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

Наведемо як приклад алгоритм обчислення модуля числа:

Дата добавления: 2013-12-13