Поняття алгоритму - Українське програмування

Головна

Програмування

- Основи програмування

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

Написав kims

П'ятниця, 03 лютого 2012 14:16

Одним із важливих етапів розв’язування задачі за допомогою комп’ютера є складання алгоритму. Кожен із нас щоденно використовує різні алгоритми: інструкції, правила , рецепти тощо. Розглянемо приклади алгоритмів.

1. Алгоритм відкривання дверей.

Витягнути ключ.

Вставити ключ в замок.

Повернути ключ двічі за годинниковою стрілкою.

Вийняти ключ.

2. Алгоритм “Як проїхати до школи”

Вийти із дому.

Повернути направо.

Пройти два квартали до автобусної зупинки.

Сісти в автобус №5.

Проїхати дві зупинки.

Вийти із автобуса.

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

Ми можемо тепер сказати, що алгоритм – це організована послідовність дій спрямована на розв’язування задачі. Дане формулювання, звичайно не можна вважати означенням алгоритму. Абсолютного строгого визначення алгоритму не існує. Поняття алгоритму є в інформатиці фундаментальним ( як наприклад, точка і пряма – у геометрії, простір і час – у фізиці).

Слово «алгоритм» походить від латинської форми написання імені арабського математика аль-Хорезмі (800-847 рр). Він написав книгу про обчислення за допомогою десяти цифр і правилах арифметичних дій з числами. Ім’я вченого аль-Хорезмі перейшло в термін algotithmi, алгоритм.

З курсу математики вам відомі алгоритми розв’язання багатьох задач. Наприклад: виконання арифметичних дій над багатозначними числами, розв’язання лінійних та квадратних рівнянь, поділ відрізок пополам, побудова бісектриси кута тощо. Розглянемо приклади алгоритмів деяких задач.

Приклад 1.3 Обчислити значення y за формулою y=(ax+b)(cx-d).

Щоб розв’язати цю задачу, потрібно виконати послідовність наступних дій:

1) Помножити а на х, результат позначити через R1;

2) До R1 додати b , результат позначити через R2;

3) Помножити C на x, результат позначити через R3;

4) Від R3 відняти d , результат позначити через R4;

5) Помножити R2 на R4, за результат взяти y.

Приклад 1.4 Знайти найбільший спільний дільник двох натульних чисел m і n. Складемо алгоритм розв’язку цієї задачі, який базується на тому, що якщо m>n, то НСД(m,n) такий як і чисел m-n, n. Алгоритм буде такий:

1) якщо числа рівні, то взяти за результат або число m або число n. В іншому випадку продовжити алгоритм;

2) визначити більше із чисел;

3) замінити більше число різницею більшого і меншого чисел;

4) почати алгоритм спочатку.

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

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

Приклад 1.5 Побудувати графік функції y=a*|x|, якщо a>0.

Алгоритм побудови має такий вигляд.

1) накреслити графік функції y=ax;

2) стерти частину графіка лівіше осі ординат;

3) симетрично відобразити частину графіка, яка залишилась відносно осі ординат.

Приклад 1.6 Гра Баше. ( В грі бере участь двох учасників). Є 15 предметів. Суперники ходять по черзі, за кожний хід будь-який із учасників може взяти 1, 2 або 3 предмети. Програє той, хто візьме останній предмет.

Алгоритм виграшу для першого гравця має наступний вид:

Взяти 2 предмети;

Другий і наступний ходи робити так, щоб кількість предметів, взятих разом із суперником за черговий хід в сумі становила 4.

Практичні завдання

В продовженні курсу ви дізнаєтесь про виконавців алгоритму та властивості алгоритму.

Зміст курсу лекцій та практичних занять по Delphi.

Кузбит І.М.

( 9 Проголосувало )

Схожі статті:

Новіші матеріали:

Старіші матеріали:

Коментарі