Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > .NET для новичков > минимальное количество прыжков

Автор: blackwitcher 15.3.2016, 12:49

Круг разбитый на 160 сегментов
Всего 16 секторов и 10 колец.
В дальнейшем каждый сегмент задается номером кольца (от 1 до 10 считая от центра) и номером сектора (от 1 до 16 по ходу часовой стрелки)
Например (1, 16) это сегмент, который расположен на первом кольце от центра и в 16 секторе.
На круге находится лягушка возвращена по ходу часовой стрелки.
Лягушка может прыгнуть в 5 точек относительно своего первоначального положения:
● на том же кольце на 3 сектора вперед
● на 1 кольцо ближе к центру и на 2 сектора вперед
● на 1 кольцо дальше от центра и на 2 сектора вперед
● на 2 кольца ближе к центру и на 1 сектор вперед
● на 2 кольца дальше от центра и на 1 сектор вперед
Лягушка не может выпрыгнуть за круг, не может развернуться, и не может прыгать через
центр.
Лягушка не может прыгать на сегменты, которые заняты деревьями (на рисунке (9, 14) и (8, 5))
Задание:
Напишите программу, которая возвращает минимальное количество прыжков, что необходимо сделать
лягушке для того, чтобы добраться из начального сегмента в конечном.
Входные параметры: начальный и конечный сегменты, количество деревьев, координаты
сегментов занятых деревьями.
В выводе программы необходимо отметить минимальное количество и минимальный путь, или
сообщение о невозможностью добраться из исходного положения в конечное.

smile

Большое спасибо

Автор: blackwitcher 15.3.2016, 13:23

Код


public int solution(int X, int[] A) 
{
    bool[] tiles = new bool[X];
    int todo = X;

    for (int i = 0; i < A.Length; i++)
    {
        int internalIndex = A[i] - 1;
        if (!tiles[internalIndex])
        {
            todo--;
            tiles[internalIndex] = true;
        }

        if (todo == 0)
            return i;
    }

    return -1;
}

кое-что нашел, но это не то, где мне нужно в этом коде вписать начальные значения 7,11 я понимаю, что нужно делать двухмерный массив, но как?

Автор: blackwitcher 15.3.2016, 18:17

Код


namespace frogtest
{
    public class Frog
    {
        public static int NumberOfWays(int n)
        {
            return NoOfPermutaions(NoOfCombinations(n));
        }

        private static List<Tuple<int, int>> NoOfCombinations(int distance)
        {
            List<Tuple<int, int>> lst = new List<Tuple<int, int>>();
            for (int i = 0; i <= distance; i++)
                for (int j = 0; j <= distance; j++)
                {
                    if ((i * 1 + j * 2) == distance) lst.Add(new Tuple<int, int>(i, j));
                }
            return lst;
        }

        private static int NoOfPermutaions(List<Tuple<int, int>> lst)
        {
            int Sum = 0;
            foreach (Tuple<int, int> itm in lst)
            {
                Sum += Convert.ToInt32(Factorial(itm.Item1 + itm.Item2) / Factorial(itm.Item1) / Factorial(itm.Item2));
            }

            return Sum;
        }

        private static double Factorial(double num)
        {
            if (num <= 1)
                return 1;
            return num * Factorial(num - 1);
        }

        public static void Main(string[] args)
        {
            Console.WriteLine(NumberOfWays(3));
        }
    }
}

Кое-что, но это не совсем верно smile

Автор: Angel_666 16.3.2016, 11:27

Алгоритм похож на это http://ru.vingrad.com/Perevod-programmnogo-koda-s-C-na-Java-id561ad20eae2015910e8b4567
особенно если круг представить в виде доски.

Этот ответ добавлен с нового Винграда - http://ru.vingrad.com/minimalnoye-kolichestvo-pryzhkov-id56e7db06ae2015de728b4567#findElement_E7045_56e918faae20155075009bf4_0

Автор: blackwitcher 16.3.2016, 14:44

Код


static void Main(string[] args)
        {
            int[,] circle = new int[10, 16];
            int i, j;
            for(i=0;i<10;++i)
            {
                for(j=0;j<16;++j)
                {
                    circle[i, j] = (i * 16) + j + 1;
                    Console.Write(circle[i, j] + " ");
                }
                Console.WriteLine();
            }
            Console.ReadKey();
        }

я развернул круг в виде таблицы, а как дальше? smile