La prova che Fowler soldi algoritmo di allocazione è corretto

Question

Martin Fowler ha una classe di Money che ha un soldi di allocazione di routine.Questa routine stanzia soldi in base ad una lista di rapporti senza perdere qualsiasi valore di arrotondamento.Si diffonde la restante parte del valore oltre i risultati.

Per esempio, $100 stanziati dalla "ratio" (1, 1, 1), resa ($34, $33, $33).

Qui è il allocate funzione:

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

(Per il bene di questa domanda, per rendere più semplice, mi sono preso la libertà di sostituzione del Denaro tipi di long.)

La domanda è, come faccio a sapere se è corretto?Tutto sembra abbastanza evidente, tranne per il finale di ciclo.Penso che per dimostrare la funzione è corretta, sarebbe sufficiente a dimostrare che la seguente relazione è vera nella finale per il ciclo:

remainder < results.length

Qualcuno può dimostrare che?

Answer 1

L'intuizione fondamentale è che il resto totale è pari alla somma dei singoli residui il calcolo di ciascuno result[i].

Poiché ogni individuo resto è il risultato di arrotondamento per difetto, è al massimo 1. results.length sono tali residui, quindi il rimanente totale è al massimo results.length.

Modifica Ovviamente non è una prova, senza alcune belle simboli, quindi ecco alcuni ...

Answer 2

Nessuna prova richiesta.

Gli importi di base sono allocate dal semplice divisione, arrotondamento. Quindi l'importo assegnato sarà sempre inferiore o uguale al totale.

Il resto contiene l'ammontare allocato. Quale sarà sempre un numero intero inferiore a 'i'. Così egli dà semplicemente ogni ricevitore 1 fino a quando il denaro è andato.

Answer 3

semplice

basta usare fatto che

a = piano (a / b) * b + (% B)

Answer 4

Direi che non è corretto, perché alcuni curioso rapporto potrebbe causare un resto maggiore è il numero di risultati.Quindi io suggerirei di results[i % results.length].amount++;.

Edit:Ho ritirato la mia risposta.Con longs non c'è curioso rapporto con virgola mobile modulo non aiuta