Опис алгоритму за допомогою блок-схеми

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

Найуживаніші позначення:

	— початок та кінець алгоритму (всередині записують слово «початок» або «кінець»).
	— операція обчислення або присвоєння (всередині записують зміст операції). В прямокутнику може знаходитись декілька операцій обчислення, які йдуть одна за одною.
	— введення чи виведення даних (всередині записують слово «введення» чи «виведення» та перелік змінних, які необхідно ввести/вивести).
	— виведення даних у документ або на папір (всередині записують перелік змінних, які потрібно вивести).
	— перевірка умови (всередині ромба записують умову). При цьому передбачають два варіанти продовження процесу. Якщо умова набирає значення істинне, то відбувається перехід по стрілці з написом «так», якщо значення умови хибне, то відбувається перехід по стрілці з написом «ні».
	— організація циклічних процесів (всередині записують модифікацію лічильника циклу)
	— пояснення до алгоритму.
	— сполучають лінії потоку, які обриваються на сторінці. Всередині сполучників записують номер блока, з якого він виходить або в який входить.

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

Опис алгоритму за допомогою алгоритмічних мов

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

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

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

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

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

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

Скінченність — виконання кожного алгоритму завжди повинно завершуватись за скінченну кількість кроків.

Результативність — виконання алгоритму завжди повинно приводити до певного результату. Воно не може закінчуватися невизначеною ситуацією або ж не закінчуватись взагалі.

Формальність — виконавець відповідно до алгоритму повинен одержати результат, не вникаючи в його суть. Ця властивість має особливе значення для автоматизації виконання алгоритмів.

Визначеність — кожен алгоритм треба описувати так, щоб при його розшифровуванні не виникало двозначностей. Тобто різні виконавці, згідно з алгоритмом, повинні діяти однаково та прийти до одного й того ж результату.

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

Зрозумілість — в алгоритмі повинні бути лише операції, які знайомі виконавцеві.

Однозначність — в алгоритмі всі правила та порядок виконання дій необхідно тлумачити однозначно.

Дискретність — будь-який алгоритм можна розбити на окремі елементарні дії, виконання яких людиною чи машиною не викликає сумнівів.

Правильність — результат виконання алгоритму завжди має бути передбачуваним.

Загальний вигляд алгоритму. Основні алгоритмічні структури

Загальний вигляд алгоритму:

Кожен алгоритм складається з описової та виконуваної частин.

Описова частина — це назва програми, опис вхідних, проміж­них та вихідних даних, створення коментарів тощо. Виконувана частина — перелік команд, виконання яких повинно дати результат.

Будь-який алгоритм можна подати у вигляді комбінацій трьох базових алгоритмічних структур — лінійної, розгалуженої та циклічної.

Лінійна структура (наступність) — це послідовність блоків (або груп блоків) алгоритму. В програмі наступність подано у вигляді послідовного виконання команд.

При створенні обчислювальних виразів потрібно дотримуватись таких правил:

· математичні операції записують за допомогою символів +, -, *, /, ^;

· звичайні дроби записують у вигляді: (чисельник)/(знаменник);

· при записуванні функцій використовують такий вигляд: назва_функції (аргументи);

· запис стандартних функцій в алгоритмічних мовах показано в таблиці:

Аналітичний вигляд	Вигляд в алгоритмічній мові
	y = a * x ^2 + b * x + c
	y = x ^ n
	y = x ^(1/ n)
, , ,	y = Cos(x), y = Sin(x), y = Tan(x), y = 1/Tan(x)
	y = 1/ x
	y = Log(a)/Log(b)

Розгалуження — структура, яка використовується тоді, коли потрібно виконати ту чи іншу операцію залежно від накладеної умови.

Дії 1 та 2 можуть містити як одну, так і декілька операцій, один або декілька етапів, які містять інші алгоритмічні структури.

У словесному вираженні така структура матиме вигляд:

Крок 1. Якщо умова виконується, то перехід на Крок 4.

