دليل على أن خوارزمية تخصيص أموال fowler صحيحة

Question

مارتن فاولر لديه فئة المال التي لديها روتين تخصيص الأموال. يخصص هذا الروتين المال وفقا لقائمة معينة من النسب دون أن تفقد أي قيمة من خلال التقريب. ينتشر أي قيمة بقية على النتائج.

على سبيل المثال، سيؤدي 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;
}

(من أجل هذا السؤال، لجعلها أكثر بساطة، لقد أخذت حرية استبدال أنواع المال مع أوقات طويلة.)

السؤال هو، كيف أعرف أنه صحيح؟ كل شيء يبدو بديهيا إلى حد كبير باستثناء النهائي للنتيجة. أعتقد أنه لإثبات الوظيفة صحيحة، فسيكون ذلك كافيا لإثبات أن العلاقة التالية صحيحة في النهائي للنتيجة:

remainder < results.length

يمكن لأي شخص أن يثبت ذلك؟

Answer 1

البصيرة الرئيسية هي أن ما تبقى إجمالي يساوي مجموع الأبقان عند حساب كل منهما result[i].

نظرا لأن كل باقي فردي هو نتيجة التقريب، فهي على الأكثر 1. هناك results.length مثل هذه البقية، وبالتالي فإن ما تبقى إجمالي هو على الأكثر results.length.

تعديل: من الواضح أنه ليس دليلا دون بعض الرموز الجميلة، لذلك هنا بعض ...

Answer 2

لا يوجد دليل مطلوب.

يتم تخصيص المبالغ الأساسية من قبل الانقسام البسيط، تقريب أسفل. لذلك سيكون المبلغ المخصص دائما أقل من أو يساوي المجموع.

الباقي يحتوي على المبلغ غير المخصص. والتي ستكون دائما عدد صحيح أقل من "أنا". لذلك يعطي ببساطة كل جهاز استقبال 1 حتى يختفي الأموال.

Answer 3

بسيط

فقط استخدم حقيقة ذلك

أ = الكلمة (A / B) * B + (٪ ب)

Answer 4

أود أن أقول أنه غير صحيح لأن بعض النسبة الغريبة يمكن أن تسبب باقي أكبر ثم عدد النتائج. لذلك أقترح results[i % results.length].amount++;.

تحرير: أنا سحب إجابتي. مع وجود نسبة فضولية لا توجد نسبة فضولية ومعدلو نقطة عائمة لا يساعد