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

[tengiz]

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

[Andrey S]

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

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

[Vovka]

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

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

[ 21-02-2002: Message edited by: Vovka ]</p>

[Drom]

how about negative numbers?

[8K]

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

[lx_uk]

<blockquote><font size="1" face="Arial, Verdana, Helvetica, sans-serif">quote:</font><hr>Originally posted by Andrey S.:
<strong> Или два прохода, или один, но с таким-же массивом. Или можно лучше?

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

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

[bumbo]

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

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

<blockquote><font size="1" face="Arial, Verdana, Helvetica, sans-serif">code:</font><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 ]</p>

[8K]

<blockquote><font size="1" face="Arial, Verdana, Helvetica, sans-serif">quote:</font><hr>Originally posted by Drom:
<strong>how about negative numbers?</strong><hr></blockquote>

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

[Andrey S]

<blockquote><font size="1" face="Arial, Verdana, Helvetica, sans-serif">quote:</font><hr>Originally posted by 8K:
<strong>Не думаю, что есть алгоритм лучше, чем идти с двух концов. Массив-то неотсортированный. Кстати, при чем тут "золотое" сечение-то? Или вы дихотомию имели в виду?</strong><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]

<blockquote><font size="1" face="Arial, Verdana, Helvetica, sans-serif">quote:</font><hr>Originally posted by 8K:
<strong>

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

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

[omnibee]

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

[Andrey S]

<blockquote><font size="1" face="Arial, Verdana, Helvetica, sans-serif">quote:</font><hr>Originally posted by Vovka:
<strong>А если просто идти одновременно с обоих концов массива, считая по пути суммы и приближаясь с того конца, где эта сумма меньше? [img:f736a56d2d]images/smiles/icon_wink.gif[/img:f736a56d2d]

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

[ 21-02-2002: Message edited by: Vovka ]</strong><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]

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

[lx_uk]

<blockquote><font size="1" face="Arial, Verdana, Helvetica, sans-serif">quote:</font><hr>Originally posted by lx_uk:
<strong>

Среднее арифметическое даст "серединную точку".</strong><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 ]</p>

[Globus]

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