Рефераты. Алгоритмы поиска кратчайших покрытий булевых матриц

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;

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;

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

__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;

}

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;

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

__fastcall TForm5::TForm5(TComponent* Owner)

: TForm(Owner)

{

}

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

void __fastcall TForm5::Button1Click(TObject *Sender)

{

Form1->Show();

Form5->Close();

}

Страницы: 1, 2, 3, 4



2012 © Все права защищены
При использовании материалов активная ссылка на источник обязательна.