Алгоритми пошуку найкоротших покриттів булевих матриць

[ виправити ] текст може містити помилки, будь ласка перевіряйте перш ніж використовувати.

скачати

ВСТУП

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

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

1. ПОСТАНОВКА ЗАВДАННЯ

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

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

Якщо позначити безліч перекладачів, з якого можна робити вибір, через A = {a, б, в, г, д}, а безліч цікавлять нас мов через B = {1,2,3,4,5,6}. То можна ввести булеву матрицю C відносини перекладачів до мов.

1 2 3 4 5 6

.

Це означає, що перекладач а знає мови 1,3, перекладач б - мови 4,5 і т.д.

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

2. ОСНОВНІ ПОНЯТТЯ І ВИЗНАЧЕННЯ

Булевой матрицею називається матриця, елементи якої - або 0, або 1.

, {0, 1}.

Кажуть, що i-й рядок покриває j-й стовпець, якщо на їх перетині варто одиниця, тобто = 1. Причому кожен рядок обов'язково покриває деяка підмножина стовпців, а кожен стовпець покривається хоча б одним рядком.

Підмножина рядків матриці B, в сукупності покриває всі її стовпці, утворює рядкове покриття цієї матриці.

Підмножина стовпців матриці B, в сукупності покриває всі її рядки, утворює столбцовое покриття цієї матриці.

Покриття, що містить мінімальне число рядків (стовпців) матриці B, називається найкоротшим покриттям матриці B.

Приклад 1.

1 2 3 4 5 6 7 8 9 10

.

Безліч рядків матриці B {а, в, г, е, ж} - одне з малих покриттів цієї матриці. І багато рядків {д, е, з} - одне з найкоротших рядкових покриттів матриці B.

  1. АЛГОРИТМИ пошуку найкоротших ПОКРИТТІВ

Нижче наведені алгоритми знаходження найкоротших покриттів методом Патріка [5] і методом Закревського [1].

3.1 Метод Патріка

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

Приклад 2. Для матриці

.

розпишемо, які рядки покривають певний стовпець у вигляді диз'юнкцій.

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

Ú д) (у Ú д) (а Ú р Ú д) (б Ú в) (б Ú р Ú д) г = серпня Ú бгд Ú вгд Ú АБВГ Ú бвгд Ú абвгд.

Звідси видно, що найкоротший покриття булевої матриці С - або {а, в, г}, або {б, г, д}, або {в, г, д}.

Це перебування покриттів перебором на ЕОМ реалізується для вихідної матриці невеликого розміру (до 7 х 7), щоб реалізувати метод Патріка для трохи великих матриць, рекомендується оптимізувати матрицю.

3.2 Метод Закревського

Аркадій Дмитрович Закревський запропонував досить ефективний і простий спосіб знаходження малої величини покриття булевої матриці (так зване розкладання по мінімальному колонку і мінімальної рядку).

Зауваження: всі випадки прораховувалися як вручну, так і на ЕОМ за допомогою розробленої програми.

3.2.1 Рядкове покриття

Алгоритм знаходження рядкового покриття методом Закревського:

1. Шукається стовпець з мінімальним числом одиниць. Якщо таких декілька, то обирається будь-який (для визначеності, допустимо, самий лівий).

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

3. Видаляються всі стовпці, які покриває отриманий рядок.

Дії продовжуємо до тих пір, поки не віддалиться вся матриця.

Приклад 3. Знайдемо найкоротший рядкове покриття матриці С:

1 2 3 4 5 6

.

1. Стовпець 6 містить мінімальне число одиниць - 1.

2. Рядок г заноситься в покриття і видаляється з матриці.

3. Видаляються стовпчики 3, 5, 6.

Отримуємо матрицю

1 2 4

.

Далі проводимо аналогічні дії з матрицею С:

  1. Стовпець 1 (самий лівий) містить тільки 2 одиниці.

  2. Рядок д, що покриває цей стовпець, покриває 2 колонки, заноситься в покриття і видаляється з матриці.

  3. Видаляються стовпці 1, 2.

Залишився тільки один стовпець матриці - 4. Можна вибрати як рядок б, так і рядок в, в обох випадках ми маємо покриття матриці, що складається з 3 рядків.

Разом отримуємо покриття {б, г, д} і {в, г, д} - як показав метод Патріка - найкоротші покриття.

Зауваження: Не завжди метод Закревського дає найкоротший покриття, воно може складатися і з більшої кількості рядків, але перебуває швидше.

Столбцовое покриття

Алгоритм знаходження столбцового покриття методом Закревського:

1. Шукається рядок з мінімальним числом одиниць. Якщо таких декілька, то обирається будь-яка (для визначеності, допустимо, сама верхня).

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

