Побудова розгалужених алгоритмів

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

 

Завдання для підготовки до виконання лабораторної роботи

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

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

 

ЗАГАЛЬНІ положення

 

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

Обрання напрямку залежить від заздалегідь визначеної ознаки, що може відноситись до первинних даних, проміжних або кінцевих результатів. Ознака характеризує властивість даних і має два або декілька значень. Напрямок обирається за допомогою перевірки логічного виразу, результатом якого є дві відповіді: «так» або «ні».

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

Операції, які здійснюються в логічних виразах, є наступними:

1 Логічне додавання - повертає ІСТИНА, якщо хоча б один з аргументів має значення ІСТИНА, та ХИБНО, якщо всі аргументи мають значення ХИБНО.

2 Логічне множення - повертає ІСТИНА, якщо всі аргументи мають значення ІСТИНА, та ХИБНО, якщо хоча б один з аргументів має значення ХИБНО.

3 Логічне «ні» - повертає ІСТИНА, якщо аргумент має значення ХИБНО та ЛОЖ, якщо аргумент має значення ІСТИНА.

Існує два типи логічних відносин:

1 Відношення еквівалентності. Бінарне відношення називається відношенням еквівалентності, якщо воно рефлексивне, симетричне та транзитивне.

2 Відношення порядку. Бінарне відношення називається відношенням порядку, якщо воно рефлексивне та транзитивне.

Приклад розв’язання задачі. Скласти схему алгоритму:

 

 

 

Вивести на друк y, Z.

Розв’язання. В даній задачі для розрахунку y та Z надано декілька формул. За якою саме з формул знаходити значення цих змінних залежить від того, яка з умов виконується, тому для розв’язання даної задачі слід побудувати блок-схему розгалуженого алгоритму.

На початку побудови алгоритму, крім відповідей на питання для лінійного алгоритму слід, з’ясувати, між якими з умов стоїть зв’язка логічного додавання (логічне АБО), а між якими – логічного множення (логічне І)?

Якщо між умовами стоїть логічне додавання (x>-5 АБО x<0), то результат такого виразу можна подати у наступному вигляді:

 

Умова 1	Умова 2	Результат
ІСТИНА	ІСТИНА	ІСТИНА
ІСТИНА	ХИБНО	ІСТИНА
ХИБНО	ІСТИНА	ІСТИНА
ХИБНО	ХИБНО	ХИБНО

 

На блок-схемі цей результат зображується наступним чином (рис. 2):

Рисунок 2 – Фрагмент алгоритму логічного виразу з оператором АБО

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

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

Якщо між логічними умовами стоїть логічне множення (x>-5 І x<0 або 5<x<0), то результат такого виразу можна подати у наступному вигляді:

 

Умова 1	Умова 2	Результат
ІСТИНА	ІСТИНА	ІСТИНА
ІСТИНА	ХИБНО	ХИБНО
ХИБНО	ІСТИНА	ХИБНО
ХИБНО	ХИБНО	ХИБНО

На блок-схемі цей результат зображується таким чином (рис. 3):

Рисунок 3 – Фрагмент алгоритму логічного виразу з оператором І

 

Так як у задачі між умовою х>-5 та умовою х<0 стоїть логічне І, а отже, якщо умова блоку 8 не виконується, то немає сенсу перевіряти другу частину виразу, так як вираз не буде виконуватись, тому у розраховується за формулою блоку 11. Якщо умова блоку 8 виконується, слід перевірити другу частину, яка записана в блоці 9. Невиконання цієї умови також призводить до невиконання всього виразу та розрахунку у за формулою блоку 11. Якщо умова блоку 9 виконується, то вираз в цілому має значення ІСТИНА, а тому у розраховується за формулою блоку10.

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

- «так» – гілка, яка відповідає виконанню умови, що міститься в блоці;

- «ні» – гілка, яка відповідає невиконанню умови, що міститься в блоці.

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

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

Блок-схему обчислюваного процесу для розв’язання наведеної задачі зображено на рисунку 4.

Рисунок 4 – Розгалужений алгоритм