Етапи вирішення технічних завдань
Етапи рішення задачі на ЕОМ
Бурхливий розвиток обчислювальної техніки призводить до широкого проникнення математичних методів в науку, техніку і народне господарство. Відбувається інтенсивний процес математизації не лише природних і технічних, а й гуманітарних наук. Все це розширює класи завдань, що вирішуються на ЕОМ. Рішення на ЕОМ завдань кожного класу має свою специфіку, однак його можна розбити на кілька етапів, характерних для більшості завдань,
Постановка завдання і побудова алгоритму
Рішення задачі починається з її постановки, викладеної на мові суворо визначених математичних понять. Тому, щоб можна було вирішити завдання, пов'язане з дослідженням реального об'єкта, необхідно спочатку описати цей об'єкт в математичних термінах, тобто побудувати його математичну модель. Математична модель об'єкту дозволяє поставити завдання математично і тим самим звести рішення реального завдання до вирішення задачі математичної. Вона, відбиваючи найбільш суттєві властивості реального досліджуваного об'єкта чи явища, не тотожна цьому об'єкту, а є лише наближеним його описом. У цьому сенсі математичні моделі - ті ж відносні істини, за посередництвом яких пізнається реальна дійсність з асимптотическим наближенням до істини абсолютної. Ступінь відповідності моделі реальному об'єкту перевіряється практикою, експериментом. Критерій практики дає можливість оцінити побудовану модель і уточнити її у разі потреби.
Метод математичного моделювання реальних явищ виник і отримав свій розвиток в фізиці.
Так, ще в XVII ст. Г. Галілеєм була запропонована добре відома тепер математична модель, що описує рух тіла, кинутого під кутом до горизонту із заданою початковою швидкістю. Перша велика математична модель в фізиці - механіка Ньютона.
Впровадження математичних методів дослідження в інші науки також тісно пов'язане зі створенням математичних моделей. Наприклад, такі моделі успішно використовуються для прогнозу погоди, дослідження та передбачення поведінки тропічних тайфунів і т. п. Створено моделі, що прогнозують глобальні наслідки термоядерного конфлікту, які відіграють значну роль у боротьбі за знищення ядерної зброї.
Все більше значення набуває математичне моделювання в економіці. Створено, наприклад, моделі для вивчення загальних закономірностей політичної економії, багатогалузеві моделі загальнодержавного планування, моделі, що описують функціонування окремих галузей та окремих підприємств.
Успіхи застосування обчислювальної техніки в багатьох областях людського знання визначаються не тільки розвитком методу математичного моделювання. Наприклад, створення потужних інформаційно-пошукових систем може зробити істотний вплив на методи наукової роботи в таких областях, як філософія чи історія, а створення людино-машинних систем автоматизованого проектування дозволить не тільки по-новому організувати роботу конструктора і скоротити терміни проектування, але і значно скоротити терміни і вартість натурних випробувань і «доведення» розроблених конструкцій.
Отже, побудова математичної моделі приводить до математичної постановці реального завдання. Далі необхідно знайти спосіб вирішення цього завдання. Дуже часто рішення такого завдання не вдається отримати в явному вигляді, тобто у вигляді формули, що зв'язує вихідні дані та результати. У таких випадках рішення шукається у вигляді алгоритму.
Побудова алгоритму - наступний етап вирішення завдання з використанням ЕОМ.
Описані етапи вирішення завдання виконуються людиною і носять творчий характер - кожна нова задача вимагає нових підходів і нових способів вирішення, і цьому навряд чи можна навчити навіть аналізуючи способи вирішення багатьох інших вже відомих задач.
Проте вже етап побудови алгоритму включає крім творчих і чисто технологічні питання. Використовуючи певну дисципліну при конструюванні алгоритму, можна отримати алгоритм з явно вираженою структурою, що полегшує його розуміння і подальшу роботу з ним.
Аналогічна технологія може бути використана і на наступних етапах - при розробці програми для ЕОМ і роботі з цією програмою. Звичайно, і тут від людини вимагається чимало творчості і винахідливості, тим не менше саме ці етапи рішення задачі на ЕОМ отримали найбільшу технологічний розвиток.
Єдина технологія, що застосовується на етапах розробки алгоритму та програми, може значно полегшити і прискорити загальний процес рішення задачі на ЕОМ.
ЕОМ ніяких рішень не приймає. Рішення приймає людина, а ЕОМ тільки допомагає знайти варіанти вирішення. Що ж потрібно зробити щоб знайти такі варіанти вирішення? Основні етапи рішення задачі проектування технологічних установок. Розглянемо ці етапи.
Вибір завдання. Вибір завдання - найважливіше питання. Рішення завдання, особливо досить складною, - це дуже важка справа вимагає багато часу. І якщо завдання обрана невдало, то це може призвести не тільки до жаль про втрачений час.
Вибір завдання завершується її змістовної постановкою. Коли вибирається завдання і здійснюється її змістовна постановка, природно, доводиться мати справу з фахівцями в предметної області (з управління, проектування, розробки технологічних процесів) Ці фахівці, як правило, дуже добросовісні, з одного боку, чудово знають свій предмет, з іншого - не завжди мають уявлення про те, що потрібно для вирішення задачі на ЕОМ. Тому змістовна постановка задачі найчастіше виявляється перенасиченої відомостями, які абсолютно зайві для роботи на ЕОМ.
Пояснимо сказане на простому прикладі. Нехай перед нами стоїть таке завдання Потрібно визначити, скільки у п'ятирічної дівчинки Маші, яка слухає тата, маму, дідуся і бабусю, щоранку їсть манну кашу, каже «дякую» і миє руки перед їжею, було яблук, якщо, коли двірник сусіднього будинку тітка Даша дала їй ще два яблука, у цієї чудесної білявої дівчинки, вже другий рік займається фігурним катанням, що колекціонує марки і співаючої в хорі при Будинку народної творчості, що знаходиться в прекрасному будинку, побудованому за проектом, удостоєному другої премії на республіканському конкурсі, їх стало п'ять.
Ось так досить часто виглядає змістовна постановка задачі, зроблена ерудованими фахівцями в предметної області, кілька далекими від знання вимог ЕОМ
Елементи теорії алгоритмів
1. Поняття алгоритму та властивості алгоритму
Поняття алгоритму є основним при складанні будь-якого виду програм для ЕОМ. Програма для ЕОМ - алгоритм, оформлений спеціальним чином, кінцева послідовність приписів, що визначають процес переробки вхідних даних у вихідні.
Слово "Алгоритм" походить від algorithmi - латинського написання імені аль-Хорезмі, під яким в середньовічній Європі знали видатного математика з Хорезму (місто в сучасному Узбекистані) Мухаммеда бен Мусу, який жив у 783-850 рр.. У своїй книзі "Про індійський рахунку" він сформулював правила запису натуральних чисел за допомогою арабських цифр і правила дій над ними стовпчиком. Надалі алгоритмом стали називати точний припис, що визначає послідовність дій, що забезпечує отримання необхідного результату з вихідних даних. Алгоритм може бути призначений для виконання його людиною або автоматичним пристроєм. Створення алгоритму, нехай навіть самого простого, - процес творчий. Він доступний винятково живим істотам, а довгий час вважалося, що тільки людині. Інша справа - реалізація вже наявного алгоритму. Її можна доручити суб'єкту чи об'єкту, який не зобов'язаний вникати в суть справи, а можливо, і не здатний його зрозуміти. Такий суб'єкт або об'єкт прийнято називати формальним виконавцем. Прикладом формального виконавця може служити пральна машина-автомат, яка неухильно виконує покладені їй дії, навіть якщо ви забули покласти в неї порошок. Людина теж може виступати в ролі формального виконавця, але в першу чергу формальними виконавцями є різні автоматичні пристрої, і комп'ютер в тому числі. Кожен алгоритм створюється з розрахунку на цілком конкретного виконавця. Ті дії, які може здійснювати виконавець, називаються його його допустимими діями. Сукупність допустимих дій утворює систему команд виконавця. Алгоритм повинен містити тільки ті дії, які допустимі для даного виконавця.
Алгоритм - формальне припис (вказівка), однозначно визначає зміст і послідовність операцій, які переводять сукупність вихідних даних у шуканий результат - рішення поставленої задачі.
зазвичай формулюють кілька загальних властивостей алгоритмів, що дозволяють відрізняти алгоритми від інших інструкцій.
З визначення алгоритму і розглянутих прикладів можна сформулювати такі вимоги до його властивостей.
Такими властивостями є:
· Дискретність (переривчастість, роздільність) - алгоритм повинен представляти процес рішення задачі як послідовне виконання простих (або раніше визначених) кроків. Кожна дія, передбачене алгоритмом, виконується тільки після того, як закінчилося виконання попереднього.
· Визначеність - кожне правило алгоритму має бути чітким, однозначним і не залишати місця для сваволі. Завдяки цій властивості виконання алгоритму носить механічний характер і не вимагає ніяких додаткових вказівок або відомостей про розв'язуваної задачі.
· Результативність (кінцівка) - алгоритм повинен призводити до вирішення завдання за кінцеве число кроків.
· Масовість - алгоритм розв'язання задачі розробляється в загальному вигляді, тобто, він повинен бути застосовний для деякого класу задач, які відрізняються лише вихідними даними. При цьому вихідні дані можуть вибиратися з деякої області, яка називається областю застосовності алгоритму.
Засоби, які використовуються для запису алгоритмів, в значній мірі визначаються тим, для якого виконавця призначається алгоритм. Якщо алгоритм призначений для виконавця - людини, то його запис може бути не повністю формалізована, на перше місце тут висуваються зрозумілість і наочність, тому для запису таких алгоритмів може використовуватися природний або графічна мова, лише б запис відображала всі основні особливості алгоритму. Для запису алгоритмів, призначених для виконавців - автоматів, необхідна формалізація, тому в таких випадках застосовують спеціальні формальні мови.
Словесна запис алгоритму. Словесна форма зазвичай використовується для алгоритмів, орієнтованих на виконавця - людини. Команди алгоритму нумерують, щоб мати можливість на них посилатися. Наведемо в якості ще одного прикладу словесної форми запису алгоритму класичний алгоритм Евкліда для знаходження найбільшого загального дільника двох натуральних чисел:
Дано два цілих позитивних числа m і n. Потрібно знайти їх найбільший спільний дільник, тобто найбільше позитивне число, на яке ділиться без залишку як m, так і n.
Суть алгоритму Евкліда можна представити наступними трьома етапами.
1. Знаходження залишку. Розділимо m на n. Нехай залишок дорівнює г:
0 <р <n.
2. Перевірка залишку на рівність нулю. Якщо р = О, обчислення кінчається, n - шукане число.
3. Заміна m ← n, n ← р. Повторити етап 1.
Приклад
1. Дано m = 125, n = 75. Наші найбільший спільний дільник.
1) 125: 75 = 1. Частка менша 1, залишок від ділення дорівнює 50,
2) Залишок від ділення не дорівнює 0. Проводимо заміну змінних:
m = 75, n = 50 і повторюємо процес,
1) 75: 50 = 1, m = 25.
2) m = 50, n = 25, г = 0.
Повторюємо процедуру.
1) 50:25 = 2.
2) Залишок від ділення дорівнює 0, тому n = 25 є найбільшим загальним дільником.
2. До відрізку АВ в точці М відновити перпендикуляр. Алгоритм рішення цієї геометричної задачі може бути описаний у вигляді чотирьох послідовних кроків (рис. 1).
1) З довільної точки О площині радіусом ОМ описати коло, що перетинає відрізок АВ.
2) Відзначити точку З перетину кола з відрізком АВ,
3) Знайти точку D перетину кола з прямою ОС.
Рис. 1. Відновлення перпендикуляра до відрізка в даній точці
4) З'єднати точку М і D.
Якщо строго виконувати всі розпорядження, то буде отриманий однозначну відповідь,
Форма запису команд не формалізується. У командах крім слів можуть використовуватись символи та формули. Важливо лише те, щоб кожна команда була зрозуміла виконавцю, точно визначала всі його дії і могла б бути їм виконана.
Для вирішення завдання можна розробити кілька алгоритмів. Кожен алгоритм створюється з розрахунку на цілком конкретного виконавця. Якщо планується реалізація алгоритму на машині, слід враховувати його пристосованість до ЕОМ, простоту і час реалізації на машині. Алгоритм повинен бути розроблений таким чином, щоб виконавець міг навіть не вникати у зміст того, що він робить, і разом з тим отримувати потрібні результати. Виконання вже наявного алгоритму можна доручити суб'єкту чи об'єкту, який не зобов'язаний вникати в суть справи, а можливо, і не здатний його зрозуміти.
Опис алгоритму
Правила виконання арифметичних операцій або геометричних побудов представляють собою алгоритми.
Вказівка формули або послідовності формул, розрахунки за якими потрібно виконати для отримання результатів.
Приклад
Обчислити об'єм круглого конуса. Для обчислення слід скористатися формулою
При заданих двох розмірах (r - радіус основи і h - висота конуса) ця формула дає розпорядження виконавцю, як діяти, тобто визначені характер і послідовність дій.
Представлення алгоритму у вигляді схеми.
При реалізації завдання на ЕОМ, особливо у разі написання програм на машинно-орієнтованих мовах, і завдань складних алгоритмів використовуються схеми алгоритмів.
Схема алгоритму - графічне представлення ходу рішення задачі.
При виконанні схем алгоритмів і програм окремі функції алгоритмів і програм (з урахуванням їх деталізації) відображаються у вигляді умовних графічних позначень - символів (ГОСТ 19.003-80 та ГОСТ 19.002-80). У табл. 1 наведені основні символи, використовувані в схемах алгоритмів. Схеми повинні бути виконані у форматах, встановлених за ГОСТ 2.301-68.
Таке графічне представлення називається схемою алгоритму або блок-схемою. У блок-схемі кожному типу дій (вводу вихідних даних, обчислення значень виразів, перевірки умов, управлінню повторенням дій, закінчення обробки і т.п.) відповідає геометрична фігура, представлена у вигляді блочного символу. Блокові символи з'єднуються лініями переходів, визначальними черговість виконання дій. У таблиці наведені найбільш часто вживані символи.
При виконанні схем символам присвоюють порядкові номери. Порядковий номер проставляють ліворуч у верхній частині символу у розриві його контуру. Символи з'єднуються прямими лініями (лініями потоку).
Лінії потоку повинні бути паралельні лініям зовнішньої рамки схеми. Напрямки ліній потоку зверху вниз і зліва направо приймають за основні і, якщо вони не мають зламів, їх можна стрілками не позначати. В інших випадках напрямок лінії потоку позначати стрілкою обов'язково.
Записи усередині символу виконуються креслярським шрифтом за ГОСТ 2.304-81. Записи усередині символу або поруч з ним повинні бути короткими. Символи застосовуються з урахуванням виконуваних функцій.
Таблиця 1. Основні символи для схем алгоритмів
Етапи рішення задачі на ЕОМ
Бурхливий розвиток обчислювальної техніки призводить до широкого проникнення математичних методів в науку, техніку і народне господарство. Відбувається інтенсивний процес математизації не лише природних і технічних, а й гуманітарних наук. Все це розширює класи завдань, що вирішуються на ЕОМ. Рішення на ЕОМ завдань кожного класу має свою специфіку, однак його можна розбити на кілька етапів, характерних для більшості завдань,
Постановка завдання і побудова алгоритму
Рішення задачі починається з її постановки, викладеної на мові суворо визначених математичних понять. Тому, щоб можна було вирішити завдання, пов'язане з дослідженням реального об'єкта, необхідно спочатку описати цей об'єкт в математичних термінах, тобто побудувати його математичну модель. Математична модель об'єкту дозволяє поставити завдання математично і тим самим звести рішення реального завдання до вирішення задачі математичної. Вона, відбиваючи найбільш суттєві властивості реального досліджуваного об'єкта чи явища, не тотожна цьому об'єкту, а є лише наближеним його описом. У цьому сенсі математичні моделі - ті ж відносні істини, за посередництвом яких пізнається реальна дійсність з асимптотическим наближенням до істини абсолютної. Ступінь відповідності моделі реальному об'єкту перевіряється практикою, експериментом. Критерій практики дає можливість оцінити побудовану модель і уточнити її у разі потреби.
Метод математичного моделювання реальних явищ виник і отримав свій розвиток в фізиці.
Так, ще в XVII ст. Г. Галілеєм була запропонована добре відома тепер математична модель, що описує рух тіла, кинутого під кутом до горизонту із заданою початковою швидкістю. Перша велика математична модель в фізиці - механіка Ньютона.
Впровадження математичних методів дослідження в інші науки також тісно пов'язане зі створенням математичних моделей. Наприклад, такі моделі успішно використовуються для прогнозу погоди, дослідження та передбачення поведінки тропічних тайфунів і т. п. Створено моделі, що прогнозують глобальні наслідки термоядерного конфлікту, які відіграють значну роль у боротьбі за знищення ядерної зброї.
Все більше значення набуває математичне моделювання в економіці. Створено, наприклад, моделі для вивчення загальних закономірностей політичної економії, багатогалузеві моделі загальнодержавного планування, моделі, що описують функціонування окремих галузей та окремих підприємств.
Успіхи застосування обчислювальної техніки в багатьох областях людського знання визначаються не тільки розвитком методу математичного моделювання. Наприклад, створення потужних інформаційно-пошукових систем може зробити істотний вплив на методи наукової роботи в таких областях, як філософія чи історія, а створення людино-машинних систем автоматизованого проектування дозволить не тільки по-новому організувати роботу конструктора і скоротити терміни проектування, але і значно скоротити терміни і вартість натурних випробувань і «доведення» розроблених конструкцій.
Отже, побудова математичної моделі приводить до математичної постановці реального завдання. Далі необхідно знайти спосіб вирішення цього завдання. Дуже часто рішення такого завдання не вдається отримати в явному вигляді, тобто у вигляді формули, що зв'язує вихідні дані та результати. У таких випадках рішення шукається у вигляді алгоритму.
Побудова алгоритму - наступний етап вирішення завдання з використанням ЕОМ.
Описані етапи вирішення завдання виконуються людиною і носять творчий характер - кожна нова задача вимагає нових підходів і нових способів вирішення, і цьому навряд чи можна навчити навіть аналізуючи способи вирішення багатьох інших вже відомих задач.
Проте вже етап побудови алгоритму включає крім творчих і чисто технологічні питання. Використовуючи певну дисципліну при конструюванні алгоритму, можна отримати алгоритм з явно вираженою структурою, що полегшує його розуміння і подальшу роботу з ним.
Аналогічна технологія може бути використана і на наступних етапах - при розробці програми для ЕОМ і роботі з цією програмою. Звичайно, і тут від людини вимагається чимало творчості і винахідливості, тим не менше саме ці етапи рішення задачі на ЕОМ отримали найбільшу технологічний розвиток.
Єдина технологія, що застосовується на етапах розробки алгоритму та програми, може значно полегшити і прискорити загальний процес рішення задачі на ЕОМ.
ЕОМ ніяких рішень не приймає. Рішення приймає людина, а ЕОМ тільки допомагає знайти варіанти вирішення. Що ж потрібно зробити щоб знайти такі варіанти вирішення? Основні етапи рішення задачі проектування технологічних установок. Розглянемо ці етапи.
Вибір завдання. Вибір завдання - найважливіше питання. Рішення завдання, особливо досить складною, - це дуже важка справа вимагає багато часу. І якщо завдання обрана невдало, то це може призвести не тільки до жаль про втрачений час.
Вибір завдання завершується її змістовної постановкою. Коли вибирається завдання і здійснюється її змістовна постановка, природно, доводиться мати справу з фахівцями в предметної області (з управління, проектування, розробки технологічних процесів) Ці фахівці, як правило, дуже добросовісні, з одного боку, чудово знають свій предмет, з іншого - не завжди мають уявлення про те, що потрібно для вирішення задачі на ЕОМ. Тому змістовна постановка задачі найчастіше виявляється перенасиченої відомостями, які абсолютно зайві для роботи на ЕОМ.
Пояснимо сказане на простому прикладі. Нехай перед нами стоїть таке завдання Потрібно визначити, скільки у п'ятирічної дівчинки Маші, яка слухає тата, маму, дідуся і бабусю, щоранку їсть манну кашу, каже «дякую» і миє руки перед їжею, було яблук, якщо, коли двірник сусіднього будинку тітка Даша дала їй ще два яблука, у цієї чудесної білявої дівчинки, вже другий рік займається фігурним катанням, що колекціонує марки і співаючої в хорі при Будинку народної творчості, що знаходиться в прекрасному будинку, побудованому за проектом, удостоєному другої премії на республіканському конкурсі, їх стало п'ять.
Ось так досить часто виглядає змістовна постановка задачі, зроблена ерудованими фахівцями в предметної області, кілька далекими від знання вимог ЕОМ
Елементи теорії алгоритмів
1. Поняття алгоритму та властивості алгоритму
Поняття алгоритму є основним при складанні будь-якого виду програм для ЕОМ. Програма для ЕОМ - алгоритм, оформлений спеціальним чином, кінцева послідовність приписів, що визначають процес переробки вхідних даних у вихідні.
Слово "Алгоритм" походить від algorithmi - латинського написання імені аль-Хорезмі, під яким в середньовічній Європі знали видатного математика з Хорезму (місто в сучасному Узбекистані) Мухаммеда бен Мусу, який жив у 783-850 рр.. У своїй книзі "Про індійський рахунку" він сформулював правила запису натуральних чисел за допомогою арабських цифр і правила дій над ними стовпчиком. Надалі алгоритмом стали називати точний припис, що визначає послідовність дій, що забезпечує отримання необхідного результату з вихідних даних. Алгоритм може бути призначений для виконання його людиною або автоматичним пристроєм. Створення алгоритму, нехай навіть самого простого, - процес творчий. Він доступний винятково живим істотам, а довгий час вважалося, що тільки людині. Інша справа - реалізація вже наявного алгоритму. Її можна доручити суб'єкту чи об'єкту, який не зобов'язаний вникати в суть справи, а можливо, і не здатний його зрозуміти. Такий суб'єкт або об'єкт прийнято називати формальним виконавцем. Прикладом формального виконавця може служити пральна машина-автомат, яка неухильно виконує покладені їй дії, навіть якщо ви забули покласти в неї порошок. Людина теж може виступати в ролі формального виконавця, але в першу чергу формальними виконавцями є різні автоматичні пристрої, і комп'ютер в тому числі. Кожен алгоритм створюється з розрахунку на цілком конкретного виконавця. Ті дії, які може здійснювати виконавець, називаються його його допустимими діями. Сукупність допустимих дій утворює систему команд виконавця. Алгоритм повинен містити тільки ті дії, які допустимі для даного виконавця.
Алгоритм - формальне припис (вказівка), однозначно визначає зміст і послідовність операцій, які переводять сукупність вихідних даних у шуканий результат - рішення поставленої задачі.
зазвичай формулюють кілька загальних властивостей алгоритмів, що дозволяють відрізняти алгоритми від інших інструкцій.
З визначення алгоритму і розглянутих прикладів можна сформулювати такі вимоги до його властивостей.
Такими властивостями є:
· Дискретність (переривчастість, роздільність) - алгоритм повинен представляти процес рішення задачі як послідовне виконання простих (або раніше визначених) кроків. Кожна дія, передбачене алгоритмом, виконується тільки після того, як закінчилося виконання попереднього.
· Визначеність - кожне правило алгоритму має бути чітким, однозначним і не залишати місця для сваволі. Завдяки цій властивості виконання алгоритму носить механічний характер і не вимагає ніяких додаткових вказівок або відомостей про розв'язуваної задачі.
· Результативність (кінцівка) - алгоритм повинен призводити до вирішення завдання за кінцеве число кроків.
· Масовість - алгоритм розв'язання задачі розробляється в загальному вигляді, тобто, він повинен бути застосовний для деякого класу задач, які відрізняються лише вихідними даними. При цьому вихідні дані можуть вибиратися з деякої області, яка називається областю застосовності алгоритму.
Засоби, які використовуються для запису алгоритмів, в значній мірі визначаються тим, для якого виконавця призначається алгоритм. Якщо алгоритм призначений для виконавця - людини, то його запис може бути не повністю формалізована, на перше місце тут висуваються зрозумілість і наочність, тому для запису таких алгоритмів може використовуватися природний або графічна мова, лише б запис відображала всі основні особливості алгоритму. Для запису алгоритмів, призначених для виконавців - автоматів, необхідна формалізація, тому в таких випадках застосовують спеціальні формальні мови.
Словесна запис алгоритму. Словесна форма зазвичай використовується для алгоритмів, орієнтованих на виконавця - людини. Команди алгоритму нумерують, щоб мати можливість на них посилатися. Наведемо в якості ще одного прикладу словесної форми запису алгоритму класичний алгоритм Евкліда для знаходження найбільшого загального дільника двох натуральних чисел:
Дано два цілих позитивних числа m і n. Потрібно знайти їх найбільший спільний дільник, тобто найбільше позитивне число, на яке ділиться без залишку як m, так і n.
Суть алгоритму Евкліда можна представити наступними трьома етапами.
1. Знаходження залишку. Розділимо m на n. Нехай залишок дорівнює г:
0 <р <n.
2. Перевірка залишку на рівність нулю. Якщо р = О, обчислення кінчається, n - шукане число.
3. Заміна m ← n, n ← р. Повторити етап 1.
Приклад
1. Дано m = 125, n = 75. Наші найбільший спільний дільник.
1) 125: 75 = 1. Частка менша 1, залишок від ділення дорівнює 50,
2) Залишок від ділення не дорівнює 0. Проводимо заміну змінних:
m = 75, n = 50 і повторюємо процес,
1) 75: 50 = 1, m = 25.
2) m = 50, n = 25, г = 0.
Повторюємо процедуру.
1) 50:25 = 2.
2) Залишок від ділення дорівнює 0, тому n = 25 є найбільшим загальним дільником.
2. До відрізку АВ в точці М відновити перпендикуляр. Алгоритм рішення цієї геометричної задачі може бути описаний у вигляді чотирьох послідовних кроків (рис. 1).
1) З довільної точки О площині радіусом ОМ описати коло, що перетинає відрізок АВ.
2) Відзначити точку З перетину кола з відрізком АВ,
3) Знайти точку D перетину кола з прямою ОС.
Рис. 1. Відновлення перпендикуляра до відрізка в даній точці
4) З'єднати точку М і D.
Якщо строго виконувати всі розпорядження, то буде отриманий однозначну відповідь,
Форма запису команд не формалізується. У командах крім слів можуть використовуватись символи та формули. Важливо лише те, щоб кожна команда була зрозуміла виконавцю, точно визначала всі його дії і могла б бути їм виконана.
Для вирішення завдання можна розробити кілька алгоритмів. Кожен алгоритм створюється з розрахунку на цілком конкретного виконавця. Якщо планується реалізація алгоритму на машині, слід враховувати його пристосованість до ЕОМ, простоту і час реалізації на машині. Алгоритм повинен бути розроблений таким чином, щоб виконавець міг навіть не вникати у зміст того, що він робить, і разом з тим отримувати потрібні результати. Виконання вже наявного алгоритму можна доручити суб'єкту чи об'єкту, який не зобов'язаний вникати в суть справи, а можливо, і не здатний його зрозуміти.
Опис алгоритму
Правила виконання арифметичних операцій або геометричних побудов представляють собою алгоритми.
Вказівка формули або послідовності формул, розрахунки за якими потрібно виконати для отримання результатів.
Приклад
Обчислити об'єм круглого конуса. Для обчислення слід скористатися формулою
При заданих двох розмірах (r - радіус основи і h - висота конуса) ця формула дає розпорядження виконавцю, як діяти, тобто визначені характер і послідовність дій.
Представлення алгоритму у вигляді схеми.
При реалізації завдання на ЕОМ, особливо у разі написання програм на машинно-орієнтованих мовах, і завдань складних алгоритмів використовуються схеми алгоритмів.
Схема алгоритму - графічне представлення ходу рішення задачі.
При виконанні схем алгоритмів і програм окремі функції алгоритмів і програм (з урахуванням їх деталізації) відображаються у вигляді умовних графічних позначень - символів (ГОСТ 19.003-80 та ГОСТ 19.002-80). У табл. 1 наведені основні символи, використовувані в схемах алгоритмів. Схеми повинні бути виконані у форматах, встановлених за ГОСТ 2.301-68.
Таке графічне представлення називається схемою алгоритму або блок-схемою. У блок-схемі кожному типу дій (вводу вихідних даних, обчислення значень виразів, перевірки умов, управлінню повторенням дій, закінчення обробки і т.п.) відповідає геометрична фігура, представлена у вигляді блочного символу. Блокові символи з'єднуються лініями переходів, визначальними черговість виконання дій. У таблиці наведені найбільш часто вживані символи.
При виконанні схем символам присвоюють порядкові номери. Порядковий номер проставляють ліворуч у верхній частині символу у розриві його контуру. Символи з'єднуються прямими лініями (лініями потоку).
Лінії потоку повинні бути паралельні лініям зовнішньої рамки схеми. Напрямки ліній потоку зверху вниз і зліва направо приймають за основні і, якщо вони не мають зламів, їх можна стрілками не позначати. В інших випадках напрямок лінії потоку позначати стрілкою обов'язково.
Записи усередині символу виконуються креслярським шрифтом за ГОСТ 2.304-81. Записи усередині символу або поруч з ним повинні бути короткими. Символи застосовуються з урахуванням виконуваних функцій.
Таблиця 1. Основні символи для схем алгоритмів
| Назва символу | Позначення і приклад заповнення | Пояснення |
| Процес | Обчислювальний дію або послідовність дій | |
| Рішення | Перевірка умов | |
| Модифікація | Початок циклу | |
| Зумовлений процес | Обчислення по підпрограмі, стандартної підпрограмі | |
| Введення-виведення | Введення-виведення в загальному вигляді | |
| Пуск-останов | Початок, кінець алгоритму, вхід і вихід в підпрограму | |
| Документ | Висновок результатів на друк |
| № п / п | Графічне зображення елементу | Опис елемента |
| а b | Процес - блок обробки даних, в якому зазначаються дії, що змінюють значення, форму подання або розташування даних. | |
| 2 | Дані - блок опису операції введення / ви-вода даних, для якої не визначено конкретний пристрій. | |
| 3 | Рішення - блок вибору напрямку виконання алгоритму в залежності від деяких умов. У результаті перевірки умови здійснюється вибір одного з декількох можливих шляхів. | |
| · · · | Межі циклу - символ складається з двох частин і визначає початок і кінець циклу. | |
| Зумовлений процес - блок опису процесу з однієї або кількох операцій, описаних в окремому модулі (самостійному алгоритмі). | ||
| Коментар - містить пояснення функції блоку, з яким пов'язаний. | ||
| Термінатор - позначає початок і кінець алгоритму. | ||
| Лінія потоку - відображає потоки даних і управління в алгоритмі. | ||
| З'єднувач - вказівка зв'язку між перерваними лініями потоку, що зв'язують блоки. |
Приклад опису алгоритму знаходження максимального з трьох чисел XI, Х2, ХЗ з допомогою схеми алгоритму представлений на рис. 2.
Графічний метод опису алгоритму дуже наочний, але в разі складного алгоритму схема виходить громіздкою і це її гідність втрачається. Використання схем алгоритмів значно спрощує написання програм початківцями програмістами.
Рис. 2 Схема алгоритму пошуку Схема алгоритму Евкліда максимального числа з трьох чисел