Der Nachweis, dass Geld Zuweisungsalgorithmus des Fowler ist richtig

Question

Martin Fowler hat eine Geld-Klasse , die ein Geld-Zuordnungs-Programm hat. Diese Routine ordnet Geld entsprechend einer vorgegebenen Liste von Verhältnissen ohne jeden Wert durch Rundung zu verlieren. Es breitet sich jeder Restwert über die Ergebnisse.

Beispiel 100 durch die "Verhältnisse" zugeordnet $ (1, 1, 1) ergeben würde (34, $ 33 $, 33 $).

Hier ist die allocate Funktion:

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

(Für die Zwecke dieser Frage, es einfacher zu machen, habe ich mir die Freiheit für den Ersatz der Geldtypen mit longs entnommen.)

Die Frage ist, wie kann ich wissen, es ist richtig? Es scheint alles ziemlich selbstverständlich mit Ausnahme der letzten for-Schleife. Ich denke, dass die Funktion zu beweisen, richtig ist, wäre es ausreichend, um zu beweisen, daß die folgende Beziehung gilt im Finale for-Schleife:

remainder < results.length

Kann jemand beweisen, dass?

Answer 1

Die wichtige Erkenntnis ist, dass der gesamte Rest der Summe der einzelnen Reste gleich ist, wenn jede result[i] berechnet wird.

Da jeder einzelner Rest das Ergebnis abgerundet ist, ist es höchstens 1. Es gibt results.length solche Reste, so dass der Gesamt Rest ist höchstens results.length.

EDIT: Natürlich ist es kein Beweis, ohne ein paar ziemlich Symbole, so sind hier einige ...

Answer 2

Kein Nachweis erforderlich.

Die Grundbeträge werden durch einfache Division zugeordnet, Abrunden. So ist der zugewiesene Betrag wird immer kleiner oder gleich die Gesamt.

Rest enthält die verfügbare Menge. Welche wird immer eine ganze Zahl kleiner als ‚i‘. So gibt er einfach jeden Empfänger 1, bis das Geld ist weg.

Answer 3

Einfach

nur verwenden, dass

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

Answer 4

Ich würde sagen, dass es nicht richtig ist, weil einige merkwürdige Verhältnis ein Rest größer als die Anzahl der Ergebnisse führen könnten. Deshalb schlage ich vor results[i % results.length].amount++;.

Edit: Ich meine Antwort zurückziehen. Mit Long-Positionen gibt es kein neugieriges Verhältnis und Punkt Modulo mit schwimmendem hilft nicht