простая алгоритмическая задача

tengiz · Post by **tengiz** » 21 Feb 2002 04:37

Найти "центр тяжести" массива чисел - т.е. для массива длиной n найти i, так чтобы разница между сумммами sum(0..i-1) и sum(i..n-1) была минимальна.

Andrey S · Post by **Andrey S** » 21 Feb 2002 06:27

<blockquote>quote:<hr>Originally posted by tengiz:
Найти "центр тяжести" массива чисел - т.е. для массива длиной n найти i, так чтобы разница между сумммами sum(0..i-1) и sum(i..n-1) была минимальна.<hr></blockquote> Или два прохода, или один, но с таким-же массивом. Или можно лучше?

p.s. О! Вроде можно n+log2(n) при наличии log2(n) памяти. Но это влом... [img:375d03c76e]images/smiles/icon_smile.gif[/img:375d03c76e]

Vovka · Post by **Vovka** » 21 Feb 2002 13:45

А если просто идти одновременно с обоих концов массива, считая по пути суммы и приближаясь с того конца, где эта сумма меньше? [img:5d777ad11c]images/smiles/icon_wink.gif[/img:5d777ad11c]

Забыл дописать. Если суммы равны, то нужно начать алгоритм заново с массивом, образованным из исходного отбрысыванием пройденных концов.

[ 21-02-2002: Message edited by: Vovka ]

Drom · Post by **Drom** » 21 Feb 2002 19:00

how about negative numbers?

8K · Post by 8K » 21 Feb 2002 20:48

Да не, это все не интересно. Вот в "Работе" товарищ dB13 в кармане кукиш держит и никому не показывает (пардон, не кукиш, а хитрое и очень быстрое решение для подсчета количества битов). Вот та задача интересная. Но я, пожалуй, пошел сдаваться.

lx_uk · Post by **lx_uk** » 21 Feb 2002 21:34

<blockquote>quote:<hr>Originally posted by Andrey S.:
 Или два прохода, или один, но с таким-же массивом. Или можно лучше?

p.s. О! Вроде можно n+log2(n) при наличии log2(n) памяти. Но это влом... [img:653abb13e0]images/smiles/icon_smile.gif[/img:653abb13e0] <hr></blockquote>

Среднее арифметическое даст "серединную точку".

bumbo · Post by **bumbo** » 21 Feb 2002 21:36

определяем сумму всех элементов и делим на 2.
в цикле из полученного результата вычитаем каждый элемент слева направо. тот элемент на котором разница перешла в минус и есть 'центр тяжести'

на перле где-то так:

