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

Содержание

программирование алгоритм динамический задача

Введение

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

2. Сведения о средствах языка программировани

3. Алгоритм Флойда-Уоршелла

4. Инструкция по установке

5. Инструкция пользователю

6. Программная реализация

7. Инструкция программисту

8. Тестирование

Заключение

Список использованной литературы

Приложения



Введение

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

В данном курсовом проекте необходимо, спроектировать программный комплекс решения задачи динамического программирования, при разработке программы обучиться навыкам объектно-ориентированного программирования на языке С++.

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

Научная значимость данной работы состоит в описании и исследовании наиболее наглядной задачи динамического программирования - алгоритма поиска кратчайшего пути. Практическая значимость темы «Решение задачи динамического программирования» состоит в анализе проблем реализации и использовании современного подхода к задачам динамического программирования.

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

Динамическое программирование в теории управления и теории вычислительных систем -- способ решения сложных задач путём разбиения их на более простые подзадачи. Он применим к задачам с оптимальной подструктурой, выглядящим как набор перекрывающихся подзадач, сложность которых чуть меньше исходной. В этом случае время вычислений, по сравнению с «наивными» методами, можно значительно сократить.

Ключевая идея в динамическом программировании достаточно проста. Как правило, чтобы решить поставленную задачу, требуется решить отдельные части задачи (подзадачи), после чего объединить решения подзадач в одно общее решение. Часто многие из этих подзадач одинаковы. Подход динамического программирования состоит в том, чтобы решить каждую подзадачу только один раз, сократив тем самым количество вычислений. Это особенно полезно в случаях, когда число повторяющихся подзадач экспоненциально велико.

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

Словосочетание «динамическое программирование» впервые было использовано в 1940-х годах Ричардом Беллманом для описания процесса нахождения решения задачи, где ответ на одну задачу может быть получен только после решения задачи, «предшествующей» ей. В 1953 году он уточнил это определение до современного. Первоначально эта область была основана, как системный анализ и инжиниринг, которая была признана IEEE. Вклад Беллмана в динамическое программирование был увековечен в названии уравнения Беллмана, центрального результата теории динамического программирования, который переформулирует оптимизационную задачу в рекурсивной форме.

Слово «программирование» в словосочетании «динамическое программирование» в действительности к «традиционному» программированию (написанию кода) почти никакого отношения не имеет и имеет смысл как в словосочетании «математическое программирование», которое является синонимом слова «оптимизация». Поэтому слово «программа» в данном контексте скорее означает оптимальную последовательность действий для получения решения задачи. К примеру, определённое расписание событий на выставке иногда называют программой. Программа в данном случае понимается как допустимая последовательность событий.

Оптимальная подструктура в динамическом программировании означает, что оптимальное решение подзадач меньшего размера может быть использовано для решения исходной задачи. К примеру, кратчайший путь в графе из одной вершины (обозначим s) в другую (обозначим t) может быть найден так: сначала считаем кратчайший путь из всех вершин, смежных с s, до t, а затем, учитывая веса рёбер, которыми s соединена со смежными вершинами, выбираем лучший путь до t (через какую вершину лучше всего пойти). В общем случае мы можем решить задачу, в которой присутствует оптимальная подструктура, проделывая следующие три шага.

1 Разбиение задачи на подзадачи меньшего размера.

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

3 Использование полученного решения подзадач для конструирования решения исходной задачи.

Подзадачи решаются делением их на подзадачи ещё меньшего размера и т. д., пока не приходят к тривиальному случаю задачи, решаемой за константное время (ответ можно сказать сразу). К примеру, если нам нужно найти n!, то тривиальной задачей будет 1! = 1 (или 0! = 1).

Перекрывающиеся подзадачи в динамическом программировании означают подзадачи, которые используются для решения некоторого количества задач (не одной) большего размера (то есть мы несколько раз проделываем одно и то же). Ярким примером является вычисление последовательности Фибоначчи, F3=F2+F1 и F4=F3+F2 -- даже в таком тривиальном случае вычисления всего двух чисел Фибоначчи мы уже посчитали F2 дважды. Если продолжать дальше и посчитать F5, то F2 посчитается ещё два раза, так как для вычисления F5 будут нужны опять F3 и F4. Получается следующее: простой рекурсивный подход будет расходовать время на вычисление решения для задач, которые он уже решал.

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

Подводя итоги вышесказанного можно сказать, что динамическое программирование пользуется следующими свойствами задачи:

- перекрывающиеся подзадачи;

