Від т відняти п і вважати цю різницю новим значенням Т. Перейти до 1.

Від п відняти т і вважати цю різницю новим значенням п. Перейти до 1.

Вважати, що НСД дорівнює m. Кінець.

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

Алгоритми складаються з орієнтацією на певного виконавця алгоритму: дресированої тварини, людини, автомата, ЕОМ. До алгоритму мають входити команди, які виконавець може виконати, і неприпустимі команди, які він не може виконати. У кожного виконавця є свій кінцевий набір команд, які для нього зрозумілі і можуть бути виконані. Цей набір називають системою команд виконавця.

 

Властивості алгоритмів.

Властивостями алгоритму є дискретність, визначеність, виконуваність, скінченність, результативність і масовість.

Дискретність (лат. discretus – розділений, розривний) алгоритму означає, що його виконання зводиться до виконання окремих дій (кроків) у певній послідовності. Причому, кожна команда алгоритму повинна виконуватися за скінченний інтервал часу.

Визначеність (або детермінованість (лат. determinans – визначальний)) алгоритму означає, що для заданого набору значень початкових (вхідних) даних алгоритм однозначно визначає порядок дій виконавця та результат цих дій. Алгоритм не повинен містити команди, які можуть сприйматися виконавцем неоднозначно, наприклад «Узяти 2–3 ложки цукру», «Трохи підігріти молоко», «Вимкнути світло через кілька хвилин», «Поділити число x на одне з двох даних чисел a або b» тощо. Крім того, в алгоритмах недопустимі ситуації, коли після виконання чергової команди виконавцю незрозуміло, яку команду він повинен виконувати наступною.

Виконуваність алгоритму означає, що алгоритм, призначений для певного виконавця, може містити тільки команди, які входять до системи команд цього виконавця. Так, наприклад, алгоритм для виконавця «Учень першого класу» не може містити команду «Побудуй бісектрису даного кута», хоча така команда може бути в алгоритмі, який призначений для виконавця «Учень восьмого класу».

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

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

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

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

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

 

Форми подання алгоритмів.

Розглянемо алгоритми розв’язування такої задачі.

Задача. Є посудина місткістю 8 л, яка заповнена рідиною, і дві порожні посудини місткістю 5 л і 3 л. Потрібно одержати в одній з посудин 1 літр рідини і повідомити в якій.

Розглянемо виконавця, який має таку систему команд:

1. Перелити рідину з однієї посудини в іншу.

2. Наповнити одну з посудин рідиною з іншої посудини.

3. Вивести повідомлення.

Для цього виконавця алгоритм розв’язування цієї задачі буде таким:

1. Наповнити 3-літрову посудину з 8-літрової.

2. Перелити з 3-літрової посудини в 5-літрову.

3. Наповнити 3-літрову посудину з 8-літрової.

4. Наповнити 5-літрову посудину з 3-літрової.

5. Вивести повідомлення: «1 л одержано в 3-літровій посудині».

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

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

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

Наведемо деякі елементи (блоки) блок-схеми алгоритму (табл.).

Блок-схема алгоритму розв’язування задачі представлена на рисунку.

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

 

Вивчення нового навчального матеріалу:

Комп’ютерні програми.

Що таке програма і коли з'явилося це поняття? Нині, мабуть, не кожен програміст відповість на це запитання. Історія програм починається в далеких 20-х роках XIX століття, коли англійський дослідник Ч. Бебідж висунув ідею про попередній запис дій обчислювальної машини.

До появи обчислювальних машин робилися спроби керувати ткацькими верстатами. Програми для верстатів записувалися на перфокарти, що були вигадані Чарлзом Бебіджем і французьким винахідником Жозефом Жаккаром. З них почалася історія програмування, а трохи пізніше почали закладатися теоретичні основи цієї науки. Разом з Бебіджем працювала його сучасниця Ада Лавлейс (дочка великого англійського поета Джорджа Байрона), яку називають першим у світі програмістом. Вона ввела до програмування терміни і поняття, які застосовуються і донині (наприклад, поняття циклу – найважливішої структури будь-якої сучасної мови програмування). На честь першої програмістки і була названа мова програмування «Ада», розроблена уже за наших часів.

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

