program ATC;
const
n = 10;
var
test1:array[1..n] of integer;{сюда записываем кол-во проводов,которое нужно протянуть}
street:array[1..n] of integer;{улица из n домов, street - кол-во телефонов в каждом доме}
count,min,i,j:integer;
begin
Randomize();
for i:=1 to n do
street:=random(10);
for i:=1 to n do
for j:=1 to n do
begin
test1:=Abs(i-j)*street[j]+test1;
end;
{далее ищем минимальный элемент и номер позиции- тут и ставим АТС}
Телефонная станция.
Найти место размещения телефонной станции на прямой улице, состоящей из N домов с заданным для каж-дого дома количеством телефонов.
Решил задачу в лоб. Но нужно еще как минимум 2 алгоритма.
Станция должна располагаться так, чтобы от нее тянулось как можно меньше проводов. Пример: дан массив из 3-х элементов - 3, 2, 8. Ставим станцию на первую позицию. Считаем длину проводов - 2*1+8*2=18. Ставим на 2-ю позицию - 3*1+8*1=11. На 3-й позиции - 3*2+2*1=8. Т.е внутри дома проводов нет. Отсюда выбираем 3-й дом для станции.
Решил задачу в лоб. Но нужно еще как минимум 2 алгоритма.
Станция должна располагаться так, чтобы от нее тянулось как можно меньше проводов. Пример: дан массив из 3-х элементов - 3, 2, 8. Ставим станцию на первую позицию. Считаем длину проводов - 2*1+8*2=18. Ставим на 2-ю позицию - 3*1+8*1=11. На 3-й позиции - 3*2+2*1=8. Т.е внутри дома проводов нет. Отсюда выбираем 3-й дом для станции.
Код:
Цитата: K1mi
Найти место размещения телефонной станции на прямой улице, состоящей из N домов с заданным для каж-дого дома количеством телефонов.
Решил задачу в лоб. Но нужно еще как минимум 2 алгоритма.
Станция должна располагаться так, чтобы от нее тянулось как можно меньше проводов. Пример: дан массив из 3-х элементов - 3, 2, 8. Ставим станцию на первую позицию. Считаем длину проводов - 2*1+8*2=18. Ставим на 2-ю позицию - 3*1+8*1=11. На 3-й позиции - 3*2+2*1=8. Т.е внутри дома проводов нет. Отсюда выбираем 3-й дом для станции.
Решил задачу в лоб. Но нужно еще как минимум 2 алгоритма.
Станция должна располагаться так, чтобы от нее тянулось как можно меньше проводов. Пример: дан массив из 3-х элементов - 3, 2, 8. Ставим станцию на первую позицию. Считаем длину проводов - 2*1+8*2=18. Ставим на 2-ю позицию - 3*1+8*1=11. На 3-й позиции - 3*2+2*1=8. Т.е внутри дома проводов нет. Отсюда выбираем 3-й дом для станции.
Я бы начал простматривать дома с наибольшим количеством телефонов и максимально близких к центру.
Я взял 7 случайных чисел и посчитал длину линий( надеюсь, посчитал правильно). Вот что получилось:
1 3 8 5 1 2 9
1(1): 3+16+15+4+10+54=102
2(3): 1+8+10+3+8+45=75
3(8): 3+2+5+2+6+36=54
4(5): 8+6+3+1+4+27=49
5(1): 2+18+5+16+9+4=54
6(2): 9+1+10+24+12+5=61
7(9): 2+2+15+32+15+6=72
Зависимость просматривается хорошо: Чем дальше от центра, тем больше длина линий.
Идея такая:
Берем централый дом(если их число нечетное) или (если число домов четное) тот из двух центральных, в котором телефонов больше. Считаем длину линий по обе стороны от этого дома. И начинаем двигаться в сторону, где длина линий больше и считаем длину линий от каждого дома до тех пор, пока длины линий слева и справа не будут примерно равны.
Далее сравниваем длины линий в результате цикла, и от среднего дома.
Выбираем меньшую.
Не уверен, что это будет работать, не проверял, т.к. придумал только что. Но если очень надо, можно реализовать.:)