По заданным натуральным числам (-10<=x, y <=10, (x,y) не равно (0,0)) найти длину кратчайшего пути от точки (0,0) до точки (х,у) по сторонам (длины 1) или диагоналям леток, и количество таких путей.
Задача была на городской олимпиаде по информатике. Времени было мало, я сделал таким образом: увеличивала х, пока не наткнешься на х искомой точки, или х точки-препятствия; затем увеличивала у таким же образом; если не доходишь до точки – снова увеличиваешь х, итд. Работает, но далеко не на все случаи (чаще всего выдает не кратчайший путь). Как оптимизировать алгоритм и как посчитать количество путей?
17 марта 2010 в 0:00
Эльмира, а препятствия там все-таки есть или нет?
Если нет и стоимости диагонали и стороны равны, то длина
L = max( abs(x), abs(y) )
И число путей тоже считается аналитически.
16 марта 2010 в 16:04
Хм. А формула Пифагора не тянет?
Как я поняла задание, нужно построить функцию, которая выдавала бы расстояние от 0 до (х,у), при том, что х и у задаются как аргументы пользователем.
Т. е. расстояние высчитыается по формуле квадратный корень из суммы квадратов х и у.
А условие (-10<=x, y <=10, (x,y) не равно (0,0) дается для того, чтобы найти возможное количество таких путей, т.е. комбинаций х и у, где они меняются на 1. Эта другая функция. В функции применяются циклы while или for с прибавлением единицы к x и у каждый раз. Там же все просчитывается, выдается ответ. Это если в лоб решать. А так – лучше, конечно, формулы из комбинаторики применять.
Я, наверно, не поняла задание, потому что слишком бы легко было.
16 марта 2010 в 2:00
Воспринимаю задание таким образом:
По заданным натуральным числам x и y найти длину кратчайшего пути от точки (0,0) до точки (х,у) по сторонам или диагоналям клеток (на выбор), а также количество таких путей. При этом:
1) -10<=x<=10;
2) -10<=y<=10;
3) x не равно 0;
4) y не равно 0;
С ходу такой вариант решения (это только идея):
- строим матрицу, в первой колонке которой – возможные "пути", а во второй колонке – "длины" этх путей (путь определяем рекурсивно смещаясь от начальной координаты в сотрону конечной точки, инкрементируя/декрементируя величину чисел координат);
- определяем "минимум" (кратчайший путь, измеренный в сторонах клеток) – это наименьшее число среди всех значений из второго столбца матрицы "путь/длина";
- определяем "количество путей", подсчитав по второму столбцу количество только тех ячеек, значения которых совпадают с "минимумом".
Матрица сама по себе большая (число строк увеличивается геометрически в зависимости от значений пределов x и y), так что с целью экономии ресурсов памяти можно выбросить её и обойтись рекурсией в купе с парой-тройкой значимых переменных, однако при этом значительно усложнится часть дополнительных проверок, которая находится в теле цикла рекурсии. Если решение не требует скорости выполнения расщетов, то проще использовать матрицу.
Остается только поколдавать над телом рекурсивного цикла, задача которого – построить матрицу…
15 марта 2010 в 22:04
Видимо, надо поправить, сумма количеств путей до вершин, из которых можно попасть в эту вершину по кратчайшему пути. Нам же надо найти в результате количество кратчайших путей.
15 марта 2010 в 22:03
Ну просто кол-во путей для вершины – сумма количеств путей до вершин, из которых можно попасть в эту вершину.
15 марта 2010 в 21:02
2 Веном int 0×80 Кац: Объясните, пожалуйста, какой алгоритм Вы имеете в виду, я постараюсь разобраться. Что насчет олимпиады – там вообще не смотрели исходники, делай как знаешь, хоть рандомом ответы генерируй.
2 Михаил [The_Grass_Was_Greener] Асташкевич: В таком случае как искать количество путей?
15 марта 2010 в 21:01
а по прямой нельзя чтоль?
15 марта 2010 в 21:01
Тут вроде есть какие-то точки-препятствия.
15 марта 2010 в 20:02
Найдем.
15 марта 2010 в 20:01
А почему бы не написать просто поиск в ширину\глубину? Или алгоритм Дейкстры?
15 марта 2010 в 20:01
Количество путей не найдете.
15 марта 2010 в 19:03
Я бы вообще использовал другой алгоритм. Но тут требуется знать, на какой уровень рассчитана олимпиада.