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

 

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

39437. Разработка линии связи между ОП1 (Брест) и ОП2 (Гомель) через ПВ (Пинск) 387 KB
  Для этого на стойке в оконечном пункте размещены: оборудование линейного тракта на две системы; оборудование дистанционного питания НРП двух систем передачи; оборудование магистральной телемеханики; оборудование участковой телемеханики; комплект служебной связи КСС; панель ввода; панель обслуживания. 3 Необслуживаемый регенерационный пункт НРП Промежуточное оборудование линейного тракта размещается в грунтовых контейнерах полуподземного типа НРПГ2. Оборудование НРПГ2 обеспечивает...
39438. Реструктуризация управленческой структуры предприятия 198.1 KB
  Целью работы является анализ финансово-хозяйственной деятельности предприятия и выработка на этой основе рекомендаций по реструктуризации предприятия на материалах ООО «Торговый дом Холод» г. Заринск Алтайский край.
39439. Создание качественных каналов связи на заданном направлении 370.5 KB
  В состав аппаратуры входит следующее оборудование: вторичного временного группообразования ВВГ оконечное оборудование линейного тракта ОЛТ необслуживаемые регенерационные пункты НРП а также комплект контрольноизмерительных приборов КИП. Сформированный в оборудовании ВВГ цифровй сигнал в коде МЧПИ или ЧПИ поступает в ОЛТ которое осуществляет согласование выхода оборудования ВВГ с линейным трактом дистанционное питание НРП телеконтроль и сигнализацию о состоянии оборудования линейного тракта служебную связь между оконечным...
39441. Создание качественных каналов и связи на направлении МИНСК-ГРОДНО (через ЛИДУ) 326.5 KB
  Основные параметры системы передачи Параметр Значение параметра Число организуемых каналов 480 Скорость передачи информации кбит с 34368 Тип линейного кода HDB3 или MI Амплитуда импульсов в линии В 302 Расчетная частота кГц 17186 Номинальное затухание участка регенерации дБ 65 Номинальное значение тока ДП мА 200 Допустимые значения напряжения ДП В 401300650 относительно земли Максимальное расстояние ОРПОРП 200 км Максимальное число НРП между ОРП 66 Максимальное число НРП в полу секции ДП 33 Комплекс аппаратуры...
39442. Использование каналов цифровых систем для передачи дискретных сигналов 190.5 KB
  В состав аппаратуры ИКМ120у входят: аналогоцифровое оборудование формирования стандартных первичных цифровых потоков АЦО оборудование вторичного временного группообразования ВВГ оконечное оборудование линейного тракта ОЛТ необслуживаемые регенерационные пункты НРП. Оборудование ОЛТ обеспечивает согласование выхода оборудования ВВГ с линейным трактом дистанционное питание ДП НРП телеконтроль ТК и сигнализацию о состоянии линейного тракта СС между оконечными и промежуточными пунктами. Для размещения НРП необходимо определить...
39443. ПРОЕКТИРОВАНИЕ МЕЖДУГОРОДНЕЙ ЦИФРОВОЙ ЛИНИИ ПЕРЕДАЧИ 446 KB
  Размещение НРП вдоль кабельной линии передачи осуществляется в соответствии с номинальной длиной регенерационного участка РУ для проектируемой ЦСП. блоки регенераторов в НРП не содержат искусственных линий ИЛ. Необходимое число НРП определяется по формуле: N=n1; N1=10; N2=16. Из произведенных расчетов следует что между ОП1 и ПВ потребуется установить 10 НРП между ОП2 и ПВ 16.
39444. Создание качественных каналов на направлении Витебск – Глубокое – Браслав 308.5 KB
  В состав аппаратуры входят: оборудование вторичного временного преобразования ВВГ оконечное оборудование линейного тракта ОЛТ необслуживаемые регенерационные пункты НРП а также комплект контрольноизмерительных приборов КИП. Оконечное оборудование линейного тракта обеспечивает согласование выхода оборудования ВВГ с линейным трактом дистанционное питание НРП телеконтроль и сигнализацию о состоянии линейного тракта служебную связь между оконечными и промежуточными пунктами. Оборудование НРП аппаратуры ИКМ120У включает в себя блоки...
39445. Разработка линии связи между ОП1 (Витебск) и ОП2 (Гродно) через ПВ (Лида) 409.5 KB
  Основные параметры системы передачи ИКМ480 Параметр Значение параметра Число организуемых каналов 480 Скорость передачи информации кбит с 34 368 Тип линейного кода КВП3 или ЧПИ Расчетная частота кГц 34 368 Номинальное затухание участка регенерации дБ 65 Номинальное значение тока ДП мА 200 Допустимые значения напряжения ДП В 1300 Максимальное расстояние ОРПОРП 201 км Максимальное число НРП между ОРП 66 Максимальное число НРП в полусекции ДП 33 Номинальная длина регенерационного участка км Комплекс аппаратуры ЦСП ИКМ480...