问题描述
予具有非负值的阵列。我想建立值的数组谁的总和是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)
这篇关于分配整数数组按比例补偿舍入误差的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!