Реферат: Алгоритмы поиска кратчайших покрытий булевых матриц
ВВЕДЕНИЕ
Микроэлектроника является одним из наиболее быстро и эффективноразвивающихся направлений науки и техники. Однако вместе с развитиемсхемотехники увеличивается и сложность разрабатываемых схем. Существуютэлементы схемы, логической моделью которых является матрица, в частности,булева. Площадь микросхемы и ее быстродействие во многом зависят от параметровматрицы. Поэтому приоритетной задачей является уменьшение размеров элемента,например, путем нахождения кратчайшего покрытия булевых матриц.Целесообразность поиска кратчайших покрытий возникает и при минимизации ДНФбулевых функций, при синтезе логических схем некоторых типов, при решениисистем логических уравнений, при поиске простейших диагностических тестов, атак же во многих других задачах, эффективность методов решения которых,оказывается, существенно зависящей от совершенства используемых алгоритмовпоиска кратчайших покрытий.
Алгоритмы нахождения кратчайших покрытий – занятие трудоемкое длячеловека, особенно при сравнительно большой размерности матрицы, поэтомуразработанная мною программа значительно упрощает выполнение этой работы.
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.
3. АЛГОРИТМЫ ПОИСКА КРАТЧАЙШИХПОКРЫТИЙ
Ниже приведены алгоритмы нахождениякратчайших покрытий методом Патрика [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}-столбцовое покрытие исследуемой матрицы.
4. Метод предварительногоредуцирования булевой матрицы
При поиске кратчайшего покрытия целесообразно уменьшить матрицу, еслитакое возможно. Можно удалить как определенные строки, так и определенныестолбцы. Отметим, что в практических задачах не требуется найти все кратчайшиепокрытия, достаточно только одно или несколько. Это упрощает алгоритм упрощения(сокращения) матрицы.
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 5
/>.
Единственное покрытие последней матрицы – она сама. Итого, строки г и исоставляют одно из кратчайших (даже единственное) покрытий матрицы A.
5. ПРОГРАММА
Написанная мной на ЭВМ программа «Нахождение кратчайшего покрытия булевыхматриц» помогает вручную не искать покрытие заданной или генерируемой булевойматрицы до размера 99 х 99, а предоставить это компьютеру.
5.1 Описание программы
Средство программирования:
Интегрированная Среда Разработки Borland C++ Builder6.0.
Поддерживаемые операционные системы:
Windows 95/98/ME/NT/2000/XP.
Система для тестирования программы:
Pentium-4 ~2.3 Gh, 512 Mb DDR, Windows XP SP2.
5.2 Описание интерфейса
Pokrytie.exe –откомпилированная и отлаженная программа. При запуске отображается окнодополнительной информации:
/>
При нажатии двойным щелчком на кнопку «Программа» в окне появляетсяосновная форма — Меню программы (рис. 1).
/>/>
Рис.1. Меню программы Рис.2. Задание вероятности единицы
Требуется ввести число строк и столбцов матрицы, а также выбрать типсоздания требуемой матрицы: вручную или автоматически (с помощью компьютера). Впервом случае возможны 2 способа создания пустого шаблона матрицы: все поля –либо нули, либо единицы (для реализации необходимо это просто отметить). Вовтором же должна быть введена вероятность создания единицы в определенном местематрицы (рис. 2).
По умолчанию все элементы матрицы – нули и программа допускаетприсутствие в матрице нулевых строк и столбцов. Если вы не ввели параметрыматрицы до конца, то при нажатии кнопки «Сгенерировать» программа сообщит вамоб этом:
/>
При правильном вводе данных и нажатии кнопки генерации на экранепоявляется окно ввода матрицы:
/>
При написании программы я применила графический способ ввода элементовматрицы: внутри прямоугольника, соответствующего размерам матрицы, чтобыизменить значение определенного элемента матрицы, необходимо нажать кнопку мышипри положении курсора внутри определенного квадрата, соответствующего этомуэлементу. Белый цвет соответствует нулю, а цвет выделяемого текста (поумолчанию – синий) соответствует единице. Для хранения данных в программеиспользованы динамические матрицы, что позволяет выделять память только по меренеобходимости.
5.3 Результат работы программы
Рассмотрим несколько примеров, иллюстрирующих работу программы.
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++Builder6.0., которая является, на мой взгляд, наиболееподходящей для решения такого типа задач, поскольку позволяет создать наиболееудобный для пользователя интерфейс.
ЛИСТИНГ ПРОГРАММЫ
Unit1.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;
//---------------------------------------------------------------------------
__fastcallTForm1::TForm1(TComponent* Owner)
: TForm(Owner)
{
}
//---------------------------------------------------------------------------
void __fastcallTForm1::RadioButton2Click(TObject *Sender)
{
Label3->Visible=true;
MaskEdit1->Visible=true;
Edit1->Visible=true;
CheckBox1->Visible=false;
}
//---------------------------------------------------------------------------
void __fastcallTForm1::RadioButton1Click(TObject *Sender)
{
Label3->Visible=false;
MaskEdit1->Visible=false;
Edit1->Visible=false;
CheckBox1->Visible=true;
}
//---------------------------------------------------------------------------
void __fastcallTForm1::Button2Click(TObject *Sender)
{
Close();
}
//---------------------------------------------------------------------------
void __fastcallTForm1::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 __fastcallTForm1::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;
//---------------------------------------------------------------------------
__fastcallTForm2::TForm2(TComponent* Owner)
: TForm(Owner)
{
}
//---------------------------------------------------------------------------
void __fastcallTForm2::FormClose(TObject *Sender, TCloseAction &Action)
{
Form1->Close();
}
//---------------------------------------------------------------------------
void __fastcallTForm2::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 __fastcallTForm2::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 __fastcallTForm2::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 __fastcallTForm2::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 __fastcallTForm2::N5Click(TObject *Sender)
{
Form1->Close();
}
//---------------------------------------------------------------------------
void __fastcallTForm2::N4Click(TObject *Sender)
{
Form1->Visible=true;
// Form5->Visible=true;
Form2->Visible=false;
}
//---------------------------------------------------------------------------
void __fastcallTForm2::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;
Form3->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;
//---------------------------------------------------------------------------
__fastcallTForm3::TForm3(TComponent* Owner)
: TForm(Owner)
{
}
//---------------------------------------------------------------------------
void __fastcallTForm3::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 __fastcallTForm3::N3Click(TObject *Sender)
{
Form2->Visible=false;
Form3->Visible=false;
Form1->Visible=false;
}
//---------------------------------------------------------------------------
void __fastcallTForm3::N2Click(TObject *Sender)
{
Form3->Visible=false;
}
//---------------------------------------------------------------------------
void __fastcallTForm3::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;
//---------------------------------------------------------------------------
__fastcallTForm4::TForm4(TComponent* Owner)
: TForm(Owner)
{
}
//---------------------------------------------------------------------------
void __fastcallTForm4::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;
}
Unit5.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;
//---------------------------------------------------------------------------
__fastcallTForm5::TForm5(TComponent* Owner)
: TForm(Owner)
{
}
//---------------------------------------------------------------------------
void __fastcallTForm5::Button1Click(TObject *Sender)
{
Form1->Show();
Form5->Close();
}