- оптимальная подструктура;

- возможность запоминания решения часто встречающихся подзадач.

Динамическое программирование обычно придерживается двух подходов к решению задач:

- нисходящее динамическое программирование: задача разбивается на подзадачи меньшего размера, они решаются и затем комбинируются для решения исходной задачи. Используется запоминание для решений часто встречающихся подзадач.

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

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

Языки программирования могут запоминать результат вызова функции с определённым набором аргументов (мемоизация), чтобы ускорить «вычисление по имени». В некоторых языках такая возможность встроена (например, Scheme, Common Lisp, Clojure, Perl, D), а в некоторых требует дополнительных расширений (C++).

Известны сериальное динамическое программирование, включённое во все учебники по исследованию операций, и несериальное динамическое программирование (НСДП), которое в настоящее время слабо известно, хотя было открыто в 1960-х годах.

Обычное динамическое программирование является частным случаем несериального динамического программирования, когда граф взаимосвязей переменных -- просто путь. НСДП, являясь естественным и общим методом для учёта структуры задачи оптимизации, рассматривает множество ограничений и/или целевую функцию как рекурсивно вычислимую функцию. Это позволяет находить решение поэтапно, на каждом из этапов используя информацию, полученную на предыдущих этапах, причём эффективность этого алгоритма прямо зависит от структуры графа взаимосвязей переменных. Если этот граф достаточно разрежен, то объём вычислений на каждом этапе может сохраняться в разумных пределах.

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



2. Сведения о средствах языка программирования

Язык Си++ является универсальным языком программирования, в дополнение к которому разработан набор разнообразных библиотек. Поэтому, строго говоря, он позволяет решить практически любую задачу программирования. Тем не менее, в силу разных причин (не всегда технических) для каких-то типов задач он употребляется чаще, а для каких-то - реже.

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

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

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

Обработка сложных структур данных - текста, бизнес-информации, Internet-страниц и т.п. - одна из наиболее распространенных возможностей применения языка. В прикладном программировании, наверное, проще назвать те области, где язык Си++ применяется мало.

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

В целом надо сказать, что язык Си++ в настоящее время является одним из наиболее распространенных языков программирования в мире.

Самая короткая программа на языке Си++ выглядит так:

// Простейшая программа

int main() { return 1; }

