Вміст тіла^ ТЕМА 15 ОСНОВИ АЛГОРИТМІЗАЦІЇ І ПРОГРАМУВАННЯ УРОК 1 ІНФОРМАЦІЙНА МОДЕЛЬОсновні етапи розв'язання задач з використанням комп'ютера Комп'ютер застосовується для розв'язання найрізноманітніших задач: проведення складних інженерних розрахунків, визначення оптимальної стратегії планування виробництва, опрацювання текстів, створення динамічних графічних зображень і т.п. Процес розв'язання задач з використанням комп'ютера складається з декількох етапів: етап 1. постановка задачі та її аналіз Постановка задачі передбачає виявлення сутності задачі. На етапі постановки задачі вирішуються такі питання: • окреслюються предмет задачі, умови, в яких він знаходиться, бажаний результат розв'язування задачі; • уточнюється мета розв'язання задачі; визначається, які дані потрібні для її вирішення, а які є несуттєвими; встановлюється, які саме результати та в якому вигляді мають бути знайдені; • з'ясовується, чи є обмеження на вхідні дані задачі; при яких умовах можна отримати результат, а при яких — ні; які результати вважатимуться правильними. етап 2. побудова інформаційної моделі задачі, вибір методу її розв'язування На цьому етапі розробляється інформаційна модель (спочатку звичайно у вербальній (усній) формі, далі — у знаковій формі), добирається метод розв'язування задачі. З цією метою реалізуються такі дії: • встановлюються параметри задачі, взаємозв'язки між ними, оцінюється залежність результатів рішення задачі від її параметрів, і на цій основі з урахуванням сутності задачі, мети її постановки створюється інформаційна модель задачі; • задача формалізується (вводиться система умовних позначень, і задача подається у формалізованому вигляді); • здійснюється перехід до знакової інформаційної моделі з використанням прийнятої системи позначень; • аналізуються можливі методи розв'язування задачі та вибирається найбільш ефективний з використанням певних критеріїв. Критеріями ефективності методу можуть виступати простота його реалізації, швидкість одержання розв'язку, точність здобутих результатів тощо. Центральним моментом цього етапу є знаходження компромісів при створенні інформаційної моделі та виборі методу її дослідження (методу розв'язування задачі). При розробці моделі обов'язково враховується постановка задачі з тим, щоб були виділені та взяті до уваги всі ті параметри, залежності та взаємозв'язки, які є впливовими, суттєвими для розв'язування поставленої задачі, а рештою можна було б нехтувати. Це дозволяє, з одного боку, максимально спростити модель, полегшити її подальші реалізацію та дослідження, а з іншого боку — не припуститися надмірного спрощення, адже модель має адекватно відбивати об'єкт поставленої задачі. Вибір методу розв'язування задачі теж є компромісним: бажано, щоб він був по можливості простим і швидким, але його точність повинна узгоджуватися з точністю моделі і не впливати на її якість. Наприклад, якщо задача полягає у визначенні відстані, на яку відлетить ядро після пострілу зі старовинної гармати, то кривизною земної поверхні, опором повітря можна нехтувати і для розв'язування задачі застосувати прості формули фізики, які стосуються польоту тіла, випущеного із заданою початковою швидкістю під заданим кутом до горизонтальної поверхні. Якщо ж йдеться про стрільбу із сучасної гармати, то всі зазначені вище дані й багато інших знадобиться врахувати, а для опису та аналізу їх співвідношень скористатися складними системами рівнянь і спеціальними методами вищої математики. етап 3. розробка комп'ютерної моделі Сутність цього етапу полягає у переході від знакової інформаційної моделі до комп'ютерної, тобто в реалізації інформаційної моделі засобами програмного середовища. Метою такого переходу є подальше надання комп'ютеру ролі виконавця дій, потрібних для розв'язування задачі. Розробка комп'ютерної моделі передбачає такі заходи: • складання алгоритму розв'язування задачі на основі вибраного методу її розв'язування. В результаті цей метод втілюється у послідовність простих дій, які приводять до одержання потрібного результату; • вибір програмного середовища для реалізації алгоритму. Цей вибір здійснюється із застосуванням таких критеріїв, як .зручність для розв'язання поставленої задачі, трудомісткість реалізації алгоритму, наявність потрібних виразних засобів для подання результатів розв'язку. Після вибору середовища може виникнути потреба у перегляді алгоритму з метою його конкретизації відповідно до тих можливостей, які надає вибране середовище; • реалізація алгоритму засобами вибраного програмного середовища, тобто переведення алгоритму у таку форму, яка робить його придатним для виконання комп'ютером. Результатом цього процесу є програма; • тестування та налагодження програми, тобто перевірка правильності роботи програми за допомогою тестів (спеціально підібраних вхідних даних, для яких результат виконання програми є відомим) і вилучення виявлених помилок. Іноді може з'ясуватися, що помилку припущено не в процесі розробки програми, а раніше (наприклад, невдало вибрано метод розв'язання задачі, припущені надмірні спрощення при розробці інформаційної моделі), у такому разі треба повернутися до попереднього етапу і здійснити потрібну корекцію. Результатом процесу тестування та налагодження програми є програмний продукт, придатний для одержання шуканих даних задачі шляхом відповідного опрацьовування її вхідних даних. Це і є комп'ютерна модель задачі. За півстоліття активної експлуатації комп'ютерів нагромаджено значний досвід розробки програмного забезпечення, і одним із наслідків цієї роботи є створення фонду програмних засобів, орієнтованих на'застосування комп'ютера у певній предметній чи професійній області. Такі програмні засоби називають інструментальними, тому що вони надають користувачеві зручні інструменти для побудови комп'ютерних моделей відповідного типу. Наприклад, математичні середовища (Gran, DG, MathLab, Derive та інші) призначаються для реалізації математичних моделей; графічні середовища (Paint, CorelDraw, PhotoShop та інші) — для створення графічних моделей і т.д. Якщо ж задача вимагає розробки власної програми, то застосову- ються середовища програмування, які полегшують процес створення комп'ютерних моделей засобами мов програмування. етап 4. комп'ютерний експеримент Метою комп'ютерного експерименту є одержання інформації, на основі якої можна приймати рішення, робити висновки про властивості об'єкта моделювання або прогнозувати його поведінку в тій чи іншій ситуації. Цей етап складається з таких дій: • розробка плану проведення експерименту; • випробування комп'ютерної моделі; •, аналіз отриманих результатів. Сутність випробування комп'ютерної моделі полягає у багаторазових запусках програми для опрацювання певних наборів вхідних даних. Такі набори розробляються в ході планування експерименту з метою виявлення певних залежностей чи отримання потрібних даних. Аналіз результатів експерименту може дати підставу для його завершення, якщо всі поставлені цілі досягнуто, або для продовження експерименту, корекції плану його проведення, якщо виявилася необхідність доповнення даних чи намітився новий напрям дослідження. Іноді за результатами експерименту виникає потреба в уточненні моделі або навіть у внесенні змін у постановку задачі, і тоді весь процес починається знову.^ ТЕМА 15 ОСНОВИ АЛГОРИТМІЗАЦІЇ І ПРОГРАМУВАННЯУРОК 2 ПОНЯТТЯ ІНФОРМАЦІЙНОЇ МОДЕЛІСлово «модель» походить від латинського modulus, що означає «міра», «взірець», «норма». Модель — це матеріальний або уявлюва-ний аналог деякого об'єкта (предмета, явища або процесу), який зберігає суттєві риси об'єкта і здатний заміщувати його під час вивчення, дослідження або відтворення. Процес створення моделі об'єкта називається моделюванням. Об'єкт, що моделюється, називається прототипом, або оригіналом. Моделювати можна не тільки існуючі предмети, явища та процеси, але й абстракції, яких немає у реальності; об'єкти, що тільки плануються для створення; явища, які можуть і не відбутися. Моделювання здійснюється з метою пізнання та перетворення людиною навколишнього світу, тому термін моделювання застосовується і в іншому значенні, як дослідження об'єктів за допомогою побудови і вивчення їх моделей. Моделлю предмета може бути його зменшена копія, креслення, яке відображає його структуру чи склад, схема, що відбиває взаємозв'язки окремих елементів. Наприклад, макет корабля, креслення будівлі, схема комп'ютера. Модель явища або процесу відтворює його хід, послідовну зміну стану, етапи розвитку. Наприклад, модель еволюції людства, модель розвитку економіки тощо. Модель завжди є штучно створюваним людиною об'єктом, який дає ідеалізоване уявлення про об'єкт-оригінал. Ідеалізація об'єкта є неодмінним етапом створення моделі. Сутність ідеалізації полягає у визначенні, які саме риси та властивості об'єкта є суттєвими для розв'язання поставленої задачі, впливають на результат рішення і мають бути відтвореними в моделі, а які риси та властивості є несуттєвими і при побудові моделі можуть не враховуватися. Відсутність у моделі несуттєвих якостей є не менш важливим моментом, ніж наявність суттєвих, тому що це дозволяє знизити рівень складності задачі, зробити її придатною для дослідження спрощеними методами, позбавитися від зайвих витрат праці та часу на врахування невпливових факторів. Так, в умовах багатьох задач з фізики ви зустрічаєте фразу, що можна нехтувати, наприклад, опором повітря чи залежністю прискорення вільного падіння від висоти. Саме це і дозволяє вам розглядати задачу у спрощеній постановці і застосовувати для знаходження рішення прості закони фізики. Ступінь ідеалізації моделі визначає межі її адекватності, тобто відповідності оригіналу в межах поставленої задачі. Оскільки значущими і потрібними можуть бути тільки надійні результати, які відповідають реальності, то визначення границь адекватності моделі є надзвичайно важливим. Фактично це означає встановлення припустимих інтервалів змінювання параметрів задачі, для яких можна стверджувати або очікувати, що результати розв'язування задачі придатні для використання. Моделі можна класифікувати за різними ознаками. За областю застосування розрізняють: • навчальні моделі (засоби наочності, навчальні програми, тренажери); • дослідні моделі (зменшені чи збільшені копії об'єкта проектування:); • науково-технічні моделі (пристрої, що створюються для дослідження явищ і процесів, — наприклад, системи); • ігрові моделі (воєнні, економічні, спортивні, ділові ігри, які застосовуються для виявлення реакції об'єкта на ту чи іншу ситуацію); • імітаційні моделі (такі моделі застосовуються для вивчення та оцінювання можливих наслідків певних дій; наприклад, перед тим, як ввести у вжиток новий лікарський препа- рат, здійснюють Імітаційний експеримент — випробують препарат на мишах). За галуззю знань, де застосовується модель, виділяють біологічні, фізичні, соціологічні та інші моделі. За фактором часу розрізняють cmaтичні і динамічні моделі. Статична модель відбиває стан об'єкта у певний фіксований момент часу (наприклад, перепис населення України дає картину його розподілу за віковими категоріями, рівнем освіти, професійною орієнтацією на початок 2001 року). Статичні моделі називають також структурними, тому що вони характеризують будову і параметри об'єкта. Динамічна модель відтворює зміни об'єкта, які відбуваються з часом, або особливості функціонування об'єкта, тому динамічні моделі називають також функціональними. Прикладами динамічних моделей є модель броунівського руху молекул газу, яка дозволяє спостерігати їх переміщення в обмеженому просторі, зіткнення тощо; модель парового двигуна, яка передає спосіб перетворення теплової енергії в механічну). За способом подання моделі поділяються на дві великі групи: матеріальні та інформаційні. Матеріальні моделі можна назвати також предметними, натурними, фізичними. Вони завжди мають реальне втілення. Прикладами матеріальних моделей є дитяча іграшка, чучело птаха, макет ракети. Інформаційні моделі являють собою сукупність інформації, що характеризує властивості та стан об'єкта і його взаємозв'язки із зовнішнім світом. Такі моделі називають також уявними (тому що вони не мають матеріального втілення), іноді — логічними. Прикладами інформаційних моделей є усний чи письмовий опис, математичні формули, які відбивають взаємозалежності параметрів об'єкта. Інформаційні моделі, у свою чергу, класифікуються за способом подання. Розрізняються такі види інформаційних моделей: • інтуїтивні моделі, які є уявленнями про об'єкт, отриманими в результаті роздумів, умовиводів (вірш, який складається у мозку поета; уявлення людини про навколишній світ тощо); • образні моделі, які виражають властивості оригінала засобами усної мови або образотворчими засобами (усна розповідь, фотографія, твір живопису, кінофільм тощо); • образно-знакові моделі, які використовують знакові образи — схеми, графіки, плани, креслення і т.п. (блок-схема алгоритму, родовідне дерево, геометричне креслення, географічна карта тощо); • знакові моделі, які створюються за допомогою умовних знаків та символів — літер, цифр, спеціальних знаків тощо. До цього виду моделей належать математичні моделі, які описують об'єкти або процеси за допомогою математичних співвідношень, формул, рівнянь. Такі моделі найчастіше застосовуються у дослідженнях. Прикладами знакових моделей є також хімічні формули, нотний запис музики тощо. Іноді наведена класифікація інформаційних моделей подається в інтегрованому вигляді: виділяються лише два види моделей: вербальні і знакові. У такому разі до вербальних належать уявні моделі і створювані засобами усної мови (вербальний — від лат. verbalis, що означає усний), а до знакових — моделі, подані за допомогою засобів графічних образів та умовних знаків. За інструментами реалізації інформаційні моделі поділяються на комп'ютерні і неком-п'ютерні моделі. Сьогодні перевага віддається комп'ютерному моделюванню, яке орієнтоване на застосовування найпотужнішого та найефективнішого інструменту зі створених людиною — комп'ютера. Сучасні комп'ютери здатні сприймати та опрацьовувати числову і текстову, звукову та графічну інформацію, відеозображення і анімацію, схеми і таблиці і т.п. Такі різноманітні можливості комп'ютера забезпечуються як програмними, так і апаратурними (технічними) засобами. Сукупність цих засобів і складає інструментарій реалізації комп'ютерних моделей. Надзвичайна значущість комп'ютерного моделювання полягає в тому, що воно дає можливість: • досліджувати об'єкти чи явища, які неможливо, дорого або небезпечно відтворювати в реальних умовах; • здійснювати пошук рішень, які потребують складних, численних або трудомістких розрахунків; • уникати можливих шкідливих чи руйнівних наслідків проведення натурних випробувань; • економити матеріальні ресурси; • зберігати екологічні умови існування людини. За допомогою комп'ютерного моделювання встановлюються причини технічних чи природних катастроф, що сталися, прогнозуються зміни клімату нашої планети чи її можливі зустрічі з іншими космічними об'єктами, здійснюється проектування споруд, досліджуються соціальні процеси, вирішується безліч наукових, технічних, економічних та інших проблем.^ ТЕМА 15 ОСНОВИ АЛГОРИТМІЗАЦІЇ І ПРОГРАМУВАННЯУРОК 2 АЛГОРИТМИПоняття алгоритму. Виконавець алгоритму З алгоритмами ми зустрічаємося на кожному кроці. Будь-яка людина користується набором всіляких алгоритмів — правил, які вона засвоює в процесі виховання та навчання, фізичного тренування, набуття власного життєвого досвіду. Інструкції користування ліфтом, телефоном, різноманітними автоматами і побутовими приладами, правила переходу вулиці, надання першої медичної допомоги, приготування страв, виконання арифметичних дій або гімнастичних вправ, покроковий план розв'язування задачі або проведення фізичного чи хімічного досліду — все це можна вважати алгоритмами. Алгоритми відіграють велику роль у житті людини: вони зберігають її сили та час, тому що саме через алгоритми передається здобутий досвід ефективних способів діяльності. Один раз засвоєним правилом людина може користуватися все своє життя.Алгоритм — це опис послідовності дій, які потрібно виконати для досягнення поставленої мети або здобуття заданого результату. Назва «алгоритм» походить від імені видатного вченого Мухамеда аль-Хорезмі (Мухамеда з Хорезму), якому належить значний внесок у розвиток математики. 825 року він написав «Книгу про індійську арифметику», де було вперше систематично викладено арифметику, засновану на десятковій системі числення із застосуванням нуля, тобто ту арифметику, яка в наш час є звичайною та природною. Арифметика виникла в Індії і тому раніше називалася індійською. В перекладі на латинську «Книги про індійську арифметику» ім'я її автора було написано як «Алгоритм». «Так казав Алгоритм» — починали європейські вчені, посилаючись на викладені в книзі правила виконання арифметичних дій. Ці правила і дістали назву алгоритмів. Тільки у XX столітті, у зв'язку зі становленням та розвитком теорії алгоритмів, поняття алгоритму стало вживатися в більш широкому значенні.^ Приклад алгоритму: Алгоритм завершення роботи з комп'ютером, який працює під управлінням операційної системи Windows. 1. Натиснути на робочому столі Windows кнопку виходу в головне-меню «Пуск». 2. Вибрати в меню «Пуск» команду «Завершення роботи». 3. У діалоговому вікні «Завершення роботи з Windows» натискуванням радіокнопки вибрати пункт «Вимкнути комп'ютер». 4. Підтвердити свій вибір натискуванням кнопки «Так» на діалоговому вікні. 5. Дочекатись повідомлення на екрані «Тепер живлення комп'ютера можна вимкнути». 6. Натиснути кнопку «Power» на системному блоці комп'ютера. Кожна дія алгоритму задається окремою вказівкою (або командою), їх кількість у записі алгоритму не визначає кількості кроків, які треба зробити для розв'язування задачі за цим алгоритмом. Іноді доводиться робити кроків більше, іноді - - менше, ніж команд в опису алгоритму, тому що залежно від поставлених умов деякі команди треба виконувати повторно, а деякі — не виконувати зовсім. Будь-який алгоритм складається з розрахунком на певного виконавця, який здатний зрозуміти та виконати кожну з команд алгоритму. Так, наприклад, наведений вище алгоритм завершення роботи з операційною системою Windows розраховано на виконавця, який знає, що таке кнопка, радіокнопка, меню, пункт меню, як здійснюється його вибір і таке інше. Кожний виконавець має свій перелік команд, які він розуміє і може виконати. Цей перелік називається системою команд виконавця. Команди алгоритму мають формулюватися чітко, коротко, без зайвої інформації. Якщо виконавцем алгоритму є людина, то одну й ту саму команду можна сформулювати дещо по-різному. Так, обидві команди «Обчислити суму чисел 5 і 7» та «Знайти значення 5+7» людина сприйме та виконає однаково. На відміну від людини автоматичний пристрій, наприклад комп'ютер, має певний обмежений перелік точно визначених команд, і ніякі відхилення від правил їх запису та застосування не припускаються. Тому неточно сформульована команда може бути сприйнятою і, як наслідок, виконаною неправильно, або комп'ютер зовсім відмовиться виконувати команду і припинить свою роботу над алгоритмом. Для виконання алгоритму звичайно недостатньо самого алгоритму. Алгоритм містить лише інформацію про послідовність дій, потрібних для досягнення результату. Виконати алгоритм — це означає застосувати його до розв'язання конкретної задачі, тобто здійснити заплановані дії стосовно певної сукупності вхідних даних задачі. Розрізняються такі види даних: вхідні, які надаються виконавцю алгоритму до початку його роботи; проміжні, які виробляються та застосовуються в процесі виконання алгоритму; вихідні, які видаються як результат здійсненої роботи.^ Властивості алгоритму Алгоритми застосовуються до розв'язання найрізноманітніших задач — обчислювальних і побутових, логічних і дослідницьких, навчальних та ігрових тощо. Але незважаючи на все розмаїття алгоритмів, в них можна знайти багато спільного. Спільні риси алгоритмів називають їх властивостями. Будь-який алгоритм подає процес розв'язування задачі як послідовність відокремлених простих дій. Дії виконуються почергово, одна за одною, в усталеному порядку. Тільки після виконання однієї дії можна перейти до наступної. Ця властивість алгоритму називається дискретністю (від лат. discretus — розділений, переривчастий). За скінченну кількість кроків алгоритм має приводити до здобуття потрібного результату або до досягнення поставленої мети. Цю властивість алгоритму називають скінченністю, або результативністю. Алгоритм має складатися з команд, які входять до системи команд його виконавця, це забезпечує зрозумілість алгоритму. Алгоритм разом із заданою сукупністю вхідних даних цілком визначає дії виконавця та їх послідовність при розв'язанні задачі. Кожна команда алгоритму однозначно встановлює, що треба робити на даному кроці та до якої команди перейти на наступному. Будь-які розбіжності в тлумаченні дій, приписуваних командою, виключаються. Не може виникнути й потреби у будь-якій додатковій інформації зовні або у прийнятті рішень самим виконавцем. Цю властивість алгоритму називають визначеністю, або детермінованістю (від лат. determinare — визначати). З детермінованості випливає, що для заданої сукупності вхідних даних будь-який виконавець алгоритму, аби він мав відповідну систему команд, неодмінно досягти одного й того самого результату шляхом виконання одних і тих самих дій. Від виконавця не вимагається усвідомлення того, яку задачу він розв'язує. Йому достатньо лише крок за кроком виконувати ті прості дії, які приписуються алгоритмом. Таким чином, алгоритм передбачає його виконання точне, тобто без будь-яких відхилень, і формальне, тобто без втручання у смисл приписуваних дій. Саме це і дозволяє використовувати автоматизовані пристрої, зокрема комп'ютер, для розв'язування задач. Звичайно алгоритм складається так, щоб його можна було застосовувати до розв'язання не однієї конкретної задачі, а всіх задач певного типу, які відрізняються між собою вхідними даними. Ця властивість алгоритму називається масовістю. Масовість не означає, що вхідним даним можна надавати довільних значень. Вони звичайно обмежені смислом задачі, застосованим способом її розв'язання тощо. Для кожного алгоритму встановлюється відповідна область припустимих значень вхідних даних, або, інакше кажучи, область його застосування. Наприклад, алгоритм знаходження найбільшого спільного дільника чисел а і b можна застосувати для будь-яких натуральних значень а, Ь. З урахуванням перелічених властивостей можна запропонувати уточнене визначення поняття алгоритму:Алгоритм — це зрозумілий і точний припис виконавцеві про здійснення скінченної послідовності певних дій для розв'язання задачі певного типу або для досягнення поставленої мети.^ ТЕМА 15 ОСНОВИ АЛГОРИТМІЗАЦІЇ І ПРОГРАМУВАННЯУРОК 3 Способи подання алгоритмів Для подання алгоритмів застосовуються різні способи. Кожний з них надає певні засоби для опису дій, які треба виконати, та встановлення послідовності їх виконання. У повсякденному житті найчастіше застосовується словесний спосіб. У такий спосіб алгоритм подається як послідовність окремих занумерованих пунктів, кожний з яких містить команду на виконання певної дії. Команди записуються словами. Пункти виконуються один за одним у порядку зростання їх номерів, якщо немає спеціальної вказівки на перехід до виконання іншого пункту, номер якого задається. Словесний спосіб подання алгоритму є найбільш прийнятним для опису інструкцій побутового характеру, дій на випадок надзвичайної ситуації, фармакологічних чи кулінарних рецептів тощо. Записом алгоритму можна вважати формулу, тому що з неї випливає порядок здійснення обчислень для здобуття числового результату. Якщо виконується серія розрахунків за однаковими формулами, то для запису алгоритму іноді використовується розрахункова таблиця, де визначаються всі етапи обчислень і фіксуються проміжні результати.^ Таблиця розрахунку заробітної платні № п/п Прізвище Розмір місячної ставки Кількість робочих днів у місяці Денний заробіток Кількість відпрацьованих днів Заробітна платня за місяць Сума податку (23%) До видачі 1 2 3 4 5 6 7 8 9 (1) (2) (3) (4) (3):(4) (6) (5)х(6) (7)хО,23 (7)-(8) 1 Асеев Б. 420 24 17,5 24 420 96,6 323,4 2 Волін О. 420 24 17,5 20 350 80,5 269,5 3 Котик І. 360 24 15.0 23 345 79,35 265,65 У наведеній таблиці верхній рядок містить найменування стовпчиків таблиці, наступний рядок — їх номери, рядок під ним — позначення дій, які треба виконати над даними у попередніх стовпцях (вказано їх номери) для здобуття значення у поточному стовпці. Так, для обчислення денного заробітку (5) треба розмір місячної ставки (3) поділити на кількість робочих днів у місяці (4), що умовно позначається як (3):(4). Поширеним способом наочного подання алгоритму є блок-схема. Блок-схема складається з геометричних фігур, які з'єднані напрямленими лініями. Зміст дій описується всередині геометричних фігур. Порядок виконання дій задається лініями. Для подання алгоритму застосовуються геометричні фігури двох видів: прямокутники та ромби. У прямокутниках записують дії, які мають виконуватися, в ромбах — умови, які треба перевіряти. Перевірка умов потрібна для вибору тих чи інших подальших дій. Якщо прямокутник має один вхід і один вихід, то у ромба вхід один, а виходів — два. Коли перевіряється умова, записана в ромбі, то існує два можливих варіанти: умова або виконується, або ні. На ці випадки («так» і «ні») і є два виходи з ромба, які спрямовують подальші дії виконавця алгоритму залежно від результату перевірки умови. Наприклад, якщо в прямокутнику записано х = 2, то це не ствердження, а наказ надати х значення 2. Яким би не було раніше значення х, тепер воно дорівнює 2. Якщо в ромбі записано х = 2, то це читається як «х = 2?». Далі перевіряється, чи виконується ця рівність для поточного значення, і вибирається відповідна вихідна гілка — «так» або «ні». Значення х залишається таким, яким воно було до цієї перевірки. Для того щоб алгоритми, подані блок-схемами, було зручно читати та виконувати, введено допоміжні елементи: овали, які застосовуються для позначення початку або кінця алгоритму, та паралелограми •— для введення або виведення даних.^ ТЕМА 14 ОСНОВИ АЛГОРИТМІЗАЦІЇ І ПРОГРАМУВАННЯУРОК 4 Види алгоритмівВиди алгоритмів розрізняють звичайно не за складністю виконуваних дій, не за їхньою.кількістю, а за складністю організації (або за управлінням, за логічною конструкцією) алгоритмічного процесу. Алгоритми найпростішого виду — лінійні. Це такі алгоритми, в яких дії виконуються послідовно, одна за одною. Кожна дія лінійного алгоритму обов'язково виконується, і виконується тільки один раз: Наведена базова алгоритмічна конструкція називається слідуванням. Ця конструкція є замкненою в тому розумінні, що у неї є один вхід і один вихід, і інші можливості увійти всередину конструкцій чи вийти з неї виключені. Якими б не були вхідні дані, лінійний алгоритм приписує виконання однієї й тієї самої послідовності дій. Прикладом лінійного алгоритму може бути наведений вище алгоритм завершення роботи з комп'ютером. Складнішими за організацією є алгоритми, в яких треба не просто виконувати всі підряд задані дії, а приймати рішення, які саме дії виконувати. Алгоритм, який приписує здійснення тієї чи іншої дії в залежності від виконання заданої умови, називається алгоритмом з розгалуженням. Розрізняють повну і коротку форму розгалуження. В короткій формі при невиконанні умови ніякі дії не передбачаються. Повну форму розгалуження можна прочитати так:«якщо умова виконується, то виконати дію 1, інакше виконати дію 2» (див. рис. а), а коротку — так:«якщо умова виконується, то виконати дію» (див. рис. б).Так Ні Дія б Наведена на рис. а базова алгоритмічна конструкція називається розгалуженням (на рис. б — п окремий випадок). Вона є замкненою: має один вхід і один вихід. Приклад алгоритму з розгалуженням У крамниці пара шкарпеток коштує 2 гривні, а в'язка (дванадцять пар) — 19 гривень. Визначити, скільки в'язок та пар шкарпеток вигідніше придбати, якщо потрібно X пар. За таких умов очевидно, що замість 11 пар шкарпеток (22 гривні) і навіть 10 пар (20 гривень) вигідніше придбати в'язку (19 гривень) — буде затрачено менше грошей, і ви ще отримаєте додаткові шкарпетки. Але для дев'яти пар (18 гривень) знижка на в'язку вже не спрацює. Розв'язання задачі ґрунтується на такому міркуванні. Треба порівняти за ціною всього два варіанти придбання шкарпеток: перший — з округленням кількості шкарпеток до в'язки в менший бік і додаванням, якщо потрібно, окремих пар; другий — з округленням кількості окремих пар, якщо такі є, до цілої в'язки. Наприклад, якщо треба придбати 45 пар шкарпеток, то обов'язково треба купувати З в'язки і, порівнявши ціну 9 пар з ціною цілої в'язки, зробити висновок, що вигідніше докупити — потрібну кількість окремих пар чи цілу в'язку. У нашому прикладі дешевше докупити 9 пар. Наведемо алгоритм розв'язування задачі: 1. Обчислити кількість цілих в'язок (N), які треба придбати: N = X поділити націло на 12. 2. Обчислити кількість окремих пар (М) : М = X — 12 N 3. Обчислити ціну окремих пар (С): С = 2 М 4. Якщо значення С менше за ціну цілої в'язки (С Третій вид алгоритмів складають такі, які приписують неодноразове виконання певної дії (або декількох дій). Це циклічні алгоритми. Дії, які мають повторюватися, називаються тілом циклу. Умова, яка визначає кількість повторень циклу, називається умовою циклу. Розрізняють два основні типи циклів: цикли, де умова перевіряється до виконання тіла циклу (цикли з передумовою), і цикли, де перевірка умови здійснюється після виконання тіла циклу (цикли з післяумовою, або постумовою). Двом типам циклів відповідають дві базові алгоритмічні конструкції повторення (див. рис. а, б), які подібно до інших базових конструкцій теж є замкненими, тобто мають один вхід і один вихід: Тіло циклу з післяумовою, на відміну від циклу з передумовою, обов'язково виконується хоча б один раз — до першої перевірки умови. У циклі з передумовою (рис. а) умова циклу формулюється так, щоб повторення тіла циклу здійснювалося за її виконанням. Через це такі цикли називаються ще циклами «поки»: поки умова виконується, виконується і тіло циклу. Якщо при черговій перевірці ця умова виявляється невиконаною, то відбувається вихід з циклу. У циклі з післяумовою (рис. б) умова циклу формулюється таким чином, щоб повторення тіла циклу здійснювалося за її невиконанням, тому такі цикли називаються також циклами «до». Вихід з циклу «до» відбувається за виконання умови. Зауважимо, що з розвитком мов програмування розширилися й види циклів, які можна застосовувати у програмах: так, наприклад, дозволяється у циклах з передумовою вживати умову «до», у циклі з післяумовою — умову «поки», комбінувати перевірку умов, використовуючи дві перевірки — і до, і після виконання тіла циклу і т.п. Цикли є єдиним видом базових алгоритмічних структур, де передбачається повернення до вже виконаних дій. Приклад циклічного алгоритму Розробимо алгоритм знаходження остачі від ділення двох натуральних чисел, використовуючи лише операцію віднімання чисел. Для розробки алгоритму позначимо через а та b задані числа,' г — остачу від ділення першого числа на друге. Якщо а менше за Ь, то остача дорівнює а; якщо ж а більше чи дорівнює 6, то треба зменшити а на величину Ь і перевірити, чи нове значення а менше за Ь. Якщо так, то останнє значення а і є остачею, якщо ні — потрібно повторити дії. Оскільки результатом роботи алгоритму має бути значення г, то доцільно одразу покласти г рівним а і подальші дії виконувати над г та Ь. У такому разі наш алгоритм не виявиться довшим, а вхідні значення а та й будуть збереженими, що завжди схвалюється як коректний стиль розробки алгоритму чи програми. Зважуючи на те, що для випадку о Блок-схему алгоритму знаходження остачі від ділення двох натуральних чисел а, Ь подано на рис. а). На рис. б) наведено кроки виконання алгоритму для випадку а = 15, 6=7. Крок 1. а=15,r=aКрок 2. Крок 3. Крок 5. Крок 7.Ні 15 (так) (так) (ні)r = r - b Крок 4. Крок 6. Крок 8 r=1a bАлгоритм знаходження остачі від ділення двох натуральних чисел.а — блок-схема алгоритму; б — кроки його виконання для а=15, Ь~7.^ ТЕМА 14 ОСНОВИ АЛГОРИТМІЗАЦІЇ І ПРОГРАМУВАННЯУРОК 5 Структурний підхід до побудови алгоритмівОдним із методів, який дозволяє поліпшити якість алгоритму в цілому, запобігти більшості логічних помилок і легко виявити ті, яких не вдалося уникнути, є структурний підхід до розробки алгоритмів. Він дозволяє забезпечити прозорість логічної будови алгоритму, його зрозумілість, легкість сприйняття, простоту перевірки, зручність використання і модифікації (тобто внесення змін, перетворення з певною метою — наприклад, для пристосування до вирішення схожої задачі). Структурний підхід ґрунтується на трьох основних принципах: • проектування алгоритму методом «згори вниз»; • організація алгоритму у вигляді відносно незалежних частин — модулів; • конструювання алгоритму з уніфікованих базових алгоритмічних структур (слідування, розгалуження, повторення). Структурне програмування - - це метод складання програм на засадах структурного підходу до побудови алгоритмів.Технологія структурного програмування — це система методів, способів і прийомів реалізації ідей структурного програмування засобами конкретної мови програмування (докладніше див. тему «Мови програмування»). Ефективним методом проектування алгоритмів у межах структурного підходу є метод «згори вниз» (йото називають також методом покро-кової деталізації, або методом послідовного уточнення). Ідея цього методу полягає у забезпеченні правильності алгоритму за рахунок самої процедури його розробки. Проектування алгоритму має ієрархічну структуру і розпочинається з вершини ієрархії. Спочатку аналізують мету задачі і визначають основні етапи її розв'язку, тобто встановлюють загальну структуру алгоритму. Далі кожний етап, який у свою чергу також є задачею, піддають подібному аналізу: виявляють його основні функції і структуру і т.д. Таким чином, крок за кроком задача розбивається на все більш дрі