Розгалужені та циклічні алгоритмічні структури

1. Розгалужені та циклічні алгоритмічні структури.

2. ПЛАН ЛЕКЦІЇ

1. Загальні принципи організації розгалужених обчислювальних
процесів.
2. Різновиди розгалужених структур.
3. Загальні принципи організації циклічних обчислювальних процесів.
4. Різновиди циклічних структур

3.

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

4.

1. Загальні принципи організації розгалужених обчислювальних
процесів.
Розгалужені структури забезпечують керування ходом виконання алгоритму в залежності від
виконання чи невиконання визначених умов. Ці умови перевіряються за допомогою блоку
РІШЕННЯ, якому в загальному випадку відповідає так називаний оператор «Умовного
переходу» і графічний символ на блок-схемі алгоритму такого виду
ТАК
Стосовно системи АЛГОРИТМ, оператор блоку РІШЕННЯ має умовну
позначку D (від Decision). Він обчислює : Логічний вираз (Логічний
НІ вираз),
і в залежності від отриманого значення вибирає подальший шлях
виконання алгоритму:
- якщо логічний вираз істина (має значення TRUE), то передається
керування тієї гілці алгоритму, яка з'єднана з виходом, тобто має ознаку Т
(ТАК);
- якщо логічний вираз неправда (має значення FALSE), то передається
керування іншої гілці алгоритму, яка з'єднана з виходом, тобто має
ознаку
Н (НІ).

5.

Як логічний вираз можна використовувати:
- змінну логічного типу (:В);
- власний логічний вираз, що складається з логічних операндів і логічних операцій
(наприклад, А & В, де А і В - логічні змінні);
- вираз, що використовує операції відносини (наприклад, А > В, де змінні А та В можуть
бути чисельного, символьного чи рядкового типу).
При побудові розгалуженого фрагмента алгоритму рекомендується
додержуватися
декількох правил:
-Для полегшення візуального сприйняття алгоритму зв'язки між блоками повинні
відображатися в максимально простому вигляді мінімальним перехрещенням сполучних
ліній.
-Для спрощення реалізації розгалуженого фрагмента алгоритму у виді програмних
конструкцій ознака «Д» повинна мати нижній вихід блоку РІШЕННЯ, а ознака «Н» - бічний
вихід. У цьому випадку вихід Д позначає також перехід «далі» (параметр msb), а вихід Н перехід «інакше» (параметр msbl). Такий варіант передбачено за замовчуванням.
-Розгалужена структура повинна бути цілісною, тобто гілки алгоритму, підключені до різних
виходів, в остаточному підсумку повинні сходитися в одній точці.
-Фрагмент алгоритму в кожній гілці також повніший утворювати цілісну структуру.

6.

Приклад побудови розгалуженого алгоритму
a=b
н
b:=0
а)
б)
в)
Рекомендований варіант розгалуження - праворуч

7.

2. Різновиди розгалужених структур.
ЛВ
Н
Д
Фрагмент
алгоритму
Рис. 4.10 Вибір з однією
альтернативою
ЛВ
Н
Д
ФрагментД
ФрагментН
Рис. 4.11 Вибір з двома
альтернативами
Як було відзначено, розгалужені структури забезпечують вибір варіанта
виконання алгоритму
Найпростіший
різновид
розгалуженої
структури
забезпечує
одноальтернативний вибір. Цей різновид показаний на рис.4.10, де ЛВ логічний вираз (умова, що перевіряється,).
У даному випадку виконання умови забезпечує перехід з нижчого виходу
(Т) до виконання фрагмента алгоритму, що слідує за блоком РІШЕННЯ. У
противному випадку розгалужена структура нічого не виконує, тому що
бічний вихід (Н) з’єднаний безпосередньо з його виходом.
Дуже розповсюдженої є різновид, що забезпечує двохальтернативний
вибір, що показана на рис.4.11.У даному випадку при виконанні умови
виконується Фрагмент Д, а при невиконанні - Фрагмент Н. Виходи обох
фрагментів з'єднуються в одній точці, яка утворює вихід розгалуженої
структури.

8.