Первая строчка в программе - комментарий, который служит лишь для пояснения. Признаком комментария являются два знака деления подряд ( // ).

main - это имя главной функции программы. С функции main всегда начинается выполнение. У функции есть имя ( main ), после имени в круглых скобках перечисляются аргументы или параметры функции (в данном случае у функции main аргументов нет). У функции может быть результат или возвращаемое значение. Если функция не возвращает никакого значения, то это обозначается ключевым словом void. В фигурных скобках записывается тело функции - действия, которые она выполняет. Оператор return 1 означает, что функция возвращает результат - целое число 1.

Если мы говорим об объектно-ориентированной программе, то она должна создать объект какого-либо класса и послать ему сообщение. Чтобы не усложнять программу, мы воспользуемся одним из готовых, предопределенных классов - классом iostream (поток ввода-вывода, базовый класс для iostream). Этот класс определен в файле заголовков " iostream.h ". Поэтому первое, что надо сделать - включить файл заголовков в нашу программу:

#include <iostream.h>

int main() { return 1; }

Кроме класса, файл заголовков определяет глобальный объект этого класса cout. Объект называется глобальным, поскольку доступ к нему возможен из любой части программы. Этот объект выполняет вывод на консоль. В функции main мы можем к нему обратиться и послать ему сообщение.

Операция сдвига << для класса iostream определена как "вывести". Таким образом, программа посылает объекту cout сообщения "вывести строку Hello, world!" и "вывести перевод строки" ( endl обозначает новую строку). В ответ на эти сообщения объект cout выведет строку " Hello, world!" на консоль и переведет курсор на следующую строку.

Компиляция и выполнение программы

Программа на языке Си++ - это текст. С помощью произвольного текстового редактора программист записывает инструкцию, в соответствии с которой компьютер будет работать, выполняя данную программу.

Для того чтобы компьютер мог выполнить программу, написанную на языке Си++, ее нужно перевести на язык машинных инструкций. Эту задачу решает компилятор. Компилятор читает файл с текстом программы, анализирует ее, проверяет на предмет возможных ошибок и, если таковых не обнаружено, создает исполняемый файл, т.е. файл с машинными инструкциями, который можно выполнять.

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

Не имея возможности описать все варианты, остановимся только на двух наиболее часто встречающихся.

Если Вы используете персональный компьютер с операционной системой Windows N, то компилятор у Вас, скорее всего, Visual C++. Этот компилятор представляет собой интегрированную среду программирования, т.е. объединяет текстовый редактор, компилятор, отладчик и еще ряд дополнительных программ. Мы предполагаем, что читатель работает с версией 5.0 или старше. Версии младше 4.2 изучать не имеет смысла, поскольку реализация слишком сильно отличается от стандарта языка.

В среде Visual C++ прежде всего необходимо создать новый проект. Для этого нужно выбрать в меню File атрибут New. Появится новое диалоговое окно. В закладке Projects в списке различных типов выполняемых файлов выберите Win32 Console Application. Убедитесь, что отмечена кнопка Create new workspace. Затем следует набрать имя проекта (например, test ) в поле Project name и имя каталога, в котором будут храниться все файлы, относящиеся к данному проекту, в поле Location. После этого нажмите кнопку " OK ".

Теперь необходимо создать файл. Опять в меню 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;

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

private: System::Windows::Forms::Panel^ panel1;

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

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

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

private: System::Windows::Forms::Panel^ panel2;

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

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

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

private:

/// <summary>

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

/// </summary>

System::ComponentModel::Container ^components;

#pragma region Windows Form Designer generated code

/// <summary>

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

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

/// </summary>

void InitializeComponent(void)

{

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

this->panel1 = (gcnew System::Windows::Forms::Panel());

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

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

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

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

this->panel2 = (gcnew System::Windows::Forms::Panel());

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

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

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

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

this->comboBox3 = (gcnew System::Windows::Forms::ComboBox());

this->comboBox2 = (gcnew System::Windows::Forms::ComboBox());

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

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

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

this->comboBox1 = (gcnew System::Windows::Forms::ComboBox());

this->panel3 = (gcnew System::Windows::Forms::Panel());

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

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

this->statusStrip1 = (gcnew System::Windows::Forms::StatusStrip());

this->toolStripStatusLabel1 = (gcnew System::Windows::Forms::ToolStripStatusLabel());

this->colorDialog1 = (gcnew System::Windows::Forms::ColorDialog());

this->groupBox1->SuspendLayout();

this->panel1->SuspendLayout();

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

this->groupBox2->SuspendLayout();

this->panel2->SuspendLayout();

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

this->groupBox3->SuspendLayout();

this->panel3->SuspendLayout();

this->statusStrip1->SuspendLayout();

this->SuspendLayout();

//

// groupBox1

//

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

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

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

this->groupBox1->Size = System::Drawing::Size(372, 261);

this->groupBox1->TabIndex = 2;

this->groupBox1->TabStop = false;

this->groupBox1->Text = L"Матрица смежности";

//

// panel1

//

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

this->panel1->Controls->Add(this->button3);

this->panel1->Controls->Add(this->button4);

this->panel1->Location = System::Drawing::Point(6, 19);

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

this->panel1->Size = System::Drawing::Size(360, 236);

this->panel1->TabIndex = 9;

//

// dataGridView2

//

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

this->dataGridView2->Location = System::Drawing::Point(3, 5);

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

this->dataGridView2->Size = System::Drawing::Size(354, 227);

this->dataGridView2->TabIndex = 8;

//

// button3

//

this->button3->Location = System::Drawing::Point(263, 358);

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

this->button3->Size = System::Drawing::Size(159, 23);

this->button3->TabIndex = 7;

this->button3->Text = L"Выбор цвета окна";

this->button3->UseVisualStyleBackColor = true;

//

// button4

//

this->button4->Location = System::Drawing::Point(12, 358);

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

this->button4->Size = System::Drawing::Size(245, 23);

this->button4->TabIndex = 5;

this->button4->Text = L"Сгенерировать и вычислить";

this->button4->UseVisualStyleBackColor = true;

//

// groupBox2

//

this->groupBox2->Controls->Add(this->panel2);

this->groupBox2->Location = System::Drawing::Point(399, 12);

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

this->groupBox2->Size = System::Drawing::Size(374, 261);

this->groupBox2->TabIndex = 3;

this->groupBox2->TabStop = false;

this->groupBox2->Text = L"Результат";

//

// panel2

//

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

this->panel2->Controls->Add(this->button5);

this->panel2->Controls->Add(this->button6);

this->panel2->Location = System::Drawing::Point(6, 15);

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

this->panel2->Size = System::Drawing::Size(360, 240);

this->panel2->TabIndex = 10;

//

// dataGridView1

//

this->dataGridView1->Location = System::Drawing::Point(5, 6);

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

this->dataGridView1->Size = System::Drawing::Size(362, 227);

this->dataGridView1->TabIndex = 8;

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

//

// button5

//

this->button5->Location = System::Drawing::Point(263, 358);

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

this->button5->Size = System::Drawing::Size(159, 23);

this->button5->TabIndex = 7;

this->button5->Text = L"Выбор цвета окна";

this->button5->UseVisualStyleBackColor = true;

//

// button6

//

this->button6->Location = System::Drawing::Point(12, 358);

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

this->button6->Size = System::Drawing::Size(245, 23);

this->button6->TabIndex = 5;

this->button6->Text = L"Сгенерировать и вычислить";

this->button6->UseVisualStyleBackColor = true;

//

// groupBox3

//

this->groupBox3->Controls->Add(this->comboBox3);

this->groupBox3->Controls->Add(this->comboBox2);

this->groupBox3->Controls->Add(this->label3);

this->groupBox3->Controls->Add(this->label2);

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

this->groupBox3->Controls->Add(this->comboBox1);

this->groupBox3->Location = System::Drawing::Point(12, 279);

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

this->groupBox3->Size = System::Drawing::Size(720, 75);

this->groupBox3->TabIndex = 4;

this->groupBox3->TabStop = false;

this->groupBox3->Text = L"Настройки";

//

// comboBox3

//

this->comboBox3->FormattingEnabled = true;

this->comboBox3->Location = System::Drawing::Point(473, 36);

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

this->comboBox3->Size = System::Drawing::Size(180, 21);

this->comboBox3->TabIndex = 11;

//

// comboBox2

//

this->comboBox2->FormattingEnabled = true;

this->comboBox2->Location = System::Drawing::Point(230, 36);

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

this->comboBox2->Size = System::Drawing::Size(180, 21);

this->comboBox2->TabIndex = 10;

//

// label3

//

this->label3->AutoSize = true;

this->label3->Location = System::Drawing::Point(456, 20);

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

this->label3->Size = System::Drawing::Size(246, 13);

this->label3->TabIndex = 9;

this->label3->Text = L"Максимальное значение случайного элемента";

//

// label2

//

this->label2->AutoSize = true;

this->label2->Location = System::Drawing::Point(210, 20);

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

this->label2->Size = System::Drawing::Size(240, 13);

this->label2->TabIndex = 8;

this->label2->Text = L"Минимальное значение случайного элемента";

//

// label1

//

this->label1->AutoSize = true;

this->label1->Location = System::Drawing::Point(9, 20);

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

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

this->label1->TabIndex = 7;

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

//

// comboBox1

//

this->comboBox1->FormattingEnabled = true;

this->comboBox1->Location = System::Drawing::Point(12, 36);

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

this->comboBox1->Size = System::Drawing::Size(180, 21);

this->comboBox1->TabIndex = 5;

//

// panel3

//

this->panel3->Controls->Add(this->button2);

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

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

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

this->panel3->Size = System::Drawing::Size(784, 390);

this->panel3->TabIndex = 8;

//

// button2

//

this->button2->Location = System::Drawing::Point(263, 358);

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

this->button2->Size = System::Drawing::Size(159, 23);

this->button2->TabIndex = 7;

this->button2->Text = L"Выбор цвета окна";

this->button2->UseVisualStyleBackColor = true;

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

//

// button1

//

this->button1->Location = System::Drawing::Point(12, 358);

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

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

this->button1->TabIndex = 5;

this->button1->Text = L"Сгенерировать и вычислить";

this->button1->UseVisualStyleBackColor = true;

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

//

// statusStrip1

//

this->statusStrip1->Items->AddRange(gcnew cli::array< System::Windows::Forms::ToolStripItem^ >(1) { this->toolStripStatusLabel1 });

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

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

this->statusStrip1->Size = System::Drawing::Size(785, 22);

this->statusStrip1->TabIndex = 6;

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

this->statusStrip1->ItemClicked += gcnew System::Windows::Forms::ToolStripItemClickedEventHandler(this, &Form1::statusStrip1_ItemClicked);

//

// toolStripStatusLabel1

//

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

this->toolStripStatusLabel1->Size = System::Drawing::Size(118, 17);

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

//

// Form1

//

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

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

this->ClientSize = System::Drawing::Size(785, 417);

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

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

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

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

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

this->Name = L"Form1";

this->Text = L"Floyd Warshall";

this->Load += gcnew System::EventHandler(this, &Form1::Form1_Load);

this->groupBox1->ResumeLayout(false);

this->panel1->ResumeLayout(false);

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

this->groupBox2->ResumeLayout(false);

this->panel2->ResumeLayout(false);

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

this->groupBox3->ResumeLayout(false);

this->groupBox3->PerformLayout();

this->panel3->ResumeLayout(false);

this->statusStrip1->ResumeLayout(false);

this->statusStrip1->PerformLayout();

this->ResumeLayout(false);

this->PerformLayout();

}

#pragma endregion

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

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";

toolStripStatusLabel1->Text= "Можно приступать к вычислениям. Выберите размерность матрицы смежности.";

}

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

