Теперь необходимо создать файл. Опять в меню File выберите атрибут New. В появившемся диалоге в закладке File отметьте text file. По умолчанию новый файл будет добавлен к текущему проекту test, в чем можно убедиться, взглянув на поле Add to project. В поле Filename нужно ввести имя файла. Пусть это будет main.cpp. Расширение.cpp - это стандарт для файлов с исходными текстами на языке Си++. Поле Location должно показывать на каталог C:\Work. Нажмите кнопку " OK ".
На экране появится пустой файл. Наберите текст программы.
Компиляция выполняется с помощью меню Build. Выберите пункт Build test.exe (этому пункту меню соответствует функциональная клавиша F7 ). В нижней части экрана появятся сообщения компиляции. Если Вы сделали опечатку, двойной щелчок мышью по строке с ошибкой переведет курсор в окне текстового редактора на соответствующую строку кода. После исправления всех ошибок и повторной компиляции система выдаст сообщение об успешной компиляции и компоновке (пока мы не будем уточнять, просто вы увидите сообщение Linking ).
Готовую программу можно выполнить с помощью меню Build, пункт Execute test.exe. То же самое можно сделать, нажав одновременно клавиши CTRL и F5. На экране монитора появится консольное окно, и в нем будет выведена строка " Hello, world!". Затем появится надпись "Press any key to continue". Эта надпись означает, что программа выполнена и лишь ожидает нажатия произвольной клавиши, чтобы закрыть консольное окно.
3. Алгоритм Флойда-Уоршелла
Алгоритм Флойда-Уоршелла -- динамический алгоритм для нахождения кратчайших расстояний между всеми вершинами взвешенного ориентированного графа. Разработан в 1962 году Робертом Флойдом и Стивеном Уоршеллом. При этом алгоритм впервые разработал и опубликовал Бернард в 1959 году.
Пусть вершины графа G=(V,E), |V|=n пронумерованы от 1 до n и введено обозначение для длины кратчайшего пути от i до j, который кроме самих вершин I,j проходит только через вершины 1…k. Очевидно, что -- длина (вес) ребра (i,j), если таковое существует (в противном случае его длина может быть обозначена как ).
Существует два варианта значения :
Кратчайший путь между i,j не проходит через вершину k, тогда =.
Существует более короткий путь между i,j, проходящий через k, тогда он сначала идёт от i до k, а потом от k до j. В этом случае, очевидно, = +.
Таким образом, для нахождения значения функции достаточно выбрать минимум из двух обозначенных значений.
Тогда рекуррентная формула для имеет вид:
-- длина ребра (i,j)
.
Алгоритм Флойда-Уоршелла последовательно вычисляет все значения для k от 1 до n. Полученные значения являются длинами кратчайших путей между вершинами i,j.
На каждом шаге алгоритм генерирует матрицу .
Матрица W содержит длины кратчайших путей между всеми вершинами графа. Перед работой алгоритма матрица W заполняется длинами рёбер графа (или запредельно большим M, если ребра нет).
На каждом шаге алгоритм генерирует матрицу Матрица W содержит длины кратчайших путей между всеми вершинами графа. Перед работой алгоритма матрица W заполняется длинами рёбер графа (или запредельно большим M, если ребра нет).
Три вложенных цикла содержат операцию, исполняемую за константное время , то есть алгоритм имеет кубическую сложность, при этом простым расширением можно получить также информацию о кратчайших путях -- помимо расстояния между двумя узлами записывать в матрицу идентификатор первого узла в пути.
Алгоритм Флойда-Уоршелла может быть использован для нахождения замыкания отношения E по транзитивности. Для этого в качестве W[0] используется бинарная матрица смежности графа, ; оператор min заменяется дизъюнкцией, сложение заменяется конъюнкцией:
for k = 1 to n
for i = 1 to n
for j = 1 to n
W[i][j] = W[i][j] or (W[i][k] and W[k][j])
После выполнения алгоритма матрица W является матрицей достижимости.
Использование битовых масок при реализации алгоритма позволяет существенно ускорить алгоритм. При этом сложность алгоритма снижается до , где k -- длина битовой маски (в модели вычислений RAM). На практике, ещё бомльшего ускорения можно достичь, используя такие специализированные наборы микропроцессорных команд, как SSE.
Алгоритм Флойда -- Уоршелла является эффективным для расчёта всех кратчайших путей в плотных графах, когда имеет место большое количество пар рёбер между парами вершин. В случае разреженных графов с рёбрами неотрицательного веса лучшим выбором считается использование алгоритма Дейкстры для каждого возможного узла. При таком выборе сложность составляет при применении двоичной кучи, что лучше, чем алгоритма Флойда -- Уоршелла тогда, когда |E| существенно меньше (условие плотности графа). Если граф разрежен, у него имеются рёбра с отрицательным весом и отсутствуют циклы с отрицательным суммарным весом, то используется алгоритм Джонсона, который имеет ту же сложность, что и вариант с алгоритмом Дейкстры.
Также являются известными алгоритмы с применением алгоритмов быстрого перемножения матриц, которые ускоряют вычисления в плотных графах, но они обычно имеют дополнительные ограничения (например, представление весов рёбер в виде малых целых чисел). Вместе с тем, из-за большого константного фактора времени выполнения преимущество при вычислениях над алгоритмом Флойда -- Уоршелла проявляется только на больших графах.
4. Инструкция по установке
Для установки программы и успешной работы необходимо установить MicrosoftVisual Studio 2019.
Среду Visual Studio 2019 можно установить и работать в ней на следующих операционных системах (перечислены официально поддерживаемые версии):
- Windows 7 с Service Pack 1;
-Windows 8.1 (с обновлением 2919355);
-Windows 10 (1703 и выше);
-Windows Server 2012 R2 (с обновлением 2919355);
-Windows Server 2016 (Standard и Datacenter);
-Windows Server 2019 (Standard и Datacenter).
Минимальные требования к оборудованию:
-процессор с тактовой частотой не ниже 1,8 ГГц. Рекомендуется использовать как минимум двухъядерный процессор;
-2 ГБ оперативной памяти, рекомендуется 8 ГБ (если устанавливать на виртуальную машину, то минимум 2.5 ГБ);
-свободного места на жестком диске от 800 мегабайт до 210 гигабайт, в зависимости от установленных компонентов. В большинстве случаев выделяйте как минимум 30 гигабайт.Также Microsoft рекомендует устанавливать Visual Studio на SSD диск.
-видеоадаптер с минимальным разрешением 1280 на 720 пикселей (для оптимальной работы Visual Studio рекомендуется разрешение 1366 на 768 пикселей и более высокое).
Дополнительные важные моменты:
-для установки Visual Studio 2019 требуются права администратора;
-для работы Visual Studio 2019 требуется платформа.NET Framework 4.7.2, она будет установлена во время установки среды;
-варианты «Основные серверные компоненты» и «Минимальный серверный интерфейс» не поддерживаются при запуске на Windows Server;
Запуск Visual Studio 2019 (Professional, Community и Enterprise) в контейнерах Windows не поддерживается;
-для установки компоненты «Разработка мобильных приложений на C++, JavaScript или.NET» в ОС Windows 7 требуется PowerShell 3.0 или более поздняя версия;
5. Инструкция пользователю
Запуск программы осуществляется путём запуска на выполнение файла
Рисунок 1 Форма программы
На форме размещены следующие компоненты:
· Компоненты label для отображения текстовых пояснений;
· Компоненты DBGrid для отображения матриц;
· Область toolstrip для размещения toolstripstatuslabel для отображения текстовых пояснений;
· Компонент contextMenuStrip для отображения контекстного меню;
· Colordialog для выбора цвета окна;
· Combobox для выбора настроек вычислений;
· Элементы Button для начала вычислений;
· Элементы Panel и GroupBox для разделения окна на секции.
Рисунок 6 Окно программы после изменения настроек
Рисунок 7 Выбор цвета окна
6. Программная реализация
Программа имеет интерфейс, представленный на рисунке 1.
Компоненты label содержат статический текст.
Компоненты используются для логического деления окна программы на отдельные части. Таким образом можно визуально разделить поля ввода и отображения данных.
Компонент ColorDialog вызывается следующим образом и служит для изменения фона окна:
colorDialog1->ShowDialog();
panel3->BackColor = colorDialog1->Color;
При загрузке окна выполняется процедура, определяющая содержимое компонентов ComboBox:
comboBox1->Items->Add("3");
comboBox1->Items->Add("4");
comboBox1->Items->Add("5");
comboBox1->Items->Add("6");
comboBox1->Items->Add("7");
comboBox1->Items->Add("8");
comboBox1->Items->Add("9");
comboBox1->Items->Add("10");
comboBox1->SelectedItem = 1;
comboBox1->Text = "4";
comboBox2->Items->Add("1");
comboBox2->Items->Add("2");
comboBox2->Items->Add("3");
comboBox2->Items->Add("4");
comboBox2->Items->Add("5");
comboBox2->Items->Add("6");
comboBox2->Items->Add("7");
comboBox2->Items->Add("8");
comboBox2->SelectedItem = 1;
comboBox2->Text = "2";
comboBox3->Items->Add("10");
comboBox3->Items->Add("12");
comboBox3->Items->Add("13");
comboBox3->Items->Add("14");
comboBox3->Items->Add("15");
comboBox3->Items->Add("16");
comboBox3->Items->Add("17");
comboBox3->Items->Add("18");
comboBox3->SelectedItem = 1;
comboBox3->Text = "12";
StatusStrip представляет строку состояния, во многом аналогичную панели инструментов ToolStrip. Строка состояния предназначена для отображения текущей информации о состоянии работы приложения.
При добавлении на форму StatusStrip автоматически размещается в нижней части окна приложения (как и в большинстве приложений). Однако при необходимости мы сможем его иначе позиционировать, управляя свойством Dock, которое может принимать следующие значения:
· Bottom: размещение внизу (значение по умолчанию)
· Top: прикрепляет статусную строку к верхней части формы
· Fill: растягивает на всю форму
· Left: размещение в левой части формы
· Right: размещение в правой части формы
· None: произвольное положение
· StatusStrip может содержать различные элементы. В режиме дизайнера мы можем добавить следующие типы элементов:
Наиболее интересным в настройке элементом является contextMenuStrip. Контекстное меню вызывается с помощью двойного щелчка мышью по области формы.
ContextMenuStrip представляет контекстное меню. Данный компонент во многом аналогичен элементы MenuStrip за тем исключением, что контекстное меню не может использоваться само по себе, оно обязательно применяется к какому-нибудь другому элементу, например, текстовому полю. Новые элементы в контекстное меню можно добавить в режиме дизайнера.
При этом есть возможность добавить все те же элементы, что и в MenuStrip. Но, как правило, используются ToolStripMenuItem, либо элемент ToolStripSeparator, представляющий горизонтальную полоску разделитель между другими пунктами меню.
Также, на панели свойств, можно обратиться к свойству Items компонента ContextMenuStrip и в открывшемся окне добавить и настроить все элементы меню.
В более сложных программах данный элемент отображает текущую информацию о работе программы. В данном же приложении элемент используется для вывода статичной поясняющей надписи:
toolStripStatusLabel1->Text= "Можно приступать к вычислениям. Выберите размерность матрицы смежности.";
7. Инструкция программисту
Проект программы запускается стандартным способом в среде MS Visual Studio.
Программная часть состоит из файлов Form1.h (основная форма) и Header.h (класс решения задачи).
При старте программы и введении данных пользователем происходит форматирование полей вывода:
dataGridView1->ColumnCount = n;
dataGridView1->RowCount = n;
dataGridView1->SetBounds(10, 10, 50 * n + n, 50 * n + n);
dataGridView2->ColumnCount = n;
dataGridView2->RowCount = n;
dataGridView2->SetBounds(10, 10, 50 * n + n, 50 * n + n);
Затем осуществляется создание нового экземпляра объекта:
FloydWarshallClass object;
Вызывается метод создания исходной матрицы смежности:
object.generate_source(n,a,b);
Вызывается метод решения на основе матрицы смежности:
object.generate_result(n);
После этого программа выводит результаты в компоненты dbgrid:
for (i = 0; i < n; i++)
{
for (j = 0; j < n; j++)
{
dataGridView2->Columns[i]->Width = 30;
dataGridView2->Rows[i]->Cells[j]->Value = object.g1[i][j];
}
}
for (i = 0; i < n; i++)
{
for (j = 0; j < n; j++)
{
dataGridView1->Columns[i]->Width = 30;
dataGridView1->Rows[i]->Cells[j]->Value = object.g2[i][j];
}
Листинг программы
#pragma once
#include <cstdlib>
#include <iostream>
#include <ctime>
#include "header.h"
namespace WinForms_NET4 {
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;
}
}
protected:
private: System::Windows::Forms::GroupBox^ groupBox1;
private: System::Windows::Forms::GroupBox^ groupBox2;
private: System::Windows::Forms::GroupBox^ groupBox3;
private: System::Windows::Forms::ComboBox^ comboBox1;
private: System::Windows::Forms::Button^ button1;
private: System::Windows::Forms::StatusStrip^ statusStrip1;
private: System::Windows::Forms::ToolStripStatusLabel^ toolStripStatusLabel1;
private: System::Windows::Forms::Panel^ panel3;
private: System::Windows::Forms::Label^ label1;
private: System::Windows::Forms::ColorDialog^ colorDialog1;
private: System::Windows::Forms::ComboBox^ comboBox3;
private: System::Windows::Forms::ComboBox^ comboBox2;
private: System::Windows::Forms::Label^ label3;
private: System::Windows::Forms::Label^ label2;