Алгоритмізація типових задач

Загальні положення

 

Етап алгоритмізації даних включає математичне формулювання задачі й розробку алгоритму її розв'язку

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

Відзначимо основні властивості алгоритмів:

● точність – передбачає встановлення чіткого порядку дій, щоб, виконавши чергову команду, виконавець точно знав, яку операцію треба виконувати далі;

● масовість – це можливість за допомогою одного алгоритму розв'язувати не тільки індивідуальну задачу, але й інши однотипні задачи на базі різних початкових даних;

● формальність — тобто можливість людини (програміста) правильно скласти програму за даним алгоритмом.

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

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

 

3.2. Особливості мови графічних символів

 

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

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

Найбільш часто використовувані символи схем алгоритмів наведено в таблиці 3.1.

 

Таблиця 3.1

Основні символи схем алгоритмів

Назва символу	Позначення	Пояснення
Пуск, зупинка		Початок, кінець, зупинка, вхід в підпрограмах і вихід з них
Введення, виведення		Перетворення даних у форму, придатну для обробки (введення) або відображення результатів обробки (виведення)
Процес		Обчислювальна дія або послідовність обчислювальних дій
Розв'язок		Перевірка умов
Модифікація		Початок циклу
Зумовлений процес		Обчислення за підпрограмою, стандартною підпрограмою
З'єднувач		Розрив лінії потоку
Коментар		Пояснення, зміст підпрограм, формули

Мінімальне значення розміру відрізка a дорівнює 10 мм, а його збільшення зазвичай відбувається на число, кратне 5. Розмір відрізка b приймається рівним 1,5а (допускається також b=2а). У межах однієї схеми рекомендовано зображувати символи однакових розмірів. Контури символів і ліній потоків, що їх з'єднують, виконуються суцільною (безперервною) лінією, товщина якої становить 0,6 – 1,5 мм.

У середині символу описується зміст операції (або операцій).

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

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

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

Символ розв'язки (розв'язок) використовується для позначення послідовності переходу керування діями відповідно до певної умови. При цьому мають бути сформульовані питання, відповіді умовам або порівняння, які стосуються кожного етапу розв'язку. Стрілки, що виходять із блоку розв'язку, мають бути позначені потрібними відповідями (наприклад, ТАК, НІ), причому враховуються всі їхні можливі варіанти.

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

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

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

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

 

3.3. Алгоритми основних видів обчислювальних процесів

 

Загальні положення

 

Помічено, що алгоритм розв'язки будь-якої задачі можна уявити як комбінацію базових алгоритмів (обчислювальних процесів). До таких процесів належать:

● прості (лінійні) обчислювальні;

● розгалужені обчислювальні;

● циклічні обчислювальніи.

3.3.2. Простий (лінійний) нерозгалужений обчислювальний процес

 

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

Приклад 3.1. Записати алгоритм обчислення значення величини Y за такою формулою:

Y = 150 + a·x. Схема алгоритму подано на рис. 3.1.