Главная Коллекция "Revolution" Программирование, компьютеры и кибернетика Алгоритмизация в инженерных задачах

Алгоритмизация в инженерных задачах

Ознакомление с процессом решения задачи нахождения совершенного паросочетания в двудольном графе, используя алгоритм чередующихся цепей. Описание и характеристика программы, которая находит минимальное паросочетание по алгоритму чередующихся цепей.

Рубрика Программирование, компьютеры и кибернетика
Вид курсовая работа
Язык русский
Дата добавления 22.02.2019
Размер файла 2,0 M
рефераты на заказ со скидкой

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Размещено на http://www.allbest.ru/

1

Министерство образования Российской Федерации

Пензенский государственный университет

Кафедра «Вычислительная техника»

Курсовая работа по курсу: «Логика и основы алгоритмизации в инженерных задачах»

Выполнил: студент группы 16ВВ2 Шишков В.В.

Принял: Пащенко Д.В.

Малютина Г.И.

Пенза 2017

Оглавление

  • Введение
  • 1. Теоретическая часть
  • 2. Описание алгоритма решения поставленной задачи
  • 3. Ручной просчет
  • 4. Описание программы
  • 5. Тесты
  • 6. Листинг
  • Литература

Введение

Логика и основы алгоритмизации в инженерных задачах связанна с построением графов. Так как для решения задачи необходимо составить алгоритм и разработать программу, которая будет работать на основе расчетов.

В графах основными элементами являются вершины и связи (ребра) между этими вершинами. Граф может изображать сеть улиц в городе, вершины графа -- перекрестки, стрелками обозначены улицы с разрешенным направлением движения. (Улицы могут быть с односторонним и двусторонним движением.)

На этом применение графов не заканчивается. Можно составить граф любой позиционной игры: шахмат, шашек, «крестиков - ноликов». Здесь позиции станут вершинами, а направленные отрезки между ними будут означать, что одним ходом можно перейти от одной позиции к другой, по направлению стрелки.

Графами являются блок - схемы программ для ЭВМ, а так же любые электрические цепи или электрическая сеть.

Немало поводов для появления графов и в математике. Наиболее очевидный пример - любой многогранник в трёхмерном пространстве.

Помимо этого графы можно использовать в: в психологии при исследовании межличностных отношений в группах, представить схему метрополитена, железных дорог, авиалиний, блок-схем, генеалогического древа.

Графы в медицине - известно, что у разных людей кровь отличается по группе. Существуют четыре группы крови. Оказывается, что при переливании крови от одного человека к другому не все группы совместимы. Граф показывает возможные варианты переливания крови. Группы крови - это вершины графов с соответствующими номерами, а стрелки указывают на возможность переливания одной группы крови человеку с другой группой крови. Из графа видно, что кровь 1-й группы можно переливать любому человеку, а человек с 1-й группой крови воспринимает кровь только своей группы.

Постановка задачи. Решить задачу нахождения совершенного паросочетания в двудольном графе, используя алгоритм чередующихся цепей.

Простая цепь С ненулевой длины в G , ребра которой попеременно лежат и не лежат в Р, называется чередующейся цепью (относительно паросочетания Р).

Эта цепь С называется Р-увеличителем, если первое и последнее ребро цепи С лежат вне Р.

С помощью Р-увеличителя паросочетание Р можно переделать в другое паросочетание Р* для G с числом ребер в Р* на единицу больше, чем в Р. Для этого достаточно все ребра в С, лежащие вне Р, добавить к Р, а ребра в С, лежащие в Р, удалить из Р. Для получившегося паросочетания Р* можно снова искать увеличитель, и так далее, последовательно расширяя получающиеся паросочетания, пока это возможно.

1. Теоретическая часть

Граф -- абстрактный математический объект, представляющий собой множество вершин графа и набор рёбер, то есть соединений между парами вершин.

Матрица смежности -- один из способов представления графа в виде матрицы. Матрица смежности неориентированного графа симметрична, а значит обладает действительными собственными значениями и ортогональным базисом из собственных векторов. Набор её собственных значений называется спектром графа, и является основным предметом изучения спектральной теории графов.

В теории графов паросочетание или независимое множество рёбер в графе -- это набор попарно несмежных рёбер

Совершенным паросочетанием - паросочетание, в котором участвуют все вершины графа. То есть любая вершина графа сопряжена ровно одному ребру, входящему в паросочетание.

2. Описание алгоритма решения поставленной задачи

