证明了福勒的资金分配算法是正确的

Question

Martin Fowler的具有具有资金分配程序的Money类。该程序根据比例不通过四舍五入失去任何价值给定的名单分配资金。它散布在结果的任何剩余的值。

例如，由 “比率” 分配$ 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;
}

（对于这个问题的缘故，使其更简单，我已经采取多头更换货币类型的自由。）

现在的问题是，我怎么知道它是正确的？这一切似乎不言自明的，除了最后的for循环。我认为，要证明该功能是正确的，这将是足以证明下面的关系为true的最后for循环：

remainder < results.length

任何人都可以证明呢？

Answer 1

的关键见解是，计算每个result[i]当总的余数是等于各个余数的总和。

由于每个单独的余数是向下取整的结果，它为至多1，有这样results.length余，所以总的余数是至多results.length。

编辑：显然，这不是没有一些漂亮的符号证明，所以这里有一些...点击

Answer 2

不需要证明。

在碱量由简单的划分分配，向下舍入。 这样所分配的量将总是小于或等于总

剩余部分包含未分配的量。这将永远是小于整数“我”。于是，他干脆给每个接收器1，直到钱不见了。

Answer 3

简单

只是使用事实

α=地板（A / B）* B +（A％B）

Answer 4

<击>我会说这是不正确的，因为有些好奇的比例可能会导致剩余大于结果的数量。因此，我建议results[i % results.length].amount++;。

编辑：我收回我的答案。与多头没有好奇比和浮点模没有帮助