如何将浮点数整数转换为整数？
比方说，我有一个浮点数的数组，在sorting（我们说升序），其总和已知是一个整数N 我想把这些数字“整数”为整数，同时保持它们的总数不变。 换句话说，我正在寻找一种将浮点数字（称为fn ）转换为整数数组的algorithm（调用它），以便：
- 两个arrays具有相同的长度
- 整数数组的总和是
N - 每个浮点数
fn[i]与其fn[i]相应的整数之间的差值小于1（如果您真的必须等于1） - （
fn[i] <= fn[i+1]），整数也将按sorting顺序排列（in[i] <= in[i+1]）
考虑到满足这四个条件，使得舍入方差最小化的algorithm（ 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,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]在技术上是不允许的，但我会把它捏在一起
回答评论中提出的一些优秀问题：
- 在这两个数组中都允许重复元素（尽pipe我也有兴趣知道仅在浮点数组不包含重复的情况下才有效）
- 没有一个正确的答案 – 对于给定的浮点数input数组，通常有多个满足四个条件的int数组。
- 我想到的应用程序 – 这有点奇怪 – 在MarioKart游戏中向顶尖的玩家分发点数;-)从来没有亲自玩过游戏，但在看别人的时候，我注意到有24点分布在前四名的终结者，我想知道如何根据完成时间来分配积分（所以如果有人在积分榜上领先，他们将得到更多的积分）。 游戏跟踪总数为整数，因此需要这种舍入。
为了好奇，这里是我用来确定哪些algorithm工作的testing脚本 。
这是一个应该完成任务的algorithm。 与其他algorithm的主要区别在于，这个按照正确的顺序总是舍入数字。 最小化舍入误差。
该语言是一些可能来源于JavaScript或Lua的伪语言。 应该说明一点。 注意一个基于索引的（对于循环来说更好，x到y）：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")
你可以尝试的一个select是“级联舍入”。
对于这个algorithm，您可以跟踪两个运行总计：到目前为止的一个浮点数，以及目前为止的一个整数。 为了得到下一个整数，你将下一个fp数加到你的运行总数中，舍入运行总数，然后从舍入后的总和中减去运行总数的整数。
number running total integer integer running total 1.3 1.3 1 1 1.7 3.0 2 3 1.9 4.9 2 5 2.2 8.1 3 8 2.8 10.9 3 11 3.1 14.0 3 14
一个非常简单的方法是把所有的小数部分和总结起来。 这个数字由你的问题的定义必须是一个整数。 从最大的数字开始平均分配整个数字。 然后给一个第二大的数字…等，直到你用完的东西分发。
请注意，这是伪代码…并且可能在索引中被closures…其晚了，我很困。
float accumulator = 0; for (i = 0; i < num_elements; i++) /* assumes 0 based array */ { accumulator += (fn[i] - floor(fn[i])); fn[i] = (fn[i] - floor(fn[i]); } i = num_elements; while ((accumulator > 0) && (i>=0)) { fn[i-1] += 1; /* assumes 0 based array */ accumulator -= 1; i--; }
更新：还有其他方法可以根据每个值执行多less截断来分配累计值。 这将需要保持一个名为损失[i] = fn [i] – floor（fn [i]）的单独列表。 然后，您可以重复fn [i]列表并重复给出最大的损失项目（之后将损失[i]设置为0）。 它的复杂，但我想它的作品。
怎么样：
a) start: array is [0.1, 0.2, 0.4, 0.5, 0.8], N=3, presuming it's sorted b) round them all the usual way: array is [0 0 0 1 1] c) get the sum of the new array and subtract it from N to get the remainder. d) while remainder>0, iterate through elements, going from the last one - check if the new value would break rule 3. - if not, add 1 e) in case that remainder<0, iterate from first one to the last one - check if the new value would break rule 3. - if not, subtract 1
基本上你要做的就是把剩下的东西四舍五入后分配给最有可能的候选人。
- 按照通常的方式将浮标四舍五入，但要将四舍五入和相关索引logging为
fn和in。 - 按三angular形sorting第二个数组。
- 当
sum(in) < N，从最大负值delta开始工作，递增取整值（确保你仍然满足规则＃3）。 - 或者，当
sum(in) > N，从最大的正向三angular洲向后工作，递减四舍五入的值（确保你仍然满足规则＃3）。
例：
[0.02,0.03,0.05,0.06,0.07,0.08,0.09,0.1,0.11,0.12,0.13,0.14] N = 1
1. [0,0,0,0,0,0,0,0,0,0] sum = 0
和[[-0.02,0]，[-0.03,1]，[-0.05,2]，[-0.06,3]，[-0.07,4]，[-0.08,5]，
[-0.09，6]，[-0.1,7]，[-0.11,8]，[-0.12,9]，[-0.13,10]，[-0.14,11]
2.sorting将颠倒数组
3.从最大的负数工作，你得到[-0.14，11]。
在[11]中递增``，得到[0,0,0,0,0,0,0,0,0,1] sum = 1
完成。
你能尝试这样的事吗？
in [i] = fn [i] - int (fn [i]); fn_res [i] = fn [i] - in [i];
fn_res→是结果分数。 （我认为这是基本的…），我们错过了什么？
那么，4是痛苦点。 否则，你可以做一些事情，比如“平时倒下并积累剩下的东西;当累加器> = 1时向上取整”。 （编辑：实际上，只要你换了位置，那还可以吗？）
线性规划可能有办法做到这一点？ （这是math“编程”，而不是计算机编程），你需要一些math来find可行的解决scheme，尽pipe你可能会跳过通常的“优化”部分）。
作为线性规划的一个例子 – 例如[1.3,1.7,1.9,2.2,2.8,3.1]，您可以遵守以下规则：
1 <= i < 2 1 <= j < 2 1 <= k < 2 2 <= l < 3 3 <= m < 4 i <= j <= k <= l <= m i + j + k + l + m = 13
然后应用一些线性/matrix代数; -p提示：有一些产品可以根据“Simplex”algorithm来进行上述操作。 普通大学的饲料也是（我为我的最后一个项目写了一个单子）。
正如我所看到的那样，问题是没有指定sortingalgorithm。 或者更喜欢 – 不pipe它是否稳定。
考虑下面的浮点数组：
[0.2 0.2 0.2 0.2 0.2]
总和是1.整数数组然后应该是：
[0 0 0 0 1]
但是，如果sortingalgorithm不稳定，则可以将数组中的“1”sorting…
使总结的差异是在1以下，并检查sorting。 有些人喜欢，
while(i < sizeof(fn) / sizeof(float)) { res += fn[i] - floor(fn[i]); if (res >= 1) { res--; in[i] = ceil(fn[i]); } else in[i] = floor(fn[i]); if (in[i-1] > in[i]) swap(in[i-1], in[i++]); }
（这是纸质代码，所以我没有检查有效性。）
下面是@ mikko-rantanen代码的python和numpy实现。 我花了一点时间把这些放在一起，所以这对未来的Google员工来说可能是有帮助的，尽pipe这个话题已经成熟了。
import numpy as np from math import floor original_array = np.array([1.2, 1.5, 1.4, 1.3, 1.7, 1.9]) # Calculate length of original array # Need to substract 1, as indecies start at 0, but product of dimensions # results in a count starting at 1 array_len = original_array.size - 1 # Index starts at 0, but product at 1 # Calculate expected sum of original values (must be integer) expected_sum = np.sum(original_array) # Collect values for temporary array population array_list = [] lower_sum = 0 for i, j in enumerate(np.nditer(original_array)): array_list.append([i, floor(j), j - floor(j)]) # Original index, lower bound, roundoff error # Calculate the lower sum of values lower_sum += floor(j) # Populate temporary array temp_array = np.array(array_list) # Sort temporary array based on roundoff error temp_array = temp_array[temp_array[:,2].argsort()] # Calculate difference between expected sum and the lower sum # This is the number of integers that need to be rounded up from the lower sum # The sort order (roundoff error) ensures that the value closest to be # rounded up is at the bottom of the array difference = int(expected_sum - lower_sum) # Add one to the number most likely to round up to eliminate the difference temp_array_len, _ = temp_array.shape for i in xrange(temp_array_len - difference, temp_array_len): temp_array[i,1] += 1 # Re-sort the array based on original index temp_array = temp_array[temp_array[:,0].argsort()] # Return array to one-dimensional format of original array array_list = [] for i in xrange(temp_array_len): array_list.append(int(temp_array[i,1])) new_array = np.array(array_list)
计算sum of floor sum of numbers和sum of numbers 。 sum of numbers ，然后与sum of floor相减，差异是我们需要修补多less天花板（我们需要多less个+1 ）。 按天花板与数量的不同，从小到大排列arrays。
对于diff时间（ diff是我们需要补丁多less天花板），我们将结果设置为ceiling of number 。 其他人将结果设置为floor of numbers 。
public class Float_Ceil_or_Floor { public static int[] getNearlyArrayWithSameSum(double[] numbers) { NumWithDiff[] numWithDiffs = new NumWithDiff[numbers.length]; double sum = 0.0; int floorSum = 0; for (int i = 0; i < numbers.length; i++) { int floor = (int)numbers[i]; int ceil = floor; if (floor < numbers[i]) ceil++; // check if a number like 4.0 has same floor and ceiling floorSum += floor; sum += numbers[i]; numWithDiffs[i] = new NumWithDiff(ceil,floor, ceil - numbers[i]); } // sort array by its diffWithCeil Arrays.sort(numWithDiffs, (a,b)->{ if(a.diffWithCeil < b.diffWithCeil) return -1; else return 1; }); int roundSum = (int) Math.round(sum); int diff = roundSum - floorSum; int[] res = new int[numbers.length]; for (int i = 0; i < numWithDiffs.length; i++) { if(diff > 0 && numWithDiffs[i].floor != numWithDiffs[i].ceil){ res[i] = numWithDiffs[i].ceil; diff--; } else { res[i] = numWithDiffs[i].floor; } } return res; } public static void main(String[] args) { double[] arr = { 1.2, 3.7, 100, 4.8 }; int[] res = getNearlyArrayWithSameSum(arr); for (int i : res) System.out.print(i + " "); }
}
class NumWithDiff { int ceil; int floor; double diffWithCeil; public NumWithDiff(int c, int f, double d) { this.ceil = c; this.floor = f; this.diffWithCeil = d; } }