За допомогою блоку РІШЕННЯ можна реалізувати також багатоальтернативний
вибір, аналогічний перемикачу.
Рис. 4. Багатоальтернативний вибір
Для будь-якого різновиду розгалуженій структури фрагменти алгоритмів у кожній
з гілок можуть мати будь-яку цілісну структуру - лінійну, розгалужену, циклічну,
що дозволяє створювати дуже складні алгоритми.

9.

3.Загальні принципи організації циклічних обчислювальних процесів.
Циклічною структурою називається цілісний фрагмент алгоритму, що забезпечує
виконання деяких повторюваних дій.
Циклічну структуру утворюють:
1. Блоки ПОЧАТОК ЦИКЛУ і КІНЕЦЬ ЦИКЛУ
2. Один чи декілька блоків, розташованих між ПЦ
та КЦ. Вони утворюють тіло циклу.
Для повторного виконання тіла циклу необхідно
передати керування від блоку КІНЕЦЬ ЦИКЛУ до
блоку ПОЧАТОК ЦИКЛУ. Однак на блок-схемі
алгоритму
такий
зворотний
зв'язок
не
відображається, але фактично він здійснюється.
Власне кажучи, графічні символи ПОЧАТОК і
КІНЕЦЬ ЦИКЛУ введені саме для того, щоб
спростити вид блок-схем, особливо у випадку
вкладених циклів. Завдяки їм, циклічні структури
виглядають подібно лінійним структурам.

10.

Для правильного виконання циклу необхідно при побудові алгоритму
наступні вимоги:
забезпечити
1.Номер циклу, що зазначений в умовних позначках блоку (УОБ) початку і кінця циклу,
повинний бути однаковим.
2.Тіло циклу повинне мати цілісну структуру, тобто, забороняється вхід у тіло циклу в обхід
блоку ПОЧАТОК ЦИКЛУ і вихід з тіла циклу в обхід блоку КІНЕЦЬ ЦИКЛУ. Крім
цілісності, інших обмежень на структуру тіла циклу немає - воно може мати лінійну,
розгалужену і циклічну структуру. Отже, допускається багаторазове вкладення циклів.
Внутрішній цикл повинний цілком (тобто, блок ПОЧАТОК ЦИКЛУ, тіло циклу і блок
КІНЕЦЬ ЦИКЛУ) знаходитися в тілі зовнішньою циклу. При введенні алгоритму ця вимога
виконується автоматично, завдяки реалізації принципу: цикл, що починається першим
(зовнішній), закривається останнім, а цикл, що починається останнім (внутрішній),
закривається першим.
3. Щоб уникнути «зациклення» алгоритму необхідно забезпечити кінцеве число повторень
тіла циклу.
4.Типи операторів початку і кінця циклу повинні бути взаємно погодженими

11.

5. Різновиди циклічних структур .
Існують кілька різновидів циклів, що відрізняються функціонуванням операторів початку і кінця
циклу:
цикл із параметром;
цикл із передумовою;
цикл із післяумовою.
Цикл із параметром.
Даний різновид циклу звичайно використовується для побудови циклічної структури алгоритму у випадку,
коли до входу в цикл відоме число повторень тіла циклу.
Блок початку циклу зображується відповідним графічним символом і його умовна позначка складається з
букви F (від For) і номера циклу ж (наприклад, F4). Оператор початку циклу має наступну форму
Поч. циклу №: параметр:=вираз_поч. ознака вираз_ кін де
Поч. циклу № : - преамбула, формована за замовчуванням (номер циклу № визначається автоматично);
параметр - змінна цілочисельного типу, що грає роль лічильника циклу;
вираз_поч. - у загальному випадку арифметичний вираз, що задає початкове значення параметра циклу;
вираз_кін. - у загальному випадку арифметичний вираз, що задає кінцеве значення параметра циклу;
ознака - характеризує напрямок зміни параметра і задається у вигляді:
ключове слово to (ТО) - у даному випадку параметр циклу на кожнім проході циклу змінюється на +1;
ключове слово downto (DOWNTO) - у даному випадку параметр циклу на кожнім проході циклу змінюється
на -1.
Ознака повинна відокремлюватися пробілом від початкового і кінцевого значення параметра.

12.

