VPF::Упростить программу - Форум программистов

tishaishii

Дата 5.12.2007, 15:14 (ссылка)

(нет голосов)

Загрузка ...

Создатель

Профиль
Группа: Завсегдатай
Сообщений: 1262
Регистрация: 14.2.2006
Где: Москва

Репутация: 4
Всего: 8

Задача:
Есть несколько ёмкостей X(n), допустим, с водой, бесконечного объёма, но заполненных по-разному. Переливать воду между вёдрами нельзя. Есть ещё одна ёмкость Y, заполненная водой на L литров.
Сколько литров из Y надо вылить в каждую X(n), чтобы расхождение объёма содержимого в ёмкостях X(n) было минимальным? Оперируем целыми числами.

Вот решил так:

Код

use Data::Dumper;

sub div {
    +($_[0]-$_[0] % $_[1])/$_[1]
}

sub find_next {
    my($key, %hash, @result)=(shift, @_);
    foreach(grep{!$key || $key ne $_ && $hash{$key}<$hash{$_}}sort{$hash{$a}<=>$hash{$b}}keys %hash) {
        last if @result && $hash{$result[-1]}!=$hash{$_};
        push @result, $_
    }
    +@result
}

#my%disp=map{
#    sprintf('%02d', $_)=>int(rand 100)
#}1..10;

my%disp=(
          '01' => 65,
          '05' => 45,
          '04' => 11,
          '02' => 81,
          '07' => 99,
          '03' => 71,
          '08' => 95,
          '10' => 75,
          '06' => 82,
          '09' => 21
);

print Dumper \%disp;

my$count=2000;

my(@first, @next, $delta)=&find_next(undef, %disp);
while($count>0) {
    if(!(($next)=&find_next($first[0], %disp)) || ($delta=$disp{$next}-$disp{$first[0]}) * @first > $count) {
        $delta=int($count / @first);
        $_+=$delta foreach @disp{@first};
        $count-=$delta * @first;
        $disp{$first[0]}+=$count if $count>0;
        $count=0;
        last
    } else {
        $_+=$delta foreach @disp{@first};
        $count-=$delta * @first;
    }
    @first=&find_next(undef, %disp);
}

print Dumper \%disp;

Суть:

Код


1. Упорядочим ёмкости по заполненности в порядке возрастания.
2. Ищем менее всего наполненные ёмкости (они в начале, но их может быть несколько).
3. Ищем следующую более наполненную ёмкость.
4. Находим разницу в литрах наполненности.
5. Проверяем, если разница умноженная на количество ёмкостей из шага 2 превышает или равно количество литров в Y, то шаг 6, обратно - шаг 7.
6. Делим количество литров в Y на количество X из шага 2, разливаем поровну. Конец решения.
7. Доливаем в X из шага 2 разницу из шага 4. И переходим на шаг 2.

Есть ли другие решения кроме такого постепенного добавления?
Как вычислить в одно действие для каждой ёмкости, сколько в неё надо долить?

amg

Дата 6.12.2007, 07:52 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1145
Регистрация: 3.8.2006
Где: Новосибирск

Репутация: 38
Всего: 50

Немного неравномерное распределение у тебя получается.
А если так:

Код


use List::Util qw(sum);

%disp=('01'=>65,'05'=>45,'04'=>11,'02'=>81,'07'=>99,
       '03'=>71,'08'=>95,'10'=>75,'06'=>82,'09'=>21);

$added_volume=200;

foreach (sort {$disp{$a}<=>$disp{$b}} keys %disp) {
  push @keys, $_;
  push @volumes, $disp{$_};
}
print "@keys\n@volumes\n";

$total_volume = sum(@volumes)+$added_volume;

$average = $total_volume/@volumes;

for ($i=0; $i<@volumes; $i++) {
  $added[$i] = $volumes[$i];
  $av1 = (sum(@added)+$added_volume)/@added;
  last if $i==$#volumes;
  next if $av1>=$volumes[$i+1];
  last if $average > $volumes[$i+1];
}

@volumes[0..$#added] = (int $av1) x @added;

$volumes[$_-1]++ for 1..$total_volume-sum(@volumes);

print "@volumes\n";

@disp{@keys} = @volumes;

tishaishii

Дата 7.12.2007, 15:10 (ссылка)

(нет голосов)

Загрузка ...

Создатель

Профиль
Группа: Завсегдатай
Сообщений: 1262
Регистрация: 14.2.2006
Где: Москва

Репутация: 4
Всего: 8

Хорошо, а есть ли формула, чтобы в одно действие узнать в какоге ведро сколько надо долить?

AlexPet

Дата 7.12.2007, 15:30 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 93
Регистрация: 5.12.2007
Где: Брянск

Репутация: 1
Всего: 1

Цитата(tishaishii @ 5.12.2007, 15:14

)

чтобы расхождение объёма содержимого в ёмкостях X(n) было минимальным?

Что понимается под расхождением?
Нужно самому определить? Или это дисперсия?

amg

Дата 7.12.2007, 17:13 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1145
Регистрация: 3.8.2006
Где: Новосибирск

Репутация: 38
Всего: 50

Цитата(tishaishii @ 7.12.2007, 15:10

)

Хорошо, а есть ли формула, чтобы в одно действие узнать в какоге ведро сколько надо долить?

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

amg

Дата 8.12.2007, 15:02 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1145
Регистрация: 3.8.2006
Где: Новосибирск

Репутация: 38
Всего: 50

Для непрерывного случая (распределение воды по ведрам представлено неубывающей функцией f(i)) надо найти х в уравнении.

Код


         x
f(x)*x - I f(i)di = L
         0

(I - символ интеграла, L - количество добавленной воды) Понятно, что уравнение, в котором неизвестная величина является одновременно аргументом, значением и пределом интегрирования функции, для произвольной фанкции не решается аналитически. Для дискретного варианта - аналогично.

tishaishii

Дата 12.12.2007, 12:35 (ссылка)

(нет голосов)

Загрузка ...

Создатель

Профиль
Группа: Завсегдатай
Сообщений: 1262
Регистрация: 14.2.2006
Где: Москва

Репутация: 4
Всего: 8

Хреново... Много времени занимает.

amg

Дата 12.12.2007, 14:36 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1145
Регистрация: 3.8.2006
Где: Новосибирск

Репутация: 38
Всего: 50

В дискретном варианте, насколько я понимаю, решение сведется к нахождению минимального $i, при котором перестанет соблюдаться неравенство

Код


(sum(@f[0..$i]) + $L)/($i+1) > $f[$i+1];

где @f - отсортированный по возрастанию массив объемов воды в ведрах
$L - объем добавленной воды
левая часть неравенста - получившийся после добавления уровень воды в первых ($i+1) ведрах

Не обязательно решать это неравенство перебором $i начиная с 0. Есть же всякие продвинутые алгоритмы, простейший - методом деления пополам. Если "ведер" очень много, получится гораздо быстрее.

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Perl: Общие вопросы \| Следующая тема »