Как округлить float до целых чисел, сохраняя их сумму?

Ответ 1

Вот один алгоритм, который должен выполнить задачу. Основное отличие от других алгоритмов заключается в том, что он всегда округляет числа в правильном порядке. Минимизация ошибки округления.

Язык - это некоторый псевдоязык, который, вероятно, получен из 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")

Ответ 2

Один из вариантов, который вы могли бы попробовать, - "каскадное округление".

Для этого алгоритма вы отслеживаете два текущих итога: один из чисел с плавающей запятой и один из целых чисел. Чтобы получить следующее целое число, вы добавляете следующий номер 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

Ответ 3

Один очень простой способ - взять все дробные части и суммировать их. Это число по определению вашей проблемы должно быть целым числом. Равномерно распределите это число, начиная с самого большого числа ваших чисел. Затем дайте один для второго по величине числа... и т.д., Пока вы не исчерпаете все, чтобы распределить.

Примечание, это псевдокод... и может быть отключен одним в индексе... его опоздание и я сонный.

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--;
}

Обновление: Существуют другие методы распределения накопленных значений на основе того, сколько усечений выполнялось для каждого значения. Это потребует сохранения отдельного списка с именем loss [i] = fn [i] - floor (fn [i]). Затем вы можете повторить по списку fn [i] и повторно нанести 1 на элемент с наибольшим убытком (после этого после этого установите значение [i] в ​​0). Это сложно, но я думаю, что это работает.

Ответ 4

Как насчет:

a) start: array is [0.1, 0.2, 0.4, 0.5, 0.8], N=3, presuming it 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

Ответ 5

По существу, вы должны распределить остатки после округления к наиболее вероятным кандидатам.

• Вокруг поплавков, как обычно, но отслеживайте дельта от округления и связанного индекса до fn и in.
• Сортировка второго массива по delta.
• Пока sum(in) < N, работайте вперед с наибольшей отрицательной дельта, увеличивая округленное значение (убедитесь, что вы все еще удовлетворяете правилу № 3).
• Или, пока sum(in) > N, работайте назад от наибольшей положительной дельта, уменьшая округленное значение (убедитесь, что вы все еще удовлетворяете правилу № 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, 0] sum=0
and [[-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 will reverse the array

3. working from the largest negative remainder, you get [-0.14, 11].
Increment `in[11]` and you get [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1] sum=1 
Done.

Ответ 6

Можете ли вы попробовать что-то вроде этого?

in [i] = fn [i] - int (fn [i]);
fn_res [i] = fn [i] - in [i];

fn_res → - итоговая доля. (Я думал, что это было основополагающим...), мы что-то упускаем?

Ответ 7

Ну, 4 - точка боли. В противном случае вы можете делать такие вещи, как "обычно округлять вниз и накапливать остатки, округлять до аккумуляторa >= 1". (править: на самом деле, все еще может быть ОК, пока вы меняете позицию?)

Может ли быть способ сделать это с помощью линейного программирования? (это математическое "программирование", а не компьютерное программирование - вам понадобится математика, чтобы найти возможное решение, хотя вы, вероятно, можете пропустить обычную часть "оптимизации" ).

В качестве примера линейного программирования - с примером [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

Затем применим некоторую линейную/матричную алгебру; -p. Hint: есть продукты для выполнения вышеизложенного на основе таких вещей, как алгоритм "Simplex". Общий университетский корм тоже (я написал один в uni для моего финального проекта).

Ответ 8

Проблема, как я вижу, заключается в том, что алгоритм сортировки не указан. Или больше - будь то стабильный вид или нет.

Рассмотрим следующий массив поплавков:

[0,2 0,2 ​​0,2 ​​0,2 ​​0,2]

Сумма равна 1. Integer массив должен быть:

[0 0 0 0 1]

Однако, если алгоритм сортировки нестабилен, он может сортировать "1" в другом месте в массиве...

Ответ 9

Сделать суммированные различия должны быть ниже 1 и проверить, чтобы их сортировка. некоторые вроде,

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++]);
}

(это бумажный код, поэтому я не проверял достоверность.)

Ответ 10

Ниже python и numpy реализация кода @mikko-rantanen. Мне потребовалось немного, чтобы собрать это вместе, так что это может быть полезно будущим Googlers, несмотря на возраст темы.

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)

Ответ 11

Вычислить sum of floor и sum of numbers. Раунд sum of numbers и вычесть с помощью sum of floor, разница в том, сколько потолков нам нужно заплатить (сколько +1 нам нужно). Сортировка массива с разностью потолка на число, от малого до большого.

В течение diff раз (diff указано, сколько потолка нам нужно заплатить), мы устанавливаем результат как 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;
    }
}

Ответ 12

Без минимизации дисперсии здесь тривиальный:

• Сортировка значений слева направо.
• Разобрать все до следующего целого числа.
• Пусть сумма этих целых чисел равна K. Увеличьте наименьшие значения N-K на 1.
• Восстановить исходный порядок.

Это, очевидно, удовлетворяет вашим условиям 1.-4. В качестве альтернативы вы можете округлить до ближайшего целого числа и увеличить N-K тех, которые были округлены. Вы можете сделать это с жадностью по разнице между исходным и округленным значением, но каждый пробег округленных значений должен быть увеличен только справа налево, чтобы сохранить отсортированный порядок.

Ответ 13

Если вы можете принять небольшое изменение в итоговом значении при улучшении дисперсии, это вероятностно сохранит итоговые значения в python:

import random
integer_list = [int(x) + int(random.random() <= math.modf(x)[0]) for x in my_list]

чтобы объяснить это, округляет все числа вниз и добавляет одно с вероятностью, равной дробной части, т.е. один из десяти 0.1 станет 1 а остальные 0

это работает для статистических данных, где вы конвертируете большое количество дробных лиц в 1 человека или 0 человек