Алгоритмы решения задач
Задача №5
Даны координаты N населенных пунктов (N<=10), (x(N), y(N)). Численность населения в каждом из них K(N). В одном из них необходимо расположить центр скорой медицинской помощи. После определения центра населенные пункты будут соединены с ним прямыми дорогами. Составить программу вычисления координат центра, исходя из условия, что транспортные затраты, зависящие от расстояния до медицинского центра и количества населения, должны быть минимальны. Задача №6 Садовник поливает шлангом деревья в саду и начинает движение от калитки в начале координат (юго-западный угол сада). Считать, что ось X направлена на восток, а ось Y - на север. Координаты N деревьев 0 <= X(I), Y(I) <= 500; I = 1,2,...,N; N <= 100. Все координаты - целые числа. Вычислить минимальную длину маршрута для садовника Lmin с точностью до 1 м. Округление выполнять только после завершения вычисления Lmin. Каждый входной файл Test3B.txt имеет следующую структуру: первая строка - число N; далее следуют N строк с координатами деревьев X(I), Y(I), разделенные пробелом. Выходной файл Result3B.txt содержит только одну строку - число Lmin. Например, при N = 10; (X(I), Y(I)) = (94,163), (14,58), (50,40), (14,103), (10,10), (74,58), (54,163), (94,103), (50,10), (74,40); Lmin = 397,0 м. Прошу помочь с решением этих задач. (Программы не нужны (сам напишу), нужны только алгоритмы их решения.) Или подтолкните в нужную сторону :) P.S. На счет 6 задачи думал, что нужно упорядочить массив координат деревьев сначала по оси X по возрастающей и посчитать путь садовника, затем по оси Y по возрастающей, снова посчитать путь, и Lmin будет наименьшим из найденных путей. Но после проверки оказалось, что решение неверно. Алгоритм решения 5 задачи вообще не знаю даже :( |
Hekumok,
5.рисуем круги с нарастанием - центр круга пункт -- чем больше народа тем меньше прирастает радиус -- пересечение всех кругов и даст оптимальное место |
хм, рони, но это не гарантирует, что круги пересекутся в каком-то населенном пункте. Да и как узнать, в какой пропорции должен уменьшаться радиус? :-?
|
Дзен-трансгуманист, благодарю)
Так значит расположение центра нужно было находить, исходя из стоимости каждой дороги, которая находится умножением населения на длину дороги :) и как я не додумался?) |
Цитата:
|
Цитата:
|
Hekumok,
0,0 14.142135623730951 10,10 40 50,10 30 50,40 24 74,40 18 74,58 49.24428900898052 94,103 60 94,163 40 54,163 72.11102550927978 14,103 45 14,58 392 может я где-то ошибся 392 а не 397 получилось |
рони, а какой алгоритм вы использовали, чтобы получить координаты деревьев именно в такой последовательности? :)
|
Цитата:
P.S. ))) и получил формулу которую Дзен-трансгуманист, написал выше |
чё-т я туплю) вот получил я эту точку, используя предыдущий алгоритм (без населения, естественно) - x: 74, y: 40, а как мне дальше от нее плясать? Не пойму
|
Hekumok, начинаем с 0,0
тупой перебор всех точек до которой короче - её запоминаем - записываем растояние -- запомненную точку убираем из массива -- ищем до какой короче ... и т.д. |
Hekumok, мой вариант
<!DOCTYPE html>
<html>
<head>
<title>Untitled</title>
</head>
<body>
<script>
var a = [[94,163], [14,58], [50,40], [14,103], [10,10], [74,58], [54,163], [94,103], [50,10], [74,40]];
var Lmin = 0,
n = 0,
f = [[0, 0]],
N = a.length;
for (var i = 0; i < N; i++) {
var c = a[0][0] - f[0][0],
d = a[0][1] - f[0][1],
temp = Math.sqrt(c * c + d * d);
for (var j = 1; j < a.length; j++) {
c = a[j][0] - f[0][0],
d = a[j][1] - f[0][1];
if (Math.sqrt(c * c + d * d) < temp) {
temp = Math.sqrt(c * c + d * d);
n = j
}
}
document.write(f + "<br>" + temp + "<br>")
Lmin += temp
f = a.splice(n, 1);
n = 0;
}
document.write(f + "<br>" + Math.round(Lmin))
</script>
</body>
</html>
|
рони, понял, спасибо :)
|
Дзен-трансгуманист, спасибо за ссылки)
рони, вашим способом получается 406( |
Hekumok,
Про деревья вроде кратчайший путь,(если круговой с возвратом к калитке), по вершинам многоугольника максимально близкого к выпуклому |
Deff, я чё-т не представляю, как это сделать :blink:
|
Цитата:
|
Вариант с возвратом на 10 пар, алгоритм тотже ближайший сосед
маршрут выбран в результате [[0,0],[50,10],[50,40],[74,40],[74,58],[94,103],[94,163],[54,163],[14,103],[14,58],[10,10],[0,0]] немного походит на Цитата:
var a = [[94,163], [14,58], [50,40], [14,103], [10,10], [74,58], [54,163], [94,103], [50,10], [74,40]];
var Lmin = 0,
n = 0,
f = [[0, 0]],ff = [[0,0]],
N = a.length;
for (var i = 0; i < 5; i++) {
var c = a[0][0] - f[0][0],
d = a[0][1] - f[0][1],
temp = Math.sqrt(c * c + d * d);
for (var j = 1; j < a.length; j++) {
c = a[j][0] - f[0][0],
d = a[j][1] - f[0][1];
if (Math.sqrt(c * c + d * d) < temp) {
temp = Math.sqrt(c * c + d * d);
n = j
}
}
Lmin += temp
f = a.splice(n, 1);
n = 0;
var c = a[0][0] - ff[0][0],
d = a[0][1] - ff[0][1],
temp = Math.sqrt(c * c + d * d);
for (var j = 1; j < a.length; j++) {
c = a[j][0] - ff[0][0],
d = a[j][1] - ff[0][1];
if (Math.sqrt(c * c + d * d) < temp) {
temp = Math.sqrt(c * c + d * d);
n = j
}
}
Lmin += temp
ff = a.splice(n, 1);
n = 0;
}
c = f[0][0] - ff[0][0],
d = f[0][1] - ff[0][1];
temp = Math.sqrt(c * c + d * d);
Lmin += temp
alert(Math.round(Lmin))
|
Цитата:
|
Цитата:
|
| Часовой пояс GMT +3, время: 17:34. |