16

Martin Fowler有一个 Money 类，它有一个货币分配例程。此例程根据给定的比率列表分配资金，而不会因四舍五入而损失任何价值。它将任何剩余值分布在结果上。

例如，按“比率”（1、1、1）分配的 100 美元将产生（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 类型替换为 long。）

问题是，我怎么知道它是正确的？除了最后的 for 循环之外，这一切似乎都是不言而喻的。我认为要证明函数是正确的，在最终的 for 循环中证明以下关系是正确的就足够了：

remainder < results.length

谁能证明这一点？

4

4 回答 4

25

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

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

编辑：显然它不是没有一些漂亮符号的证明，所以这里有一些......
替代文字

于 2009-11-05T09:47:11.740 回答
1

无需证明。

基数通过简单除法四舍五入分配。因此，分配的金额将始终小于或等于总数。

余额包含未分配的金额。这将始终是小于“i”的整数。所以他简单地给每个接收者1，直到钱花光。

于 2009-11-05T09:31:47.417 回答
1

简单的

只是使用事实

a=地板(a/b)*b+(a%b)

于 2009-11-06T09:32:22.543 回答
0

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

编辑：我撤回我的答案。多头没有奇怪的比率，浮点模没有帮助

于 2009-11-05T09:28:28.157 回答