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

 

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

85537. Життя тварин моря. Б.Коробейников “Дельфіни” 166 KB
  Мета. Ознайомити учнів з текстом. Поширити знання дітей про тварин моря – дільфінів. Продовжити роботу над формуванням навичок виразного читання, розвивати критичне мислення, збагачувати активний словниковий запас. Вчити працювати в групі.
85538. Закувала та сива зозуля (козацька пісня) 92.5 KB
  Як розумієте вираз сива давнина У які ігри любив гратися в дитинстві письменник Які співав пісні дід письменника Що вони викликали Прочитайте згадки автора про козацькі пісні. Козачі пісні думи. а Читання пісні вчителем. Проблемне питання: Про що мріяли невільники козаки б Словникова робота...
85539. Від усмішки йде до всіх тепло. В.О.Сухомлинський «Усмішка» 66 KB
  Актуалізувати і розширити знання дітей про життя і творчість видатного українського педагога і письменника; розвивати уміння аналізувати і структурувати текст (знаходити описи, міркування, зачин, основну частину, кінцівку).
85540. Підсумок за темою: «З любов’ю до рідної землі» 37 KB
  Мета: викликати інтерес до читання творів, удосконалювати навички свідомого читання, розуміння прочитаного, оволодівати лексикою і фразеологією української мови; розвивати спостережливість; вчити логічно мислити, аналізувати...
85541. Урок Доброти за творами В.О. Сухомлинського 53.5 KB
  Обладнання: Крилаті вислови прислівя про доброту твори В. Творити повсякчас добро для інших це велике покликання людини. Тож хочу наш урок позакласного читання розпочати такими словами: Живи добро звершай Та нагород за це не вимагай Хай оживає істина стара: Людина починається з добра Саме цей вислів Людина починається з добра є темою нашого уроку ДОБРОТИ.
85542. Життя і творчість М. Рильського М. Рильський. Не кидайсь хлібом 69.5 KB
  Мета: Продовжити знайомити дітей із творчістю українського письменника М. Виховувати почуття поваги до праці хлібороба бережне ставлення до хліба. Давайте розшифруємо що ж хотіли хлопчаки нам сказати НЕ кидайсь хлібом IV Повідомлення теми та мети уроку Цими словами розпочинається ще один вірш...
85543. З думкою про канікули. Правила поведінки під час масових заходів 63.5 KB
  Мета: Навчати учнів бачити, відчувати створені словами образи природи; удосконалювати техніку читання віршованих та прозових творів, насичених діалогами. Вчити свідомо сприймати художні тексти, визначати головну думку в прочитаному творі.
85544. Як по-різному звучать мелодії природи... С. Жупанин «Мелодії природи». О. Олесь «В небі жайворонки в’ються» 81.5 KB
  Вправи для підвищення швидкості читання і розвитку мовлення Творче завдання Розвиток звязного мовлення. Співи яких птахів ви чуєте Який настрій викликає у вас щебетання пташок 2 Самостійне читання учнями тексту на с. Читання слів знизу вгору. Читання слів у парі римовані слова.
85545. Т.Г.Шевченко – поет, художник, патріот 144.5 KB
  Шевченка вчити сприймати зміст поезії на слух відображати його в малюнках викликати бажання розповідати вивчені вірші й слухати нові показати барвистість красу рідної мови її мелодійність; розвивати память увагу спостережливість поповнювати словниковий запас учнів; виховувати милосердя доброту любов...