Крок 2. Операції дії 1.

Крок 3. Перехід на Крок 5.

Крок 4. Операції дії 2.

Крок 5. ….

Частковим випадком розгалуження є обхід — структура, коли в одній із гілок немає жодних дій.

Узагальненим випадком розгалуження є множинний вибір —структура, яка дозволяє виконати одну з дій, залежно від того, якого значення набуває змінна.

а б

Рис. 17 Види розгалуженої структури:

а — обхід, б — множинний вибір.

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

Кількість повторень у циклі повинна бути скінченою. Розріз­няють цикли, де кількість повторень відома заздалегідь, і цикли, де вона невідома, але її можна визначити під час виконання циклу.

Розрізняють два типи циклів:

Цикл-ДО (цикл із параметром) призначений для організації повторного виконання певної команди чи серії команд для різних значень параметрів циклу. При цьому декілька разів виконується послідовність команд, яка називається тілом циклу. Особливістю даного циклу є те, що тіло циклу обов’язково виконується хоча б один раз, оскільки перед першою перевіркою параметра будуть виконані оператори циклу (Рис № 18 а).

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

Цикл-ПОКИ (цикл з умовою) призначений для повторного виконання деякої команди чи серії команд, поки виконується умова циклу. Він використовується в тих випадках, коли наперед невідома кількість його повторень. У такій структурі тіло циклу може не виконуватись жодного разу, якщо умова при першій перевірці набуває значення хибне (Рис № 18 б).

а б

Рис. 18 Види циклічних структур:

а – цикл-ДО; б – цикл-ПОКИ.

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

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

Етапи розв’язування задач на ЕОМ

Перед початком створення програми розробник повинен зосередити увагу на таких питаннях:

Хто буде виконувати програму?

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

Звідки будуть надходити дані для програми?

Дані можуть знаходитись у тому ж місці, де й оболонка програми, а можуть імпортуватись із зовнішніх джерел. Вхідні дані також можуть вводитись користувачем із клавіатури. Місце розташування вхідних даних — один із найважливіших чинників під час розробки програми.

Де і як будуть зберігатися дані (результати проведених обчислень чи аналізу)?

Результати можуть розміщуватись у тому ж файлі, що й оболонка, або ж їх потрібно експортувати в зовнішній файл чи просто виводити на друк.

Як дані оброблятимуться програмою і в якій послідовності?

Потрібно визначити спосіб подання інформації та послідов­ність дій, які необхідно виконати.

Процес створення програмного коду для розв’язування певного класу задач можна сформулювати у такій послідовності:

1 - постановка задачі;

2 - побудова математичної моделі;

3 - побудова алгоритму та написання програми на вибраній алгоритмічній мові;

4 - налагодження та тестування програми;

5 - контрольний розрахунок;

6 - створення інтерфейсу та інструкції для роботи користувача;

7 - експлуатація програми.

Окремі етапи розв’язування завдання на комп’ютері взаємо­пов’язані між собою: наступні етапи залежать від реалізації попередніх.

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

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

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

Існує декілька концепцій сучасного програмування. Воно може бути структурним, функціональним, модульним або об’єктно-орієнтованим.

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

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

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

Найбільшого поширення серед розробників програмних продуктів набули такі мови програмування, як Pascal і Turbo Pascal, Delphi, C багатьох модифікацій, C++, Qbasic, Visual Basic.

Четвертий етап — тестування та налаштування програми, тобто перевірка правильності роботи програми та виправлення знайдених помилок. Для виявлення змістових помилок використовують контрольні (тестові) обчислення. Тест — спеціально піді­брані вхідні дані разом з результатами, які повинна видавати програма при опрацюванні цих даних.

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

На шостому етапі потрібно провести додаткові роботи, пов’язані з її сервісною обробкою. Програма, яка призначена для багаторазового використання, повинна мати документацію з інструкцією для її експлуатації.

Дата добавления: 2014-01-07