如何在保留它们的总和的同时将浮点数舍入为整数? [英] How to round floats to integers while preserving their sum?

问题描述

假设我有一个浮点数数组，按排序(假设升序)顺序，其总和已知为整数 N.我想将这些数字四舍五入"为整数，同时保持它们的总和不变.换句话说，我正在寻找一种将浮点数数组(称为 fn)转换为整数数组(称为 in)的算法，例如那个:

1. 两个数组的长度相同
2. 整数数组之和为N
3. 每个浮点数 fn[i] 与其对应的整数 in[i] 之间的差小于 1(或等于 1，如果你真的必须)
4. 鉴于浮点数按排序顺序(fn[i] <= fn[i+1])，整数也将按排序顺序(in[i]<= in[i+1])

鉴于这四个条件都满足，最小化舍入方差的算法 (sum((in[i] - fn[i])^2)) 是可取的，但它不是大不了.

示例:

<前>[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] 更可取=> [0, 0, 0, 0, 10, 10] 是可以接受的[0.5, 0.5, 11]=> [0, 1, 11] 很好=> [0, 0, 12] 在技术上是不允许的，但我会在紧要关头接受它

回答评论中提出的一些很好的问题:

• 两个数组中都允许重复元素(尽管我也有兴趣了解仅在浮点数组不包含重复时才起作用的算法)
• 没有单一的正确答案 - 对于给定的输入浮点数组，通常有多个满足四个条件的整数数组.
• 我想到的应用是 - 这有点奇怪 - 在 MarioKart 游戏中将积分分配给前几名;-) 我自己从未真正玩过这款游戏，但在观看其他人时，我注意到有 24积分在前 4 名完成者之间分配，我想知道如何根据完成时间分配积分(因此，如果有人以较大的领先优势完成比赛，他们将获得更大的积分份额).游戏以整数形式跟踪总分，因此需要这种四舍五入.

<小时>

出于好奇，这里是测试脚本我用来确定哪个算法有效.

解决方案

这是一种应该完成任务的算法.与其他算法的主要区别在于，该算法始终以正确的顺序舍入数字.最小化舍入误差.

该语言是一些可能源自 JavaScript 或 Lua 的伪语言.应该说明点.请注意基于一个的索引(x 到 y 循环更好.:p)

//与 fn 长度相同的临时数组.tempArr = Array(fn.length)//计算预期总和.arraySum = sum(fn)下和 = 0-- 填充临时数组.对于 i = 1 到 fn.lengthftempArr[i] = { result: floor(fn[i]),//下界区别: fn[i] - floor(fn[i]),//舍入误差index: i }//原始索引//计算下和lowerSum = lowerSum + tempArr[i].result结束于//根据舍入误差对临时数组进行排序排序(tempArr，差异")//现在 arraySum - lowerSum 给出了这些总和之间的差值//数组.tempArr 的排序方式是，最接近//下一个在顶部.差异 = arraySum - lowerSum//将最有可能四舍五入到下一个数字的值加 1，以便//差异无效.对于 i = (tempArr.length - difference + 1) 到 tempArr.lengthtempArr.result = tempArr.result + 1结束于//可选择根据原始索引对数组进行排序.数组(排序，索引")

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. 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])

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.

Examples:

[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:

• Repeated elements are allowed in both arrays (although I would also be interested to hear about algorithms that work only if the array of floats does not include repeats)
• There is no single correct answer - for a given input array of floats, there are generally multiple arrays of ints that satisfy the four conditions.
• The application I had in mind was - and this is kind of odd - distributing points to the top finishers in a game of MarioKart ;-) Never actually played the game myself, but while watching someone else I noticed that there were 24 points distributed among the top 4 finishers, and I wondered how it might be possible to distribute the points according to finishing time (so if someone finishes with a large lead they get a larger share of the points). The game tracks point totals as integers, hence the need for this kind of rounding.

---

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.

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].result
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")

这篇关于如何在保留它们的总和的同时将浮点数舍入为整数?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！