本文介绍了分配整数数组按比例补偿舍入误差的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

予具有非负值的阵列。我想建立值的数组谁的总和是20,使得它们成比例的第一阵列

I have an array of non-negative values. I want to build an array of values who's sum is 20 so that they are proportional to the first array.

这将是一个简单的问题,但我想比例阵列来概括准确20,补偿任何舍入误差。

This would be an easy problem, except that I want the proportional array to sum to exactly20, compensating for any rounding error.

例如,阵列

input = [400, 400, 0, 0, 100, 50, 50]

将产生

output = [8, 8, 0, 0, 2, 1, 1]
sum(output) = 20

然而,大多数情况下,将有大量的舍入误差,如

However, most cases are going to have a lot of rounding errors, like

input = [3, 3, 3, 3, 3, 3, 18]

天真地产生

output = [1, 1, 1, 1, 1, 1, 10]
sum(output) = 16  (ouch)

有没有分摊输出数组,这样加起来20的好办法,每次?

Is there a good way to apportion the output array so that it adds up to 20 every time?

推荐答案

所以上面的答案和意见是有益的......特别是从@Frederik下降的总和评论。

So the answers and comments above were helpful... particularly the decreasing sum comment from @Frederik.

我想出了解决方案利用了这样一个事实:一个输入数组V,和(V-I * 20)整除之和(V)。因此,对于在v中的每个值,我mulitply 20和除以相加。我把商,积累的剩余部分。每当累加器大于总和(v)中,我加一的值。这样,我保证,所有的余数得到滚入结果。

The solution I came up with takes advantage of the fact that for an input array v, sum(v_i * 20) is divisible by sum(v). So for each value in v, I mulitply by 20 and divide by the sum. I keep the quotient, and accumulate the remainder. Whenever the accumulator is greater than sum(v), I add one to the value. That way I'm guaranteed that all the remainders get rolled into the results.

是清晰?下面是用Python实现:

Is that legible? Here's the implementation in Python:

def proportion(values, total):
    # set up by getting the sum of the values and starting
    # with an empty result list and accumulator
    sum_values = sum(values)
    new_values = []
    acc = 0

    for v in values:
        # for each value, find quotient and remainder
        q, r = divmod(v * total, sum_values)

        if acc + r < sum_values:
            # if the accumlator plus remainder is too small, just add and move on
            acc += r
        else:
            # we've accumulated enough to go over sum(values), so add 1 to result
            if acc > r:
                # add to previous
                new_values[-1] += 1
            else:
                # add to current
                q += 1
            acc -= sum_values - r

        # save the new value
        new_values.append(q)

    # accumulator is guaranteed to be zero at the end
    print new_values, sum_values, acc

    return new_values

(我补充说,如果累加器>部分,我增加当前值的previous值,而不是增强)

(I added an enhancement that if the accumulator > remainder, I increment the previous value instead of the current value)

这篇关于分配整数数组按比例补偿舍入误差的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!

08-20 04:18