49238

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

Курсовая

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

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

Русский

2013-12-23

58.36 KB

5 чел.

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

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

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

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

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

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

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

 

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

14987. ТАРАЗ - ҚАЗАҚ МӘДЕНИЕТIНIҢ АЛТЫН БЕСIГI 37 KB
  ТАРАЗ ҚАЗАҚ МӘДЕНИЕТIНIҢ АЛТЫН БЕСIГI Кәнкиев Ә.Ш. Жүншеев Р.Е. Тараз қ. М.Х.Дулати атындағы ТарМУ Ежелгi Тараз Ұлы Жiбек жолын жалғап жататын турақты дипломатикалық және саудасаттык қарымқатынас жасалатың күре тамыры iспеттес. Бұл байланыс көпiрiнiң маңызы дүние
14988. Тараздың көне моншалары 37.5 KB
  Тараздың көне моншалары. Көне деректерге сүйенетін болсақ Тараз қаласы Талас өңіріндегі саяси мәдениеттің ірі орталығы болған республикадағы ежелгі қалалардың бірі. Онда көптеген елдің көпестері мемлекетаралық іспен шұғылданған елшілер әртүрлі діни ағымды тарат
14989. Түркістан аймағындағы Сығанақ қаласының тарихы 35.5 KB
  ТҮРКІСТАН АЙМАҒЫНДАҒЫ СЫҒАНАҚ ҚАЛАСЫНЫҢ ТАРИХЫ Сыр бойындағы ірі қалалардың бірі Сығанақ болды. Ол қазіргі Қызылорда облысының Жаңақорған ауданындағы қала еді. Бұл қала туралы алғаш рет Х ғасырдағы жазба деректерде айтылған. XI ғ. Ғұлама ғалым түркі тілінің маманы Ма
14990. ҮСТІРТ КЕРУЕН ЖОЛЫНДАҒЫ САМ ҚАЛАСЫ 66.5 KB
  ҮСТІРТ КЕРУЕН ЖОЛЫНДАҒЫ САМ ҚАЛАСЫ Тарихтың атасы атанған Геродот бiздiң дәуiрiмiзге дейiнгi мыңжылдықтың орта шенiнде Қара теңiз маңынан Дон жағалауына одан Оңтүстiк Оралдағы савроматтар жерi арқылы Ертiс бойы мен Алтайға Зайсан көлiне дейiн барған далалық сақ жолының
14991. Ұлы даланың астаналары 52.5 KB
  Ұлы даланың астаналары Дидарыңда Мәңгіліктің мұңы ұйыған Ұлы Дала... Керуендеп көшкен тұтас дәуірлер ол үшін қасқағымдық мезет қана. Қатпарлы тау аңырған оқшау төбелермен толқындап шексіздікке маңған ұлан жазық алапат кеңістік мұхитының шежіреестелігі де біртүрлі...
14992. Мұражай тәрбие өзегі 67.5 KB
  Мұражай тәрбие өзегі Ақселеу Сланұлы Сейдімбеков бұрыны Жезқазған қазіргі Қарағанды облысы Жаңаарқа ауданына қарасты Дружба совхозына 1942 жылы дүниеге келген. 1962 жылдан 1968 жылға дейін Киров атындағы Қазақ мемлекеттік университетінде оқып журналистика факульте...
14993. Шу өңірінің тарихын білеміз бе 58 KB
  Шу өңірінің тарихын білеміз бе Біздің білетініміз Шу тарихын зерттеп жүрген екі ғалым бар. Бірі тарих ғылымдарының докторы профессор Қожа Ахмет Ясауи атындағы Халықаралық қазақтүрік университетінің құрметті профессоры Әбу Насыр ӘлФараби атындағы Қазақ ұл...
14994. Web-бет дизайны, HTML 504 KB
  Webбет дизайны HTML Кіріспе Қазақстан Республикасының білім беру жүйесін ақпараттандыру еліміздің даму стратегиясының негізгі бағыттарының бірі себебі ХХІ ғасыр – білім беру жүйесін ақпараттандыру ғасыры. Информатика пәнінің орта білім беру жүйесіндегі ролі ...
14995. Интернет жүйесі 622.5 KB
  Интернет жүйесі Интернет туралы ұғым. Жиырмасыншы ғасырдың аяғында пайда болған Интернет қазір жер шарының әр түкпірін байланыстырып сан алуан адамдарды елдер мен құрылқтарды біріктіріп отыр. Интернет 1960 жылдары АҚШта дүниеге келдi.Оны соғыс бола қалған жағ...