Минимальное покрытие

Размещено на http://www.allbest.ru/

УРАЛЬСКИЙ ГОСУДАРСТВЕННЫЙ ГОРНЫЙ УНИВЕРСИТЕТ

КАФЕДРА ИНФОРМАТИКИ

КУРСОВАЯ РАБОТА

по программированию

МИНИМАЛЬНОЕ ПОКРЫТИЕ

Студент: Ростовщиков Н.В.

гр. АСУ - 09 - 2

алгоритмический язык: С#

среда разработки: Microsoft Visual Studio 2010

Преподаватель: доц. Дружинин А.В.

Екатеринбург 2010



Оглавление

1. Постановка задачи

2. Визуализация

3. Пример работы программы

4. Листинг

Литература

1. Постановка задачи

минимальный покрытие таблица алгоритм

Требуется расчитать минимальное покрытие для заданной таблицы, который можно редактировать с рабочей формы

2. Визуализация

В программе реализован алгоритм вершинного покрытия. Пользователь может изменят размеры таблицы. На форме две кнопки: "определить минимальное покрытие" - соответственно после нажатия определит минимальное покрытие, результат будет выведен в соседней таблице. Кнопка "перемешать" заполняет исходную таблицу случайными значениями.

3. Примеры работы программы

Все действия с программой производятся в одном окне, представленном ниже:

4. Листинг

using System;

using System.Collections.Generic;

using System.ComponentModel;

using System.Data;

using System.Drawing;

using System.Linq;

using System.Text;

using System.Windows.Forms;

namespace _2

{

public partial class Form1 : Form

{

public Form1()

{

InitializeComponent();

}

private void button1_Click(object sender, EventArgs e)

{

// очищаем таблицу 1

dataGridView1.Rows.Clear();

// делаем невидимыми все столбцы таблицы 1

for (int i = 0; i < numericUpDown2.Maximum; i++)

dataGridView1.Columns[i].Visible = false;

// добавляем соответствующее количество строк

for (int i = 0; i < numericUpDown1.Value; i++)

dataGridView1.Rows.Add(numericUpDown1.Value);

// делаем видимыми соответствующее количество столбцов

for (int i = 0; i < numericUpDown2.Value; i++)

dataGridView1.Columns[i].Visible = true;

Random rnd = new Random(); // переменная для случайного задания элементов таблицы

// пробегаем по всем строкам таблицы 1

foreach (DataGridViewRow row in dataGridView1.Rows)

{

// задаём номер строки в столбце названий

row.HeaderCell.Value = (row.Index + 1).ToString();

// пробегаем по каждой ячейке в строке

foreach (DataGridViewCell cell in row.Cells)

// и задаём значение ячейки

cell.Value = rnd.Next() % 2; // это операция 'остаток от деления на 2' - соответственно 0 или 1

}

}

private void button2_Click(object sender, EventArgs e)

{

int i, j; // счётчики циклов

int coverCount; // количество строк, покрывающих таблицу

int [] Cover = new int [dataGridView1.RowCount]; // массив с номерами строк, составляющих мин. покрытие

int isFind; // признак того, что данный столбец уже покрыт

//unsigned long *table = new unsigned long [StringGrid1->RowCount];

//for (j=0; j<StringGrid1->RowCount; j++) {

// table[j] = 0;

// for (i=1; i<StringGrid1->ColCount; i++) {

// table[j] <<= 1;

// if (StringGrid1->Cells[i][j] == '1') {

// table[j] += 1;

// }

//}

//}

//Cover = new int [StringGrid1->RowCount]; // выделение памяти для массива номеров строк

coverCount = 0;

// цикл начинается с 1, поскольку 0-й столбец содержит названия строк

for (i = 0; i < numericUpDown2.Value; i++)

{

// сначала производится проверка, покрыт ли i-й столбец

isFind = 0;

// поиск осуществляется среди отобранных строк

for (j = 0; j < coverCount; j++)

{

// если в списке отобранных строк уже содержится i-й столбец,

if (dataGridView1[i, Cover[j]].Value.ToString() == "1")

{

// то устанавливаем соответствующий признак

isFind = 1;

// и выходим из цикла for (j...

break;

}

}

// если же среди отобранных строк нет покрытия текущего i-го столбца

if (isFind == 0)

{

// то пробегаем по всем строкам

for (j = 0; j < numericUpDown1.Value; j++)

{

// и если на пересечении i-го столбца и j-й строки стоит 1,

if (dataGridView1[i, j].Value.ToString() == "1")

{

// то заносим текущую j-ю строку в список Cover

Cover[coverCount] = j;

// и увеличиваем счётчик

coverCount++;

break;

}

}

}

}

// очищаем таблицу 2

dataGridView2.Rows.Clear();

// добавляем соответствующее количество строк

for (i = 0; i < coverCount; i++)

dataGridView2.Rows.Add("");

// делаем невидимыми все столбцы таблицы 2

for (i = 0; i < numericUpDown2.Maximum; i++)

dataGridView2.Columns[i].Visible = false;

// делаем видимыми соответствующее количество столбцов

for (i = 0; i < numericUpDown2.Value; i++)

dataGridView2.Columns[i].Visible = true;

// копируем найденные строки из таблицы 1 в таблицу 2

for (i = 0; i < numericUpDown2.Value; i++)

for (j = 0; j < coverCount; j++)

{

dataGridView2[i, j].Value = dataGridView1[i, Cover[j]].Value.ToString();

dataGridView2.Rows[j].HeaderCell.Value = dataGridView1.Rows[Cover[j]].HeaderCell.Value.ToString();

}

}

}

}



Литература

1. http://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%B2%D0%B5%D1%80%D1%88%D0%B8%D0%BD%D0%BD%D0%BE%D0%BC_%D0%BF%D0%BE%D0%BA%D1%80%D1%8B%D1%82%D0%B8%D0%B8 -Задача о вершинном покрытии

2. http://rain.ifmo.ru/cat/view.php/vis/graph-general/vertex-cover-2005- ДИСКРЕТНАЯ МАТЕМАТИКА: АЛГОРИТМЫ

3. http://rain.ifmo.ru/cat/view.php/vis/graph-general/vertex-cover-2005/algorithm - ДИСКРЕТНАЯ МАТЕМАТИКА: АЛГОРИТМЫ

Размещено на Allbest.ru