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

 

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

75755. Понятие о температуре воспламенения и вспышки. Самовозгорание 11.59 KB
  Температура самовоспламенения минимальная температура вещества или материала при которой происходит резкое увеличение скорости экзотермических реакций заканчивающихся пламенным горением. Используются также понятия температура воспламенения температура вспышки. Последняя используется для характеристики всех горючих жидкостей по пожарной опасности и делятся на легковоспламеняющиеся температура до 610С бензин ацетон и т. Температура воспламенения используется для характеристик пыли.
75756. Классификация горючих жидкостей по температуре вспышки 12.31 KB
  Несгораемые материалы которые при воздействии огня или высокой температуры не воспламеняются не тлеют и не обугливаются. К несгораемым относятся все неорганические строительные материалы: бетон железобетон газобетон металл стекло асбест кирпич природные камни цемент известь. Трудносгораемые материалы которые при воздействии огня или высокой температуры с трудом воспламеняются тлеют или обугливаются и продолжают гореть или тлеть при наличии источника огня. К этой группе относят: смешанные строительные материалы органического и...
75757. Понятие о взрыве паров и газов. Степень взрывоопасности газовоздушной смеси 13.99 KB
  Степень взрывоопасности газовоздушной смеси. Взрывоопасную среду могут образовать смеси веществ газов паров пылей с воздухом и другими окислителями кислород озон. Газовоздушные смеси могут воспламеняться взрываться только тогда когда содержание газа в смеси находится в определенных для каждого газа пределах. Нижний предел соответствует минимальному а верхний максимальному количеству газа в смеси при котором происходят их воспламенение при зажигании и самопроизвольное без притока тепла извне распространение пламени...
75758. Характеристика производственных помещений по степени пожарной опасности 13.33 KB
  Все помещения и здания подразделяются на 5 категорий. Б помещения где осуществляются технологические процессы с использованием ЛВЖ с температурой вспышки свыше 28 С способные образовывать взрывоопасные и пожароопасные смеси. В помещения и здания где обращаются технологические процессы с использованием горючих и трудногорючих жидкостей твердых горючих веществ которые при взаимодействии друг с другом или кислородом воздуха способны только гореть. Г помещения и здания где обращаются технологические процессы с использованием негорючих...
75759. Пожарная сигнализация, ее виды 12.36 KB
  Пожарная связь и сигнализация играют важную роль в мероприятиях для предупреждения пожаров способствуют своевременному их обнаружению и вызову пожарных подразделений к месту возникшего пожара а также обеспечивают управление и оперативное руководство работами на пожаре. Пожарную связь можно подразделить на связь извещения своевременный прием вызовов на пожары диспетчерскую связь управление силами и средствами для тушения пожаров и связь на пожаре руководство пожарными подразделениями. Наиболее надежное и быстродействующее средство...
75760. Понятие системы «Человек-среда обитания» 14.32 KB
  Человеку эти потоки необходимы для удовлетворения своих потребностей в пище воде воздухе солнечной энергии информации об окружающей среде и т. В то же время человек в жизненное пространство выделяет потоки механической и интеллектуальной энергии потоки масс в виде отходов биологического процесса потоки тепловой энергии и др. Естественная среда обеспечивает поступление на нашу планету потоков солнечной энергии что создает в свою очередь потоки растительной и животной масс в биосфере потоки абиотических веществ воздух вода...
75761. Причины региональной деградации биосферы. Формирование техносферы-нового типа среды обитания 15.71 KB
  Этим изменениям во многом способствовали: высокие темпы роста численности населения на Земле демографический взрыв и его урбанизация; рост потребления и концентрация энергетических ресурсов; интенсивное развитие промышленного и сельскохозяйственного производства; массовое использование транспорта; рост затрат на военные цели и ряд других процессов. Достижения в медицине повышение комфортности деятельности и быта интенсификация и рост продуктивности сельского хозяйства во многом способствовали увеличению продолжительности...
75762. Взаимодействие человека и техносферы 12.42 KB
  Взаимодействие человека и техносферы Человек и окружающая его среда гармонично взаимодействуют и развиваются лишь в условиях когда потоки энергии вещества и информации находятся в пределах благоприятно воспринимаемых человеком и природной средой. Любое превышение привычных уровней потоков сопровождается негативными воздействиями как на человека так и природную среду. и действиями человека. комфортное оптимальное когда потоки соответствуют оптимальным условиям взаимодействия: создают оптимальные условия деятельности и отдыха;...
75763. Понятие опасных и вредных производственных факторов 42.64 KB
  Понятие опасных и вредных производственных факторов По степени и характеру действия на организм все факторы условно делят на вредные и опасные. К вредным относятся такие факторы которые становятся в определенных условиях причиной заболеваний или снижения работоспособности. Опасными называют такие факторы которые приводят в определенных условиях к травматическим повреждениям или внезапным и резким нарушениям здоровья. И опасные и вредные факторы могут быть естественного или природного и антропогенного характера т.