Найти длину кратчайшей ломаной - C#
Формулировка задачи:
Даны координаты N точек на плоскости. Найти длину кратчайшей ломаной, соединяющей эти точки.
возможно только через коммивояжер, который не получается описать
Решение задачи: «Найти длину кратчайшей ломаной»
textual
Листинг программы
- class Program
- {
- static int i, j, n, p, xn, xk;
- static bool[] flag = new bool[11];
- static uint[,] c = new uint[11, 11];
- static uint[] l = new uint[11];
- //static string s = new string(new char[80]);
- //static sbyte[,] path = new sbyte[11,80];
- static int min(int n)
- {
- int i, result=0;
- for (i = 0; i < n; i++)
- if (!(flag[i])) result = i;
- for (i = 0; i < n; i++)
- if ((l[result] > l[i]) && (!flag[i])) result = i;
- return result;
- }
- static uint minim(uint x, uint y)
- {
- if (x < y) return x;
- return y;
- }
- static void Main(string[] args)
- {
- string s="";
- string path="";
- Console.Write("Напишите число точек: ");
- n = Convert.ToInt32(Console.ReadLine());
- for (i = 0; i < n; i++)
- for (j = 0; j < n; j++) c[i,j] = 0;
- for (i = 0; i < n; i++)
- for (j = i + 1; j < n; j++)
- {
- Console.Write(" задайте длины рёбер x");
- Console.Write(i + 1);
- Console.Write(" do x");
- Console.Write(j + 1);
- Console.Write(": ");
- c[i, j] = Convert.ToUInt32(Console.ReadLine());
- }
- Console.Write(" ");
- for (i = 0; i < n; i++)
- {Console.Write(" X");
- Console.Write(i + 1);
- }
- Console.Write("\n");
- Console.Write("\n");
- for (i = 0; i < n; i++)
- {
- Console.Write("X{0:D}", i + 1);
- for (j = 0; j < n; j++)
- {
- Console.Write("{0,6:D}", c[i, j]);
- c[j, i] = c[i, j];
- }
- Console.Write("\n\n");
- }
- for (i = 0; i < n; i++)
- for (j = 0; j < n; j++)
- if (c[i,j] == 0) c[i,j] = 65535; //nekonecno
- Console.Write(" задайте начальную точку: ");
- xn = Convert.ToInt32(Console.ReadLine());
- path = Convert.ToString(xn+" ");
- Console.Write(" задайте конечную точку: ");
- xk = Convert.ToInt32(Console.ReadLine());
- int rem = xk;
- xk--;
- xn--;
- if (xn == xk)
- {
- Console.WriteLine("Начальная и конечные точки совпадают");
- Console.ReadLine();
- return;
- }
- for (i = 0; i < n; i++)
- {
- flag[i] = false;
- l[i] = 65535;
- }
- l[xn] = 0;
- flag[xn] = true;
- p = xn;
- s = Convert.ToString(xn + 1);
- for (i = 1; i <= n; i++)
- {
- }
- do
- {
- for (i = 0; i < n; i++)
- if ((c[p,i] != 65535) && (!flag[i]) && (i != p))
- {
- if (l[i] > l[p] + c[p,i])
- {
- s = Convert.ToString(i + 1);
- }
- l[i] = minim(l[i], l[p] + c[p,i]);
- }
- p = min(n);
- path += n;
- flag[p] = true;
- }
- while (p != xk);
- if (l[p] != 65535)
- {
- path += Convert.ToString(rem);
- Console.Write("Put: ");
- Console.Write(path);
- Console.Write("\n");
- Console.Write("Dlina puti: ");
- Console.Write(l[p]);
- Console.Write("\n");
- }
- else
- Console.Write("Путь не существует!");
- Console.Write("\n");
- Console.ReadLine();
- }
- }
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д