Програми складаються для виконання комп’ютером алгоритмів. Ці алгоритми утворюють логіку програми (програмну логіку).

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

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

Мови програмування.

У XX столітті з'явилися електронні обчислювальні машини. Перші програми Для них записувалися в машинних кодах. Для написання правильної програми Програміст мав детально уявляти роботу ЕОМ. Це дуже ускладнювало спілкування людини з комп'ютером, тому вони стали серйозно замислюватися над кодуванням програм і дійшли висновку, що програма має складатися мовою доступнішою для людини, ніж мова машинних команд. Тому необхідно було створити мови програмування.

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

Кожна мова програмування має такі компоненти:

1) алфавіт – множину символів, з яких можна утворювати слова та речення цієї мови;

2) словник – набір спеціальних (зарезервованих, ключових) слів;

3) синтаксис – правила складання та запису мовних конструкцій (не словникових слів і речень);

4) семантику – встановлене однозначне тлумачення мовних конструкцій, правил їх виконання.

Оскільки мова програмування незрозуміла для обчислювальної машини, має бути спеціальна програма, яка перекладала б символи цієї мови мовою машинних команд. Така програма перекладу символів, або, простіше, транслятор (від англійського слова translation – переклад), була створена на початку 50-х років XX століття американською програмісткою, контр-адміралом морських сил США Грейс Хопер.

Транслятор – це програма, яка перетворює команди мови програмування на машинний код.

З винаходом трансляторів роль машинних команд у програмуванні різко зменшилася. Перші транслятори призначалися для мов Асемблера (мов низького рівня). У 50 – 60-ті роки почали створюватися мови програмування високого рівня. Зазначимо, що близькі до числового коду процесора мови називають мовами низького рівня, а мови, зручні для людини, – мовами високого рівня. Мова найнижчого рівня – мова машинного кодування. Трохи вище – мова Асемблера, у якій машинні команди замінюються мнемонічними скороченнями. Всі інші мови програмування є мовами вищого, ніж мова Асемблера, рівня. Дві популярні нині мови високого рівня – Basic (Бейсік) і Pascal (Паскаль).

Програма записується в текстовому редакторі мовою програмування і називається вихідним кодом (текстом). Він складається зі спеціальних команд-операторів мови програмування. За допомогою перекладача-транслятора вихідний код програми перетвориться на машинний код. Під час виконання програми комп'ютер діє так, як йому запропоновано заздалегідь.

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

Отже, для перекладу тексту програми на мову, зрозумілу для комп'ютера, має існувати окрема програмна оболонка – транслятор. Транслятори бувають двох видів: компілятори й інтерпретатори. Компілятор перетворює вихідний код програми на машинну мову, тобто мову нулів і одиниць. До одержаного коду підключаються стандартні процедури, використані програмістом, внаслідок чого з'являється робоча програма - її називають робочим кодом. Файли таких програм мають розширення.ехе чи.com і є машинним кодом.

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

Сучасні мови програмування – це не тільки мова програмування з компілятором. Мови програмування як програмні продукти комплектуються інструментами для створення програм. Такий комплект називається інтегрованим середовищем програмування. Він призначений не тільки для полегшення" процесу і складання програм, а й для професійної розробки додатків. До складу інтегрованого середовища програмування входять, як правило, такі інструменти: текстовий редактор для набору і редагування програми і мова програмування з компілятором; компонувальник; система усунення синтаксичних помилок; покроковий наладчик; бібліотека готових програмних модулів; довідкова система з питань розробки програм у даному середовищі.

Прикладами інтегрованих середовищ програмування є Turbo Pascal, Delphi, Visual Basic і безліч інших. Використання цих середовищ під час розробки І додатків дозволяє користувачам докладати набагато менше зусиль, ніж при І написанні програм мовами низького рівня.