1. АЛГОРИТМИ ТА МОВИ ПРОГРАМУВАННЯ 1.1. Алгоритми, загальні поняття Поняття алгоритму виникло в математиці. Здавна при виконанні обчислювальних робіт використовувалися різноманітні інструкції, правила. За допомогою правил обчислювач міг, не вникаючи в суть задачі, одержати правильний розв'язок. Такі правила виконання математичних дій отримали назву алгоритмів. Велика роль у введенні поняття алгоритмів належить видатному узбецькому математику ІX століття Мухаммеду ібн Муса ал-Хорезмі, який сформулював правила виконання чотирьох арифметичних дій над числами. Головна його праця з арифметики була перекладена в Європі на латинь. На латині ім'я математика писали Аlgorіthmі, звідки утворилося слово «алгоритм». Наведемо приклади математичних задач, алгоритми розв’язання яких ви знаєте: • додавання двох багатоцифрових чисел; •ділення відрізка навпіл за допомогою циркуля і лінійки; •розв'язування квадратного рівняння тощо. У житті людини трапляються алгоритми не тільки як правила математичних обчислень, а й у вигляді інших послідовностей дій. Прикладами дій, для виконання яких можна скласти алгоритми, можуть бути: • як перейти регульоване перехрестя двох вулиць; • як зварити картоплю; •як розкласти багаття. Алгоритм «Користування телефоном»: 1. зняти трубку; 2. почувши гудок, набрати номер; 3. якщо з'єднання відбулось — говорити; 4. якщо з'єднання не відбулось — покласти трубку і перейти до п.1. Алгоритм «Відгадай число»: 1. Задумай будь-яке число. 2. Додай до нього 12. 3. Від результату відніми 7. 4. Відніми від результату задумане число. 5. Одержано число 5. Останній алгоритм — це приклад числового алгоритму. Числовий алгоритм описує послідовність математичних дій над числами. Наведемо приклади алгоритмів, за допомогою яких обробляється не числова інформація, а літерна: • алгоритм запису прізвищ учнів класу в алфавітному порядку; • алгоритм вибору із даного списку осіб жіночої статі; •алгоритм-рецепт приготування салату з крабів тощо. Нечисловий алгоритм описує послідовність дій, не пов'язаних з обробкою числової інформації. Існує багато визначень поняття «алгоритм». Ми будемо використовувати таке: Алгоритм — це зрозумілий, точний та повний опис послідовності простих дій для розв'язування конкретної задачі. Алгоритм знаходження найбільшого спільного дільника (НСД) двох натуральних чисел вперше описав Евклід: 1. Порівняй числаа іb. 2. Якщоа =b , тоа найбільший спільний дільник. 3. Якщоа >b , то замінитиа наa – b. 4. Якщоа 5. Перейти до п. 1. Алгоритми застосовується не тільки в математиці, але й у багатьох сферах людської діяльності. Виконавцем алгоритмів може бути людина або машина. 1
Для людини це звичайні правила, рецепти, інструкції (як перейти вулицю, як спекти торт, як користуватися магнітофоном). Ці правила передаються усно або записуються на папері у вигляді тексту, креслень і малюнків. Машині для роботи потрібен опис дій на її «машинній» мові, який записується на магнітну стрічку або диск, лазерний диск тощо. До розробки алгоритмів звертаються тоді, коли потрібно «доручити» автоматичному приладу роботу, яку виконувала людина. Саме тут виникає необхідність точного опису послідовності простих дій для виконання певної роботи. Машині не скажеш: «Візьми ту штуку і стукай по цій штуці!» Саме після розробки відповідних алгоритмів створювалися пральні і швейні машини, м'ясорубки, трактори, газові плити, авторучки, екскаватори, друкарські машини тощо. В інформатиці використовують більш спеціалізоване поняття «алгоритму», яке ґрунтується на поняттях «команда» і «виконавець». Алгоритм — це послідовність команд, що визначають дії виконавця з урахуванням його можливостей. Ми будемо вчитися розробляти алгоритми для того, щоб за їх допомогою писати програми для комп'ютера. За програмою-алгоритмом комп'ютер буде дуже швидко розв'язувати складні задачі, на які людина потратила б багато часу і зусиль. Питання для самоконтролю: 1. Як виникло слово «алгоритм»? 2. Який алгоритм називається числовим? Наведіть приклад. 3. Хто може бути виконавцем алгоритмів? 4. Для чого вивчають алгоритми? 1.2. Властивості алгоритмів Виконавцями алгоритмів можуть бути як люди, так і машини. На відміну від людей, технічні пристрої у змозі виконувати тільки точно визначені операції. Роботу- виконавцю не скажеш, як, наприклад, мама донці: «Піди в кімнату, там десь ножиці лежать!». Дитині не треба детально і точно описувати алгоритм, де знайти ножиці і що їх треба принести саме мамі (чого б вона її інакше посилала?). Для робота-виконавця довелось би розробити, наприклад, такий алгоритм: повернутися на 12,7 градусів ліворуч; пересуватися прямо на відстань 4,34 метра; відчинити двері (що потребує свого алгоритму); перелізти через поріг заввишки 2,6 см і завширшки 16,5 см і т.д. Саме тому алгоритми, які виконуються автоматичними пристроями і машинами, повинні мати певні властивості. Алгоритмам необхідно мати властивості однозначності, зрозумілості, дискретності, універсальності та правильності. Відсутність хоча б однієї з цих властивостей робить неможливим виконання алгоритму машиною або пристроєм, тому що їх робота стане помилковою. Однозначність алгоритму — це точний опис дій та послідовності їх виконання, відсутність їх неоднозначного тлумачення. Таких властивостей часто не мають вказівки, які дають люди один одному. Наприклад, у мультфільмі «Вовка у тридев'ятому царстві» хлопчик дає наказ двом молодцям зі скриньки: «Нарубати і замісити!». І перший молодець почав рубати тісто, а другий місити дрова. Інший приклад: в одному німецькому місті бургомістр вночі зіштовхнувся з перехожим і набив собі гулю. Вранці він написав наказ: «Всім мешканцям міста вночі ходити з ліхтарями». Ввечері він пішов перевірити, як виконується його наказ. І знову набив гулю. «Чому ти без ліхтаря?» — «Ось він». — «Чому він без свічки?» — «Наказу не було». Наступного дня з'явився наказ: «У ліхтарях повинна бути свічка». Знову бургомістр пішов перевіряти виконання свого наказу і знову набив гулю. «Чому без ліхтаря?» — «Ось він». — «Чому ліхтар без свічки?» — «Ось вона». — «Чому вона не запалена?» — «Не було наказу». І тільки на третій день вийшов вичерпний наказ: перехожі в темну пору доби повинні ходити з ліхтарями, у ліхтарях повинна бути свічка, свічка повинна бути запалена. Зрозумілість алгоритму означає, що виконавець правильно сприйме кожну команду і зможе її виконати. Наприклад, алгоритм, розроблений для автоматичної пральної машини, не буде зрозумілим для металообробного верстата з числовим програмним управлінням. 2
Будь-який алгоритм повинен бути розбитий на послідовність окремих кроків, мати властивість дискретності. Алгоритм має властивості дискретності, якщо всі його команди чітко відокремлені одна від одної. Наприклад, на автомобільних заводах весь технологічний процес розбито на послідовність простих операцій (дискретів), виконання яких доручається машинам. Для машини алгоритм має бути записаний у вигляді послідовності найпростіших команд, які вона зможе послідовно виконувати. Універсальність (масовість) алгоритму — це можливість використовувати його для розв'язування подібних задач. Наприклад, наведений в підрозділі 1.1 алгоритм знаходження НСД двох чисел можна застосувати до будь-яких цілих чисел. Алгоритм є правильним (результативним), якщо його виконання дає правильні результати розв'язування задачі. Алгоритм містить помилки, якщо при виконанні він не завершиться взагалі або отримані результати виявляться неправильними. Помилки в алгоритмах поділяють на синтаксичні та логічні. Синтаксичні помилки — це порушення правил запису алгоритму: пропущені дужки, коми, помилки в написанні команд тощо. Наприклад: A++B; X=Y∗(Z–; Відсутність синтаксичних помилок не гарантує правильної роботи алгоритму. Є більш складні і «замасковані» помилки алгоритму, знайти і виправити які значно важче. Логічні помилки — це порушення в логіці алгоритму: помилки у виборі формул, неправильно вказані умови в розгалуженнях тощо. Наприклад, якщо ми записали в алгоритм обчислення гіпотенузи трикутника за формулоюc = a b 2+ (деа іb — катети), то комп'ютер не помітить помилки і «добросовісно» проведе обчислення. Результат буде неправильним, тому що гіпотенуза обчислюється за формулоюc =a b 2 2 + . Деякі логічні помилки, наприклад, спробу ділення на нуль або обчислення квадратного кореня з від'ємного числа, комп'ютер може знайти, але далеко не всі. Знаходити і виправляти логічні помилки — завдання людини. Ознакою логічної помилки може бути одержання неправильних результатів. Причиною цього можуть бути помилки у вибраному методі розв'язування або його неправильна реалізація. Питання для самоконтролю: 1. Для чого розробляється алгоритм? 2. Які властивості повинні мати алгоритми? 3. Що означає вираз «однозначність алгоритму»? Наведіть приклад. 4. Що означає вираз «зрозумілість алгоритму»? Наведіть приклад. 5. Що означає вираз «дискретність алгоритму»? Наведіть приклад. 6. Що означає вираз «універсальність алгоритму»? Наведіть приклад. 7. Що означає вираз «правильність алгоритму»? Наведіть приклад. 8. Які помилки можуть бути в алгоритмі? 9. Які помилки називаються синтаксичними? 10. Які помилки називаються логічними? Хто їх знаходить і виправляє? 1.3. Способи запису алгоритмів Для запису алгоритму використовують такі способи: • словесний запис алгоритму; • графічний запис алгоритму; • запис алгоритму мовою програмування. Словесний запис алгоритму орієнтований на людину-виконавця. Правила запису словесного алгоритму такі: 3
•алгоритм складається з послідовності дій, записаних словами; •дії можуть мати різні скорочення, позначення і формули; •дії повинні бути точно визначеними і посильними для виконання; •усі дії алгоритму повинні бути пронумеровані. Наприклад, словесний алгоритм для задачі: «Визначити, чи належить точка D трикутнику АВС»: 1. обчислити площу трикутника АВС (S1); 2. обчислити площу трикутника АВD (S2); 3. обчислити площу трикутника АCD (S3); 4. обчислити площу трикутника BCD (S4); 5. якщо S16. якщо S1=S2+S3+S4, то точка належить трикутнику. Графічний запис алгоритму складається із визначених зображень дій. Ці зображення називаються блоками, а графічний запис алгоритму прийнято називати блок-схемою алгоритму. Графічний запис алгоритмів у вигляді блок-схем буде розглянуто далі. Блок-схему будують для того, щоб полегшити написання програми. Блок-схема зображає алгоритм у більш наглядній формі, ніж словесний запис алгоритму. Запис алгоритму мовою програмування називається програмою. Програма пишеться для виконавця алгоритму — комп’ютера. Програма пишеться мовою, зрозумілою не тільки людині, але і комп’ютеру. Алгоритм, записаний на мові програмування, складається з послідовності чітко визначених команд, на які комп’ютер відповідним чином реагує. Існує багато мов програмування, серед яких Бейсик (будемо вивчати), Паскаль, Фортран, Алгол, СІ, PL/2, С++, Java і т.д. Перед тим як написати програму, необхідно спочатку продумати, як задачу розв'язати, тобто скласти словесний алгоритм розв'язку задачі. Потім за словесним алгоритмом потрібно розробити блок-схему алгоритму. Після цього можна починати писати текст програми. Власне кажучи, програма — це текстове відбиття алгоритму, але не таке наочне, як блок-схема алгоритму. Серйозний програміст ніколи не почне писати текст програми, не розробивши і не перевіривши в деталях блок-схему програми. Буває, що учень спочатку пише програму, а потім на вимогу вчителя складає блок-схему. На простих програмах такий «номер» проходить. Хибність такого «методу» показують більш складні задачі. Питання для самоконтролю: 1. Які способи запису алгоритмів ви знаєте? 2. Які правила словесного запису алгоритму? 3. Для чого потрібний графічний запис алгоритму? 4. Що означає вираз «блок-схема»? 5. Для чого пишеться програма? 6. Що означає вираз «мова програмування»? 7. Яка послідовність розробки програми?1.4. Блок-схеми алгоритмів Блок-схемою алгоритму називають графічне зображення, на якому окремі дії алгоритму зображуються за допомогою геометричних фігур, а послідовність виконання дій вказується за допомогою ліній зі стрілками, які з’єднують ці фігури. Блок-схеми дозволяють наочно зобразити структуру алгоритму. На такій схемі добре видно послідовність виконання дій, а також цикли і розгалуження. Геометричні фігури у блок-схемах називають блоками. Вони позначаються символами, які мають стандартне зображення і призначення. Найчастіше використовуються чотири основні символи: овал, паралелограм, прямокутник і ромб. Початок та кінець алгоритму позначається овалом. Усередині символу пишеться відповідно слово «Початок» або «Кінець». Правилами дозволяється замість слів «Початок» і «Кінець» записувати умовне ім'я алгоритму або назву виконуваної ним дії. Від блоку «Початок» відходить, а до блоку «Кінець» приходить одна лінія. Кінець Початок 4
Для позначення введення вхідних даних та виведення результатів використовується паралелограм. Усередині символу записуються значення, які вводяться у програму або виводяться з неї. У блок «введення-виведення» може входити тільки одна лінія і виходити лише одна лінія в будь-якому із чотирьох напрямків. Для позначення дії (процесу) використовується прямокутник. Усередині символу записуються вказівки або формули. У блок «процес» може входити тільки одна лінія і виходити лише одна лінія в будь-якому із чотирьох напрямків. Усередині символу записується умова, яка перевіряється. Якщо умова виконується, то далі обчислювальний процес здійснюється за розгалуженням «так», якщо не виконується — за розгалуженням «ні». У блок «розгалуження» входить одна лінія, а виходять дві лінії. За допомогою ліній, якими з'єднуються блоки, позначається послідовність виконання алгоритму. Після виконання дій одного блоку переходять по лінії до виконання дій наступного блоку. За основний напрямок виконання дій прийнято напрямок зверху вниз і зліва направо. У цьому випадку стрілки на кінцях ліній можна не ставити. Коли лінія прямує знизу вгору і справа наліво, ставити стрілки потрібно обов’язково. Блокам алгоритму можуть присвоюватись номери відповідно до словесного алгоритму (див. рис.). Якихось правил розбиття алгоритму на окремі блоки при побудові блок-схем не існує. У блоки можна виділяти виконання окремих арифметичних операцій, обчислення за формулами і навіть окремі алгоритми, які розв'язують більш вузькі класи задач. Рівень узагальнення залежить від рівня кваліфікації того, хто розробляє блок-схему. На наступних етапах алгоритмізації деякі з блоків можна більш докладно деталізувати, оформивши їх у вигляді окремих блок-схем. У професійному програмуванні використовується до 30 різноманітних стандартних символів для зображення блок-схем. Питання для самоконтролю: 1. Які чотири основні символи блок-схем ви знаєте? 2. Як зображується у блок-схемі початок і кінець алгоритму? 3. Як зображується у блок-схемі введення або виведення даних? 4. Як зображується у блок-схемі дія (процес)? 5. За допомогою якого символу зображується розгалуження? 6. Які виходи має символ «ромб»? 7. В яких випадках стрілки на кінцях з'єднуючих ліній є обов'язковими? вхід вихід вхід вихід y = a + sіn(x) x = y – cos(b) Поміняти місцями А і В Для позначення перевірки виконання деякої умови та розгалуження обчислювального процесу залежно від результату перевірки цієї умови використовується ромб. Лінія приходить справа Лінія приходить зліва Лінія приходить знизу Лінія приходить зверху 5 вхід вихід Введення X, Y, Z Введення P, T вхід вихід вхід вихід y = a + sіn(x) x = y – cos(b) 18 Так Ні Вхід Умова?
1.5. Лінійні алгоритми. Базові структури алгоритмів Алгоритм зветься лінійним, якщо всі його дії виконуються послідовно, одна за одною, від початку до кінця. У лінійному алгоритмі не може бути команди, яка б передбачала різну послідовність виконання алгоритму. Приклад лінійного алгоритму «Як перевезти по одному через річку без втрат вовка, козу і капусту»: 1. Переправити на той берег козу, вовка залишити з капустою; 2. Повернутись, взяти вовка, переправитись з ним до кози; 3. Забрати козу і повернутись назад до капусти; 4. Залишити козу, забрати і перевезти капусту до вовка; 5. Повернутись і забрати козу. У цьому прикладі дії алгоритму виконуються послідовно одна за одною до закінчення алгоритму. Наведемо приклад побудови блок-схеми лінійного алгоритму «Обчислити шлях за швидкістю і часом руху» (див. рис.). Словесний запис алгоритму задачі буде таким: 1. Ввести швидкістьv і час рухуt. 2. Обчислити шлях за формулою S = v·t. 3. Вивести шляхS. Ще один приклад: Алгоритм «Обчислити площу трикутника за трьома сторонами». Словесний запис алгоритму: 1. Ввести сторони трикутника а, b, с. 2. Обчислити півпериметр трикутника 0.5 ( ) p a b c = ⋅ ++. 3. Обчислити площу S за формулою Герона ( )( )( ) s p p a p b p c = ⋅− − − 4. Вивести площу трикутника S. Запис алгоритму у вигляді блок-схеми буде таким: Початок Вв едення a, b, c Обчислення p=(a+b+c)/2 Обчислення площіS Виведення пл ощіS Кінець Базові структури алгоритмів За структурою алгоритми можна класифікувати на три базові різновиди: лінійні, розгалужені, циклічні. Основна властивість базових структур полягає в тому, що за допомогою лінійних, розгалужених і циклічних алгоритмів можна зображати алгоритми будь-якої складності. Реальні алгоритми, як правило, включають усі три типи алгоритмів у різноманітних комбінаціях. Структурний підхід до конструювання (розробки) алгоритмів полягає в тому, що спочатку продумується і фіксується загальна структура алгоритму без деталізації окремих його частин. Блоки, що потребують подальшої деталізації, позначаються пунктиром. На наступних кроках ці блоки уточнюються. Коли завершено деталізацію всіх блоків, одержимо алгоритм розв’язку задачі в цілому. Це простіше, ніж відразу розробляти детально весь алгоритм. Такий підхід до конструювання алгоритмів ще називають розробкою «зверху вниз». Структурний підхід до конструювання алгоритмів забезпечує легкість розуміння алгоритму, простоту його перевірки і редагування. Питання для самоконтролю: 1. Які різновиди алгоритмів ви знаєте? 2. Які алгоритми називаються лінійними? 3. Які базові структури алгоритмів ви знаєте? 4. Яка основна властивість базових структур алгоритмів? 5. У чому полягає структурний підхід до конструювання алгоритмів? 6. Що дає структурний підхід до конструювання алгоритмів? 6 Початок Введення v, t Обчислення S= v· t ВиведенняS Кінець
Введення a, b, c Обчислення дискримінанту Початок "Розв’язку немає" Обчислення Виведення x1, x2 Кінець D <0 x1, x2 Ні Так x< 0? S= 0 S = –1 S= 1 Так Так Ні Ні Кінець x = 0? Початок Введенняx 1.6. Розгалужені алгоритми На практиці часто доводиться аналізувати різні умови, для того щоб приймати ті чи інші рішення для наступних дій. Розгалужений алгоритм — це алгоритм, в якому виконуються ті або інші дії залежно від результату перевірки умови. У блок-схемі розгалуженого алгоритму, показаній на рисунку, інколи може бути відсутня Дія 1 або Дія 2. Умова — це логічний вираз, який може приймати два значення: «так» — якщо умова виконується і «ні» — якщо умова не виконується. Умови можуть мати вигляд як математичних співвідношень, так і текстових виразів і запитань. Побудуємо блок-схему алгоритму розв'язування квадратного рівняння з коефіцієнтамиа,b іc. Словесний запис алгоритму буде таким: 1. Ввести значення кое- фіцієнтівa,b іc. 2. Обчислити дискримінантD. 3. Якщо D < 0, то вивести повідомлення «Розв'язку немає», перехід на кінець алгоритму. 4. Обчислити кореніx1 іx2 квадратного рівняння. 5. Вивести значенняx1 іx2. 6. Кінець алгоритму Ще один приклад: Нехай задано числох. Побудуємо блок-схему обчислення функції, заданої співвідношеннями: -1, якщо < 0 0, якщо = 0 1, якщо > 0 x S x x = Питання та завдання для самоконтролю: 1. Які алгоритми називаються розгалуженими? 2. Наведіть приклад розгалуженого алгоритму. 3. Напишіть словесний алгоритм і побудуйте блок- схему: «Знайти більше число з двох заданих». 4. Напишіть словесний алгоритм і побудуйте блок- схему: «Знайти найбільше число з трьох заданих». 5. Напишіть словесний алгоритм і побудуйте блок- схему: «Визначити тип трикутника за двома заданими кутами». 1.7. Циклічні алгоритми При розв'язуванні багатьох задач доводиться багато разів виконувати одні й ті ж дії або обчислювати одні й ті ж вирази. Для розв'язування таких задач слід використовувати циклічні алгоритми. Алгоритм називається циклічним, якщо одна і та ж послідовність дій виконується кілька разів, доки не виконається задана умова. Організація циклу вимагає встановлення початкових значень тим змінним, які використовуються в циклі. Такі дії зображуються блоком «початкові надання» (блоком ініціалізації). Дії, описані блоком «початкові надання», виконуються тільки один раз і в подальшій роботі циклу участі не беруть. Команда або група команд, виконання яких повторюється при кожному проходженні циклу, називається тілом циклу. 7 Умова Ні Так Дія 1 Дія 2
Кожного разу після виконання тіла циклу робиться перевірка умови виходу з циклу за допомогою блоку «Умова». Вихід з циклу відбувається після досягнення лічильником циклів заданого значення або після виконання заданої умови. Блоки «Початкові надання», «Тіло циклу» та «Умова» є складовими частинами циклу. Дії всередині тіла циклу можуть бути досить складними. Це може бути велика послідовність команд або ще один алгоритм, зокрема циклічний. Цикли бувають двох видів: •цикл «До» (з післяумовою); •цикл «Поки» (з передумовою); Цикл«До». Застосовується при необхідності виконати «Тіло циклу» кілька разів до виконання заданої «Умови». Особливість цього циклу полягає в тому, що він виконується хоча б один раз. Цикл«Поки». Застосовується при необхідності спочатку перевірити «Умову» і, можливо, потім виконати «Тіло циклу». Якщо при першій пере- вірці «Умови» виконається умова виходу з циклу, то «Тіло циклу» не виконається ні разу. При логічних помилках в циклічних алгоритмах може виникнути ситуація, коли тіло циклу виконується раз за разом, а умова припинення циклу не настає. Така ситуація називається «зациклювання». Роботу таких програм доводиться припиняти і шукати помилку. Розглянемо блок-схему циклічного алгоритму для обчислення виразу У = X ^ N (X у степені N, де N — натуральне число. Очевидно, що для обчислення заданої функції слід послідовно N разів перемножити значення Х. Для організації циклу необхідно передбачити лічильник K. З кожним проходженням циклу лічильник збільшується на 1. Коли лічильник стає більшим за N, цикл завершується. За початкове значення Y беремо одиницю. Команди K = 1 і Y = 1 виконуються в блоці «Початкові надання». Основні дії, а саме Y = Y∗ X і K = K + 1, які виконуються у тілі циклу, будуть повторюватися з кожним проходженням циклу. І, нарешті, у логічному блоці «Умова» слід записати К > N?. Побудуємо блок-схему алгоритму Евкліда для знаходження найбільшого спільного дільника двох чисел (словесний запис алгоритму Евкліда дивись у п. 1.1.): Питання та завдання для самоконтролю: 1. Які алгоритми називаються циклічними? 2. Наведіть приклад циклічного алгоритму. 3. Які функції блоку «початкові надання» в циклічному алгоритмі? 4. Що називають «тілом циклу» в циклічному алгоритмі? 5. Для чого існує блок «умова» в циклічному алгоритмі? 6. Які особливості циклу «До»? Вхід Початкові надання Умова Так Ні Тіло циклу Вихід 8 Початкові надання Тіло циклу Умова Так Ні Вхід Вихід Початок Введення X, N K =1 Y =1 Y =Y X K =K+1 K > N? Ні Так Виведення Y Кінець Так Ні Так Ні Початок Введення a, b Взятиa як відповідь Замінити aн а a–b Замінити bн а b–a a = b? a > b? Кінець
7. Які особливості циклу «Поки»? 8. Напишіть словесний алгоритм і побудуйте блок-схему: «Знайти всі числа, на які ділиться введене число». 9. Напишіть словесний алгоритм і побудуйте блок-схему: «Обчислити суму парних натуральних чисел у заданому проміжку чисел». 1.11. Етапи підготовки задач до розв'язування на комп’ютері Підготовки задач до розв'язування на комп’ютері здійснюється в кілька етапів. Треба зауважити, що окремі етапи взаємопов’язані: наступні етапи залежать від реалізації попередніх, а після виконання чергового етапу може виникнути потреба повернення до попереднього етапу і пошуку нового методу розв’язування. Етапи підготовки задачі до розв'язування на комп’ютері: •постановка задачі; •математична формалізація задачі; •вибір методу розв'язування задачі; •розробка блок-схеми алгоритму; •перевірка алгоритму; •написання тексту програми; •налагодження і тестування програми; •розв'язування задачі, аналіз результатів; •експлуатація програми. Постановка задачі — це чітке формулювання задачі, визначення вхідних даних для її розв'язування і точні вказівки відносно того, які результати і в якому вигляді повинні бути отримані. Постановку задачі виконує фахівець з тих питань, для вирішення яких розробляється програма. Наприклад, постановку задачі для продажу квитків на вокзалі за допомогою комп'ютера повинен робити спеціаліст, який розуміється на цій справі. Постановку задачі для тестування учнів на комп'ютері робить учитель. Для автоматизації банківських операцій постановку задачі робить фінансовий працівник. При постановці задачі потрібно вказати, які вхідні дані будуть оброблятись, що з ними необхідно зробити і в якому вигляді повинні бути видані результати. Приклад постановки задачі: «Розв'язати квадратне рівнянняах2 +bх +с = 0, де а, b, с — дійсні числа (а≠ 0). Вказати всі варіанти розв'язання: два різні корені; два рівні корені; немає розв'язку». Математична формалізація задачі — це опис задачі у вигляді формул, рівнянь, співвідношень, обмежень. Деякі задачі, які розв'язують на комп'ютері, не потребують математичної формалізації (наприклад, задачі обробки текстів). Формалізуємо задачу про розв'язання квадратного рівняння. Квадратне рівняння має розв'язки: x b D a 1 2 = − + ( );x b D a 2 2 = − − ( ), деD =b2 – 4ac — дискримінант. ЯкщоD > 0, то одержимо два різні дійсні корені рівняння. ЯкщоD = 0, то одержимо два рівні дійсні корені рівняння. ЯкщоD < 0, то дійсних коренів немає. Вибір методу полягає у виборі того чи іншого способу розв'язування задачі. Вибір методу розв'язування задачі залежить як від самої задачі, так і від можливостей комп’ютера: швидкодії, об'єму пам'яті, наявності розроблених раніше програм. Побудова блок-схеми — це графічний запис алгоритму на основі вибраного методу. При побудові алгоритму бажано розглянути і проаналізувати кілька варіантів перед тим, як зробити остаточний вибір. Алгоритм більшою мірою визначається методом, хоч один і той же метод, у свою чергу, може бути реалізований за допомогою різних алгоритмів. Перевірка алгоритму, як правило, полягає в ручній перевірці («прокрутці») окремих розв'язків задачі. 9
Для цього потрібні аркуш паперу з зображеним на ньому алгоритмом. У клітинках записуються під їх позначеннями всі змінні і їх початкові значення. Поступово рухаючись за алгоритмом, виконуємо записані в ньому операції, проміжні результати записуємо у відповідні колонки. І так до закінчення алгоритму та одержання результатів розв'язування задачі. Дані треба підбирати так, щоб перевірити всі розгалуження алгоритму. Якщо отримані результати відповідають дійсності, можна сподіватись, що алгоритм правильний. Але це можна встановити остаточно лише налагодивши і протестувавши програму. Написання тексту програми — це запис алгоритму на алгоритмічній мові програмування. Алгоритмічна мова програмування — це сукупність символів, слів, команд і правил, за допомогою яких можна у формальному вигляді записувати послідовність дій для розв'язування даної задачі. Цю послідовність дій називають програмою на алгоритмічній мові. Якщо блок-схема алгоритму достатньо деталізована, то при написанні тексту програми принципових труднощів не виникає. У комп'ютерах завдання перетворення програм на алгоритмічних мовах у машинні коди виконують спеціальні програми, які називаються трансляторами. Людина пише програму на алгоритмічній мові, зрозумілій людині, а транслятор цю програму перетворює в машинну програму, зрозумілу комп'ютеру. Таким чином, алгоритмічна мова відіграє роль посередника між людиною і комп'ютером. Налагодження і тестування програми — це перевірка правильності роботи програми і виправлення знайдених помилок. У програмі, складеній вперше, як правило, містяться помилки. Помилки можуть бути синтаксичні і логічні. Якщо при записі програми допущені синтаксичні помилки (порушені правила запису команд і даних), то такі помилки знайде транслятор. Логічні помилки у виборі формул, розгалужень, логічних висновків тощо трансляторами не виявляються. Ці помилки повинен знайти та усунути програміст. Для виконання тестування необхідно підготувати тести. Тест — це спеціально підібрані вхідні дані разом з результатами, які повинні бути отримані за цими даними. При тестуванні перевіряється чи отримуються програмою ті самі результати, які вказано в тесті. Розв'язування задачі та аналіз результатів — це остаточна перевірка правильності реалізації всіх попередніх етапів. Після налагодження програми здійснюється перевірка її роботи при різних вхідних даних. Цей етап є підсумком виконання всіх попередніх етапів і служить підтвердженням (або запереченням) їх правильності. Після цього етапу інколи доводиться переглянути сам підхід до розв'язування задачі та повернутися до першого етапу для повторного виконання всіх етапів з оглядом на набутий досвід. Упевнившись, що в заданому діапазоні вхідних даних програма функціонує правильно, програміст передає розроблену ним програму для експлуатації. Експлуатація програми — це використання програми замовниками або користувачами. Налагоджена програма з відповідною документацією на неї (опис програми, інструкція по експлуатації і т.д.) передається замовнику для подальшого використання. При необхідності проводиться навчання користувачів роботі з програмою. Програміст здійснює авторський контроль за програмою, тому що під час експлуатації можуть бути виявлені помилки, які не вдалось знайти під час тестування і налагодження. Програміст робить необхідні доробки у програмі, і її експлуатація продовжується. Питання для самоконтролю: 1. Які етапи підготовки задачі до розв'язування на комп’ютері ви знаєте? 2. Що означає вираз «постановка задачі»? Хто її виконує? 3. Що означає вираз «математична формалізація задачі»? 4. Що означає вираз «вибір методу розв'язку задачі»? 5. Що означає вираз «побудова блок-схеми алгоритму»? 6. Як перевіряється правильність алгоритму? 7. Які помилки можуть бути в алгоритмі? 8. Що означає вираз «алгоритмічна мова програмування»? 9. Як розуміти вираз «машинна програма»? 10. Як створюється машинна програма? 11. Як здійснюється налагодження і тестування програми? 10
1.12. Мови програмування Існує велика кількість алгоритмічних мов програмування. Багато з них зорієнтовані на певні класи задач. Одними з перших мов програмування були Фортран для розв'язування інженерних задач і більш універсальний Алгол. На базі Фортрану і Алголу розроблено багато інших мов програмування. Мова програмування Бейсик створена як навчальна. Цю мову слід використовувати на початкових етапах програмування. У неї прості засоби введення даних, налагодження і виконання. Професійні програмісти використовують мови Паскаль або Сі. Фортран і Алгол є мовами програмування, орієнтованими для математичних обчислень. Для розв'язування економічних і комерційних задач зручний Кобол. Для задач моделювання та управління створена спеціалізована мова програмування Симула. Мова ЛІСП створена в 1965 р. американським професором Джоном Маккарті для дослідження проблем «штучного інтелекту». Ця мова дозволяє моделювати на комп’ютері інтелектуальну діяльність людей. Спробу створити єдину мову програмування для різного застосування зробила на початку 70-их років фірма ІBM (США). Вона розробила універсальну мову PL/1. Однією з найбільш поширених мов програмування є Паскаль, створений у 1971 р. швейцарським професором Н. Віртом. Паскаль стала прототипом багатьох сучасних мов програмування: Ади, Сі, Модули- 2. Мова Пролог була створена у Франції в 1972 році також для проведення досліджень з проблем «штучного інтелекту». У 1979 р. було оголошено про нову мову програмування Ада, яка названа на честь першої жінки- програміста Ади-Августи Лавлейс. Її основне призначення — програмування систем управління. Мови програмування поділяються на: •мови низького рівня; •мови високого рівня; До мов низького рівня належать асемблери, в яких кожна команда має відповідний машинний аналог. На асемблері пишуть програми, коли необхідно найбільш раціонально використати ресурси комп’ютера. Це можуть бути системні програми, драйвери (програми управління апаратними засобами), утиліти (сервісні програми) тощо. До мов високого рівня належать мови Фортран, Алгол, Бейсик, PL/1, Ада, Сі тощо. Кожну команду цих мов здійснює кілька машинних команд або окрема машинна програма. На таких мовах пишуть різноманітні прикладні програми. Основні поняття мови програмування: Алфавіт — символи, дозволені для запису команд і даних. Як правило, це літери латинського алфавіту, арабські цифри, розділові знаки, спеціальні символи. Команди — перелік і правила запису дій, які передбачені мовою програмування. Дані — вхідна інформація і результати обробки. Дані, які в процесі обробки змінюють своє значення, називаютьсязмі н н им и. Постійні дані називаютьсяк он стан там и. Ідентифікатори — символьне позначення (ім’я, адреса) даних, функцій, програм тощо. Коментарі — пояснення до команд і програм. Синтаксис — правила запису команд, опису і позначення даних, викорис
