УФІМСЬКИЙ ДЕРЖАВНИЙНАФТОВИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ

КАФЕДРА ВИЧИСЛЮВАЛЬНОЇ ТЕХНІКИ ТА ІНЖЕНЕРНОЇ КИБЕРНЕТИКИ

ОСНОВИ АЛГОРИТМІЗАЦІЇ

УФА 2000

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

Навчальний посібник може бути використаний для студентів усіх спеціальностей заочної форми навчання УДНТУ.

Упорядники: ІВАНОВ В.І., доцент,

МУХАМАДЄЄЄВ І.Г., доцент,

ІВАНОВА О.В., гр. ЕА-96-01

Рецензент: ХОРОБРОВ В.Р., доцент

Ó Уфімський державний нафтовий

технічний університет, 2000

ВСТУП

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

1) постановка задачі (формалізація задачі);

2) алгоритмічна частина (алгоритмізація);

4) оцінка та аналіз отриманих результатів (контрольний розрахунок).

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

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

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

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

Наступним етапом вирішення завдання на комп'ютері є програмування. З цією метою можна використовувати алгоритмічний мову високого рівня, наприклад, ПАСКАЛЬ.

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

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

АЛГОРИТМІЗАЦІЯ

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

Існують три основні (базові) алгоритмічні структури:

1) лінійна структура;

2) циклічна структура;

3) розгалужена структура.

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

Найбільш простим і легким для розуміння є алгоритм лінійної структури, який є сукупністю операцій, що йдуть один за одним. Алгоритм лінійної структури показано на рис. 1.Алгоритм циклічної структури включає операції, що регулярно повторюються, звані “тілом циклу”. Варіанти оформлення алгоритмів циклічної структури наведено на рис. 2.

Рис.1

a) цикл "до" б) цикл "поки" в) арифметичний цикл

Зазначимо, що арифметичний цикл з параметром циклу i (варіант в) використовується, коли число обчислень (циклів) N, що повторюються, відоме.

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

a) альтернатива б) обхід б) корекція

Зазвичай існує необхідність уточнення вихідного алгоритму, складеного із загальних формальних міркувань. В цьому випадку говорять про розробку деталізованої схеми алгоритму методом послідовного уточнення (метод "згори донизу").

Приклад 1

Необхідно обчислити максимальне значення змінних. Існує багато різних способів вирішення цього завдання. Розглянемо один із них з використанням додаткової змінної. Алгоритм прикладу 1 показаний на рис. 4.

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

1 крок 2 крок 3 крок

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

Чи не знайшли те, що шукали? Скористайтеся пошуком гугл на сайті:

---