49238

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

Курсовая

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

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

Русский

2013-12-23

58.36 KB

9 чел.

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

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

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

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

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

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

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

 

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

24458. Метод обратных функций 69 KB
  Предположим что случайная величина определенная на интервале [a ; b] имеет плотность распределения . Зная можно вычислить функцию распределения. Теорема Случайная величина удовлетворяющая уравнению имеет плотность распределения . Замечание отсюда название Доказательство Так как функция распределения это строго возрастающая функция на интервале [a ; b] то она должна удовлетворять условию .
24459. Метод суперпозиции 91.5 KB
  Существует три вида атрибутов SEGMENT: Выравнивание Выравнивания сегмента задача компоновщика. Он должен обеспечить размещение начала сегмента на заданной границе. Размеры сегмента Отдельной проблемой при разработке системы со страничной или сегментной адресацией является выбор размера страницы или максимального размера сегмента. Это дает ряд мелких преимуществ например позволяет раздавать права доступа сегментам а подкачку с диска осуществлять постранично.
24460. Погрешность и сходимость метода Монте-Карло 49.5 KB
  таблица настройки адресов имеет переменную длину состоит из элементов по 4 байта которые указывают на адрес который должен быть настроен. Смещение от начала файлов: 0001: 4D5A; 0203: длина абзаца задачи по модулю 512; 0405: длина файла в блоках колво блоков по 512 байт; 0607: число элементов таблицы настройки адресов; 0809: длина заголовка в параграфе; 0А0В: минимальный объем памяти который нужно выделить после конца абзаца задачи MIN ALLOC 0000; 0С0D: максимальный объем памяти который нужно выделить после конца абзаца...
24461. Процессы восстановления. Уравнение восстановления 129.5 KB
  Процессы восстановления. Уравнение восстановления. Определение: Под процессом восстановления понимается последовательность неотрицательных взаимнонезависимых случайных величин которые при i 1 имеют одно и тоже распределение. случайная наработка системы после i1 восстановления.
24462. Восприятие и его характеристики 45.5 KB
  В отличие от ощущений отражающих лишь отдельные свойства предметов в образе восприятия представлен весь предмет в совокупности его постоянных свойств. Образ восприятия выступает как результат синтеза ощущений. При этом особенно важную роль во всех видах восприятия играют двигательные или кинестетические ощущения которые регулируют по принципу обратной связи реальные взаимоотношения субъекта с предметом. В процессе слухового восприятия активную роль играют слабые движения артикуляционного аппарата.
24463. Сфера вторичных образов: эмпирические характеристика представления в сравнении с характеристиками восприятия 58.5 KB
  Сфера вторичных образов: эмпирические характеристика представления в сравнении с характеристиками восприятия. К вторичным образом относятся образы представления сновидения галлюцинации. При этом степень обобщенности того или иного представления может быть различной в связи с чем различают единичные и общие представления. Представления различаются по ведущему анализатору зрительные слуховые осязательные обонятельные по их содержанию математические технические музыкальные.
24464. Понятие о памяти, её видах и процессах. Способы повышения эффективности запоминания 72.5 KB
  Память форма психического отражения действительности заключающаяся в закреплении сохранении и последующем воспроизведении прошлого опыта делающая возможным его повторное использование в деятельности или возвращение в сферу сознания. Память является процессом обеспечивающим построение всестороннего образа мира связывающим разрозненные впечатления в целостную картину прошлое с настоящим и будущим. По длительности сохранения информации выделяют сенсорную кратковременную долговременную память. В соответствии с видом стимула сенсорная...
24465. Внимание: его характеристики и методы диагностики 69 KB
  Объектом внимания могут быть предметы явления отношения свойства предметов действия мысли чувства других людей и свой собственный внутренний мир. Внимание обладает следующими основными характеристиками: Устойчивость внимания проявляется в способности в течение длительного времени сохранять состояние внимания на какомлибо объекте предмете деятельности не отвлекаясь и не ослабляя внимание. Концентрация внимания противоположное качество рассеянность проявляется в различиях которые имеются в степени концентрированности...
24466. Понятие мышления, его виды. Фазы мыслительного процесса и мыслительные операции 70.5 KB
  Мышление это социально обусловленный неразрывно связанный с речью психический процесс поисков и открытия существенно нового процесс опосредованного и обобщенного отражения действительности в ходе ее анализа и синтеза. Мышление возникает на основе практической деятельности из чувственного познания и далеко выходит за его пределы. Мышление является базовым компонентом интеллекта. 1 Наиболее распространена среди них классификация рассматривающая такие разновидности мыслительной деятельности как нагляднодейственное нагляднообразное и...