Найти длину кратчайшей ломаной - C#

Узнай цену своей работы

Формулировка задачи:

Даны координаты N точек на плоскости. Найти длину кратчайшей ломаной, соединяющей эти точки.
возможно только через коммивояжер, который не получается описать

Решение задачи: «Найти длину кратчайшей ломаной»

textual
Листинг программы
  1. class Program
  2.     {
  3.         static int i, j, n, p, xn, xk;
  4.         static bool[] flag = new bool[11];
  5.         static uint[,] c = new uint[11, 11];
  6.         static uint[] l = new uint[11];
  7.         //static string s = new string(new char[80]);
  8.         //static sbyte[,] path = new sbyte[11,80];
  9.         static int min(int n)
  10.         {
  11.             int i, result=0;
  12.             for (i = 0; i < n; i++)
  13.                 if (!(flag[i])) result = i;
  14.             for (i = 0; i < n; i++)
  15.                 if ((l[result] > l[i]) && (!flag[i])) result = i;
  16.             return result;
  17.         }
  18.         static uint minim(uint x, uint y)
  19.         {
  20.             if (x < y) return x;
  21.             return y;
  22.         }
  23.         static void Main(string[] args)
  24.         {
  25.             string s="";
  26.             string path="";
  27.             Console.Write("Напишите число точек: ");
  28.  
  29.  
  30.             n = Convert.ToInt32(Console.ReadLine());
  31.            
  32.             for (i = 0; i < n; i++)
  33.                 for (j = 0; j < n; j++) c[i,j] = 0;
  34.             for (i = 0; i < n; i++)
  35.                 for (j = i + 1; j < n; j++)
  36.                 {
  37.                     Console.Write(" задайте длины рёбер  x");
  38.                     Console.Write(i + 1);
  39.                     Console.Write(" do x");
  40.                     Console.Write(j + 1);
  41.                     Console.Write(": ");
  42.                     c[i, j] = Convert.ToUInt32(Console.ReadLine());
  43.  
  44.                 }
  45.             Console.Write("   ");
  46.             for (i = 0; i < n; i++)
  47.             {Console.Write("    X");
  48.             Console.Write(i + 1);
  49.         }
  50.         Console.Write("\n");
  51.         Console.Write("\n");
  52.  
  53.             for (i = 0; i < n; i++)
  54.             {
  55.                 Console.Write("X{0:D}", i + 1);
  56.  
  57.                 for (j = 0; j < n; j++)
  58.                 {
  59.                     Console.Write("{0,6:D}", c[i, j]);
  60.                     c[j, i] = c[i, j];
  61.                 }
  62.                 Console.Write("\n\n");
  63.  
  64.             }
  65.             for (i = 0; i < n; i++)
  66.                 for (j = 0; j < n; j++)
  67.                     if (c[i,j] == 0) c[i,j] = 65535; //nekonecno
  68.             Console.Write(" задайте начальную точку: ");
  69.             xn = Convert.ToInt32(Console.ReadLine());
  70.             path = Convert.ToString(xn+" ");
  71.             Console.Write(" задайте конечную точку: ");
  72.             xk = Convert.ToInt32(Console.ReadLine());
  73.             int rem = xk;
  74.             xk--;
  75.             xn--;
  76.             if (xn == xk)
  77.             {
  78.                
  79.                 Console.WriteLine("Начальная и конечные точки совпадают");
  80.                 Console.ReadLine();
  81.                 return;
  82.             }
  83.  
  84.             for (i = 0; i < n; i++)
  85.             {
  86.                 flag[i] = false;
  87.                 l[i] = 65535;
  88.             }
  89.             l[xn] = 0;
  90.             flag[xn] = true;
  91.             p = xn;
  92.            
  93.             s = Convert.ToString(xn + 1);
  94.             for (i = 1; i <= n; i++)
  95.             {
  96.                
  97.  
  98.             }
  99.             do
  100.             {
  101.                 for (i = 0; i < n; i++)
  102.                     if ((c[p,i] != 65535) && (!flag[i]) && (i != p))
  103.                     {
  104.                         if (l[i] > l[p] + c[p,i])
  105.                         {
  106.                            
  107.                             s = Convert.ToString(i + 1);
  108.                      
  109.  
  110.                            
  111.                         }
  112.                         l[i] = minim(l[i], l[p] + c[p,i]);
  113.                     }
  114.                 p = min(n);
  115.                 path += n;
  116.                 flag[p] = true;
  117.             }
  118.             while (p != xk);
  119.          
  120.             if (l[p] != 65535)
  121.             {
  122.                 path += Convert.ToString(rem);
  123.                 Console.Write("Put: ");
  124.                 Console.Write(path);
  125.                 Console.Write("\n");
  126.                 Console.Write("Dlina puti: ");
  127.                 Console.Write(l[p]);
  128.                 Console.Write("\n");
  129.  
  130.             }
  131.             else
  132.                 Console.Write("Путь не существует!");
  133.             Console.Write("\n");
  134.  
  135.             Console.ReadLine();
  136.  
  137.  
  138.  
  139.         }
  140.     }

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

5   голосов , оценка 3.8 из 5

Нужна аналогичная работа?

Оформи быстрый заказ и узнай стоимость

Бесплатно
Оформите заказ и авторы начнут откликаться уже через 10 минут
Похожие ответы