Базові структури алгоритмів. Основні властивості базових структур алгоритмів. Приклади

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

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. Оцінити ефективність алгоритмів (тобто дати оцінку алгоритму з точки зору обчислювальних затрат).

 


Репетитор в місті Рівне та Рівненському районі.

Поліграфічні послуги та фотодрук
Тел.: +38 (093) 515-57-24, +38 (098) 050-8649
м. Рівне, вул. Дубенська (Район Боярка)

Написати електронного листа репетитору

 

Реклама:

Пропонуємо фотодрук та Поліграфічні послуги.