Введення
Теорія алгоритмів та практика їх побудови та аналізу є концептуальною основою різноманітних процесів обробки інформації. В даний час теорія алгоритмів утворює теоретичний фундамент обчислювальних наук. Застосування теорії алгоритмів здійснюється як у використанні самих результатів (особливо це стосується використання розроблених алгоритмів), так і у виявленні нових понять і уточнення старих. З її допомогою прояснюються такі поняття як довідність, ефективність, розв'язність, перераховуваній та інші.
Фактично, алгоритм - це точно певна (однозначна) послідовність простих (елементарних) дій, які забезпечують вирішення будь-якої задачі з деякого класу, тобто такий набір інструкцій, який можна реалізувати чисто механічно, незалежно від розумових здібностей і можливостей виконавця.
Як зауважив Кнут: «Алгоритм повинен бути визначений настільки чітко, щоб його вказівкам міг слідувати навіть комп'ютер».
Ефективність алгоритму визначається аналізом, який повинен дати чітке уявлення, по-перше, про ємнісний і, по-друге, про часової складності процесу.
Мова йде про розміри пам'яті, в якій належить розміщувати всі дані, які беруть участь в обчислювальному процесі (природно, до них відносяться вхідні набори, проміжна і вихідна інформація), а також фізичних ресурсах, витрачених виконавцем.
У курсовій роботі представлені різні підходи та методи використання алгоритмів, наведені оцінки складнощів алгоритмів, реалізації математичних задач за допомогою алгоритмів. Проведена коротка характеристика використовуваних структур даних, ефективність їх застосування в даній задачі
1. Вибір варіанта завдання
В основі вибору індивідуального варіанту завдання лежить процедура визначення цілочисельного залишку від ділення вираження Y, утвореного сумою номера студента по журнальному списку і числом Х, отриманим множенням останньої цифри номера групи на 100. Після визначення значення виразу Y знаходиться залишок від ділення для відповідного списку алгоритмів:
Y mod 4 + 1 - алгоритми покриття;
Y mod 6 + 1 - алгоритми на графах;
Y mod 5 + 1 - Алгоритми сортування.
Мій номер по журнальному списку дорівнює 5, група АЕ-035. Тому маємо Y = 5 +5 * 100 = 505. Отримуємо такі варіанти:
А = 505 mod 4 +1 = 2;
B = 505 mod 6 +1 = 2;
C = 505 mod 5 +1 = 1.
Таким чином, маємо наступні алгоритми: покриття - за методом «побудова одного найкоротшого покриття», на графах - знаходження найдовшого шляху, сортування - простими включеннями.
Постановка завдання. Необхідно ввести таблицю покриття. Алгоритм повинен знайти покриття, близьке до найкоротшим.
2. Алгоритм сортування
2.1 Математичне опис завдання і методів її рішення
У загальному значенні сортування слід розуміти як процес перегрупування заданої множини об'єктів в деякому певному порядку. Її мета - полегшити подальший пошук елементів у такому відсортованому множині.
Якщо у нас є елементи а 1, ..., а n, то сортування є перестановка цих елементів в масив а к1, ..., а до n, де при деякій впорядкує функції f виконуються відносини f (a k 1) ≤ f (a k 2 ) ≤ ... ≤ f (a kn).
Метод сортування називається стійким, якщо в її процесі відносне розташування елементів з рівними ключами не змінюється.
Існують такі алгоритми сортувань масиву: сортування за допомогою прямого включення, прямого вибору, прямого обміну, включень з зменшуються відстанями, дерева, поділу та інші.
2.2 Словесне опис алгоритму і його роботи
У силу простоти алгоритм сортування простими включеннями не вимагає розділення на підпрограми.
Елементи подумки діляться на вже «готову» послідовність а 1 ... а 2 і вихідну послідовність а 1 ... а n. При кожному кроці, починаючи з i = 2 і збільшуючи i кожного разу на одиницю, з вихідної послідовності витягується i-й елемент і перекладається в готову послідовність, при цьому він вставляється в потрібне місце.
Словесний опис алгоритму сортування простими включеннями:
0. У готову підпослідовність записується а 1, у вхідні - а 2, .... А n.
1. I = 2.
2 Переносимо елемент х = а з вхідної підпослідовності в готову так, щоб готова підпослідовність залишилася під сортованого. Для цього:
а) розширюємо готову підпослідовність ліворуч: а 0 = х - бар'єр;
б) переглядаючи елементи готової підпослідовності зліва направо, знаходимо такий номер j що і a i <= x <a i +1;
в) якщо j = j -1, то переходимо до пункту г), інакше розширюємо готову
підпослідовність праворуч, зрушуючи її елементи, починаючи з a i вправо;
г) a i +1 = x
д) i = i + 1. Якщо i <= n, то переходимо до п. 2, інакше сортування закінчується.
Процес може закінчитися при двох різних умовах: 1) знайдений елемент з ключем, меншим, ніж ключ x; 2) досягнення кінця готової послідовності. Виходить цикл з двома умовами. Тому для деякого поліпшення швидкодії застосовується бар'єр - a [0] присвоюється значення ключа x.
Проаналізуємо цей алгоритм. Число порівнянь (С i) при i-му просіюванні найбільше одно i -1, найменше - 1; якщо припустити, що всі перестановки з n ключів різновірогідні, то середня кількість порівняння - i / 2. Число ж пересилань (привласнення елементів) M i одно З i +2 (включаючи бар'єр). Тому загальна кількість порівнянь і кількість пересилань такі:
З min = n -1, M min = 3 * (n -1)
C ave = (n 2 + n-2) / 4, M ave = (n 2 + * n-10) / 4,
C max = (n 2 + n-4) / 4, M max = (n 2 +3 n-4) / 2.
Мінімальні оцінки у разі вже впорядкованої вихідної послідовності елементів, найгірші ж оцінки - коли вони спочатку розташовані у зворотному порядку. Очевидно, що наведений алгоритм описує метод стійкої сортування (див. [1]).
Цей алгоритм можна легко поліпшити, оскільки готова послідовність сама вже впорядкована. Тому при пошуку підходящої позиції для i-го ключа доцільно використовувати двійковий пошук. При цьому такий модифікований алгоритм носить назву методу з двійковим включенням.
Словесний опис алгоритму сортування бітового включенням:
0. У готову підпослідовність записується а 1, у вхідні а 2, .... А n.
1. I = 2
2 Переносимо елемент х = а i з вхідної підпослідовності в готову так, щоб остання залишилася під сортованого. Для цього:
а) організуємо бінарний пошук місця включення х у готову підпослідовність: знаходимо серединний елемент готової підпослідовності - a m, де m =] i / 2 (, і порівнюємо його з х. Якщо a m> х то ведемо далі пошук в лівій половині готової підпослідовності , тобто знову знаходимо серединний елемент і порівнюємо його з х і т.д., поки не знайдемо номер j такий, що a i <= x <a i +1, інакше аналогічно ведемо пошук в правій половині готової підпослідовності;
б) якщо j = j -1, то переходимо до пункту в), інакше розширюємо готову підпослідовність праворуч, зрушуючи її елементи, починаючи з a i вправо;
в) a i +1 = х
3. I = i +1. Якщо i <= n, то переходимо до п. 2, інакше сортування закінчується.
Розподіл навпіл виробляється i * log 2 i. Число порівнянь практично не залежить від початкового порядку елементів. У нижній частині послідовності місце включення відшукується трохи швидше, ніж у верхній, тому краща ситуація, коли елементи трохи впорядковані. Фактично, якщо елементи в зворотному порядку, буде потрібно мінімальне число порівнянь, якщо вже впорядковані - максимальне:
C ≈ n * log 2 (log 2-log 2 e ± 0,5). Однак число пересилань так і залишається близько n 2. І насправді сортування вже впорядкованого масиву зажадає більше часу, ніж метод з прямими включеннями (див. [1]).
2.3 Вибір структур даних
Алгоритми сортування дуже сильно залежать від структури даних, так що виділяють два класи: сортування масивів і сортування послідовностей (файлів). У даній роботі розглядається сортування масивів. Тип даних «масив» зручний тим, що зберігається у внутрішній пам'яті і має випадковий доступ до елементів, то є більш швидкий, ніж у послідовності. Тому масиви доцільно використовувати для зберігання невеликих, часто використовуваних множин.
Зазвичай впорядковує функція не обчислюється з якого-небудь правилом, а зберігається як явна компонента (поле) кожного елемента. Її значення називається ключем елемента. Тому для представлення елемента добре підходить тип «запис», що на мові «Pascal» виглядає наступним чином:
TYPE item = RECORD key: INTEGER;
{Тут описані інші компоненти}
END;
Оскільки в алгоритмі сортування використовується тільки ключ елемента, то решту інформацію про елемент можна опустити - вважаємо, що тип елемента визначено як INTEGER. Можна вибрати й інший тип, на якому визначено загальне відношення порядку.
З вище сказаного випливає, що в процесі роботи будуть потрібні наступні змінні:
n - кількість елементів масиву;
A - сортований масив;
i - мінлива циклу (по вихідної послідовності);
j - мінлива внутрішнього циклу (по готовій послідовності);
x - i-й ключ (переносимий елемент).
Всі змінні цілого типу.
2.4 Опис схеми алгоритму
Блок-схема даного алгоритму зображена на рис. 2 в Додатку.
Алгоритм працює наступним чином. Спочатку вводяться вихідні дані: довжина масиву та його елементи (блоки 1, 2), потім організується цикл по всій довжині масиву, під час якого ставиться «бар'єр» (блок 3) і проводиться порівняння i-го ключа з елементами готової послідовності (стоять раніше нього). При цьому всі елементи, великі цього ключа (ця умова перевіряється в блоці 4), зсуваються вправо (блок 5). Це відбувається до тих пір, поки не зустрінеться елемент менший або рівний даному ключу (принаймні бар'єру). Тоді i-й ключ вставляється в цю позицію (блок 6).
2.5 Контрольні приклади розв'язання задачі за допомогою алгоритму сортування простими включеннями
Приклад сортування масиву, відсортовані випадковим чином.
Нехай задано такий масив з восьми елементів: (32,43,2,30,82,8,5,52) (див. Таб. 1).
Початкові ключі | 32 | 43 | 0 2 | 30 | 82 | 0 8 | 0 5 | 52 |
i = 2 | 32 | 43 | 0 2 | 30 | 82 | 0 8 | 0 5 | 52 |
i = 3 | 0 2 | 32 | 43 | 30 | 82 | 0 8 | 0 5 | 52 |
i = 4 | 02 | 30 | 32 | 43 | 82 | 0 8 | 0 5 | 52 |
i = 5 | 02 | 30 | 32 | 43 | 82 | 0 8 | 0 5 | 52 |
i = 6 | 0 2 | 0 8 | 30 | 32 | 43 | 82 | 0 5 | 52 |
i = 7 | 02 | 05 | 08 | 30 | 32 | 43 | 82 | 52 |
i = 8 | 02 | 05 | 08 | 30 | 32 | 43 | 52 | 82 |
Покрокове рішення:
Крок 1:
i = 2;
x = 43; a [0] = 43; j = 1;
3) x> a [j] = 32;
3.2) a [2] = 43;
4) i = 3; i ≤ n = 8 → п. 2;
Крок 2:
2) x = 2; a [0] = 2; j = 2;
3) x <a [j] = 43;
3.1) a [3] = 43; j = 1; → п. 3;
3) x <a [j] = 32;
3.1) a [2] = 32; j = 0; → п. 3;
3) x = a [j];
3.2) a [1] = 2;
4) i = 4; i <n → п. 2;
Крок 3:
2) x = 30; a [0] = 30; j = 3;
3) x <a [j] = 43;
3.1) a [4] = 43; j = 2; → п. 3;
3) x <a [j] = 32;
3.1) a [3] = 32; j = 1; → п. 3;
3) x> a [1] = 2
3.2) a [2] = 30;
4) i = 5; i <n → п. 2;
Крок 4:
2) x = 82; a [0] = 82; j = 4;
3) x> a [j];
3.2) a [5] = 82;
4) i = 6; i <n → п. 2;
Крок 5:
2) x = 8; a [0] = 8; j = 5;
3) x <a [j] = 82;
3.1) a [6] = 82; j = 4; → п. 3;
3) x <a [j] = 43;
3.1) a [5] = 43; j = 3; → п. 3;
3) x <a [j] = 32;
3.1) a [4] = 32; j = 2; → п. 3;
3) x <a [j] = 30;
3.1) a [3] = 30; j = 1; → п. 3;
3) x> a [j] = 2;
3.2) a [2] = 8;
4) i = 7; i <n → п. 2;
Крок 6:
2) x = 5; a [0] = 5; j = 6;
3) x <a [j] = 82;
3.1) a [7] = 82; j = 5; → п. 3;
3) x <a [j];
3.1) a [6] = 43; j = 4; → п. 3;
3) x <a [j] = 32;
3.1) a [5] = 32; j = 3; → п. 3;
3) x <a [j] = 30;
3.1) a [4] = 30; j = 2; → п. 3;
3) x <a [j] = 8;
3.1) a [3] = 8; j = 1; → п. 3;
3) x> a [j] = 2;
3.2) a [2] = 5;
4) i = 8; i ≤ n → п. 2;
Крок 7:
2) x = 52; a [0] = 52; j = 7;
3) x <a [j] = 82;
3.1) a [8] = 82; j = 6; → п. 3;
3) x> a [j] = 43;
3.2) a [7] = 52;
4) i = 9; i> n → кінець алгоритму.
Таким чином, маємо 21 пересилання елементів і 20 порівнянь.
Приклад сортування вже відсортованого масиву.
Нехай задано такий масив з восьми елементів: (2,5,8,30,32,43,52,82).
Покрокове рішення:
Крок 1:
1) i = 2;
2) x = 5; a [0] = 2; j = 1;
3) x> a [j] = 2;
3.2) a [2] = 5;
4) i = 3; i <n → п. 3;
Крок 2:
2) x = 8; a [0] = 8; j = 2;
3) x> a [j] = 5;
3.2) a [3] = 8;
4) i = 4; i <n → п. 3;
Крок 3:
2) x = 30; a [0] = 30; j = 3;
3) x> a [j] = 8;
3.2) a [4] = 30;
4) i = 5; i <n → п. 3;
Крок 4:
2) x = 32; a [0] = 32; j = 4;
3) x> a [j] = 30;
3.2) a [5] = 32;
4) i = 6; i <n → п. 3;
Крок 5:
2) x = 43; a [0] = 43; j = 5;
3) x> a [j] = 32;
3.2) a [6] = 43;
4) i = 7; i <n → п. 3;
Крок 6:
2) x = 52; a [0] = 52; j = 6;
3) x> a [j] = 43;
3.2) a [7] = 52;
4) i = 8; i ≤ n → п. 3;
Крок 7
2) x = 82; a [0] = 82; j = 7;
3) x> a [j] = 52;
3.2) a [8] = 82;
4) i = 9; i> n → кінець алгоритму.
Таким чином отримали 7 пересилань і 7 порівнянь.
Приклад сортування масиву, відсортовані в зворотному порядку.
Нехай задано такий масив з восьми елементів: (82,52,43,32,30,8,5,2).
Покрокове рішення:
Крок 1:
1) i = 2;
2) x = 52; a [0] = 52; j = 1;
3) x <a [j] = 52;
3.1) a [2] = 82; j = 0; → п. 3;
3) x = a [j];
3.2) a [1] = 52;
4) i = 3; i <n → п. 2;
Крок 2:
2) x = 43; a [0] = 43; j = 2;
3) x <a [j] = 82;
3.1) a [3] = 82; j = 1; → п. 3;
3) x <a [j] = 52;
3.1) a [2] = 52; j = 0; → п. 3;
3) x = a [j];
3.2) a [1] = 43;
4) i = 4; i <n → п. 2;
Крок 3:
2) x = 32; a [0] = 32; j = 3;
3) x <a [j] = 82;
3.1) a [4] = 82; j = 2; → п. 3;
3) x <a [j] = 52;
3.1) a [3] = 52; j = 1; → п. 3;
3) x <a [j] = 43;
3.1) a [2] = 43; j = 0; → п. 3;
3) x = a [j];
3.2) a [1] = 32;
4) i = 5; i <n → п. 2;
Крок 4:
2) x = 30; a [0] = 30; j = 4;
3) x <a [j] = 82;
3.1) a [5] = 82; j = 3; → п. 3;
3) x <a [j] = 52;
3.1) a [4] = 52; j = 2; → п. 3;
3) x <a [j] = 43;
3.1) a [3] = 43; j = 1; → п. 3;
3) x <a [j] = 32;
3.1) a [2] = 32; j = 0; → п. 3;
3) x = a [j];
3.2) a [1] = 30;
4) i = 6; i <n → п. 2;
Крок 5:
2) x = 8; a [0] = 8; j = 5;
3) x <a [j] = 82;
3.1) a [6] = 82; j = 4; → п. 3;
3) x <a [j] = 52;
3.1) a [5] = 52; j = 3; → п. 3;
3) x <a [j] = 43;
3.1) a [4] = 43; j = 2; → п. 3;
3) x <a [j] = 32;
3.1) a [3] = 32; j = 1; → п. 3;
3) x <a [j] = 30;
3.1) a [2] = 30; j = 0; → п. 3;
3) x = a [j];
3.2) a [1] = 8;
4) i = 7; i <n → п. 2;
Крок 6:
2) x = 5; a [0] = 5; j = 6;
3) x <a [j] = 82;
3.1) a [7] = 82; j = 5; → п. 3;
3) x <a [j] = 52;
3.1) a [6] = 52; j = 4; → п. 3;
3) x <a [j] = 43;
3.1) a [5] = 43; j = 3; → п. 3;
3) x <a [j] = 32;
3.1) a [4] = 32; j = 2; → п. 3;
3) x <a [j] = 30;
3.1) a [3] = 30; j = 1; → п. 3;
3) x <a [j] = 8;
3.1) a [2] = 8; j = 0; → п. 3;
3) x = a [j];
3.2) a [1] = 5;
4) i = 8; i <n → п. 2;
Крок 7:
2) x = 2; a [0] = 2; j = 7;
3) x <a [j] = 82;
3.1) a [8] = 82; j = 6; → п. 3;
3) x <a [j] = 52;
3.1) a [7] = 52; j = 5; → п. 3;
3) x <a [j] = 43;
3.1) a [6] = 43; j = 4; → п. 3;
3) x <a [j] = 32;
3.1) a [5] = 32; j = 3; → п. 3;
3) x <a [j] = 30;
3.1) a [4] = 30; j = 2; → п. 3;
3) x <a [j] = 8;
3.1) a [3] = 8; j = 1; → п. 3;
3) x <a [j] = 5;
3.1) a [2] = 5; j = 0; → п. 3;
3) x = a [j];
3.2) a [1] = 2;
4) i = 9; i> n → кінець алгоритму.
Таким чином, маємо 35 порівнянь і 35 пересилань.
3. Алгоритм покриття за методом «Побудова одного найкоротшого покриття»
3.1 Математичне опис завдання і методів її рішення
Нехай -Опорна множина. Є безліч
підмножин множини B (
). Кожному підмножині
зіставлять число
, Званої ціною. Безліч
називається рішенням задачі про покриття, або просто покриттям, якщо виконується умова
, При цьому ціна
. Термін «покриття» означає, що сукупність множин
містить всі елементи множини В, тобто «Покриває» безліч B
Безізбиточним називається покриття, якщо при видаленні з нього хоча б одного елемента воно перестає бути покриттям. Інакше - покриття надлишково.
Покриття Р називається мінімальним, якщо його ціні - Найменша серед всіх покриттів даної задачі.
Покриття Р називається найкоротшим, якщо l - найменше серед всіх покриттів даної задачі.
Зручним і наочним поданням вихідних даних і їх змін у завданню про покриття є таблиця покриттів. Таблиця покриттів - це матриця Т відносини приналежності елементів множин опорному безлічі В. Стовпці матриці зіставлені елементам множини В, рядки - елементам множини
А:
Нулі в матриці T не проставляються.
Є такі варіанти формулювання завдання про покриття:
1. Потрібно знайти всі покриття. Для вирішення завдання необхідно виконати повний перебір всіх підмножин множини А.
2. Потрібно знайти тільки беззбиткові покриття. Не існує простого і ефективного алгоритму, що не потребує побудови всіх надлишкових покриттів: добре, якщо зменшується їх кількість. (Використовується граничний перебір або розкладання по стовпцю в ТП).
Потрібно знайти одне безізбиточное покриття. Рішення завдання грунтується на скороченні таблиці.
Завдання про покриття можуть бути вирішені точно (при невеликій розмірності) або наближено (див. [2]).
Для знаходження точного рішення використовуються такі алгоритми.
1) Алгоритм повного перебору. (Заснований на методі впорядкування перебору підмножин множини А).
2) Алгоритм граничного перебору по увігнутому безлічі. (Заснований на однойменному методі скорочення перебору).
3) Алгоритм розкладання по стовпцю таблиці покриття. Заснований на методі скорочення перебору, який полягає в розгляді тільки тих рядків таблиці покриття, в яких є «1» в обраному для розкладання стовпці.
4) Алгоритм скорочення таблиці покриття. Заснований на методі побудови циклічного залишку таблиці покриття, для якого далі покриття будується методами граничного перебору або розкладання по стовпцю.
Наближене рішення задачі про покриття базується на розумінні. Якщо навіть скорочений перебір призводить до дуже трудомісткого процесу вирішення, то для отримання відповіді доводиться відмовлятися від гарантій побудови оптимального рішення (мінімального або найкоротшого); однак доцільно отримати не найгірший результат - хоча б безнадлишкових покриття, задовольняє необхідній умові. При цьому на шкоду якості можна значно спростити процес вирішення.
Для випадку побудови одного найкоротшого покриття використовується алгоритм побудови циклічного залишку таблиці покриттів і безлічі ядерних рядків.
3.2 Словесне опис алгоритму і його роботи
0) Вважаємо вихідну таблицю покриттів поточної, а безліч ядерних рядків - порожнім.
1) Знаходимо ядерні рядки, запам'ятовуємо безліч ядерних рядків. Поточну таблицю покриттів скорочуємо, викреслюючи ядерні рядка і всі стовпці, покриті ними.
2) викреслюємо антиядерні рядка.
3) викреслюємо поглинають стовпці.
4) викреслюємо поглинаються рядка.
5) Якщо в результаті виконання пунктів з 1 по 4 поточна таблиця покриттів змінилася, знову виконуємо пункт 1, інакше перетворення закінчуємо.
Тому алгоритм роботи наступний:
1) введення числа рядків і стовпців таблиці покриття;
2) введення таблиці покриття;
3) пошук ядерних рядків. Якщо їх немає, то п. 4. Інакше, запам'ятовуємо ці ядерні рядка. Шукаємо стовпці, вкриті ядерними рядками. Викреслюємо всі ядерні рядки і стовпці, покриті ними.
4) викреслення антиядерних рядків. Перехід в п. 5.
6) викреслення поглинаючих стовпців.
7) викреслення поглинаються рядків.
8) якщо в результаті перетворень таблиця покриттів змінилася, виконуємо пункт 3. Інакше - висновок безлічі покриття, кінець алгоритму.
3.3 Вибір структур даних
З аналізу задачі та її даних видно, що алгоритм повинен працювати з таблицею покриття і з деякими змінними, які представлені нижче (всі змінні цілого типу):
m - кількість рядків таблиці покриття;
n - кількість стовпців таблиці покриття;
i, j - змінні циклу по рядках і стовпцях відповідно;
S prev - попередня сума стовпця або рядка;
S curr - поточна сума стовпця або рядка.
Таблиця покриття - це двовимірна матриця. Її доцільно представити у вигляді двовимірного масиву A (m, n).
P - одномірний масив для зберігання номерів рядків, що покривають матрицю. Для зберігання номерів обраний масив, оскільки кількість рядків, хоча й невідомо заздалегідь, обмежена кількістю рядків матриці покриття (m).
3.4 Опис схеми алгоритму
Блок-схема даного алгоритму зображена на рис. 3 в Додатку.
Спочатку вводяться вихідні дані: розмірність таблиці m і n і сама таблиця покриття (блок 1). Далі відбувається пошук пустого стовпця (блок 2): це доцільно, оскільки, якщо хоча б один стовпець не покритий, то й не існує покриття цієї таблиці, і, отже, кінець алгоритму. Далі, якщо не знайдено порожнього стовпця (перевірка в блоці 3), - пошук ядерних рядків (блок 4), після - стовпців, покритих ними (блок 5). Після цього викреслюються всі стовпці і рядки, знайдені в блоках 4,5 (блок 6). Викреслюються антиядерні рядка (блок 7). Викреслюються поглинають стовпці (блок 8). Викреслюються поглинаються рядка (блок 9). Якщо в результаті виконання блоків 6-9 поточна таблиця покриттів змінилася, то виконується блок 4; інакше випливає висновок знайденого найкоротшого покриття у вигляді номерів рядків, що покривають таблицю. Потім кінець алгоритму.
3.5 Підпрограми основного алгоритму
Функція MOJNO _ LI (A) веде пошук порожніх стовпців, тобто не покриваються ні одним рядком. Блок-схема цієї функції представлена на рис. 3.1 Програми. Організовується цикл по всіх стовпцях (блоки 1-6). У кожному стовпці йде рахунок нулів (лічильник i ініціалізується в кожному проході - блок 2; рахунок ведеться в блоці 5), тобто якщо зустрічається хоча б одна одиниця (перевірка в блоці 3), то відбувається перехід у наступний стовпець. Алгоритм працює до тих пір, поки не буде досягнутий кінець таблиці (тобто кінець циклу по j, блок6) або поки не буде пораховано m нулів в одному стовпці (перевірка умови в блоці 4), тобто i = m. Функція повертає 0, якщо знайдено m нулів, і 1, якщо досягнуто кінець таблиці.
Функція YAD - STROKA (A) веде пошук ядерних рядків. У блоці 1 S ініціалізується значенням 0. Далі організовується цикл по всіх стовпцях (блок 2). Обнуляємо поточну суму (блок 4) і вважаємо суму в j-му стовпці (цикл у блоках 5-7 і власне підсумовування елементів у блоці 6). Далі порівнюємо отриману суму S з 1 (блок 8). Якщо поточна сума дорівнює 1, запам'ятовуємо її і номеру цього стовпця присвоюємо 0 (блок 9), інакше переходимо до наступного стовпцю. Таким чином, після закінчення циклу по j у змінній yad stroka (A) буде зберігатися масив ядерних рядків. Блок-схема даного алгоритму зображена на рис. 3.2 у Додатку.
Функція ANTI _ STROK (A) веде пошук антиядерних рядків. Змінної S 2 присвоюється значення 0. Організовується цикл по рядках. Шукається сума кожного рядка і якщо вона дорівнює 0, то рядок викреслюється. Якщо ні, то переходимо до наступного рядка. Блок-схема даного алгоритму зображена на рис. 3.3 у Додатку.
Процедура VICHEK (A) реалізує викреслювання стовпців, покритих ядерними рядками. Аналогічно дана процедура працює і для самих ядерних рядків, і для антиядерних рядків, поглинаючих стовпців, що поглинаються рядків. Щоб даний стовпець (рядок) «викреслити», необхідно поставити 1 на його (її) перетині з нульовою рядком (стовпчиком). Блок-схема даного алгоритму зображена на рис. 3.4 у Додатку.
Процедура VIVOD (P) реалізує висновок отриманого безлічі рядків з масиву P. Для цього організується цикл за елементами масиву Р (блоки 1-4), в якому перевіряється відзначений чи номер рядка i одиницею (блок 2). Якщо так, то виводиться номер рядка i (блок 3). Блок-схема даного алгоритму зображена на рис. 3.5 в Додатку.
3.6 Приклад роботи алгоритму
Нехай задана таблиця покриттів (див. Таб. 3). Розглянемо приклад роботи алгоритму.
1. Безліч ядерних рядків пусте.
B | B 1 | B 2 | B 3 | B 4 | B5 | B6 |
А1 | 1 | 1 | 1 | |||
А2 | 1 | 1 | 1 | |||
A3 | 1 | 1 | 1 | |||
А4 | 1 | 1 | 1 |
2. Безліч антиядерних рядків пусте.
3. Викреслюємо стовпці В1, В3, В5, В6 як поглинаючі
4. Викреслюємо рядок А2 як поглинену.
Тепер таблиця покриттів буде мати вигляд (див. Таб. 4)
Таб. 4.
В2 | В4 | |
А1 |