1. Выберем исходное паросочетание P1, например одно ребро графа G.

2. Предположим, что паросочетание Pi=(Ui,Vi,Xi) для графа G построено. Построим паросочетание Pi+1 для G следующим образом: выбираем u из U, не принадлежащую Pi, например u1. Если такой вершины u нет, то Pi есть совершенное паросочетание. Строим в G чередующуюся цепь i = [u1,v1,u2,v2,...up,vp] с u1=u, в которой всякое ребро (ui,vi) не принадлежит Xi , а всякое ребро (vi,ui+1) принадлежит Xi. Если такой цепи нет, то совершенного паросочетания граф G не имеет, а паросочетание Pi является для G максимальным (тупиковым). Цепь i есть Pi-увеличитель.

3. Выбрасываем из Pi все ребра (vi,ui+1) и добавляем все ребра (ui,vi) цепи i. Получившееся паросочетание Pi+1 на одно ребро длиннее паросочетания Pi. Переходим к п.1.

3. Ручной просчет

Построим совершенное паросочетание для двудольного графа G = (U,V, X), U={u1,u2,u3,u4,u5,u6}, V={v1,v2,v3,v4,v5,v6,v7}, матрица смежности которого имеет вид

v1 v2 v3 v4 v5 v6 v7

u1 1 1 0 0 1 0 0

u2 1 0 1 0 1 0 0

u3 1 0 0 0 0 1 0

u4 0 0 1 1 0 1 1

u5 0 0 0 0 1 0 1

u6 0 0 0 1 0 1 1

Шаг 1. Выбираем исходное паросочетание Р1={u1,v1}.

Рис. 1

Шаг 2. Выберем вершину u2, которая не входит в паросочетание P1, но которая смежна с вершиной v1, содержащейся в P1. Далее ищем вершину v, смежную с вершиной u1, содержащейся в Р1. В результате получим чередующуюся цепь:

1= [u2,v1,u1,v2]

0 1 0

1 0 1

Единица в первой строке из нулей и единиц означает, что соответствующее этой единице ребро {v1,u1} лежит в P1. Убираем это ребро из P1, а вместо него добавляем ребра {u2,v1}, {u1,v2}, соответствующие единицам второй строки. В результате получим паросочетание P2 ={ {u1,v1}, {u2,v3} }, число ребер в котором на одно больше, чем в P1.

Шаг 3.

Рис. 2

Найдем чередующуюся цепь:

2= [u3,v1,u2,v3,]

0 1 0

1 0 1

P3={ {u1,v2}, {u2,v3},{u3,v1}}.

Шаг 4.

Рис. 3

Найдем чередующуюся цепь:

3= [u4,v3,u2,v3]

0 1 0

1 0 1

P4={ {u1,v2}, {u2,v5},{u3,v1},{u4,v3}}.

Шаг 5.

Рис. 4

Найдем чередующуюся цепь:

4 = [u5,v5,u2,v1,u3,v6]

0 1 0 1 0

1 0 1 0 1

P5={ {u1,v2}, {u2,v1},{u3,v6},{u4,v3},{u5,v5}}.

Шаг 6.

Рис. 5

Найдем чередующуюся цепь:

5= [u6,v6,u3,v1,u2,v3,u4,v7]

0 1 0 1 0 1 0

1 0 1 0 1 0 1

Рис. 6

P6={ {u1,v2}, {u2,v3}, {u3,v1}, {u4,v7},{u5,v5},{u6,v6}}. Полученное паросочетание является совершенным для исходного графа.

4. Описание программы

Программа находит минимальное паросочетание по алгоритму чередующихся цепей.

Язык программирования, на котором написана программа - Visual C(C++)

Интерфейс программы:

Рис. 7

5. Тесты

Удачный запуск программы, все введено верно.

Рис. 8

Не удачный запуск программы, значения не входят в диапазон разрешенных. паросочетание граф программа

Рис. 9

6. Листинг

#pragma once

#include <stdlib.h>

