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

 

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

37610. Изучение частотных характеристик мультивибратора Ройера в зависимости от величины нагрузки 310.5 KB
  Установив входное напряжение 30 В, путем изменения нагрузки, изменяем ток нагрузки до минимального возможного значения, фиксируя каждый раз значения токов Iвх , Iн, напряжения на нагрузке и частоты. Рассчитываем значения потребляемой мощности, выходной мощности и КПД
37611. Описание и моделирование регулярных (систолических) схем 289.5 KB
  Необходимо спроектировать VHDL-модель заданного устройства одним из указанных способов согласно требованиям, сформулированным к каждому варианту задания, разработать тестирующие воздействия и выполнить моделирование работы устройства.
37612. Проведение экспериментальных работ при исследовании переходных процессов в электрических цепях 115 KB
  На экране осциллографа получаем изображение зависимости напряжения и тока конденсатора от времени.Зарисовываем осциллограммы тока и напряжения на конденсаторе: Рассчитываем по осциллограмме постоянные времени разряда и заряда конденсатора по кривой uсt. На экране осциллографа получаем изображения зависимости тока и напряжения катушки от времени. Зарисовываем осциллограммы тока и напряжения катушки: Рассчитываем по осциллограмме постоянные времени при подключении и отключении катушки по кривой it.
37613. История государства и права зарубежных стран (ИГПЗС) 712 KB
  В силу конкретноисторического подхода к государственноправовым явлениям и процессам присущим тому или иному обществу на том или ином этапе его развития оперируя множеством фактов и событий политической жизни деятельности государств правительств классов и партий ИГПЗС ставит своей целью выявление исторических закономерностей развития государства и права. ИГПЗС тесно связана с другой юридической наукой и учебной дисциплиной Теорией государства и права также изучающей закономерности развития государства и права. Теория...
37614. Основи теорії транспортних процесів і систем 4.22 MB
  У цьому розділі вивчаються питання стосовно експлуатаційних властивостей транспортних засобів що використовуються для організації процесу перевезення вантажів та пасажирів. В країнах Азії до цих пір переміщення вантажів та людей за допомогою коромисел є дуже розповсюдженим. В умовах первинно общинного ладу для транспортування людей та вантажів використовувались найпростіші засоби включаючи в'ючних тварин. На сьогодні транспорт це одна із найважливіших галузей матеріального виробництва що виконує перевезення людей та вантажів.
37615. Программирование на языке ассемблера для микропроцессоров фирмы Intel 411.5 KB
  Программист или любой другой пользователь может использовать любые высокоуровневые средства вплоть до программ построения виртуальных миров и возможно даже не подозревать что на самом деле компьютер выполняет не команды языка на котором написана его программа а их трансформированное представление в форме скучной и унылой последовательности команд совсем другого языка машинного. шесть регистров сегментов: cs ds ss es fs gs; регистры состояния и управления: регистр флагов eflags flags; регистр указателя команды eip ip. Его...
37616. Тезисы лекций по маркетингу 534.5 KB
  В этой ипостаси маркетинг существует несколько тысяч лет когда произошло отделение купца негоцианта от производителя товара ремесленника. Производственная: Разработка ассортимента новых продуктов; Разработка требований к новым товарам Сбытовая: Выбор каналов сбыта. Сравнительный анализ сбытовой и современной концепций маркетинга Сбытовая Современный маркетинг Учет потребностей Предприятия Потребителей Производится то что Удается произвести Что будет куплено Ассортимент Узкий Широкий Горизонт планирования Краткосрочный Длительный...
37617. Бег с барьерами 15.99 KB
  Дисциплины: Зимний сезон : 50 метров 60 метров Летний сезон : 100 метров женщины 110 метров мужчины 400 метров История Первые упоминания об официальных стартах в барьерном беге относятся к соревнованиям в Англии в 1837 году в колледже Итон. Олимпийский дебют на дистанции 110 метров с барьерами состоялся в 1896 году.
37618. Горный бег 18.2 KB
  Классификация трасс по критерию набор высоты Категория А: набор высоты составляет как минимум 76 метров 250 футов на каждую милю 16 км дистанции; по шоссе проходит не более 20 от общей длины трассы; трасса должна быть длиной не менее одной мили 16 Категория В: набор высоты составляет как минимум 38 метров 125 футов на каждую милю 16 км дистанции; по шоссе проходит не более 30 от общей длины трассы; Категория С: набор высоты составляет как минимум 304 метра 100 футов на каждую милю 16 км дистанции; по шоссе проходит не...