точное вычисление пенни за один проход

Question

У нас есть стоимость C, которую необходимо присвоить отделам 1..n.Еще одно вычисление дает долю для каждого отдела, это число от 0 до 1, имеющее более 5 десятичных знаков.Сумма долей всех отделов равна ровно 1, но они не обязательно равны.

Цель состоит в том, чтобы вычислить точную сумму в долларах и центах для выставления счетов каждому отделу.Сумма счета должна ТОЧНО соответствовать стоимости C, она не может быть на несколько копеек меньше или больше.Кроме того, доля каждого ведомства не должна требовать дробных грошей.Кроме того, хотя несправедливо просто сбрасывать остаток на последний отдел, нет необходимости оглядываться на предыдущие сроки.Обратите внимание, что простое округление доли каждого отдела до пенни почти всегда приводит к увеличению/меньшему значению в несколько пенни.

Сильно упрощенный пример:C = 33,34, 4 отдела каждый с долей ровно 0,2500.Поскольку 33,34 * 0,25 = 8,335, вы можете видеть, что два отдела должны платить 8,33, а два — 8,34.Одним из правильных заданий будет:d1=8,33, d2=8,34, d3=8,33, d4=8,34.Если округлить, то каждый отдел платит 8,34, что дает избыток в 0,02 доллара.Если вы умножите это на гораздо большее количество отделов и гораздо больше затрат, вы получите расхождение в сотни долларов.

Я хочу сделать это за 1 проход, то есть я не хочу проходить цикл, обнаруживать, что я отклонился на 0,02, затем снова зацикливаться и настраивать значения, пока они не станут правильными.Я хочу сделать это за 1 проход.Я также хотел бы знать, есть ли у этого алгоритма имя.

Answer 1

В Перле:

#!/usr/bin/perl

use strict;
use warnings;

use Data::Dumper;

use List::AllUtils qw( sum );

print Dumper allocate(10_000, .23, .37, .4);
print Dumper allocate(33.34, .25, .25, .25, .25);
print Dumper allocate(100, 1/3, 1/3, 1/3);

sub allocate {
    my ($C, @shares) = @_;

    my @alloc;

    while ( my $share = shift @shares ) {
        push @alloc, sprintf '%.2f', $C * $share;
        $C -= $alloc[-1];
        my $denom = sum @shares;
        $_ /= $denom for @shares;
    }

    return \@alloc;
}

Выход:

$VAR1 = [
          '2300.00',
          '3700.00',
          '4000.00'
        ];
$VAR1 = [
          '8.34',
          '8.33',
          '8.34',
          '8.33'
        ];
$VAR1 = [
          '33.33',
          '33.34',
          '33.33'
        ];

Answer 2

Не используйте поплавки. Используйте десятичные числа с фиксированной запятой или целые числа, чтобы вы могли делить на любой коэффициент масштабирования, чтобы получить значение в долларах.

Никогда, никогда не когда-либо вычисляйте деньги с помощью поплавков.

Answer 3

Я бы назвал это "итоговой суммой" и реализовать его следующим образом:

<Ол>

Рассчитайте долю, причитающуюся с отдела № 1 (могут быть ошибки округления)

Заставьте отдел № 1 оплатить сумму, рассчитанную на шаге 1

Рассчитайте долю в долгах между отделами № 1 и № 2

Сделайте так, чтобы отдел № 1 оплатил сумму, рассчитанную на шаге 3, за вычетом суммы, фактически уплаченной на шаге 2.

Etc. на сумму, которая в долгу перед депозитами #s 1, 2 и 3.

Это гарантирует, что ошибка, с которой сталкивается любой отдел, составляет не более одной ошибки округления (а не суммы нескольких ошибок округления) и что итоговая сумма является правильной.