namespace Курсач {

using namespace System;

using namespace System::ComponentModel;

using namespace System::Collections;

using namespace System::Windows::Forms;

using namespace System::Data;

using namespace System::Drawing;

/// <summary>

/// Сводка для Form1

/// </summary>

public ref class Form1 : public System::Windows::Forms::Form

{

public:

Form1(void)

{

InitializeComponent();

//

//TODO: добавьте код конструктора

//

}

protected:

/// <summary>

/// Освободить все используемые ресурсы.

/// </summary>

~Form1()

{

if (components)

{

delete components;

}

}

private: System::Windows::Forms::DataGridView^ dataGridView1;

protected:

private: System::Windows::Forms::MenuStrip^ menuStrip1;

private: System::Windows::Forms::ToolStripMenuItem^ вычислитьToolStripMenuItem;

private: System::Windows::Forms::ToolStripMenuItem^ оПрограммеToolStripMenuItem;

private: System::Windows::Forms::GroupBox^ groupBox1;

private: System::Windows::Forms::RadioButton^ radioButton2;

private: System::Windows::Forms::RadioButton^ radioButton1;

private: System::Windows::Forms::Label^ label1;

private: System::Windows::Forms::NumericUpDown^ numericUpDown2;

private: System::Windows::Forms::NumericUpDown^ numericUpDown1;

private: System::Windows::Forms::Button^ button1;

private: System::Windows::Forms::PictureBox^ pictureBox1;

private: System::Windows::Forms::DataGridView^ dataGridView2;

private:

/// <summary>

/// Требуется переменная конструктора.

/// </summary>

System::ComponentModel::Container ^components;

#pragma region Windows Form Designer generated code

/// <summary>

/// Обязательный метод для поддержки конструктора - не изменяйте

/// содержимое данного метода при помощи редактора кода.

/// </summary>

void InitializeComponent(void)

{

this->dataGridView1 = (gcnew System::Windows::Forms::DataGridView());

this->menuStrip1 = (gcnew System::Windows::Forms::MenuStrip());

this->вычислитьToolStripMenuItem = (gcnew System::Windows::Forms::ToolStripMenuItem());

this->оПрограммеToolStripMenuItem = (gcnew System::Windows::Forms::ToolStripMenuItem());

this->groupBox1 = (gcnew System::Windows::Forms::GroupBox());

this->label1 = (gcnew System::Windows::Forms::Label());

this->numericUpDown2 = (gcnew System::Windows::Forms::NumericUpDown());

this->numericUpDown1 = (gcnew System::Windows::Forms::NumericUpDown());

this->radioButton2 = (gcnew System::Windows::Forms::RadioButton());

this->radioButton1 = (gcnew System::Windows::Forms::RadioButton());

this->button1 = (gcnew System::Windows::Forms::Button());

this->pictureBox1 = (gcnew System::Windows::Forms::PictureBox());

this->dataGridView2 = (gcnew System::Windows::Forms::DataGridView());

(cli::safe_cast<System::ComponentModel::ISupportInitialize^ >(this->dataGridView1))->BeginInit();

this->menuStrip1->SuspendLayout();

this->groupBox1->SuspendLayout();

(cli::safe_cast<System::ComponentModel::ISupportInitialize^ >(this->numericUpDown2))->BeginInit();

(cli::safe_cast<System::ComponentModel::ISupportInitialize^ >(this->numericUpDown1))->BeginInit();

(cli::safe_cast<System::ComponentModel::ISupportInitialize^ >(this->pictureBox1))->BeginInit();

(cli::safe_cast<System::ComponentModel::ISupportInitialize^ >(this->dataGridView2))->BeginInit();

this->SuspendLayout();

//

// dataGridView1

//

this->dataGridView1->AllowUserToAddRows = false;

this->dataGridView1->AllowUserToDeleteRows = false;

this->dataGridView1->AllowUserToOrderColumns = true;

this->dataGridView1->ColumnHeadersHeightSizeMode = System::Windows::Forms::DataGridViewColumnHeadersHeightSizeMode::AutoSize;

this->dataGridView1->Location = System::Drawing::Point(12, 131);

this->dataGridView1->Name = L"dataGridView1";

this->dataGridView1->ReadOnly = true;

this->dataGridView1->Size = System::Drawing::Size(484, 311);

this->dataGridView1->TabIndex = 0;

this->dataGridView1->CellContentClick += gcnew System::Windows::Forms::DataGridViewCellEventHandler(this, &Form1::dataGridView1_CellContentClick);

this->dataGridView1->CellEndEdit += gcnew System::Windows::Forms::DataGridViewCellEventHandler(this, &Form1::dataGridView1_CellEndEdit);

//

// menuStrip1

//

this->menuStrip1->Items->AddRange(gcnew cli::array< System::Windows::Forms::ToolStripItem^ >(2) {this->вычислитьToolStripMenuItem,

this->оПрограммеToolStripMenuItem});

this->menuStrip1->Location = System::Drawing::Point(0, 0);

this->menuStrip1->Name = L"menuStrip1";

this->menuStrip1->Size = System::Drawing::Size(1030, 24);

this->menuStrip1->TabIndex = 1;

this->menuStrip1->Text = L"menuStrip1";

//

// вычислитьToolStripMenuItem

//

this->вычислитьToolStripMenuItem->Name = L"вычислитьToolStripMenuItem";

this->вычислитьToolStripMenuItem->Size = System::Drawing::Size(94, 20);

this->вычислитьToolStripMenuItem->Text = L"О программе";

this->вычислитьToolStripMenuItem->Click += gcnew System::EventHandler(this, &Form1::вычислитьToolStripMenuItem_Click);

//

// оПрограммеToolStripMenuItem

//

this->оПрограммеToolStripMenuItem->Name = L"оПрограммеToolStripMenuItem";

this->оПрограммеToolStripMenuItem->Size = System::Drawing::Size(53, 20);

this->оПрограммеToolStripMenuItem->Text = L"Выход";

this->оПрограммеToolStripMenuItem->Click += gcnew System::EventHandler(this, &Form1::оПрограммеToolStripMenuItem_Click);

//

// groupBox1

//

this->groupBox1->Controls->Add(this->label1);

this->groupBox1->Controls->Add(this->numericUpDown2);

this->groupBox1->Controls->Add(this->numericUpDown1);

this->groupBox1->Controls->Add(this->radioButton2);

this->groupBox1->Controls->Add(this->radioButton1);

this->groupBox1->Location = System::Drawing::Point(12, 27);

this->groupBox1->Name = L"groupBox1";

this->groupBox1->Size = System::Drawing::Size(466, 98);

this->groupBox1->TabIndex = 2;

this->groupBox1->TabStop = false;

//

// label1

//

this->label1->AutoSize = true;

this->label1->Location = System::Drawing::Point(6, 74);

this->label1->Name = L"label1";

this->label1->Size = System::Drawing::Size(123, 13);

this->label1->TabIndex = 4;

this->label1->Text = L"Размерность матрицы";

//

// numericUpDown2

//

this->numericUpDown2->Location = System::Drawing::Point(196, 72);

this->numericUpDown2->Maximum = System::Decimal(gcnew cli::array< System::Int32 >(4) {15, 0, 0, 0});

this->numericUpDown2->Minimum = System::Decimal(gcnew cli::array< System::Int32 >(4) {1, 0, 0, 0});

this->numericUpDown2->Name = L"numericUpDown2";

this->numericUpDown2->Size = System::Drawing::Size(55, 20);

this->numericUpDown2->TabIndex = 3;

this->numericUpDown2->Value = System::Decimal(gcnew cli::array< System::Int32 >(4) {1, 0, 0, 0});

//

// numericUpDown1

//

this->numericUpDown1->Location = System::Drawing::Point(135, 72);

this->numericUpDown1->Maximum = System::Decimal(gcnew cli::array< System::Int32 >(4) {15, 0, 0, 0});

this->numericUpDown1->Minimum = System::Decimal(gcnew cli::array< System::Int32 >(4) {1, 0, 0, 0});

this->numericUpDown1->Name = L"numericUpDown1";

this->numericUpDown1->Size = System::Drawing::Size(55, 20);

this->numericUpDown1->TabIndex = 2;

this->numericUpDown1->Value = System::Decimal(gcnew cli::array< System::Int32 >(4) {1, 0, 0, 0});

//

// radioButton2

//

this->radioButton2->AutoSize = true;

this->radioButton2->Location = System::Drawing::Point(146, 20);

this->radioButton2->Name = L"radioButton2";

this->radioButton2->Size = System::Drawing::Size(67, 17);

this->radioButton2->TabIndex = 1;

this->radioButton2->TabStop = true;

this->radioButton2->Text = L"Вручную";

this->radioButton2->UseVisualStyleBackColor = true;

this->radioButton2->CheckedChanged += gcnew System::EventHandler(this, &Form1::radioButton2_CheckedChanged);

//

// radioButton1

//

this->radioButton1->AutoSize = true;

this->radioButton1->Location = System::Drawing::Point(7, 20);

this->radioButton1->Name = L"radioButton1";

this->radioButton1->Size = System::Drawing::Size(72, 17);

this->radioButton1->TabIndex = 0;

this->radioButton1->TabStop = true;

this->radioButton1->Text = L"Случайно";

this->radioButton1->UseVisualStyleBackColor = true;

this->radioButton1->CheckedChanged += gcnew System::EventHandler(this, &Form1::radioButton1_CheckedChanged);

//

// button1

//

this->button1->Enabled = false;

this->button1->Location = System::Drawing::Point(951, 454);

this->button1->Name = L"button1";

this->button1->Size = System::Drawing::Size(67, 67);

this->button1->TabIndex = 3;

this->button1->Text = L"Ок";

this->button1->UseVisualStyleBackColor = true;

this->button1->Click += gcnew System::EventHandler(this, &Form1::button1_Click);

//

// pictureBox1

//

this->pictureBox1->BackColor = System::Drawing::SystemColors::ButtonHighlight;

this->pictureBox1->Location = System::Drawing::Point(514, 131);

this->pictureBox1->Name = L"pictureBox1";

this->pictureBox1->Size = System::Drawing::Size(504, 311);

this->pictureBox1->TabIndex = 4;

this->pictureBox1->TabStop = false;

//

// dataGridView2

//

this->dataGridView2->AllowUserToAddRows = false;

this->dataGridView2->AllowUserToDeleteRows = false;

this->dataGridView2->AllowUserToOrderColumns = true;

this->dataGridView2->ColumnHeadersHeightSizeMode = System::Windows::Forms::DataGridViewColumnHeadersHeightSizeMode::AutoSize;

this->dataGridView2->Location = System::Drawing::Point(12, 454);

this->dataGridView2->Name = L"dataGridView2";

this->dataGridView2->Size = System::Drawing::Size(484, 67);

this->dataGridView2->TabIndex = 5;

//

// Form1

//

this->AutoScaleDimensions = System::Drawing::SizeF(6, 13);

this->AutoScaleMode = System::Windows::Forms::AutoScaleMode::Font;

this->ClientSize = System::Drawing::Size(1030, 533);

this->Controls->Add(this->dataGridView2);

this->Controls->Add(this->pictureBox1);

this->Controls->Add(this->button1);

this->Controls->Add(this->groupBox1);

this->Controls->Add(this->dataGridView1);

this->Controls->Add(this->menuStrip1);

this->MainMenuStrip = this->menuStrip1;

this->Name = L"Form1";

this->Text = L"Form1";

(cli::safe_cast<System::ComponentModel::ISupportInitialize^ >(this->dataGridView1))->EndInit();

this->menuStrip1->ResumeLayout(false);

this->menuStrip1->PerformLayout();

this->groupBox1->ResumeLayout(false);

this->groupBox1->PerformLayout();

(cli::safe_cast<System::ComponentModel::ISupportInitialize^ >(this->numericUpDown2))->EndInit();

(cli::safe_cast<System::ComponentModel::ISupportInitialize^ >(this->numericUpDown1))->EndInit();

(cli::safe_cast<System::ComponentModel::ISupportInitialize^ >(this->pictureBox1))->EndInit();

(cli::safe_cast<System::ComponentModel::ISupportInitialize^ >(this->dataGridView2))->EndInit();

this->ResumeLayout(false);

this->PerformLayout();

}

#pragma endregion

private: void random(int sizeX, int sizeY, int **mas) {

for(int i=0; i<sizeX; i++)

{

for(int j=0; j<sizeY; j++)

mas[i][j]=rand()%2;

}

}

private: void typing(int sizeX, int sizeY, int **mas) {

for(int i=0; i<sizeX; i++)

{

for(int j=0; j<sizeY; j++)

mas[i][j] = Convert::ToInt32(dataGridView1->Rows[i]->Cells[j]->Value);

}

}

private: void clear() {

for(int i=0; i<dataGridView1->Rows->Count; i++)

{

for(int j=0; j<dataGridView1->Columns->Count; j++)

dataGridView1->Rows[i]->Cells[j]->Value = 0;

}

}

private: bool try_kuhn (int v, int sizeY, int *mt, int **gg, bool *used) {

if (used[v]) return false;

used[v] = true;

for (size_t i=0; i<sizeY; ++i) {

if (gg[v][i]!=-1)

{

int to = gg[v][i];

if (mt[to] == -1 || try_kuhn (mt[to],sizeY,mt,gg,used)) {

mt[to] = v;

return true;

}

}

}

return false;

}

private: void search(int sizeX, int sizeY, int **mas, int *mt, int **gg, bool *used) {

for(int i=0; i<sizeX; i++)

{

for(int j=0; j<sizeY; j++)

{

if (mas[i][j]==1)

gg[i][j]=j;

else gg[i][j]=-1;

mt[j]=-1;

}

}

for (int v=0; v<sizeX; ++v) {

for (int i=0; i<sizeX; i++)

used[i] = false;

try_kuhn (v,sizeY,mt,gg,used);

}

}

private: void show(int sizeX, int sizeY, int **mas, int *mt, int **gg, bool *used) {

search(sizeX,sizeY,mas,mt,gg,used);

this->pictureBox1->Refresh();

String ^ v, ^ u;

System::Drawing::Font^ font= gcnew System::Drawing::Font("Arial",10);

SolidBrush^ brush = gcnew SolidBrush(Color::Black);

Point pt1, pt2;

Graphics ^ g = pictureBox1->CreateGraphics();

Pen^ p = gcnew Pen( Color::Black,1.0f );

Pen^ pp = gcnew Pen( Color::Red,1.0f );

for(int i=0; i<sizeX; i++)

{

g->DrawRectangle(p, 50+30*i, 70, 2, 2);

pt1 = Point(45+30*i, 55);

v=Convert::ToString(i);

g->DrawString(("v"+v),font,brush,pt1);

}

for(int j=0; j<sizeY; j++)

{

g->DrawRectangle(p, 50+30*j, 250, 2, 2);

pt2 = Point(45+30*j, 250);

u=Convert::ToString(j);

g->DrawString(("u"+u),font,brush,pt2);

}

dataGridView1->TopLeftHeaderCell->Value = "Матрица";

for(int i=0; i<sizeX; i++)

{

for(int j=0; j<sizeY; j++)

{

dataGridView1->Columns[j]->HeaderCell->Value = "u" + Convert::ToString(j);

dataGridView1->Rows[i]->HeaderCell->Value = "v" + Convert::ToString(i);

dataGridView1->Rows[i]->Cells[j]->Value = mas[i][j];

if(mas[i][j]==1)

{

pt1 = Point(51+30*i, 72);

pt2 = Point(51+30*j, 250);

g->DrawLine(p, pt1, pt2);

}

}

}

dataGridView2->Rows[1]->HeaderCell->Value = "v";

dataGridView2->Rows[0]->HeaderCell->Value = "u";

for(int j=0; j<sizeY; j++)

if (mt[j] != -1)

{

dataGridView2->Rows[0]->Cells[j]->Value = mt[j];

dataGridView2->Rows[1]->Cells[j]->Value = j;

pt1 = Point(51+30*mt[j], 72);

pt2 = Point(51+30*j, 250);

g->DrawLine(pp, pt1, pt2);

}

else {

dataGridView2->Rows[0]->Cells[j]->Value = "-";

dataGridView2->Rows[1]->Cells[j]->Value = "-";

}

dataGridView2->TopLeftHeaderCell->Value = "Паросочетание";

}

private: System::Void dataGridView1_CellContentClick(System::Object^ sender, System::Windows::Forms::DataGridViewCellEventArgs^ e) {

}

private: System::Void button1_Click(System::Object^ sender, System::EventArgs^ e) {

int sizeX = Convert::ToInt32(numericUpDown1->Value);

int sizeY = Convert::ToInt32(numericUpDown2->Value);

int *mt = new int [sizeX];

bool *used = new bool [sizeY];

int **gg = new int *[sizeX];

int **mas = new int *[sizeX];

for(int i=0; i<sizeX; i++)

{

gg[i] = new int[sizeY];

mas[i] = new int[sizeY];

}

dataGridView1->ColumnCount = sizeY;

dataGridView1->RowCount = sizeX;

dataGridView2->ColumnCount = sizeY;

dataGridView2->RowCount = 2;

if(radioButton1->Checked)

random(sizeX,sizeY,mas);

if(radioButton2->Checked)

typing(sizeX,sizeY,mas);

show(sizeX,sizeY,mas,mt,gg,used);

dataGridView1->AutoResizeRowHeadersWidth(DataGridViewRowHeadersWidthSizeMode::AutoSizeToAllHeaders);

dataGridView1->AutoResizeColumns();

dataGridView2->AutoResizeRowHeadersWidth(DataGridViewRowHeadersWidthSizeMode::AutoSizeToAllHeaders);

dataGridView2->AutoResizeColumns();

for(int i=0; i<sizeX; i++)

{

delete [] gg[i];

delete [] mas[i];

}

delete [] gg;

delete [] mt;

delete [] used;

delete [] mas;

}

private: System::Void radioButton2_CheckedChanged(System::Object^ sender, System::EventArgs^ e) {

button1->Enabled = true;

clear();

dataGridView1->ReadOnly = false;

}

private: System::Void radioButton1_CheckedChanged(System::Object^ sender, System::EventArgs^ e) {

button1->Enabled = true;

clear();

dataGridView1->ReadOnly = true;

}

private: System::Void dataGridView1_CellEndEdit(System::Object^ sender, System::Windows::Forms::DataGridViewCellEventArgs^ e) {

int q;

if(!Int32::TryParse(Convert::ToString(dataGridView1->CurrentCell->Value), q))

{

MessageBox::Show("Матрица может принимать только значения 0 или 1","Ошибка");

dataGridView1->CurrentCell->Value = "0";

}

else if(q!=0 && q!=1)

{

MessageBox::Show("Матрица может принимать только значения 0 или 1","Ошибка");

dataGridView1->CurrentCell->Value = "0";

}

}

private: System::Void оПрограммеToolStripMenuItem_Click(System::Object^ sender, System::EventArgs^ e) {

exit(0);

}

private: System::Void вычислитьToolStripMenuItem_Click(System::Object^ sender, System::EventArgs^ e) {

MessageBox::Show("Эта программа выполняет поиск\nсовершенного паросочетания в двудольном графе","Информация");

}

};

}

