La preuve que l'algorithme d'allocation de l'argent de Fowler est correct

Question

Martin Fowler a une classe d'argent qui a une routine d'allocation d'argent. Cette routine alloue de l'argent selon une liste donnée de rapports sans perdre aucune valeur par l'arrondissement. Il se propage toute valeur restante sur les résultats.

Par exemple, 100 $ alloué par les "rapports" (1, 1, 1) donnerait (34 $, 33 $, 33 $).

Voici la fonction allocate:

public long[] allocate(long amount, long[] ratios) {
    long total = 0;
    for (int i = 0; i < ratios.length; i++) total += ratios[i];

    long remainder = amount;
    long[] results = new long[ratios.length];
    for (int i = 0; i < results.length; i++) {
        results[i] = amount * ratios[i] / total;
        remainder -= results[i];
    }

    for (int i = 0; i < remainder; i++) {
        results[i]++;
    }

    return results;
}

(Par souci de cette question, pour le rendre plus simple, je me suis permis de remplacer les types d'argent avec languit.)

La question est, comment puis-je savoir qu'il est correct? Tout semble assez évident, sauf pour la finale de la boucle. Je pense que pour prouver la fonction est correcte, il suffit de prouver que la relation suivante est vrai dans la finale pour la boucle:

remainder < results.length

Quelqu'un peut-il prouver?

Answer 1

L'idée essentielle est que le reste total est égal à la somme des restes individuels lors du calcul de chaque result[i].

Étant donné que chaque individu reste est le résultat de l'arrondi vers le bas, il est au plus 1. Il y a results.length ces reliquats, de sorte que le reste total est au plus results.length.

EDIT: Il est évident que ce n'est pas une preuve sans quelques jolis symboles, alors voici quelques-unes ...

Answer 2

Aucune preuve nécessaire.

Les montants de base sont attribués par simple division, arrondi vers le bas. Ainsi, le montant alloué sera toujours inférieur ou égal au total.

Remainder contient la quantité non attribuée. Ce qui sera toujours un nombre entier inférieur à « i ». Alors il donne simplement chaque récepteur 1 jusqu'à ce que l'argent est parti.

Answer 3

Simple

il suffit d'utiliser fait que

a = plancher (a / b) * b + (a% b)

Answer 4

Je dirais que ce n'est pas correct parce que certains curieux rapport pourrait causer un reste plus alors le nombre de résultats. Par conséquent, je suggère results[i % results.length].amount++;.

Edit: Je retire ma réponse. Avec languit il n'y a pas de ratio curieux et flottant modulo points ne permet pas