Способи подання алгоритму

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

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

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

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

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

Перед тим, як навести декілька прикладів розробки та запису алгоритму, треба зробити одне важливе зауваження відносно класифікації алгоритмів.

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

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

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

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

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

Таблиця 1.1

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

Приклад 1. Розрахувати кількість пального G, необхідного для здійснення маршу колоною з N однотипних бойових машин з пункту А до пункту Б, що задані топографічними координатами x, y.

Розв’язання задачі виконується, як це звичайно прийнято у математиці, починаючи з шуканого результату. Кількість пального G визначаєтьсяза формулою:

G=qNS,

де q – питомі витрати пального однією машиною, л/км;

S – довжина маршруту, км.

Довжина маршруту S обчислюється за формулою

S=k _г k _в D,

де k _г та k _в – коефіцієнти скривлення шляху відповідно у горизонтальній

та вертикальній площині;

D – відстань між пунктами, яка визначається їх топографічними координатами:

.

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

Пояснимо це на короткому прикладі. Якщо для людини запис двох кроків y= 6 x, x= 2не викликає непорозумінь і вона знайде значення y (y= 12), то машина зупиниться на першому кроці, бо на цей час значення x

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

Кінець

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

Слід звернути увагу на те, що формули, за якими виконуються обчислення, можуть бути показані у прямокутнику “процес” або, якщо формули мають великі розміри, збоку від прямокутника у вигляді коментарю, як показано на рис. 1.2.

Приклад 2. Групова ціль з N бойових машин обстрілюється m ракетами. Імовірність знищення бойової машини однією ракетою дорівнює p. Ціль вважається знищеною, якщо відносна частка q знищених машин становить не менш заданої k. Розробити алгоритм визначення результату обстрілу, якщо задані N, m, p, k.

Частка знищених машин визначається співвідношенням

q = M/N,

де M – математичне очікування кількості знищених бойових машин, що обчислюється за формулою

M = N [ 1 - (1 - p/N) ^m ].

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

Групова ціль вважається знищеною, якщо q ³ k (0£ k £ 1). Ця умова визначає, що сформульована задача має розгалужену алгоритмічну структуру. Блок-схема алгоритму показана на рис. 1.3.

Висновок про результати обстрілу (рішення) приймається після перевірки умови

q ³ k?, яка закінчується однією з двох можливих відповідей: “так” чи “ні”.

Приклад 3. Розробити алгоритм розрахунку залежності тривалості переправи T (хв) під водою танкової колони з N машин від дистанції між ними d (м), якщо задана ширина водної перешкоди S (м) та швидкість руху танків під водою V (км/год).

Шукана залежність задається формулою

T = 0,06(S + (N - 1) d) / V,

де 0,06 – коефіцієнт, що узгоджує розмірності змінних.

Розглянемо розробку алгоритму розв’язання задачі за умовою, що дистанція d може змінюватись у межах від d _minдо d _max з кроком D d.

Щоб знайти шукану залежність, треба розрахувати значення тривалості часу T для кожного d з інтервалу.

Спочатку можна знайти тривалість переправи T для d = d _min. Потім слід перейти до наступного значення d = d _min + D d і знову обчислити T. Далі, додаючи на кожному кроці до значення d величину D d, повторювати розрахунки тривалості T, доки буде виконуватися нерівність d £ d _max.

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

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

величина дистанції d відрізняється від попередньої на D d. Тому у алгоритмі розрахунок значення дистанції d можна подати у вигляді:

d = d + D d.

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

Слід звернути увагу на те, що умова d £ d _max перевіряється на кожному кроці розрахунку.

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

, тобто S = 1+2+3 +…+ n

не викликає ніяких труднощів, якщо n відоме. Але алгоритм – це послідовність дій, яка не повинна бути пов’язаною з конкретними числами, тому він має приводити до результату для будь-якого невідомого заздалегідь значення n (властивість масовості алгоритму). Розробити алгоритм для обчислення цієї суми не так просто, якщо не користуватися певними прийомами алгоритмізації.

Під час розробки алгоритму визначається загальна послідовність дій. Тому у алгоритмі замість конкретних чисел використовуються змінні. До чисел користувач звертається лише на етапі виконання алгоритму. При цьому кожний крок алгоритму – це саме виконання дій, процесу знаходження результату, що має свій початок та кінець. Тому запис, наприклад кроку алгоритму i = i + 1, не викликає ніяких непорозумінь: треба взяти значення змінної i, що відоме на цей час, додати одиницю та присвоїти одержане нове значення змінній i. Це нове значення змінної і буде використовуватися у наступних розрахунках. Саме цей прийом визначення наступного значення шуканої змінної через попереднє був використаний у прикладі 3.

Під час розробки алгоритму необхідно обов’язково передбачити всі варіанти, що можуть виникнути при конкретних значеннях змінних. Наприклад, якщо на певному кроці зустрічається вираз, до складу якого входить квадратний корінь Ö x, треба обов’язково указати подальші дії у випадках, коли x ³ 0 та x < 0. Грамотно розроблений алгоритм має також передбачати можливі помилки, які можуть виникнути під час введення вихідних даних внаслідок неуважності виконавця.

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

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

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