如何在保留整数和的同时将浮点数舍入为整数？

一尘不染

如何在保留整数和的同时将浮点数舍入为整数？

algorithm

假设我有一个浮点数数组，该数组以已排序（假设升序）的顺序排列，其和已知为整数N。我想将这些数字“舍入”为整数，同时保持它们的总和不变。换句话说，我正在寻找一种将浮点数数组（称为
fn）转换为整数数组（称为in）的算法，使得：

两个数组的长度相同
整数数组的总和为 N
每个浮点数fn[i]与其对应的整数之间in[i]的差小于1（如果确实需要，则等于1）
假设浮点数按排序顺序（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名的选手，我想知道如何根据完成时间分配分数（因此，如果某人以较大的领先优势完成比赛，他们会获得更大的分数）。游戏将点的总和作为整数进行跟踪，因此需要这种舍入。

出于好奇，这里是我用来确定哪些算法起作用的测试脚本。

阅读 254

2020-07-28

共1个答案

一尘不染

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

该语言是一些伪语言，可能源自JavaScript或Lua。应该说明一下。注意一个基于索引的索引（对于循环，x到y更好。

// 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")

2020-07-28