Найти длину кратчайшей ломаной - 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(); } }
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д