int n, i, j, k,a,b;

n = int::Parse(comboBox1->SelectedItem->ToString());

a = int::Parse(comboBox2->SelectedItem->ToString());

b = int::Parse(comboBox3->SelectedItem->ToString());

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);

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];

}

}

}

private: System::Void statusStrip1_ItemClicked(System::Object^ sender, System::Windows::Forms::ToolStripItemClickedEventArgs^ e) {

}

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

colorDialog1->ShowDialog();

panel3->BackColor = colorDialog1->Color;

}

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

colorDialog1->ShowDialog();

panel3->BackColor = colorDialog1->Color;

}

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

}

};

}

8. Тестирование

Для тестирования необходимо изменять настройки в компонентах ComboBox. Для решения задачи необходимо нажимать кнопку «Сгенерировать и вычислить».

Рисунок 5 Окно программы после нажатия кнопки «Сгенерировать и вычислить»



Заключение

В данном курсовом проекте при разработке программы были закреплены навыки объектно-ориентированного программирования на языке С++.

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



Список использованной литературы

Основная литература

1. Анисимов, А.Е. Сборник заданий по основаниям программирования: учеб. пособие / А.Е. Анисимов, В.В. Пупышев. М.: Интернет-ун-т информ. технологий; БИНОМ. Лаборатория знаний, 2006. 348с. <15>

