Курсовая работа: Алгоритмы поиска кратчайших покрытий булевых матриц

 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++)

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