.NET 4.x Динамическое программирование: задача о черепашке - C#

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

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

Задача о черепашке. Дан 2х мерный массив с очками (длиной пути ну и.т.д.). Найти кротчайший путь из точки

А

в точку

Б

. Пример верной работы:
{ 1, 3, 4, 8 }, { 5, 6, 2, 0 }, { 1, 3, 4, 2 }, { 0, 1, 8, 6 }, { 7, 4, 5, 1 }

1 4 8

8 5 6

10 10

1 3 4

12

0 1 8

18

7 4 5

19

Но при таком
{ 1, 3, 4, 8 }, { 5, 6, 2, 0 }, { 1, 3, 4, 2 }, { 0, 1, 8, 60 }, { 7, 4, 5, 1 }
она работает не верно вместо:

1 4 8

8 5 6

10 10

1 3

16

12

0 1

24

60 7 4

29

30

Она

1 4 8

8 5 6

10 10

1 3 16

12

0 1 24

72

7 4 5

73

    class Program
    {
        static public void print(int[,] a)
        {
            for (int i = 0; i < a.GetLength(0); i++, Console.WriteLine())
                for (int j = 0; j < a.GetLength(1); j++)
                    Console.Write(a[i, j] + " ");
        }
        static void herepahka(int[,] a, int i, int j)
        {
            Console.WriteLine();
            if (i + 1 < a.GetLength(0) && j + 1 < a.GetLength(1))
            {
                if (a[i, j] + a[i + 1, j] <= a[i, j] + a[i, j + 1])
                {
                    a[i + 1, j] += a[i, j];
                    print(a);
                    herepahka(a, i + 1, j);
                }
                else
                {
                    a[i, j + 1] += a[i, j];
                    print(a);
                    herepahka(a, i, j + 1);
                }
            }
            else
            {
                if (i + 1 < a.GetLength(0))
                {
                    a[i + 1, j] += a[i, j];
                    print(a);
                    herepahka(a, i + 1, j);
                }
                if (j + 1 < a.GetLength(1))
                {
                    a[i, j + 1] += a[i, j];
                    print(a);
                    herepahka(a, i, j + 1);
                }
                print(a);
            }
        }
        static void Main(string[] args)
        {
            Console.WriteLine("Vvedite razmer polia");
            int[,] a = { 
                       { 1, 3, 4, 8 }, 
                       { 5, 6, 2, 0 }, 
                       { 1, 3, 4, 2 }, 
                       { 0, 1, 8, 60 }, 
                       { 7, 4, 5, 1 } };
            print(a);
            Console.WriteLine();
            herepahka(a, 0, 0);
            
            Console.ReadKey();
        }
}
ap...

Решение задачи: «.NET 4.x Динамическое программирование: задача о черепашке»

textual
Листинг программы
int[,] a = {{ 0, 0, 0, 8 }, 
            { 5, 6, 0, 5 }, 
            { 0, 0, 0, 2 }, 
            { 0, 1, 8, 1 }, 
            { 0, 0, 0, 0 } };

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


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

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

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