파울러의 돈 할당 알고리즘이 정확하다는 증거

Question

마틴 파울러 머니 클래스가 있습니다 돈 할당 루틴이 있습니다. 이 루틴은 반올림을 통해 가치를 잃지 않고 주어진 비율 목록에 따라 돈을 할당합니다. 결과에 대한 나머지 값을 전파합니다.

예를 들어, "비율"(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;
}

(이 질문을 위해 더 간단하게하기 위해 돈 유형을 오랫동안 대체 할 자유를 얻었습니다.)

문제는 그것이 정확하다는 것을 어떻게 알 수 있습니까? 최종 루프를 제외하고는 모두 자명 한 것 같습니다. 기능이 정확하다는 것을 증명하기 위해서는 최종 루프에서 다음과 같은 관계가 사실임을 증명하기에 충분할 것입니다.

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++;.

편집 : 나는 대답을 철회합니다. 오랫동안 호기심이없고 플로팅 포인트 모듈로는 도움이되지 않습니다.