5.1 Описание программы
Средство программирования:
Интегрированная Среда Разработки Borland C++ Builder 6.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;
__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]++;
arr[i][j]=0;
if(CheckBox1->Checked==false)
} } } }
for(int i=0;i<b; i++)
if((arrb[i]==0 || arra[j]==0) & RadioButton2->Checked==true)
{ Application->MessageBox("Попробуйте еще раз или введите другое значение вероятности", "Внимание!");
} } }
Form1->Hide();
Form2->Show();
Form5->Visible=false;
void __fastcall TForm1::FormShow(TObject *Sender)
Form5->ShowModal();
Unit2.cpp
TForm2 *Form2;
int a, b, c, **pokr,**pokr2, q;
extern int **arr, *arra, *arrb,Flag;
__fastcall TForm2::TForm2(TComponent* Owner)
void __fastcall TForm2::FormClose(TObject *Sender, TCloseAction &Action)
Form1->Close();
void __fastcall TForm2::FormShow(TObject *Sender)
Страницы: 1, 2, 3, 4
