Prova che l'algoritmo di allocazione del denaro di Fowler è corretto

Question

Martin Fowler has a Money class che ha una routine di allocazione del denaro. Questa routine assegna denaro in base a una determinata lista di rapporti senza perdere alcun valore attraverso l'arrotondamento. Distribuisce qualsiasi valore residuo sui risultati.

Ad esempio, $ 100 assegnati dai "ratios" (1, 1, 1) produrranno ($ 34, $ 33, $ 33).

Ecco la funzione 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; 
} 

(. Per il bene di questa domanda, per rendere più semplice, mi sono preso la libertà di sostituire i tipi di denaro con anela)

Il la domanda è, come faccio a sapere che è corretto? Sembra tutto molto evidente tranne che per il ciclo finale. Credo che per dimostrare la funzione è corretta, sarebbe sufficiente a dimostrare che la seguente relazione è vera nella finale per-loop:

remainder < results.length 

Qualcuno può dimostrare che?

Answer 1

L'intuizione chiave è che il resto totale è uguale alla somma dei singoli rimanenti durante il calcolo di ogni result[i].

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

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

Answer 2

Direi che non è corretto perché qualche rapporto curioso potrebbe causare un resto maggiore del numero di risultati. Pertanto suggerisco results[i % results.length].amount++;.

Modifica: ritiro la risposta. Con i lunghi non c'è un rapporto curioso e con il modulo in virgola mobile non aiuta

Answer 3

Nessuna prova richiesta.

Gli importi di base sono assegnati per divisione semplice, arrotondando per difetto. Quindi l'importo assegnato sarà sempre inferiore o uguale al totale.

Il resto contiene la quantità non assegnata. Quale sarà sempre un numero intero inferiore a "i". Quindi dà semplicemente ad ogni ricevitore 1 fino a che i soldi non sono andati.

Answer 4

semplice

basta usare fatto che

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