Зверніть увагу на наступні обставини. Для того, щоб знайти цей план-алгоритм, потрібно трохи подумати (на те вона і головоломка). Потрібно також обґрунтувати правильність цього плану, інакше кого-небудь з'їдять. Нарешті, потрібно так оформити рішення, щоб його зміг зрозуміти і виконати перевізник – тобто виконавець алгоритму.
Це і є ті основні проблеми, з якими постійно має справу програміст, розробляючи програми для комп'ютерів.
Алгоритм додавання дробів можна задати наступною послідовністю команд:
Приклад 1.1 Алгоритм додавання дробів.
Алгоритм Сума;
Вихідна інформація A, B, C, D; {скласти A/B і C/D}
Результат E,F; {E/F = A/B + C/D}
1. Обчислити Y = B*D; {Перейти до наступної команди}
2. Обчислити X1 = A*D; {Перейти до наступної команди}
3. Обчислити X2 = B*C; {Перейти до наступної команди}
4. Обчислити X = X1+X2; {Перейти до наступної команди}
5. Обчислити Z = НОД(X,Y); {Перейти до наступної команди}
6. Обчислити Е = X div Z; {Перейти до наступної команди}
7. Обчислити F = Y div Z. {Закінчити роботу}.
Вихідна інформація цього алгоритму представлена чотирма цілими числами A, B, C, D. Це – чисельники і знаменники доданків. Результат роботи алгоритму – числа E і F – чисельник і знаменник суми.
Інформацію, вихідну для алгоритму, прийнято називати його входом, а результат виконання – виходом.
Знати, яку саме задачу вирішує алгоритм, необхідно тільки тому, хто хоче використовувати цей алгоритм для своїх цілей. Таким чином, перші два рядки приклада 1 містять інформацію, необхідну користувачеві алгоритму. Виконавець алгоритму нічого не знає і не повинен знати про те, яку саме задачу він вирішує. У цьому і полягає властивість формальності виконання алгоритму.
Власне алгоритм складається з 7-ми команд, кожна з яких містить команду – виконати одну з арифметичних дій над цілими числами: додавання, множення, обчислення НОД і div (обчислення неповної частки). Крім виконання арифметичної дії, кожна команда запам'ятовує результат як значення величини, зазначеної в лівій частині рівності, що входить у команду. Нарешті, кожна команда (у неявному виді) містить указівку на наступну виконувану команду – перейти до виконання команди з наступним номером.
Таким чином, алгоритм описує деталізований по кроках процес перетворення інформації. Виконавець алгоритму не тільки виконує дії, але і запам'ятовує їхні результати. Для відображення цього факту в записі алгоритму ми використовуємо літерні позначення даних. Ці позначення називають іменами, а самі дані – величинами.
Для позначення величин в алгоритмах використовуються імена.
Послідовний порядок виконання команд необхідний тільки для того, щоб результати виконання попередніх команд можна було б використовувати як вихідні дані у виконуваній команді.
У нашому прикладі команди 1, 2, 3 обчислення величин X1, Х2, Y можна виконувати або паралельно (у три руки), або змінювати порядок їхнього виконання. Від цього результат алгоритму не зміниться. Це ж можна сказати про команди 6 і 7. Відповідь на питання про те, чи представляють ці варіанти запису алгоритму той самий алгоритм, чи ні, залежить від точного визначення поняття алгоритму. Істотною є та обставина, що дві форми запису можуть представляти алгоритми, що дають той самий результат.
Відзначимо ще одну важливу властивість алгоритму – він розрахований на виконавця, який розуміє і уміє виконувати команди алгоритму.
Учень 6-го класу, швидше за все, уміє складати, множити і ділити куточком цілі числа. Однак не всі діти вміють знаходити НСД – найбільший спільний дільник двох цілих чисел. Це означає, що вони не зможуть виконати Ваш алгоритм.
Рівень деталізації опису алгоритму визначається набором допустимих команд. Цей набір називають набором команд Виконавця або Інтерпретатора.
1.2. Виконавець алгоритмів і його система команд
При складанні алгоритму треба мати на увазі, що його буде виконувати Виконавець (Інтерпретатор) – деякий фізичний або абстрактний пристрій, що однозначно розпізнає і точно виконує (інтерпретує) кожну команду алгоритму.
Для виконання алгоритму додавання дробів Виконавець повинен вміти оперувати з цілими числами. Крім того, виконавець повинен уміти запам'ятовувати результати виконання операцій як значення відповідних змінних і переходити до виконання наступної команди.
Уявимо собі, що в нашому розпорядженні є Виконавець, що інтерпретує команди – операції арифметики цілих чисел – додавання, віднімання, множення, обчислення неповної частки (div) і залишку (mod), обчислення НСД і НСК із запам'ятовуванням результатів і умінням переходити до наступної команди. Тоді для цього Виконавця можна складати різноманітні алгоритми арифметичних обчислень – тобто обчислень, заданих формулами типу
X = НСД((A + B) div 100, (A*B - 7) mod 10),
використовуючи команди, аналогічні командам алгоритму з приклада 1.1. Для цього необхідно, з огляду на пріоритети арифметичних операцій, правильно визначити послідовність виконання арифметичних дій і записати її у виді послідовності команд.
Приклад 1.2 Алгоритм поділу відрізка навпіл за допомогою циркуля і лінійки.
Алгоритм Середина відрізку;
Вхід Точки A, B – кінці відрізка АВ;
Вихід Точка Е - середина відрізка AB.
Побудувати коло O1 з центром A і радіусом AB;
Побудувати коло O2 з центром B і радіусом AB;
Знайти точки С і D перетину кіл O1 і O2;
Побудувати пряму l1 через точки C, D;
Побудувати пряму l2 через точки A, В;
Знайти точку E перетину прямих l1 , l2.
У прикладі 1.2 Виконавець має систему команд, за допомогою яких можна вирішувати геометричні задачі на побудови за допомогою циркуля і лінійки. Назвемо цього Виконавця Геометром. Виконання алгоритму полягає в послідовному виконанні кожної побудови і переході до наступної команди. Тому нумерувати команди алгоритму не потрібно. Перелічимо команди Геометра:
Побудувати відрізок s з кінцями в точках A, В:
Вхід: точки А, В.
Вихід: відрізок s з кінцями в точках A, В.
Побудувати пряму l через точки A, B:
Вхід: точки А, В.
Вихід: пряма l, що проходить через точки A, В.
Побудувати коло O з центром A і радіусом ВC:
Вхід: точки А, B, C.
Вихід: коло O з центром A і радіусом BC.
Знайти точку А перетину прямих l1 і l2 :
Вхід: прямі l1, l2.
Вихід: точка A перетину l1 і l2.
Знайти точки А і В перетину кола O і прямої l;
Вхід: коло О, пряма l.
Вихід: точки A і В перетину кола О і прямої l.
Знайти точки А і В перетину кіл O1 і O2;
Вхід: кола О1, О2.
Вихід: точки A і В перетину кіл О1 і О2.
На відміну від приклада 1.1, у прикладі 1.2 величинами є найпростіші геометричні фігури – точки, прямі, кола. Вони служать і вихідними даними, і результатами команд. Кожна з команд виконавця Геометр виконує одну з дій, які можна виконати за допомогою циркуля або лінійки.
Таким чином, набір команд виконавця Геометр орієнтований на рішення точно визначеного класу задач – геометричних задач на побудови за допомогою циркуля і лінійки.
Опис кожної команди містить у собі:
· точний «зовнішній вигляд»,
· вхідні величини,
· вихідні величини,
· зв'язок між вхідними і вихідними величинами.
Сукупність величин, розглянута разом з набором припустимих перетворень, утворює предметну область.
Виконавець алгоритмів уміє виконувати команди, кожна з яких визначає одне з припустимих перетворень. Алгоритм є послідовністю цих команд. Тому виконавець призначений для виконання будь-якого алгоритму над даною предметною областю.
Наведемо ще кілька прикладів предметних областей.
1. Шахи. Ця предметна область являє собою шахівницю, на якій розташовані білі і чорні шахові фігури. Кожна з фігур описується сукупністю своїх припустимих ходів і правилами взаємодії з іншими фігурами. Тому в шахах можливі постановки алгоритмічних задач.
Наприклад: Побудувати алгоритм, що переводить коня з поля a1 на поле h8. Інших фігур на шахівниці немає.
2. Дороги міста. Ця предметна область представлена картою міста, на якій позначені вулиці і перехрестя, а також списком видів транспортних засобів, які їздять містом. Визначені правила руху уздовж кожної вулиці, що дозволяють або забороняють рух уздовж вулиці в даному напрямку тому або іншому видові транспорту, а також аналогічні правила проїзду через перехрестя. В цій ситуації можливі постановки алгоритмічних задач.
Наприклад: Проїхати на легковому автомобілі від одного перехрестя до іншого через мінімально можливе число проміжних перехресть.
3. Черепашка. Алгоритмічна мова Лого, призначена для навчання основам алгоритмізації молодших школярів, виконавцем алгоритмів пропонує Черепашку. Черепашка вміє рухатися в різних напрямках, що задаються в командах, малювати хвостом лінії уздовж напрямку свого руху. Програміст має можливість описувати алгоритми малювання простих картинок.
Наприклад: Намалювати будиночок з дахом, одними дверима і двома вікнами.
1.3. Основні властивості алгоритмів
Алгоритм має наступні властивості:
1. Елементарність. Кожна команда з набору команд Виконавця містить вказівку виконати деяку елементарну (не деталізовану більш детально) дію, яку розуміє, однозначно і точно виконує Виконавець.
Поняття елементарності відносне. Так, в алгоритмі приклада 1.1 є команда обчислення НСД двох чисел. Це означає, що Виконавець уміє знаходити НСД, причому алгоритм обчислення (алгоритм Евкліда або який-небудь інший) прихований від людини, яка складає алгоритми для цього Виконавця. Якщо набір команд Виконавця не містить команди обчислення НСД, обчислення НСД має бути визначеним у вигляді алгоритму.
Приклад 1.3 Алгоритм Евкліда обчислення найбільшого спільного дільника цілих позитивних чисел A і B: НСД(A, B).
Алгоритм Евкліда;
Вхід A, B;
Вихід: D;
{Коментар: D - найбільший спільний дільник A і B}
