如何圆花车为整数，而preserving它们的和？ [英] How to round floats to integers while preserving their sum?

问题描述

让我们说我有浮点数的数组，在排序（比方说升序）订单，其总和被称为是一个整数 N 。我想圆圆这些数字为整数，同时使它们的总和不变。换句话说，我在寻找一种算法，浮点数（称之为 FN ）的数组转换为整数数组（称之为在），使得：

Let's say I have an array of floating point numbers, in sorted (let's say ascending) order, whose sum is known to be an integer N. I want to "round" these numbers to integers while leaving their sum unchanged. In other words, I'm looking for an algorithm that converts the array of floating-point numbers (call it fn) to an array of integers (call it in) such that:

1. 两个阵列具有相同的长度
2. 整数数组的总和 N
3. 在每一个浮点数之间的差异 FN [I] 及其对应的整数中的[I] 是小于1（或等于1，如果你真的必须）
4. 鉴于彩车都在有序（ FN [1] - = FN [I + 1] ），整数也将有序（在[1] - =在[I + 1] ）

1. the two arrays have the same length
2. the sum of the array of integers is N
3. the difference between each floating-point number fn[i] and its corresponding integer in[i] is less than 1 (or equal to 1 if you really must)
4. given that the floats are in sorted order (fn[i] <= fn[i+1]), the integers will also be in sorted order (in[i] <= in[i+1])

由于这四个条件都满足，一种算法，最大限度地减少舍入差异（ SUM（（在[I] - FN [I]）^ 2））是preferable，但它不是一个大问题。

Given that those four conditions are satisfied, an algorithm that minimizes the rounding variance (sum((in[i] - fn[i])^2)) is preferable, but it's not a big deal.

例如：

[0.02, 0.03, 0.05, 0.06, 0.07, 0.08, 0.09, 0.1, 0.11, 0.12, 0.13, 0.14]
    => [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
[0.1, 0.3, 0.4, 0.4, 0.8]
    => [0, 0, 0, 1, 1]
[0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1]
    => [0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
[0.4, 0.4, 0.4, 0.4, 9.2, 9.2]
    => [0, 0, 1, 1, 9, 9] is preferable
    => [0, 0, 0, 0, 10, 10] is acceptable
[0.5, 0.5, 11]
    => [0, 1, 11] is fine
    => [0, 0, 12] is technically not allowed but I'd take it in a pinch

要回答的意见中提出的一些优秀的问题：

To answer some excellent questions raised in the comments:

• 在重复的元素被允许在两个数组（虽然我也很想听到只有工作的算法，如果彩车的数组不包括重复）
• 在没有唯一正确的答案 - 为彩车给定的输入数组，有整数一般多个阵列满足四个条件
。
• 在我脑子里想的应用是 ​​- 这是一种奇怪的 - 在一场比赛中MarioKart ;-)的实际上从未玩过的游戏自己分发点顶端的选手，但在看着别人，我注意到，有24个分布式的前4名选手之间的分，我想知道这是可能的，根据完成时间分发点（因此，如果有人以较大的领先优势，他们获得更大的份额之分结束）。本场比赛曲目总积分为整数，因此需要进行这种舍入。

对于好奇，这里是 我用来识别哪些算法工作的测试脚本。

For the curious, here is the test script I used to identify which algorithms worked.

推荐答案

这是一种算法应该完成的任务。主要区别其他算法是，这一个舍入的数字在正确的顺序总是如此。 最小化的舍入误差。

Here is one algorithm which should accomplish the task. The main difference to other algorithms is that this one rounds the numbers in correct order always. Minimizing roundoff error.

语言是可能从JavaScript或者Lua中衍生的一些伪语言。应该说明的一点。注意一个基于索引（这是更好的与X到Y的循环：P）

The language is some pseudo language which probably derived from JavaScript or Lua. Should explain the point. Note the one based indexing (which is nicer with x to y for loops. :p)

// Temp array with same length as fn.
tempArr = Array(fn.length)

// Calculate the expected sum.
arraySum = sum(fn)

lowerSum = 0
-- Populate temp array.
for i = 1 to fn.lengthf
    tempArr[i] = { result: floor(fn[i]),              // Lower bound
                   difference: fn[i] - floor(fn[i]),  // Roundoff error
                   index: i }                         // Original index

    // Calculate the lower sum
    lowerSum = lowerSum + tempArr[i] + lowerBound
end for

// Sort the temp array on the roundoff error
sort(tempArr, "difference")

// Now arraySum - lowerSum gives us the difference between sums of these
// arrays. tempArr is ordered in such a way that the numbers closest to the
// next one are at the top.
difference = arraySum - lowerSum

// Add 1 to those most likely to round up to the next number so that
// the difference is nullified.
for i = (tempArr.length - difference + 1) to tempArr.length
    tempArr.result = tempArr.result + 1
end for

// Optionally sort the array based on the original index.
array(sort, "index")

这篇关于如何圆花车为整数，而preserving它们的和？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！