3. Видаляються всі рядки, які покриває отриманий стовпець.

Дані дії тривають до тих пір, поки не віддалиться вся матриця.

Разом отримаємо покриття {3,4}-столбцовое покриття досліджуваної матриці.

  1. Метод попереднього редукування булевої матриці

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

1. Кажуть, що i-й рядок булевої матриці поглинає j-й рядок цієї матриці ( ), Якщо на позиціях одиниць j-го рядка в i-й - теж «одиниці», причому число одиниць у i-му рядку більше числа одиниць в j-му рядку (якщо ж число одиниць однаково, то дані рядка називаються рівними).

Аналогічне твердження можна сформувати і для стовпців.

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

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

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

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

Приклад 4. Нехай дана булева матриця A (10 х 10):

1 2 3 4 5 6 7 8 9 10

.

Видаляємо рядки б і е (поглинаються рядком к), рядки в, д, ж (поглинаються рядком і) і рядок з "(поглинається рядком г). Отримаємо матрицю , Вже меншу за розмірами:

1 2 3 4 5 6 7 8 9 10

.

Видаляємо стовпець 1 (поглинає будь-який інший стовпець), стовпці 2, 8 і 10 (поглинають стовпець 4), стовпчики 3 та 7 (рівні стовпцю 9) і стовпець 6 (дорівнює стовпцю 4). У результаті отримуємо матрицю (4 х 3):

4 5 9

.

Видаляємо рядка а, к (поглинаються рядком г). Отримуємо матрицю (2 х 3):

4 5 9

.

З останньої матриці видаляємо стовпець 9 (дорівнює стовпцю 5) і отримуємо не спрощуємо матрицю (2 х 2):

4 Травня

.

Єдине покриття останньої матриці - вона сама. Разом, рядки г і і становлять одну з найкоротших (навіть єдине) покриттів матриці A.

  1. ПРОГРАМА

Написана мною на ЕОМ програма «Знаходження найкоротшого покриття булевих матриць» допомагає вручну не шукати покриття заданої або генерується булевої матриці до розміру 99 х 99, а надати це комп'ютера.

5.1 Опис програми

Засіб програмування:

Інтегрована середу Розробки Borland C + + Builder 6.0.

Операційні системи:

Windows 95/98 / ME / NT / 2000 / XP.

Система для тестування програми:

Pentium -4 ~ 2.3 Gh, 512 Mb DDR, Windows XP SP 2.

5.2 Опис інтерфейсу

Pokrytie. Exe - відкомпілювати і налагоджена програма. При запуску відображається вікно додаткової інформації:


При натисканні подвійним клацанням на кнопку «Програма» у вікні з'являється основна форма - Меню програми (рис. 1).


Рис.1. Меню програми Рис.2. Завдання ймовірності одиниці

