Найти длину кратчайшей ломаной - 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();
 
 
 
        }
    }

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


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

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

5   голосов , оценка 3.8 из 5
Похожие ответы