2. Макконелл, Д. Основы современных алгоритмов: учеб. Пособие. М.: Техносфера, 2006. 368 с. <7>

3. Подбельский, В.В. Язык Си+:Учеб. пособие для вузов / В.В. Подбельский. 5-е изд. М.: Финансы и статистика, 2003. 560с. <13>

4. Павловская, Т.А. C/C++:Программирование на языке высокого уровня: Учебник для вузов / Т.А. Павловская. М. и др.: Питер, 2004. 461с.<7>

5. Ганеев, Р.М. Проектирование интерфейса пользователя средствами Win32 API: учеб. пособие для вузов / Р. М. Ганеев. 2-е изд., испр. и доп. М.: Горячая линия-Телеком, 2007. 358 с.<3>

Дополнительная литература

1. Вирт Н. Алгоритмы + структуры данных = программы. М.; Mиp, 1985. 281 с.

2. Шлее, М. Профессиональное программирование на С++ / М. Шлее. СПб.: БХВ-Петербург, 2005. 544с.: ил. + 1 CD. (В подлиннике). <3>

3. Страуструп, Б. Язык программирования Си++:Спец.изд. / Б.Страуструп;Пер.сангл.С.Анисимова,М.Кононова;Подред.Ф.Андреева,А.Ушаков. М.: Бином, 2004. 1098с. <4>



Приложения

Приложение 1

Исходный текст класса (модуль Header.h)

#pragma once

#include <string>

class FloydWarshallClass {

public:

void generate_source(int n,int a, int b)

{

srand(time(NULL));

g1 = new int *[n];

for (int i = 0; i < n; i++) { // (3)

g1[i] = new int[n]; // инициализация указателей

}

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

{

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

{

g1[i][j] = a + rand() % (b - a);

}

}

}

void generate_result(int n)

{

g2 = new int *[n];

for (int i = 0; i < n; i++) { // (3)

g2[i] = new int[n];

}

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

{

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

{

g2[i][j] = g1[i][j];

}

}

for (int k = 0; k < n; k++)

{

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

{

if (g2[i][k] > 0)

{

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

{

if (g2[k][j] > 0 && g2[i][j] > (g2[i][k] + g2[k][j]))

{

g2[i][j] = g2[i][k] + g2[k][j];

}

}

}

}

}

}

public:

int **g1;

int **g2;

};

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