Потрібно вказати число рядків і стовпців матриці, а також вибрати тип створення необхідної матриці: вручну або автоматично (за допомогою комп'ютера). У першому випадку можливі 2 способи створення порожнього шаблону матриці: всі поля - або нулі, або одиниці (для реалізації необхідно це просто відзначити). У другому ж повинна бути введена вірогідність створення одиниці в певному місці матриці (рис. 2).

За замовчуванням всі елементи матриці - нулі і програма допускає присутність в матриці нульових рядків і стовпців. Якщо ви не ввели параметри матриці до кінця, то при натисканні кнопки «Згенерувати» програма повідомить вам про це:

При правильному введенні даних і натискання кнопки генерації на екрані з'являється вікно введення матриці:

При написанні програми я застосувала графічний спосіб введення елементів матриці: усередині прямокутника, відповідного розмірами матриці, щоб змінити значення певного елемента матриці, необхідно натиснути кнопку миші при положенні курсору всередині певного квадрата, відповідного цьому елементу. Білий колір відповідає нулю, а колір виділяється тексту (за замовчуванням - синій) відповідає одиниці. Для зберігання даних у програмі використані динамічні матриці, що дозволяє виділяти пам'ять тільки в міру необхідності.

    1. Результат роботи програми

Розглянемо кілька прикладів, які ілюструють роботу програми.

5.3.1 Приклад 1. Нехай дана матриця С:

1 2 3 4 5 6

.

Побудуємо для цієї матриці найкоротші покриття методами Патріка і Закревського (рядкове і столбцовое).

Матриця C в програмі:


Покриття методом Патріка:


Покриття методом Закревського


Разом, покриття, побудовані програмою, збігаються з покриттями, побудованими вручну.

5.3.2 Приклад 2. Побудуємо найкоротший покриття для довільної матриці розміром 7 × 7 з щільністю одиниці 0,2 методом Патріка і методом Закревського:

Матриця, що згенерована програмою:


Покриття методом Патріка


Покриття методом Закревського


5.3.3 Приклад 3. Побудуємо найкоротший покриття для довільної матриці розміром 30 × 30 з щільністю одиниці 0,3 методом Закревського

Матриця, що згенерована програмою


Покриття, побудовані програмою:

6. Довжина покриття

Довжина покриття булевої матриці - це кількість рядків (стовпців), що утворюють покриття цієї матриці.

За допомогою створеної програми можна простежити залежність довжини покриття матриці (L) від густини одиниці (P) в ній.

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

Видно, що при досить малих розмірностях матриці, всього 7 × 7, середня довжина покриття майже збігається.

Побудуємо графік для методу Закревського для матриць 10 × 10, для цього зробимо 20 спроб на кожне значення ймовірності:

ВИСНОВОК

В результаті виконання курсової роботи мною була розроблена і налагоджена програма, що дозволяє знаходити найкоротші покриття булевих матриць розміром до 100 × 100 методом Патріка (див. розділ 3.1) і методом Закревського (столбцовое і рядкове покриття) (див. розділ 3.2), а так само розглянуто спосіб оптимізації (скорочення) булевих матриць (див. розділ 3.3).

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

Дані алгоритми реалізовані в інтегрованому середовищі C + + Builder 6.0., Яка є, на мій погляд, найбільш підходящою для вирішення такого типу завдань, оскільки дозволяє створити найбільш зручний для користувача інтерфейс.

Лістинг програм

Unit 1. Cpp

# Include <vcl. H>

# Include <stdlib.h>

# Pragma hdrstop

# Include "Unit5.h"

# Include "Unit4.h"

# Include "Unit3.h"

# Include "Unit2.h"

# Include "Unit1.h"

//------------------------------------------------ ---------------------------

# Pragma package (smart_init)

# Pragma resource "*. dfm"

TForm1 * Form1;

extern int a, b, c;

int ** arr, * arra, * arrb, Flag = 0;

//------------------------------------------------ ---------------------------

__fastcall TForm1:: TForm1 (TComponent * Owner)

: TForm (Owner)

{

}

//------------------------------------------------ ---------------------------

void __fastcall TForm1:: RadioButton2Click (TObject * Sender)

{

Label3-> Visible = true;

MaskEdit1-> Visible = true;

Edit1-> Visible = true;

CheckBox1-> Visible = false;

}

//------------------------------------------------ ---------------------------

void __fastcall TForm1:: RadioButton1Click (TObject * Sender)

{

Label3-> Visible = false;

MaskEdit1-> Visible = false;

Edit1-> Visible = false;

CheckBox1-> Visible = true;

}

//------------------------------------------------ ---------------------------

void __fastcall TForm1:: Button2Click (TObject * Sender)

{

Close ();

}

//------------------------------------------------ ---------------------------

void __fastcall TForm1:: Button1Click (TObject * Sender)

{

a = StrToInt (MaskEdit2-> EditText);

b = StrToInt (MaskEdit3-> EditText);

if (a * b == 0 | | (RadioButton2-> Checked == true & & MaskEdit1-> EditText == "0"))

{

Application -> MessageBox ("Введіть дані до кінця або перевірте дані", Увага! ");

Abort ();

}

if (RadioButton2-> Checked)

c = StrToInt (MaskEdit1-> EditText);

else

c = 0;

arr = new int * [b];

arra = new int [a];

arrb = new int [b];

for (int i = 0; i <a; i + +)

arra [i] = 0;

for (int i = 0; i <b; i + +)

{

arrb [i] = 0;

arr [i] = new int [a];

for (int j = 0; j <a; j + +)

{

if (c> 0)

if (random (10) <= c)

{

arr [i] [j] = 1;

arrb [i] + +;

arra [j] + +;

}

else

arr [i] [j] = 0;

else

{

if (CheckBox1-> Checked == false)

arr [i] [j] = 0;

else

{

arr [i] [j] = 1;

arrb [i] + +;

arra [j] + +;

}}}}

for (int i = 0; i <b; i + +)

{

for (int j = 0; j <a; j + +)

{

if ((arrb [i] == 0 | | arra [j] == 0) & RadioButton2-> Checked == true)

{Application-> MessageBox ("Спробуйте ще раз або введіть інше значення ймовірності", "Увага!");

Abort ();

}}}

Form1-> Hide ();

Form2-> Show ();

Form5-> Visible = false;

}

//------------------------------------------------ ---------------------------

void __fastcall TForm1:: FormShow (TObject * Sender)

{

Form5-> ShowModal ();

}

//------------------------------------------------ ---------------------------

Unit2.cpp

# Include <vcl.h>

# Pragma hdrstop

# Include "Unit5.h"

# Include "Unit4.h"

# Include "Unit3.h"

# Include "Unit2.h"

# Include "Unit1.h"

//------------------------------------------------ ---------------------------

# Pragma package (smart_init)

# Pragma resource "*. dfm"

TForm2 * Form2;

int a, b, c, ** pokr, ** pokr2, q;

extern int ** arr, * arra, * arrb, Flag;

//------------------------------------------------ ---------------------------

__fastcall TForm2:: TForm2 (TComponent * Owner)

: TForm (Owner)

{

}

//------------------------------------------------ ---------------------------

void __fastcall TForm2:: FormClose (TObject * Sender, TCloseAction & Action)

{

Form1-> Close ();

}

//------------------------------------------------ ---------------------------

void __fastcall TForm2:: FormShow (TObject * Sender)

{

Image1-> Width = 10 * a;

Image1-> Height = 10 * b;

for (int i = 0; i <b; i + +)

{

Image1-> Canvas-> MoveTo (0, i * Image1-> Height / b);

Image1-> Canvas-> LineTo (Image1-> Width, i * Image1-> Height / b);

}

for (int j = 0; j <a; j + +)

{

Image1-> Canvas-> MoveTo (j * Image1-> Width / a, 0);

Image1-> Canvas-> LineTo (j * Image1-> Width / a, Image1-> Height);

}

if (c> 0 | | c == 0 & & arr [0] [0] == 1)

{

Image1-> Canvas-> Brush-> Color = clActiveCaption;

for (int i = 0; i <b; i + +)

{

for (int j = 0; j <a; j + +)

{

if (arr [i] [j] == 1)

Image1-> Canvas-> FillRect (Rect (10 * j +1,10 * i +1,10 * j +10,10 * i +10));

}}}}

//------------------------------------------------ ---------------------------

void __fastcall TForm2:: N1Click (TObject * Sender)

{

int * arra_copy, * arrb_copy, ** arr_copy;

int min, * pokr_d, * counter1, * counter2, ** pokr1, t = 0, res = 1;

arr_copy = new int * [b];

arra_copy = new int [a];

arrb_copy = new int [b];

for (int i = 0; i <a; i + +)

arra_copy [i] = arra [i];

for (int i = 0; i <b; i + +)

{

arrb_copy [i] = arrb [i];

arr_copy [i] = new int [a];

for (int j = 0; j <a; j + +)

arr_copy [i] [j] = arr [i] [j];

}

for (int i = 0; i <b; i + +)

{

for (int j = 0; j <a; j + +)

{

if (arrb_copy [i] == 0 | | arra_copy [j] == 0)

{

Application -> MessageBox ("Занадто маленьке значення ймовірності", "Помилка");

Abort ();}}}

if (a * b> 36)

{

for (int i = 0; i <b; i + +)

{

if (arrb_copy [i]> 0)

{

for (int temp, j = i +1; j <b; j + +)

{

if (arrb_copy [j]> 0 & & arrb_copy [i]> 0)

{

int z;

temp = 0;

for (int k = 0; k <a; k + +)

if (arr_copy [i] [k] == 1 & arr_copy [j] [k] == 1)

temp + +;

if (arrb_copy [i]> = arrb_copy [j])

z = j;

else

z = i;

if (temp == arrb_copy [z])

{

for (int k = 0; k <a; k + +)

{

if (arr_copy [z] [k] == 1)

arra_copy [k] -;

arr_copy [z] [k] = 0;

}

arrb_copy [z] = 0;

}}}}}

for (int i = 0; i <a; i + +)

{

if (arra_copy [i]> 0)

{

for (int temp, j = i +1; j <a; j + +)

{

if (arra_copy [j]> 0)

{

int z;

temp = 0;

for (int k = 0; k <b; k + +)

if (arr_copy [k] [i] == 1 & arr_copy [k] [j] == 1)

temp + +;

if (arra_copy [i]> = arra_copy [j])

z = i;

else

z = j;

if (temp == arra_copy [z])

{

for (int k = 0; k <b; k + +)

{

if (arr_copy [k] [z] == 1)

arrb_copy [k] -;

arr_copy [k] [z] = 0;

}

arra_copy [z] = 0;

}}}}}

}

counter1 = new int [a];

counter2 = new int [a];

for (int i = 0; i <a; i + +)

{

if (arra_copy [i]> 0)

{

res *= arra_copy [i];

if (arra_copy> 0)

counter2 [i] = 1;

else

counter2 [i] = 0;

}

}

pokr1 = new int * [res];

for (int i = 0; i <res; i + +)

{

pokr1 [i] = new int [b];

for (int j = 0; j <b; j + +)

pokr1 [i] [j] = 0;

}

for (;;)

{

for (int i = 0; i <a; i + +)

{

counter1 [i] = counter2 [i];

if (arra_copy [i]> 0)

{

for (int j = 0; j <b; j + +)

{

if (arr_copy [j] [i] == 1)

{

if (counter1 [i]> 1)

{

counter1 [i] -;

continue;

}

pokr1 [t] [j] = 1;

break;

}}}}

counter2 [0] + +;

for (int i = 0; i <(a-1); i + +)

{

if (counter2 [i]> arra_copy [i] & & counter2 [a-1] <= arra_copy [a-1])

{

counter2 [i] = 0;

counter2 [i +1] + +;

}

}

if (counter2 [a-1]> arra_copy [a-1])

break;

t + +;

if (t == res)

break;

}

delete [] arr_copy;

delete [] arra_copy;

delete [] arrb_copy;

delete [] counter1;

delete [] counter2;

pokr_d = new int [res];

for (int i = 0; i <res; i + +)

{

pokr_d [i] = 0;

for (int j = 0; j <b; j + +)

if (pokr1 [i] [j] == 1)

pokr_d [i] + +;

}

min = pokr_d [0];

for (int i = 1; i <res; i + +)

if (pokr_d [i] <min && pokr_d[i]> 0)

min = pokr_d [i];

q = res;

for (int i = 0; i <res; i + +)

{

if (pokr_d [i]> min)

{

q -;

for (int j = 0; j <b; j + +)

pokr1 [i] [j] = 0;

pokr_d [i] = 0;

}

}

for (int i = 0; i <res; i + +)

{

if (pokr_d [i]! = 0)

{

for (int temp, j = i +1; j <res; j + +)

{

temp = 0;

for (int k = 0; k <b; k + +)

{

if (pokr1 [i] [k] == pokr1 [j] [k])

temp + +;

}

if (temp == b)

{

q -;

pokr_d [j] = 0;

for (int k = 0; k <b; k + +)

pokr1 [j] [k] = 0;

}}}}

pokr = new int * [q];

for (int i = 0; i <q; i + +)

pokr [i] = new int [b];

for (int i = 0, j = 0; i <res; i + +)

{

if (pokr_d [i]> 0)

{

for (int k = 0; k <b; k + +)

pokr [j] [k] = pokr1 [i] [k];

j + +;

}}

delete [] pokr1;

Flag = 0;

Form3-> Caption = "Метод Патріка ";

Form3-> Show ();

}

//------------------------------------------------ ---------------------------

void __fastcall TForm2:: N3Click (TObject * Sender) / / Рядковий

{

for (int i = 0; i <b; i + +)

{

for (int j = 0; j <a; j + +)

{

if (arrb [i] == 0 | | arra [j] == 0)

{Application -> MessageBox ("Неправильно ввели матрицю! \ N Будь ласка, перевірте початкові дані", "Увага!");

Abort ();

}}}

int x, y, res, * str, * stb, str_max, stb_min;

res = 1;

q = 1;

pokr = new int * [res];

pokr [0] = new int [b];

str = new int [b];

stb = new int [a];

for (int i = 0; i <b; i + +)

{

pokr [0] [i] = 0;

str [i] = arrb [i];

}

for (int i = 0; i <a; i + +)

{

stb [i] = arra [i];

}

for (;;)

{

for (int i = 0; i <a; i + +)

{

if (stb [i]> 0)

{

stb_min = stb [i];

break;

}}

for (int i = 0; i <a; i + +)

if (stb [i] <stb_min & & stb [i]! = 0)

stb_min = stb [i];

for (int i = 0; i <a; i + +)

{

if (stb [i] == stb_min)

{

x = i;

break;

}}

for (int i = 0, j = 0; i <b; i + +)

{

if (arr [i] [x] == 1)

{

if (j == 0)

{

str_max = str [i];

j + +;

}

if (str [i]> str_max)

str_max = str [i];

}}

for (int i = 0; i <b; i + +)

{

if (str [i] == str_max & & arr [i] [x] == 1)

{

y = i;

pokr [0] [y] = 1;

str [y] = 0;

for (int j = 0; j <a; j + +)

{

if (arr [y] [j] == 1)

{

stb [j] = 0;

for (int k = 0; k <b; k + +)

if (arr [k] [j] == 1 & & k! = y)

str [k] -;

}}

break;

}}

int z = 0;

for (int i = 0; i <a; i + +)

z + = stb [i];

if (z == 0)

break;

}

delete [] str;

delete [] stb;

int x1, y1, res1, * str1, * stb1, str_min1, stb_max1; / / Столбцовий

res1 = 1;

q = 1;

pokr2 = new int * [res1];

pokr2 [0] = new int [b];

str1 = new int [a];

stb1 = new int [b];

for (int i = 0; i <a; i + +)

{

pokr2 [0] [i] = 0;

str1 [i] = arra [i];

}

for (int i = 0; i <b; i + +)

{

stb1 [i] = arrb [i];

}

for (;;)

{

for (int i = 0; i <b; i + +)

{

if (stb1 [i]> 0)

{

str_min1 = stb1 [i];

break;

}}

for (int i = 0; i <b; i + +)

if (stb1 [i] <str_min1 & & stb1 [i]! = 0)

str_min1 = stb1 [i];

for (int i = 0; i <b; i + +)

{

if (stb1 [i] == str_min1)

{

x = i;

break;

}}

for (int i = 0, j = 0; i <a; i + +)

{

if (arr [x] [i] == 1)

{

if (j == 0)

{

stb_max1 = str1 [i];

j + +;

}

if (str1 [i]> stb_max1)

stb_max1 = str1 [i];

}}

for (int i = 0; i <a; i + +)

{

if (str1 [i] == stb_max1 & & arr [x] [i] == 1)

{

y = i;

pokr2 [0] [y] = 1;

str1 [y] = 0;

for (int j = 0; j <b; j + +)

{

if (arr [j] [y] == 1)

{

stb1 [j] = 0;

for (int k = 0; k <a; k + +)

if (arr [j] [k] == 1 & & k! = y)

str1 [k] -;

}}

break;

}}

int z = 0;

for (int i = 0; i <b; i + +)

z + = stb1 [i];

if (z == 0)

break;

}

Flag = 1;

Form3-> Caption = "Метод Закревського ";

Form3-> Show ();

}

//------------------------------------------------ ---------------------------

void __fastcall TForm2:: Image1MouseDown (TObject * Sender,

TMouseButton Button, TShiftState Shift, int X, int Y)

{

if (c == 0)

{

X = X/10 * 10;

Y = Y/10 * 10;

if (Image1-> Canvas-> Pixels [X +5] [Y +5] == clWhite)

{

arr [Y/10] [X/10] = 1;

arra [X/10] + +;

arrb [Y/10] + +;

Image1-> Canvas-> Brush-> Color = clActiveCaption;

}

else

{

arr [Y/10] [X/10] = 0;

arra [X/10] -;

arrb [Y/10] -;

Image1-> Canvas-> Brush-> Color = clWhite;

}

Image1-> Canvas-> FillRect (Rect (X +1, Y +1, X +10, Y +10));

}}

//------------------------------------------------ ---------------------------

void __fastcall TForm2:: N5Click (TObject * Sender)

{

Form1-> Close ();

}

//------------------------------------------------ ---------------------------

void __fastcall TForm2:: N4Click (TObject * Sender)

{

Form1-> Visible = true;

/ / Form5-> Visible = true;

Form2-> Visible = false;

}

//------------------------------------------------ ---------------------------

void __fastcall TForm2:: N6Click (TObject * Sender)

{

for (int i = 0; i <b; i + +)

{

for (int j = 0; j <a; j + +)

{

if (arrb [i] == 0 | | arra [j] == 0)

{Application -> MessageBox ("Неправильно ввели матрицю! \ N Будь ласка, перевірте початкові дані", "Помилка!");

Abort ();

}}}

int x, y, res, * str, * stb, str_max, stb_min;

res = 1;

q = 1;

pokr = new int * [res];

pokr [0] = new int [b];

str = new int [b];

stb = new int [a];

for (int i = 0; i <b; i + +)

{

pokr [0] [i] = 0;

str [i] = arrb [i];

}

for (int i = 0; i <a; i + +)

{

stb [i] = arra [i];

}

for (;;)

{

for (int i = 0; i <a; i + +)

{

if (stb [i]> 0)

{

stb_min = stb [i];

break;

}}

for (int i = 0; i <a; i + +)

if (stb [i] <stb_min & & stb [i]! = 0)

stb_min = stb [i];

for (int i = 0; i <a; i + +)

{

if (stb [i] == stb_min)

{

x = i;

break;

}}

for (int i = 0, j = 0; i <b; i + +)

{

if (arr [i] [x] == 1)

{

if (j == 0)

{

str_max = str [i];

j + +;

}

if (str [i]> str_max)

str_max = str [i];

}}

for (int i = 0; i <b; i + +)

{

if (str [i] == str_max & & arr [i] [x] == 1)

{

y = i;

pokr [0] [y] = 1;

str [y] = 0;

for (int j = 0; j <a; j + +)

{

if (arr [y] [j] == 1)

{

stb [j] = 0;

for (int k = 0; k <b; k + +)

if (arr [k] [j] == 1 & & k! = y)

str [k] -;

}

}

break;

}}

int z = 0;

for (int i = 0; i <a; i + +)

z + = stb [i];

if (z == 0)

break;

}

delete [] str;

delete [] stb;

int x1, y1, res1, * str1, * stb1, str_min1, stb_max1;

q = 1;

pokr2 = new int * [res1];

pokr2 [0] = new int [b];

str1 = new int [a];

stb1 = new int [b];

for (int i = 0; i <a; i + +)

{

pokr2 [0] [i] = 0;

str1 [i] = arra [i];

}

for (int i = 0; i <b; i + +)

{

stb1 [i] = arrb [i];

}

for (;;)

{

for (int i = 0; i <b; i + +)

{

if (stb1 [i]> 0)

{

str_min1 = stb1 [i];

break;

}}

for (int i = 0; i <b; i + +)

if (stb1 [i] <str_min1 & & stb1 [i]! = 0)

str_min1 = stb1 [i];

for (int i = 0; i <b; i + +)

{

if (stb1 [i] == str_min1)

{

x = i;

break;

}}

for (int i = 0, j = 0; i <a; i + +)

{

if (arr [x] [i] == 1)

{

if (j == 0)

{

stb_max1 = str1 [i];

j + +;

}

if (str1 [i]> stb_max1)

stb_max1 = str1 [i];

}}

for (int i = 0; i <a; i + +)

{

if (str1 [i] == stb_max1 & & arr [x] [i] == 1)

{

y = i;

pokr2 [0] [y] = 1;

str1 [y] = 0;

for (int j = 0; j <b; j + +)

{

if (arr [j] [y] == 1)

{

stb1 [j] = 0;

for (int k = 0; k <a; k + +)

if (arr [j] [k] == 1 & & k! = y)

str1 [k] -;

}}

break;

}}

int z = 0;

for (int i = 0; i <b; i + +)

z + = stb1 [i];

if (z == 0)

break;

}

Flag = 1;

Form 3 -> Caption = "Метод попереднього редукування";

Form3-> Show ();

}

//------------------------------------------------ ---------------------------

Unit3.cpp

//------------------------------------------------ ---------------------------

# Include <vcl.h>

# Pragma hdrstop

# Include "Unit5.h"

# Include "Unit4.h"

# Include "Unit3.h"

# Include "Unit2.h"

# Include "Unit1.h"

//------------------------------------------------ ---------------------------

# Pragma package (smart_init)

# Pragma resource "*. dfm"

TForm3 * Form3;

extern int b, a, q, ** pokr, ** pokr2, ** arr, Flag;

int wert = 0, wert2 = 0;

//------------------------------------------------ ---------------------------

__fastcall TForm3:: TForm3 (TComponent * Owner)

: TForm (Owner)

{

}

//------------------------------------------------ ---------------------------

void __fastcall TForm3:: FormShow (TObject * Sender)

{

Image1-> Hide ();

q = 1;

Image1-> Width = 10 * q;

Image1-> Height = 10 * b;

for (int i = 0; i <b; i + +)

{

Image1-> Canvas-> MoveTo (0, i * Image1-> Height / b);

Image1-> Canvas-> LineTo (Image1-> Width, i * Image1-> Height / b);

}

for (int j = 0; j <q; j + +)

{

Image1-> Canvas-> MoveTo (j * Image1-> Width / q, 0);

Image1-> Canvas-> LineTo (j * Image1-> Width / q, Image1-> Height);

}

/ / Image1-> Canvas-> Brush-> Color = clActiveCaption;

for (int i = 0; i <q; i + +)

{

for (int j = 0; j <b; j + +)

{

if (pokr [i] [j] == 1)

{

Image1-> Canvas-> Brush-> Color = clActiveCaption;

wert + +;

}

else

Image1-> Canvas-> Brush-> Color = clWhite;

Image1-> Canvas-> FillRect (Rect (10 * i +1,10 * j +1,10 * i +10,10 * j +10));

}

}

Image2-> Hide ();

Label4-> Caption = IntToStr (wert);

Label6-> Caption = IntToStr (wert2);

Image1-> Show ();

wert = 0;

wert2 = 0;

if (Flag == 1)

{

Image2-> Show ();

Image2-> Width = 10 * a;

Image2-> Height = 10 * q;

for (int i = 0; i <b; i + +)

{

Image2-> Canvas-> MoveTo (0, i * Image2-> Height / q);

Image2-> Canvas-> LineTo (Image2-> Width, i * Image2-> Height / q);

}

for (int j = 0; j <a; j + +)

{

Image2-> Canvas-> MoveTo (j * Image2-> Width / a, 0);

Image2-> Canvas-> LineTo (j * Image2-> Width / a, Image2-> Height);

}

/ / Image2-> Canvas-> Brush-> Color = clActiveCaption;

for (int i = 0; i <q; i + +)

{

for (int j = 0; j <a; j + +)

{

if (pokr2 [i] [j] == 1)

{

Image2-> Canvas-> Brush-> Color = clActiveCaption;

wert2 + +;

}

else

Image2-> Canvas-> Brush-> Color = clWhite;

Image2-> Canvas-> FillRect (Rect (10 * j +1,10 * i +1,10 * j +10,10 * i +10));

}

}

Label6-> Caption = IntToStr (wert2);

wert2 = 0;

}

delete [] pokr;

delete [] pokr2;

}

//------------------------------------------------ ---------------------------

void __fastcall TForm3:: N3Click (TObject * Sender)

{

Form2-> Visible = false;

Form3-> Visible = false;

Form1-> Visible = false;

}

//------------------------------------------------ ---------------------------

void __fastcall TForm3:: N2Click (TObject * Sender)

{

Form3-> Visible = false;

}

//------------------------------------------------ ---------------------------

void __fastcall TForm3:: N1Click (TObject * Sender)

{

Form1-> Show ();

}

//------------------------------------------------ ---------------------------

Unit4.cpp

# Include <vcl.h>

# Pragma hdrstop

# Include "Unit5.h"

# Include "Unit4.h"

# Include "Unit3.h"

# Include "Unit2.h"

# Include "Unit1.h"

//------------------------------------------------ ---------------------------

# Pragma package (smart_init)

# Pragma resource "*. dfm"

TForm4 * Form4;

extern int b, a, q, ** pokr, ** pokr2, ** arr, Flag;

//------------------------------------------------ ---------------------------

__fastcall TForm4:: TForm4 (TComponent * Owner)

: TForm (Owner)

{

}

//------------------------------------------------ ---------------------------

void __fastcall TForm4:: FormShow (TObject * Sender)

{

Image1-> Width = 10 * q;

Image1-> Height = 10 * b;

for (int i = 0; i <b; i + +)

{

Image1-> Canvas-> MoveTo (0, i * Image1-> Height / b);

Image1-> Canvas-> LineTo (Image1-> Width, i * Image1-> Height / b);

}

for (int j = 0; j <q; j + +)

{

Image1-> Canvas-> MoveTo (j * Image1-> Width / q, 0);

Image1-> Canvas-> LineTo (j * Image1-> Width / q, Image1-> Height);

}

Image1-> Canvas-> Brush-> Color = clActiveCaption;

for (int i = 0; i <q; i + +)

{

for (int j = 0; j <b; j + +)

{

if (pokr [i] [j] == 1)

Image1-> Canvas-> FillRect (Rect (10 * i +1,10 * j +1,10 * i +10,10 * j +10));

}}

delete [] pokr;

}

Unit 5. Cpp

# Include <vcl.h>

# Pragma hdrstop

# Include "Unit5.h"

# Include "Unit4.h"

# Include "Unit3.h"

# Include "Unit2.h"

# Include "Unit1.h"

//------------------------------------------------ ---------------------------

# Pragma package (smart_init)

# Pragma resource "*. dfm"

TForm5 * Form5;

//------------------------------------------------ ---------------------------

__fastcall TForm5:: TForm5 (TComponent * Owner)

: TForm (Owner)

{

}

//------------------------------------------------ ---------------------------

void __fastcall TForm5:: Button1Click (TObject * Sender)

{

Form1-> Show ();

Form5-> Close ();

}

41


Додати в блог або на сайт

Цей текст може містити помилки.

Програмування, комп'ютери, інформатика і кібернетика | Курсова
107.6кб. | скачати


Схожі роботи:
Алгоритми сортування пошуку найкоротшого шляху в графі та пошуку покриття близького до найкоротшому
Алгоритми сортування пошуку найдовшого шляху в зваженому графі та пошуку покриття близького до найкоротшому
Алгоритми пошуку підрядка в рядку 2
Алгоритми пошуку підрядка в рядку
Алгоритми пошуку підрядка в рядку 2 лютого
Алгоритми пошуку кістяка Прима та Крускала
Системи булевих функцій
Мінімальні форми булевих многочленів
Повні системи булевих функцій
© Усі права захищені
написати до нас