La prueba de que el dinero algoritmo de asignación de Fowler es correcta

Question

tiene una clase de dinero que tiene una rutina de asignación de dinero. Esta rutina asigna dinero de acuerdo a una lista dada de proporciones sin perder ningún valor a través de redondeo. Se propaga a cualquier valor restante en los resultados.

Por ejemplo, $ 100 asignado por los "proporciones" (1, 1, 1) daría ($ 34, $ 33, $ 33).

Esta es la función 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;
}

(En aras de esta pregunta, para que sea más sencillo, me he tomado la libertad de la sustitución de los tipos de dinero con desea.)

La pregunta es, ¿cómo sé que es correcto? Todo parece bastante evidente por sí mismo a excepción de la final de ciclo para. Creo que para probar la función es correcta, sería suficiente para demostrar que la siguiente relación es verdadera en la final de bucle:

remainder < results.length

¿Alguien puede probar eso?

Answer 1

La idea clave es que el resto total es igual a la suma de los residuos individuales en el cálculo de cada result[i].

Dado que cada resto individuo es el resultado de redondeo hacia abajo, es como máximo 1. Hay results.length dichos residuos, por lo que el resto total es de, como máximo, results.length.

EDIT: Obviamente no es una prueba sin algunos símbolos bonitas, así que aquí están algunos ...

Answer 2

No se requiere prueba.

Las cantidades de base son asignados por simple división, redondeo hacia abajo. Por lo que la cantidad asignada será siempre menor o igual al total.

El resto contiene la cantidad no asignada. Que siempre habrá un número entero inferior a 'i'. Así que simplemente le da a cada receptor 1 hasta que el dinero se ha ido.

Answer 3

Simple

sólo tiene que utilizar hecho de que

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

Answer 4

Yo diría que no es correcta debido a que algunos curiosa relación podría causar un resto mayor que el número de resultados. Por tanto, sugiero results[i % results.length].amount++;.

Editar: Retiro mi respuesta. Con largos que no hay relación curiosa y con el punto de módulo flotante no ayuda