<blockquote>code:<hr><pre>
print "Enter array scope: ";
chop ($N=<STDIN> [img:5ee1250efb]images/smiles/icon_wink.gif[/img:5ee1250efb] ;
$len=0;
for ($i=0; $i<=$N-1; $i++) {
print "A[$i] = ";
chop($A[$i]=<STDIN> [img:5ee1250efb]images/smiles/icon_wink.gif[/img:5ee1250efb] ;
if ($len<length($A[$i]) {
$len=length($A[$i]
}
}
print "\n";
$X=-100;
$sum=0;
for ($i=0; $i<=$#A; $i++) {
$sum=$sum+$A[$i];
}
$sum1=$sum/2;

for ($i=0; $i<=$#A; $i++) {
$sum1=$sum1-$A[$i];
if ($sum1<0&&$X==-100) {
if (($sum1*2+$A[$i])>0) {
$X=$i;
}
else {
$X=$i-1;
}
}
}
print "Array element is looked for: A[$X] \n";</pre><hr></blockquote>

[ 21-02-2002: Message edited by: bumbo ]

8K · Post by 8K » 21 Feb 2002 22:06

<blockquote>quote:<hr>Originally posted by Drom:
how about negative numbers?<hr></blockquote>

А что с ними? Нули мешают - это да. Но это уже к постановщику задачи.

Andrey S · Post by **Andrey S** » 21 Feb 2002 23:10

<blockquote>quote:<hr>Originally posted by 8K:
Не думаю, что есть алгоритм лучше, чем идти с двух концов. Массив-то неотсортированный. Кстати, при чем тут "золотое" сечение-то? Или вы дихотомию имели в виду?<hr></blockquote> Je ne znaju, chto ja imel v vidu, ja v matenatike profan. No -
mi ishem "0" ot funktsii F(x)=S(x)-(S(n)-S(x)) = 2*S(x)-S(n) . pri chislax >0 eta funktsija nachinajetsja nizhe nulja, konchajetsja vishe, i F(i+1) >= F(i) . dlja etoj zadachi (poisk 0 dlja takoj F) est' raznije algoritmi, i algoritm zolotogo setchenija -optimalnij.

Drom · Post by **Drom** » 22 Feb 2002 01:51

<blockquote>quote:<hr>Originally posted by 8K:


А что с ними? Нули мешают - это да. Но это уже к постановщику задачи.<hr></blockquote>

nah. negatives allow to have more than one "almost equilibriums".

omnibee · Post by **omnibee** » 22 Feb 2002 02:03

Красивое решение с двух концов. Снимаю шляпу! [img:e2cbeccb63]images/smiles/icon_smile.gif[/img:e2cbeccb63]

Andrey S · Post by **Andrey S** » 22 Feb 2002 09:02

<blockquote>quote:<hr>Originally posted by Vovka:
А если просто идти одновременно с обоих концов массива, считая по пути суммы и приближаясь с того конца, где эта сумма меньше? [img:f736a56d2d]images/smiles/icon_wink.gif[/img:f736a56d2d]

Забыл дописать. Если суммы равны, то нужно начать алгоритм заново с массивом, образованным из исходного отбрысыванием пройденных концов.

[ 21-02-2002: Message edited by: Vovka ]<hr></blockquote>
chto ja imel vvidu. pust' S(i) - summa vsex elementov ot 1 do i . Togda zadacha svoditsja k naxozhdeniju nulja F(i) = 2*S(i)-S(n) . dlja etoj zadachi est' algoritmi luchshe, chem "sleva napravo" ili "s dvux kontsov", naprimer zolotoje setchenije. pravda pri otritsatelnix chislax, kak uzhe skazali, rabotat' ne budet. zagvozdka - kak vichislit' S(i) i S(n) . Esli est' pamjat' - vse za odin proxod. esli net - to n + exp(n) . i est' promezhutochnije reshenija (xranit' summu kazhdux 10,etc chisel - 10% pamjati).

8K · Post by 8K » 22 Feb 2002 09:54

Не думаю, что есть алгоритм лучше, чем идти с двух концов. Массив-то неотсортированный. Кстати, при чем тут "золотое" сечение-то? Или вы дихотомию имели в виду?

lx_uk · Post by **lx_uk** » 22 Feb 2002 21:23

<blockquote>quote:<hr>Originally posted by lx_uk:


Среднее арифметическое даст "серединную точку".<hr></blockquote>

Гм. И чего это я подумал, что массив отсортирован?

Тогда есть такое решение: y = sum(i*x[i])/sum(x[i])

i - индекс от 0 до n,
x[i] - соответственно i-ый элемент массива.

Получаем "условный" центр тяжести. Если y дробное число - тогда делим массив на 0..(int)y и (int)y+1..n. Если целое, то элемент x[y] можно отнести как в правую так и в левую половины. O(n).

[ 22-02-2002: Message edited by: lx_uk ]

[ 22-02-2002: Message edited by: lx_uk ]

Globus · Post by **Globus** » 24 Feb 2002 18:05

а если видоизменить условие задачи?
найти центр тяжести массива при условии что элементы массива можно менять местами.
т.е. найти в заданном множестве два таких подмножества разница сумм элементов которых будет минимальна.

tengiz · Post by **tengiz** » 24 Feb 2002 20:59

<blockquote>quote:<hr>Originally posted by Globus:
а если видоизменить условие задачи?
найти центр тяжести массива при условии что элементы массива можно менять местами.
т.е. найти в заданном множестве два таких подмножества разница сумм элементов которых будет минимальна.<hr></blockquote>Тогда получается слегка модифицированный вариант The Knapsack Problem. Что уже несравнимо по сложности с исходной задачкой. Целая диссертация. И участие в дискусии на Привете придётся приравнять к публикации в специальной периодике... [img:54f3c59bfc]images/smiles/icon_razz.gif[/img:54f3c59bfc]

listen_me_now · Post by **listen_me_now** » 26 Feb 2002 12:57

Я немного потестировал вашу задачу .
В 1-м варианте я брал n=100 ,
и генерация чисел : s[i]= rand()%100 .
Оказалось , центр тяжести лежит в диапазоне n={45...55}
с вероятностью в 99% .
В 2-м варианте я брал n=1000 ,
и генерация чисел : s[i]= rand()%1000 .
Диапазон центра тяжести сузился к n=500 где-то раза в 2 с той же вероятностью .
Впрочем , это мало что дает для решения .