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

ОСНОВИ ПРОГРАМУВАННЯ.

Теорія

1. Етапи розв’язування задач за допомогою комп’ютера. Поняття " алгоритм". Властивості алгоритму. Поняття “програмування”, “комп’ютерна програма”. Сучасні мови програмування.

Розв’язання будь-якої задачі на ЕОМ складається з кількох етапів, а саме:

– постановка завдання;

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

– вибір (або розроблення) методу розв’язування;

– розроблення алгоритму;

– складання програми;

– налагодження програми;

– обчислення та обробка результатів.

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

– вибір мови програмування;

– опис структури даних;

– оптимізація програми;

– тестування;

– документування та ін.

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

1) чи зрозуміла термінологія у формулюванні задачі;

2) що дано;

3) що необхідно знайти;

4) які загальні властивості явища чи об’єкта;

5) чи існує розв’язок поставленої задачі і чи він єдиний;

6) яких даних не вистачає і чи всі вони потрібні;

7) які слід зробити припущення;

8) які можливості конкретної ЕОМ і заданої системи програмування

(проаналізувати).

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

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

Побудуємо математичну модель задачі: плитка має форму квадрата, підлога форму прямокутника. Завдання, що поставлене у задачі, мовою математики формулюється так: у скільки разів площа прямокутника зі сторонами 3, 3 м і 2, 8 м більші від площі квадрата зі стороною 15 см.

Розв’язання математичної задачі.

Площа прямокутника: 3, 3*2, 8=9, 24(кв.м)

Площа квадрата: 15*15=225(кв.см)=0, 0225(кв.м)

Відношення площ: 9, 24/0, 0225=410, 6

Записуємо результат мовою вихідної задачі. Щоб застелити підлогу, потрібно не менше ніж 411 плиток.

Визначення алгоритму

Алгоритм – послідовність дій, що приводить до рішення поставленої задачі за скінчену кількість операцій.

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

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

Можна виділити три основних види обчислювальних алгоритмів:

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