Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
+09-Пояснювальна записка.doc
Скачиваний:
2
Добавлен:
01.05.2025
Размер:
974 Кб
Скачать
☆

2.7 Аналіз правильності побудови графу

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

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

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

Оскільки для побудови алгоритму буде використовуватися орієнтований граф, то необхідно враховувати направленість ребер графа.

Основні обмеження на побудову графа алгоритму наведені нижче:

  1. Кожен граф алгоритму повинен містити вершину «Введення даних» та «Виведення даних»

Вершина «Введення даних» відповідає аналогічному блоку, який використовується в блок-схемах «Початок», відповідно вершина «Виведення даних», якою обов’язково повинен закінчуватися алгоритм, є аналогом блоку «Кінець» у блок-схемах.

  1. Кожна вершина повинна мати тільки одне вихідне ребро, виключенням в цьому випадку є тільки вершина умовного оператора, у якого одне вихідне ребро відповідає гілці, коли умова виконується, а інше ребро відповідає гілці ELSE умовного оператора.

  1. Кожна вершина повинна мати одне або два вхідні ребра, крім початкової вершини «Введення даних». Прикладом таких ситуацій можуть бути:

    1. Вершини закінчення оператора (IF.. ELSE), коли обидві гілки сходяться до одного оператора, наприклад, до «Виведення даних»,

    1. Вершина початку циклу DO…WHILE

    1. Вершина початку циклу WHILE…DO

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

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

Наступним обмеженням реалізованим програмно є обмеження на кількість вхідних і вихідних ребер вершини. Оскільки для побудови використовується граф, то виходячи з його визначення, кожна вершина може мати n-1 ребро, де n – це кількість вершин у графі, тобто вершина може бути з’єднана з усіма вершинами графа окрім самої себе. Але для поставленої задачі ця властивість вершини графа була трохи модифікована, тому що в основній своїй більшості, алгоритми є лінійними, або розгалуженими.

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

В разі використання вершин умовного оператора (IF.. ELSE) в алгоритмах розгалуження на неї накладається обмеження згідно якого тільки вершина умовного оператора може мати два вихідних ребра: гілка виконання умови і гілка не виконання умов (гілка ELSE) .

Обмеження на кількість вхідних ребер вершини може мати виняток тільки у тому разі, коли вершина є складовою вершиною циклу DO…WHILE, або вершиною закінчення оператора (IF.. ELSE).

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]