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

Question

Martin Fowler has a Money class 돈 할당 루틴이 있습니다. 이 루틴은 반올림을 통해 값을 잃지 않고 주어진 비율 목록에 따라 돈을 할당합니다. 결과에 대한 나머지 값을 분산시킵니다.

예를 들어, "ratios"(1, 1, 1)로 할당 된 $ 100은 ($ 34, $ 33, $ 33)이됩니다.

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; 
} 

. (이 질문을 위해, 내가 갈망으로 돈 유형을 대체하는 자유를 촬영했습니다 그것은 간단하게하기)

: 여기

는 allocate 기능입니다 질문은, 그것이 옳은지 어떻게 알 수 있습니까? 최종 for-loop를 제외하고는 모두 자명 한 것처럼 보입니다. 나는 다음과 같은 관계에 사실이라고, 그것을 증명하기에 충분하다고 함수가 정확한지 증명하는 생각에 대한 루프 최종 :

이

remainder < results.length 

사람이 증명할 수 있습니까?

Answer 1

키 통찰력은 각 result[i]을 계산할 때 총 나머지가 개별 나머지의 합계와 같습니다.

각 나머지는 반올림 한 결과이므로 1 이하 여야합니다. 나머지는 results.length이므로 총 잔량은 많아야 results.length입니다.

편집 : 분명히 그렇게 여기에 일부입니다, 꽤 문자가없는 증거가 아니다 ... 간단한

Answer 2

나는 호기심의 비율이 결과의 수보다 더 큰 원인이 될 수 있기 때문에 정확하지 않다고 말하고 싶습니다. 그러므로 results[i % results.length].amount++;을 제안합니다.

편집 : 답변을 철회합니다. longs와 호기심 비율이없고 부동 소수점 모듈로 도움이되지 않습니다

Answer 3

증거가 필요하지 않습니다.

기본 금액은 간단한 나누기로 반올림하여 할당됩니다. 그래서 할당 된 금액은 항상 합계보다 작거나 같습니다.

나머지는 할당되지 않은 금액을 포함합니다. 항상 'i'보다 작은 정수가 될 것입니다. 그래서 그는 돈이 없어 질 때까지 각 수신자에게 간단하게 1을줍니다.

Answer 4

바로 사용 사실이

A = 바닥 (A/b) * b + (a % b)