Число повторень тіла циклу залежить від початкового значення параметра, кінцевого значення
параметра й ознаки. Позначимо початкове значення параметра як in, кінцеве значення
параметра як ik. Тоді число повторень циклу дорівнює:
Ознака
Співвідношення
Число повторень
to
in<=ik
ik-in+1
to
in>ik
жодного разу
downto
in>=ik
in-ik+1
downto
in<ik
жодного разу
Блок кінця циклу зображується відповідним графічним символом і його умовна позначка
повинна складатися з букви Е (від End) і того ж номера циклу №, що й в операторі початку
циклу (для приклада, Е4). Збіг номерів забезпечується автоматично. Оператор кінця циклу має
наступну форму
Кін. циклу № :
де Кін. циклу №: - преамбула, формована за замовчуванням. У даному випадку він не
виконує ніяких дій.
При вставці блоку «Кінець циклу» у вікні «Характеристики й опис блоку» нічого вводити не
потрібно. Даний блок служить лише для вказівки, де закінчується тіло циклу і куди необхідно
перейти після його завершення.

13.

Цикл із передумовою
Даний різновид циклічної структури використовується у випадку, якщо деяку послідовність дій
(операцій) потрібно виконати декілька разів, причому необхідне число повторень тіла циклу під
час розробки програми невідомо і може бути визначене лише під час роботи програми.
Необхідно також передбачити ситуацію, у якій тіло циклу взагалі жодного разу не
виконається.
Блок початку циклу зображується відповідним графічним символом і його
умовна позначка складається з букви W (від While) і номера циклу" №
(наприклад, W2). Оператор початку циклу має наступну форму
Поч. циклу №: логічний_вираз , де
Поч. циклу №: - преамбула, формована за замовчуванням (номер циклу №
визначається автоматично);
логічний_вираз - умова, у випадку істинності якої виконується тіло циклу,
у противному випадку здійснюється вихід з циклу.
Якщо умова із самого початку виявиться хибною, то вхід у цикл не
відбудеться і керування буде передано блоку, на який вказує блок кінця
циклу.

14.

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

15.

Цикл із післяумовою
Як і попередній різновид циклу, цикл із післяумовою застосовується у випадку, коли число
повторень тіла циклу заздалегідь невідомо. Однак, на відміну від попереднього різновиду, тут
тіло циклу обов'язково виконується хоча б один раз.
Блок початку циклу з післяумовою зображується відповідним графічним символом і його
умовна позначка складається з букви R (від Repeat) і номера циклу № (наприклад, R3).
Оператор початку циклу має наступну форму:
Поч. циклу №:
де Поч. циклу №: - преамбула, формована за замовчуванням (номер
циклу № визначається автоматично). Він фактично не виконує ніяких дій
і-служить лише для вказівки, що слідом за ним починається тіло циклу.
Блок кінця циклу з післяумовою зображується відповідним графічним
символом і його умовна позначка складається з букви U (від Until) і того
ж номера №, що й у блоці початку циклу (для приклада, R3). Оператор
кінця циклу має наступну форму
Кін. циклу №:логічний_вираз, де
Кін. циклу №: - преамбула, формована за замовчуванням;
логічний_вираз - умова, у випадку істинності якої цикл завершується,
у противному випадку – продовжується.

16.

Попередження. У тілі циклу повинно змінюватися значення якої-небудь змінної чи елемента
масиву, що ,в остаточному підсумку, повинне призвести до виконання умови та виходу з
циклу. У протилежному випадку цикл не зможе закінчитися.
Приклад використання циклу з параметром.
ЗАДАЧА 1. Обчислити факторіал п! цілого позитивного числа п. Дана
задача описується дуже простою інформаційною моделлю.
Математична модель. Факторіалом числа п називається число, яке
дорівнює n!=1*2*3*…*n.
у відповідності з цим виразом 1!=1 , 2!=2, 3!=6, 4!=24 і т.д. В математиці
прийняте також , що 0!=1.
Обчислювальна модель. Неважко зрозуміти,що n!=((n-1)!).n.
Звідки
для n=l: 1! =(0!)1 = 1(1 = 1,
для n = 2 : 2! = 1!2= 1*2 = 2,
для n =3: 3! = 2!*3 = 2*3 = 6 і т.д.
Позначимо fact - змінну, яка накопичує значення факторіала. Тоді для
кожного значення змінної і = 1,2, ..., п необхідно обчислити
fact : = fact * і ,
де початкове значення перемінної fact повинне бути дорівнює 1