При конструюванні можуть використовувати такі базові алгоритмічні структури:
1. Слідування. Команда слідування подається у вигляді послідовності двох (або більше) простих команд, що виконуються одна за одною. Якщо алгоритм можна подати у вигляді послідовності команд, то його називають лінійним алгоритмом.
Приклад 1. Скласти алгоритм обчислення і роздрукування значення виразу у = (Ax+B)(Cx+D).
1. Ввести значення А, В, С, D, х.
2. Обчислити у = (Ax+B)(Cx+D).
3. Роздрукувати у.
4. Процес обчислення завершити.
2. Розгалуження (вибір). Команда розгалуження — це вказівка виконати одну з двох команд: команду1 або команду2 залежно від істинності (true) чи хибності (false) деякого твердження Р. Якщо твердження Р істинне, то виконується команда1 і на цьому виконання розгалуження закінчується. Якшо ж твердження Р хибне, то виконується команда2 і на цьому виконання команди розгалуження закінчується.
Окремим випадком розгалуження є неповне розгалуження, коли в разі хибності твердження Р ніякі операції в розгалуженні взагалі не виконуються. Повне розгалуження завжди можна подати у вигляді слідування двох неповних.
Твердження Р може бути утворене з інших тверджень за допомогою логічних операцій НЕ, І, АБО, а замість команди1 чи команди2 може бути декілька команд, які називаються серією команд.
Приклад 2. Скласти алгоритм знаходження найбільшого з трьох чисел a, b, c і результат призначити змінній у.
Для розв'язку пропонованої задачі, поставимо додаткову перехідну змінну порівняння надання значень d. Реалізація потрібного алгоритму може відбуватися у наступній формі:
1. Задати значення а, b, с.
2. Якщо а>=b, то d:=a, інакше d:=b.
3. Якщо d>=c, то y:=d, інакше у:=с.
4. Роздрукувати значення у.
5. Процес обчислення завершити.
3. Повторення (цикл). Виділяють основні два типи циклів — цикл-ПОКИ і цикл-ДО.
У циклі-ПОКИ спочатку варто визначити, справжність (істинне чи хибне) твердження Р. Якщо воно істинне, то виконати команду1, яка утворює тіло циклу, і знову повертаються до визначення істинності твердження Р. Якщо ж твердження Р хибне, то виконання команди1 завершується. Отже, поки твердження Р справджується (істинне), потрібно повторювати виконання команди1 та повертатися до перевірки умови істинності данного твердження Р.
У циклі-ДО спочатку виконується команда1, а потім визначається істинність твердження Р. Якщо твердження Р хибне, то знову виконується команда1 і знову визначається істинність твердження Р. Якщо ж твердження Р істинне, то виконання вказівки завершується. Отже, команда1 і визначення істинності твердження Р повторюються до настання істинності твердження Р .
У структурі цикл-ПОКИ тіло циклу може не виконуватися жодного разу. У структурі ж цикл-ДО тіло циклу буде виконуватися принаймні один раз.
Приклад 3. Скласти алгоритм обчислення суми цілих чисел від 1 до 100.
1. Присвоїти початкові значення для суми (S) S:=0; та для змінної числа (х) х:=1.
2. Поки х<=100, виконувати команди S:=S+x; x:=x+1.
3. Вивести значення S.
4. Процес обчислення завершити.
Важливою особливістю розглянутих структур є те, що кожна з них має єдиний вхід і єдиний вихід. При конструюванні алгоритмів вихід кожної базової структури приєднується до входу іншої. При цьому весь алгоритм матиме вигляд лінійної послідовності базових алгоритмічних структур. Така послідовність може складатися з єдиної базової алгоритмічної структури. В одні базові алгоритмічні структури можуть вкладатися інші. Таким чином, у процесі побудови алгоритмів їх можна розвивати як «у ширину», так і в «глибину».
З теорії відомо, що кожний алгоритм можна подати у вигляді комбінації трьох базових алгоритмічних структур, що є їх основною властивістю. Використання цього принципу покладено в основі структурного підходу до побудови алгоритмів. Розроблені алгоритми мають чітко виражену структуру.
Використання алгоритмічних базових структур дозволяє:
1. Зробити алгоритми читабельними та зрозумілими.
2. Доводити правильність алгоритмів (тобто довести, що кожний алгоритм має одну точку входу і одну точку виходу, не містить нескінченних циклів, а також показати, що результати, які отримаємо за допомогою алгоритму відповідають шуканим).
3. Оцінити ефективність алгоритмів (тобто дати оцінку алгоритму з точки зору обчислювальних затрат).
|
