Доказательство правильности алгоритма распределения денег Фаулера.

Question

Мартин Фаулер имеет класс денег у которого есть процедура распределения денег.Эта процедура распределяет деньги в соответствии с заданным списком коэффициентов, не теряя при этом никакой ценности из-за округления.Он распределяет любое остаточное значение по результатам.

Например, 100 долларов, распределенные по «коэффициентам» (1, 1, 1), дадут доход (34 доллара, 33 доллара, 33 доллара).

Здесь 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;
}

(Ради этого вопроса, чтобы упростить его, я взял на себя смелость заменить типы Money на длинные.)

Вопрос в том, как я узнаю, что это правильно?Все кажется само собой разумеющимся, за исключением последнего цикла for.Я думаю, что для доказательства корректности функции было бы достаточно доказать, что в конечном цикле for верно следующее соотношение:

remainder < results.length

Может ли кто-нибудь это доказать?

Answer 1

Ключевой вывод заключается в том, что общий остаток равен сумме отдельных остатков при вычислении каждого result[i].

Поскольку каждый отдельный остаток является результатом округления в меньшую сторону, он не превышает 1.Есть results.length такие остатки, поэтому общий остаток не превышает results.length.

РЕДАКТИРОВАТЬ: Очевидно, что это не доказательство без красивых символов, поэтому вот некоторые из них...

Answer 2

Никаких доказательств не требуется.

Базовые суммы распределяются путем простого деления с округлением в меньшую сторону.Таким образом, выделенная сумма всегда будет меньше или равна общей сумме.

Остаток содержит нераспределенную сумму.Которое всегда будет на целое число меньше, чем «i».Поэтому он просто дает каждому получателю по 1, пока деньги не закончатся.

Answer 3

Простой

просто используй тот факт, что

a=пол(a/b)*b+(a%b)

Answer 4

Я бы сказал, что это неправильно, потому что какое-то любопытное соотношение может привести к тому, что остаток будет больше, чем количество результатов.Поэтому я предлагаю results[i % results.length].amount++;.

Редактировать:Я снимаю свой ответ.С длинными нет любопытного соотношения, а с плавающей запятой по модулю не помогает.