Обоснование выбора средств разработки
На сегодняшний день существует достаточно языков и сред программирования, при помощи которых можно создавать приложения. Наиболее известные: Delphi, Pascal, C# и т.д.
C#, являясь последним из широко распространенных языков программирования, должен впитать в себя весь имеющийся опыт и вобрать лучшие стороны существующих языков программирования, при этом являясь специально созданным для работы в .NET. Сама архитектура .NET продиктовала ему (как и многим другим языкам, на которых можно писать под .NET) объектно-ориентированную направленность. Конечно, это не является правилом, возможно создание компиляторов даже функциональных языков по .NET, на эту тему существуют специальные работы.
Конечно, излюбленным объектом для сравнения с C# у мировой коммьюнити является Java. Также разработанный для работы в виртуальной среде выполнения, имеющей объектно-ориентированную архитектуру и сборщик мусора, осноыванный на механизме ссылок. При сравнении с этим языком сразу выделаются такие особенности, как возможность объявлять несколько классов в одном файле, из чего следует синтаксическая поддержка иерархической системы пространств имен. Из реализации ООП-концепций сходство в механизме наследования и реализации (и в Java и в C# возможно единичное наследование, но множественная реализация интерфейсов,
в отличие от C++). Но в Java отсутствуют свойства и индексаторы (а также делегаты и события, но они отсутствуют еще много где). Также есть возможность перечисления контейнеров.
Из вещей, включенных в спецификацию языка, но не являющихся чисто "программистскими" необходимо отметить возможность использование комментариев в формате XML. Если комментарии отвечают специально описанной структуре, компилятор по ним может сгенерировать единый XML-файл документации.
Но C# внес и свои уникальные черты, которые уже были упомянуты - это события, индексаторы, атрибуты и делагаты. Все эти элементы будут обсуждены в следующих частях, сейчас лишь отмечу, что они предоставляют собой очень полезные возможности, которые не останутся невостребованными.
В результате проведенного анализа наиболее популярных средств программирования можно прийти к выводу, что для реализации поставленных задач наиболее всего подходит язык программирования C#.
3.6 Описание программных модулей
Программа состоит из трех частей - форм.
Первая форма отвечает за задание параметров для создаваемой таблицы. Невозможно продолжить работу с программой, пока первая форма не будет заполнена.
Вторая форма полностью зависима от первой и в зависимости от того, какие параметры заданы в первой форме будет создана таблица во второй форме.
Третья форма выводит ответ из результатов работы программы над условиями, заданными во второй форме.
3.7 Тестирование программы
В результате тестирования программы ни одной ошибки, мешающей работе программы, обнаружено не было. Программа работает при любых заданных условиях. В результате решения задачи данной для тестирования программы, было найдено решение этой задачи, ответ которой полностью совпал с ответом, найденным разработчиком самостоятельно. Программа полностью готова к работе, независимо от того, будет ли пользователь следовать инструкции по использованию программы или нет.
У данной программы есть только один недостаток - если при решении задачи могут иметься несколько вариантов решений, то программа будет рассматривать только одно, так что пользователю будет выведена информация только об одном решении.
.8 Инструкция пользователю
После того как пользователь запустил исполняемый файл, на рабочем столе появится пустое окно (рис В1), в котором пользователь должен ввести цифру количества столбцов и строк таблицы. Число строк соответствует числу городов. Так как созданная таблица будет квадратная , то пользователю достаточно ввести одну цифру.
Далее открывается окно с созданной таблицей (рис. В2), в которую следует ввести цифры из таблицы, данной в качестве условия пользователю. Цифры соответствуют расстояниям между городами. В данном окне так же возможен выбор города, с которого коммивояжер начнет маршрут.
После того, как все поля таблицы заполнены, следует нажать кнопку «Продолжить»
В третьем окне появится результат подсчетов программы, а именно оптимальный маршрут между данными городами и расстояние, потраченное на прохождение этого маршрута.(рис.В3)
Заключение
коммивояжёр программирование нелинейный
В данном курсовом проекте был рассмотрен вопрос о создании программы для решения задачи «коммивояжёра» прямым алгоритмом.
Суть прямого алгоритма в следующем: Имеется N городов, которые должен обойти коммивояжер с минимальными затратами. При этом на его маршрут накладывается два ограничения:
маршрут должен быть замкнутым, то есть коммивояжер должен вернуться в тот город, из которого он начал движение;
в каждом из городов коммивояжер должен побывать точно один раз, то есть надо обязательно обойти все города, при этом не побывав ни в одном городе дважды.
Для расчета затрат существует матрица условий, содержащая затраты на переход из каждого города в каждый, при этом считается, что можно перейти из любого города в любой, кроме того же самого. Целью решения является нахождения маршрута, удовлетворяющего всем условиям и при этом имеющего минимальную сумму затрат.
Для того, чтобы начать решать задачу необходимы условия задачи, в данном случае они представлены в виде таблицы 1. В таблице даны расстояния между городов.
В результате решения задачи самым оптимальным маршрутом между данными городами был выявлен маршрут, состоящий из семи шагов, а именно:
->5->4->3->6->7->2->1.
Длинна пройденного пути для этого маршрута оказалась самой наименьшей:
Q = 22
Ответ совпал с ответом задачи, решенной программистом, значит программа написана верно.
Далее была создана инструкция для пользователей, где программа была полностью расписана.
После того как пользователь запустил исполняемый файл, на рабочем столе появится пустое окно (рис В1), в котором пользователь должен ввести цифру количества столбцов и строк таблицы. Число строк соответствует числу городов. Так как созданная таблица будет квадратная , то пользователю достаточно ввести одну цифру.
Далее открывается окно с созданной таблицей (рис. В2), в которую следует ввести цифры из таблицы, данной в качестве условия пользователю. Цифры соответствуют расстояниям между городами. В данном окне так же возможен выбор города, с которого коммивояжер начнет маршрут.
После того, как все поля таблицы заполнены, следует нажать кнопку «Продолжить»
В третьем окне появится результат подсчетов программы, а именно оптимальный маршрут между данными городами и расстояние, потраченное на прохождение этого маршрута.(рис.В3)
Подведем итог, после всех перечисленных шагов, получилась программа, позволяющая высчитать ответ, согласно решению задач «коммивояжера» все пункты были детально рассмотрены и выполнены, благодаря этому цель курсового проекта была достигнута.
Литература
1.Агальцов В.П., Валдайская И.В. Математические методы в программировании: Учебник. - М.: ИД «ФОРУМ»: ИНФРА-М, 2006. - 224 с.: ил. - (Профессиональное образование).
2.Голицына О.Л., Попов И.И. Основы алгоритмизации и программирования: Учебное пособие. - М.: Форум: Инфра-М, 2014
.Орлов В.В. Технологии разработки программных продуктов. -СПб.: Питер, 2003. - 437 с.
. Партыка т.Л., Попов И.И. Математические методы: Учебник. - М.: ФОРУМ: ИНФРА-М, 2010. - 464с.: ил. - ( Профессиональное образование)
Приложение А. Глоссарий понятий
Задачи коммивояжера.
Прямой алгоритм.
Метод ветвей и границ.
Маршрут.
Форма.
Шаги.
Модуль программы.
Нелинейное программирование.
Таблица.
Функции.
Экономическая постановка задачи.
Математическая постановка задачи.
Блок - схема.
Приложение Б. Текст программы
Форма 1.
using System;System.Collections.Generic;System.ComponentModel;System.Data;System.Drawing;System.Linq;System.Text;System.Windows.Forms;
ex_20
{
public partial class Form1 : Form
{
public Form1()
{
InitializeComponent();
}
int x;
int[,] matrix;
int[,] new_matrix;
int[] second;
int q;
string _q;
string _l;
bool[] vis;
int count;
int j_min;
private void Form1_Load(object sender, EventArgs e)
{
Form2 f2 = new Form2();
f2.ShowDialog();
if (!f2.error)
{
x = f2.getResult();
f2.Dispose();
Form3 f3 = new Form3(x);
f3.ShowDialog();
if (!f3.error)
{
Class1 gr = f3.getResultate();
f3.Dispose();
x = gr.x;
matrix = gr.matrix;
start = gr.start;
string starting = (start + 1).ToString();
vis = new bool[x];
second = new int[x * x];
new_matrix = new int[x, x];
count = 0;
for (int j = 0; j < x * x; j++)
{
for (int i = 0; i < x; i++)
if (i != start && !vis[i])
{
second[count] = matrix[start, i];
j_min = i;
}
if (second[count] != 0)
{
for (int i = 0; i < x; i++)
if (i != start && matrix[start, i] < second[count] && !vis[i])
{
second[count] = matrix[start, i];
j_min = i;
}
if (count == 0)
{
_q = second[count].ToString();
_l = (start + 1).ToString();
}
else
{
_q += string.Format(" + {0}", second[count]);
_l += string.Format(" -> {0}", start + 1);
}
q += second[count];
new_matrix[start, j_min] = second[count];
vis[start] = true;
start = j_min;
vis[j_min] = true;
count++;
}
else
break;
}
_l += string.Format(" -> {0} -> {1}", start + 1, starting);
_q += string.Format(" + {0}", matrix[start, Convert.ToInt16(starting) - 1]);
q += matrix[start, Convert.ToInt16(starting) - 1];
new_matrix[start, Convert.ToInt16(starting) - 1] = matrix[start, Convert.ToInt16(starting) - 1];
label1.Text = string.Format("Q = {0} = {1} L = {2}", _q, q, _l);
int loc_y = 53;
int l_y = 0;
int l_x = 0;
Label[,] lbl = new Label[x,x];
for (int i = 0; i < x; i++)
{
l_y = loc_y * (i + 1);
Label lb = new Label();
lb.Size = new Size(50, 15);
lb.AutoSize = false;
lb.Text = string.Format("Город {0}", i + 1);
lb.Location = new Point(14, l_y);
this.Controls.Add(lb);
for (int j = 0; j < x; j++)
{
l_x = (loc_x + 50) * (j + 1);
if (j == 0)
{
int lo_x = (loc_x + 50) * (i + 1);
Label lab = new Label();
lab.Size = new Size(50, 15);
lab.AutoSize = false;
lab.Text = string.Format("Город {0}", i + 1);
lab.Location = new Point(lo_x, 30);
this.Controls.Add(lab);
}
if (i != j && new_matrix[i, j] != 0)
{
lbl[i, j] = new Label();
lbl[i, j].Text = new_matrix[i, j].ToString();
lbl[i, j].Size = new Size(40, 20);
lbl[i, j].Location = new Point(l_x + 15, l_y);
this.Controls.Add(lbl[i, j]);
}
}
}
return;
}
}
this.Close();
}
}
}
Форма 2.
using System;System.Collections.Generic;System.ComponentModel;System.Data;System.Drawing;System.Linq;System.Text;System.Windows.Forms;
ex_20
{
public partial class Form2 : Form
{
public Form2()
{
InitializeComponent();
button1.Enabled = false;
}
int x = 0;
public bool error = true;
private void button1_Click(object sender, EventArgs e)
{
error = false;
try { x = Convert.ToInt16(textBox1.Text); }
catch
{
MessageBox.Show("Значение введено не верно !");
error = true;
return;
}
if (x < 3)
{
MessageBox.Show("Значение введено не верно !");
error = true;
}
this.Close();
}
private void textBox1_TextChanged(object sender, EventArgs e)
{
if (textBox1.Text.Length != 0)
button1.Enabled = true;
else
button1.Enabled = false;
}
public int getResult() { return x; }
}
}
Форма 3.
using System;System.Collections.Generic;System.ComponentModel;System.Data;System.Drawing;System.Linq;System.Text;System.Windows.Forms;
ex_20
{
public partial class Form3 : Form
{
int x = 0;
TextBox[,] tb;
int[,] matrix;
public Form3(int x)
{
InitializeComponent();
this.x = x;
tb = new TextBox[x, x];
int loc_x = 12;
int loc_y = 53;
int l_y = 0;
int l_x = 0;
for (int i = 0; i < x; i++)
{
l_y = loc_y * (i + 1);
Label lb = new Label();
lb.Size = new Size(50, 15);
lb.AutoSize = false;
lb.Text = string.Format("Город {0}", i + 1);
comboBox1.Items.Add(i + 1);
lb.Location = new Point(14, l_y + 4);
this.Controls.Add(lb);
for (int j = 0; j < x; j++)
{
l_x = (loc_x + 50) * (j + 1);
if (j == 0)
{
int lo_x = (loc_x + 50) * (i + 1);
Label lab = new Label();
lab.Size = new Size(50, 15);
lab.AutoSize = false;
lab.Text = string.Format("Город {0}", i + 1);
lab.Location = new Point(lo_x, 37);
this.Controls.Add(lab);
}
tb[i, j] = new TextBox();
if (i == j)
{
tb[i, j].Text = "∞";
tb[i, j].TextAlign = HorizontalAlignment.Center;
tb[i, j].Enabled = false;
tb[i, j].Font = new System.Drawing.Font("Microsoft Sans Serif", 11F, System.Drawing.FontStyle.Regular, System.Drawing.GraphicsUnit.Point, ((byte)(204)));
}
tb[i, j].Size = new Size(40, 20);
tb[i, j].Location = new Point(l_x, l_y);
this.Controls.Add(tb[i, j]);
}
}
comboBox1.SelectedIndex = 0;
}
public bool error = true;
{
error = false;
matrix = new int[x, x];
for(int i = 0; i < x; i++)
for (int j = 0; j < x; j++)
{
if(i != j)
try { matrix[i, j] = Convert.ToInt16(tb[i, j].Text); }
catch { error = true; }
}
if (error)
{
MessageBox.Show("Значения введены не верно !");
return;
}
this.Close();
}
public Class1 getResultate() { Class1 gr = new Class1(x, matrix, comboBox1.SelectedIndex); return gr; }
}
}
Приложение В. Видовые экраны работы программы
Рис. В1 Форма 1
Рис. В2 Форма 2
Рис. В3 Форма 3