Chứng minh rằng thuật toán phân bổ tiền của Fowler là chính xác

Question

Martin Fowler has a Money class có thói quen phân bổ tiền. Quy trình này phân bổ tiền theo danh sách các tỷ lệ đã cho mà không làm mất bất kỳ giá trị nào thông qua làm tròn. Nó lây lan bất kỳ giá trị còn lại trên kết quả.

Ví dụ: $ 100 được phân bổ theo "tỷ lệ" (1, 1, 1) sẽ mang lại ($ 34, $ 33, $ 33).

Đây là allocate chức năng:

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

(. Vì mục đích của câu hỏi này, để làm cho nó đơn giản hơn, tôi đã lấy sự tự do thay thế các loại tiền với chờ đợi)

Các câu hỏi là, làm thế nào để tôi biết nó là chính xác? Tất cả có vẻ khá rõ ràng, ngoại trừ vòng lặp cuối cùng. Tôi nghĩ rằng để chứng minh chức năng là chính xác, sẽ đủ để chứng minh rằng mối quan hệ sau đây là đúng trong vòng lặp cuối cùng:

remainder < results.length 

Có ai chứng minh điều đó không?

Answer 1

Thông tin chi tiết chính là tổng số tiền còn lại bằng tổng của các khoản tiền cá nhân khi tính mỗi result[i].

Vì mỗi phần còn lại là kết quả làm tròn xuống, tối đa là 1. Có results.length số dư còn lại, vì vậy tổng số dư còn lại tối đa là results.length.

EDIT: Rõ ràng nó không phải là một bằng chứng mà không cần một số biểu tượng khá, vì vậy đây là một số ...

Answer 2

Tôi muốn nói điều đó không chính xác vì một số tỷ lệ tò mò có thể khiến số dư còn lại lớn hơn số lượng kết quả. Do đó tôi đề nghị results[i % results.length].amount++;.

Chỉnh sửa: Tôi rút câu trả lời của mình. Với thời gian dài không có tỷ lệ tò mò và với điểm nổi modulo không giúp

Answer 3

Không cần bằng chứng.

Số tiền cơ sở được phân bổ theo phân chia đơn giản, làm tròn xuống. Vì vậy, số tiền được phân bổ sẽ luôn nhỏ hơn hoặc bằng tổng số.

Phần còn lại chứa số tiền chưa phân bổ. Mà sẽ luôn luôn là một số nguyên nhỏ hơn 'i'. Vì vậy, ông chỉ đơn giản là cung cấp cho mỗi người nhận 1 cho đến khi tiền đã biến mất.

Answer 4

Simple

chỉ cần sử dụng thực tế là

a = sàn (một/b) * b + (a% b)