Comment arrondir les flottants aux entiers tout en préservant leur somme ?

Question

Disons que j'ai un tableau de nombres à virgule flottante, dans un ordre trié (disons ascendant), dont la somme est connue pour être un entier. N . Je veux "arrondir" ces nombres en nombres entiers tout en laissant leur somme inchangée. En d'autres termes, je cherche un algorithme qui convertit le tableau de nombres à virgule flottante (que j'appelle fn ) à un tableau d'entiers (appelé in ) tel que :

1. les deux tableaux ont la même longueur
2. la somme du tableau d'entiers est N
3. la différence entre chaque nombre à virgule flottante fn[i] et son entier correspondant in[i] est inférieur à 1 (ou égal à 1 si vous y tenez vraiment)
4. étant donné que les flottants sont dans l'ordre trié ( fn[i] <= fn[i+1] ), les entiers seront également dans l'ordre trié ( in[i] <= in[i+1] )

Si ces quatre conditions sont satisfaites, un algorithme qui minimise la variance d'arrondi ( sum((in[i] - fn[i])^2) ) est préférable, mais ce n'est pas un gros problème.

Exemples :

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

Pour répondre à d'excellentes questions soulevées dans les commentaires :

• Les éléments répétés sont autorisés dans les deux tableaux (mais je serais également intéressé de connaître les algorithmes qui ne fonctionnent que si le tableau de flottants ne comprend pas de répétitions).
• Il n'y a pas de réponse correcte unique - pour un tableau d'entrée donné de flottants, il existe généralement plusieurs tableaux d'ints qui satisfont aux quatre conditions.
• L'application que j'avais en tête était - et c'est un peu bizarre - la distribution de points aux premiers arrivés dans une partie de MarioKart ;-) Je n'ai jamais joué au jeu moi-même, mais en regardant quelqu'un d'autre, j'ai remarqué qu'il y avait 24 points répartis entre les 4 premiers, et je me suis demandé comment il serait possible de distribuer les points en fonction du temps d'arrivée (ainsi, si quelqu'un termine avec une grande avance, il obtient une plus grande part des points). Le jeu enregistre les totaux de points sous forme d'entiers, d'où la nécessité de ce type d'arrondi.

---

Pour les curieux, voici le test script que j'utilisais pour identifier les algorithmes qui fonctionnaient.

Answer 1

Une option que vous pouvez essayer est "l'arrondi en cascade".

Pour cet algorithme, vous gardez la trace de deux totaux courants : l'un des nombres à virgule flottante jusqu'à présent, et l'autre des nombres entiers jusqu'à présent. Pour obtenir le prochain nombre entier, vous ajoutez le prochain nombre en virgule flottante à votre total courant, vous arrondissez le total courant, puis vous soustrayez le total courant entier du total courant arrondi.

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

Answer 2

Voici un algorithme qui devrait accomplir la tâche. La principale différence avec les autres algorithmes est que celui-ci arrondit toujours les nombres dans le bon ordre. Minimiser l'erreur d'arrondi.

Le langage est un pseudo-langage probablement dérivé de JavaScript ou Lua. Cela devrait expliquer le point. Notez l'indexation basée sur un seul élément (qui est plus agréable avec les boucles for x to 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")

Answer 3

Une façon très simple est de prendre toutes les parties fractionnaires et de les additionner. Ce nombre, selon la définition de votre problème, doit être un nombre entier. Distribuez ce nombre entier de manière égale en commençant par le plus grand de vos nombres. Puis donnez-en un au deuxième plus grand nombre... etc. jusqu'à ce que vous soyez à court d'éléments à distribuer.

Note C'est du pseudo-code... et il se peut qu'il y ait une erreur dans un index... il est tard et j'ai sommeil.

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

Mise à jour : Il existe d'autres méthodes pour distribuer les valeurs accumulées en fonction du degré de troncature effectué sur chaque valeur. Il faudrait pour cela conserver une liste séparée appelée perte[i] = fn[i] - floor(fn[i]). Vous pouvez ensuite répéter sur la liste fn[i] et donner 1 à l'élément de plus grande perte de façon répétée (en mettant la perte[i] à 0 après). C'est compliqué mais je pense que ça marche.

Answer 4

Pourquoi pas :

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

Answer 5

Ce que vous feriez essentiellement, c'est distribuer les restes après avoir arrondi aux candidats les plus probables.

1. Arrondissez les flottants comme vous le feriez normalement, mais gardez la trace du delta de l'arrondi et de l'indice associé dans fn y in .
2. Trier le deuxième tableau par delta.
3. Alors que sum(in) < N En partant du delta négatif le plus important, vous progressez en augmentant la valeur arrondie (en vous assurant que vous respectez toujours la règle n° 3).
4. Ou, alors que sum(in) > N Dans le cas contraire, travaillez à rebours à partir du delta positif le plus grand, en décrémentant la valeur arrondie (en vous assurant que vous respectez toujours la règle n° 3).

Exemple :

\[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.