Литература

1. Пауэрс Л., Снелл М . “Microsoft Visual Studio” 2010г.

2. Чарльз Петцольд “Программирование с использованием Microsoft Windows Forms”.

3. http://www.e-maxx-ru.1gb.ru/algo/kuhn_matching - Алгоритм Куна

Размещено на Allbest.ru

...

Подобные документы

  • Использование ПК для расчета разветвленной электрической цепи постоянного тока

    Законы электрических цепей, порядок и методы их расчета. Разработка программы на языке программирования Borland C++ Builder 5.0 для анализа разветвленных электрических цепей с использованием матричного метода. Алгоритм решения задачи и описание его работы

    курсовая работа [211,5 K], добавлен 08.10.2012

  • Основы алгоритмизации

    Математическая постановка задачи для алгоритмизации, рекуррентная зависимость. Алгоритм решения задачи, блок-схема программы. Тестовые данные для тестирования программы. Результаты, соответствующие для первых вводимых данных и листинг программы.

    контрольная работа [27,0 K], добавлен 09.05.2012

  • Деревянный алгоритм решения задачи коммивояжёра

    Задачи, решаемые методом динамического программирования. Основные этапы нахождения деревянного алгоритма решения задачи. Выполнение алгоритма Прима. Построение Эйлерового цикла. Решение задач средствами Excel. Алгоритм основной программы - Derevo.

    курсовая работа [586,3 K], добавлен 04.04.2015

  • Моделирование электрических цепей при помощи программы Micro-Cap

    Простейшие электрические цепи первого порядка. Характеристика электрических цепей второго порядка, их параметры. Элементы нелинейных цепей. Основные этапы моделирования схем с помощью программы схемотехнического проектирования и моделирования Micro-Cap.

    контрольная работа [196,6 K], добавлен 17.03.2011

  • Комбинаторные алгоритмы. Поиск кратчайшего пути на графе

    Исследование методов решения задачи о ходе коня. Описание алгоритмов для итеративной и рекурсивной программ. Генерация перестановок элементов по индексам. Построение эйлерова цикла на графе. Поиск кратчайшего пути на графе. Программная реализация задачи.

    курсовая работа [411,6 K], добавлен 25.04.2013

  • Программная реализация алгоритма Дейкстры (построение цепей минимальной длины)

    Теоретическое исследование вопроса и практическое применение. Общие сведения о графах. Алгоритм Дейкстры. Особенности работы в среде. Программная реализация. Описание алгоритма и структуры программы. Описание программных средств. Текст программы.

    курсовая работа [1,0 M], добавлен 27.11.2007

  • Поиск кратчайшего пути в лабиринте

    Разработка в среде Delphi программы "Поиск кратчайшего пути", которая создает лабиринт, находит кратчайший путь его прохождения и отображает его. Структура данных задачи и методы ее решения. Общая схема организации и взаимодействия модулей, их описание.

    курсовая работа [86,5 K], добавлен 19.10.2010

  • Разработка программы на Delphi для решения транспортной задачи

    Описание алгоритма решения транспортной задачи по планированию перевозки зерна. Ход решения задачи вручную, в программе TORA методом наименьшего элемента, с помощью MS Excel. Разработка программы для решения задачи в общем виде средствами Delphi.

    курсовая работа [2,5 M], добавлен 22.11.2012

  • Расчет сетевого графика табличным способом

    Графическое изображение последовательности технологического процесса. Описание метода решения задачи на математическом языке. Общий алгоритм решения задачи и структура программы. Основные понятия сетевых моделей. Разработка программы на языке С++.

    курсовая работа [1,3 M], добавлен 23.05.2013

  • Нахождение минимального пути в графе (алгоритм Дейкстры)

    Теория графов и её применения. Разработка программного продукта для решения задач нахождения минимального пути. Анализ надежности и качества ПП "метода Дейкстры". Математическая модель задачи. Алгоритмы Дейкстры на языке программирования Turbo Pascal.

    курсовая работа [1,6 M], добавлен 26.03.2013

  • Разработка системы для нахождения кратчайших маршрутов

    Анализ алгоритмов нахождения кратчайших маршрутов в графе без отрицательных циклов: Дейкстры, Беллмана-Форда и Флойда-Уоршалла. Разработка интерфейса программы на языке C++. Доказательство "правильности" работы алгоритма с помощью математической индукции.

    курсовая работа [1,5 M], добавлен 26.07.2013

  • Составление и описание программы по заданным параметрам

    Характеристика программы на языке VBA, которая вводит исходные данные, выполняет расчеты и выводит результаты на экран. Описание переменных в программе, ее блок-схема и алгоритм работы. Листинг программы. Описание входных данных и результат вычислений.

    курсовая работа [721,4 K], добавлен 10.11.2010

  • Метод Гаусса для расчета электрических цепей

    Разработка алгоритма составления системы уравнений при помощи законов Кирхгофа по определенной электрической схеме. Приложение для решения данной системы методом Гаусса с выбором ведущего элемента по строке. Описание программы, руководство пользователя.

    курсовая работа [435,9 K], добавлен 02.07.2010

  • Программы в среде Turbo Pascal

    Разработана программа решения двух задач на языке программирования Turbo Pascal. Спецификация задания. Описание входных и выходных данных. Математическая постановка задачи. Алгоритм ее решения. Описание и блок-схема программы. Результаты тестирования.

    курсовая работа [275,8 K], добавлен 28.06.2008

  • Создание программы на языке Delphi 7.0

    Написание программы для работы с клиентами средствами языка Delphi, которая предусматривает ввод, редактирование и удаление информации. Разработка алгоритма решения задачи, описание переменных, вспомогательных процедур, входных и выходных данных.

    курсовая работа [355,7 K], добавлен 21.09.2010

  • Алгоритм Беллмана—Форда

    Содержательная и формальная (математическая) постановка задачи. Разработка алгоритма решения задачи. Структуры программы и алгоритмы программных модулей, их описание. Решение задачи на конкретном примере. Разработка системы тестов и отладка программы.

    курсовая работа [882,1 K], добавлен 24.11.2014

  • Разработка игры "крестики-нолики"

    Разработка алгоритма, выполняющего поиск наилучшего решения на каждый ход в игре "крестики-нолики" (используя минимальный алгоритм). Обоснование выбора программных средств для решения задачи. Блок-схема интеллектуального алгоритма реализации программы.

    контрольная работа [380,0 K], добавлен 28.04.2014

  • Программное средство нахождения кратчайших путей в графе

    Разработка модифицированных алгоритмов поиска оптимального маршрута в графе. Задание дополнительных условий и ограничений. Реализация модели для внутреннего представления транспортной сети. Создание программного комплекса в среде Visual Studio 2010.

    курсовая работа [1,1 M], добавлен 16.04.2015

  • Силовой расчет групп Ассура

    Определение реакции для шарнирного четырехзвенника силовым расчетом статически определимых кинематических цепей первого вида. Математическая модель решения задачи. Схема головной программы. Таблица идентификаторов. Текст программы, результаты ее работы.

    контрольная работа [61,5 K], добавлен 08.03.2013

  • Создание программы для решения нелинейных уравнений

    Изучение методов решения нелинейных уравнений таких как: метод Ньютона, модифицированный метод Ньютона, метод Хорд, метод простых Итераций. Реализация программы для персонального компьютера, которая находит решение нелинейного уравнения разными способами.

    практическая работа [321,9 K], добавлен 24.06.2012

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.

© 2000 — 2023, ООО «Олбест» Все права защищены