49238

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

Курсовая

Информатика, кибернетика и программирование

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

Русский

2013-12-23

58.36 KB

7 чел.

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

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

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

ПО ПРОГРАММИРОВАНИЮ

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

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

гр. АСУ – 09 – 2

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

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

Фамилия: Ростовщиков

Имя: Николай

Отчество: Викторович

группа АСУ – 09 – 2

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

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

Формулировка задания

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

Дата выдачи задания:

Дата сдачи отчёта:

Отчёт принял: доцент Дружинин А.В.


Оглавление

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

2) Описание базового класса……………………………………5

3) Визуализация………………………………………………….6

4) Пример работы программы…………………………………..7

5) Листинг………………………………………………………...8

6) Литература………………………………………………...…11


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

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

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

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

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

Листинг

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 - ДИСКРЕТНАЯ МАТЕМАТИКА: АЛГОРИТМЫ

 

А также другие работы, которые могут Вас заинтересовать

82559. СОВЕРШЕНСТВОВАНИЕ ПРАВОВОГО РЕГУЛИРОВАНИЯ ИПОТЕЧНЫХ ОТНОШЕНИЙ В РОССИЙСКОЙ ФЕДЕРАЦИИ 394.5 KB
  Правовое регулирование ипотеки. Общая характеристика правового регулирования ипотеки. Коллизии правового регулирования ипотеки зданий сооружений расположенных на земельном участке. Правовое регулирование ипотеки зданий и земельного участка.
82560. Разработка алгоритма подсчета контрольных сумм в RAID-подобных массивах с ненадежными и медленными каналами связи между устройствами хранения данных 229.55 KB
  Одним из возможных применений могут быть системы хранения данных СХД. В распределенных СХД появляется проблема передачи данных между устройствами если они расположены далеко друг от друга или соединены медленными и не надежными каналами связи.
82561. Моделирование процессов полирования оптических деталей на станках с ЧПУ 12.23 MB
  Объектом моделирования включает в себя процесс полирования поверхности оптических деталей а также автоматизацию анализа входных данных с поверхности линзы расчёта оптимального способа обработки оптических деталей генерации и записи кода ISO для станка с ЧПУ.
82562. Быстрое сравнение по образцу и обучение в глубину с помощью диаграмм решений 259.19 KB
  Машинное обучение – раздел информатики изучающий методы построения моделей, способных обучаться. Различают два типа обучения: обучение по прецедентам, или индуктивное обучение, т.е. выделение закономерностей в экспериментальных данных, и дедуктивное обучение, предполагающее формализацию знаний экспертов.
82563. Разработка мероприятий, направленных на повышение рентабельности ООО Поликлиника «А-3» 943.5 KB
  Целью любого предприятия является прибыль, она же, соответственно, является и важнейшим объектом экономического анализа. Однако сам размер прибыли не может охарактеризовать эффективность использования предприятием своих ресурсов. Одним из основных показателей, характеризующих эффективность работы предприятия, является рентабельность.
82564. Определение апостолом Петром теологической концепции несправедливого страдания последователей Иисуса Христа 518.08 KB
  Автор работы выбрал Первое Послание святого Апостола Петра потому, что тема страданий в этом Послании встречается чаще, чем в других книгах Нового Завета. Первое Послание наиболее подходит для рассмотрения данной темы, т.к. Апостол Пётр, предвидя грядущие страдания последователей Иисуса Христа...
82565. Совершенствование системы оценки и аттестации персонала на предприятии (на примере ООО «ПромСтройТорг») 469 KB
  При переходе к рынку происходит медленный отход от иерархического управления, жесткой системы административного воздействия, практически неограниченной власти к рыночным взаимоотношениям, отношениям собственности, базирующимся на экономических методах управления.
82566. PR-ПРОДВИЖЕНИЕ ФЕРМЕРСКИХ ПРОДУКТОВ НА ТЕРРИТОРИИ МОСКВЫ И МОСКОВСКОЙ ОБЛАСТИ В ПЕРИОД С 2012 ПО 2013 ГОД 3.36 MB
  Сегодня у компании уже есть четыре точки сбыта в разных районах Москвы отработанная система заказов через сайт компании с доставкой по Москве база постоянных клиентов и самое главное - перспективы для дальнейшего роста. Предмет: PR-инструменты в сфере продвижения фермерских продуктов на опыте компании Пенка.
82567. Система анализа реконструктивных хирургических операций при помощи Microsoft Kinect 3.61 MB
  Одной из ключевых особенностей хирургии как сферы использования ПО - это требование стерильности, которое обычно сложно было выполнять из-за устройств ввода/вывода, которые требуется заново тщательно стерилизовать после каждой операции.