सबूत है कि फाउलर का पैसा आवंटन एल्गोरिदम सही है

मार्टिन फाउलर has a Money class जिसमें धन आवंटन दिनचर्या है। यह दिनचर्या राउंडिंग के माध्यम से किसी भी मूल्य को खोए बिना अनुपात की एक दी गई सूची के अनुसार धन आवंटित करता है। यह परिणामों पर किसी भी शेष मूल्य फैलता है।सबूत है कि फाउलर का पैसा आवंटन एल्गोरिदम सही है

उदाहरण के लिए, "अनुपात" (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 समारोह है सवाल यह है कि, मुझे कैसे पता चलेगा कि यह सही है? फाइनल फॉर-लूप को छोड़कर यह सब बहुत स्पष्ट है। मुझे लगता है कि साबित करने के लिए समारोह सही है, यह साबित करने के लिए पर्याप्त होगा कि निम्नलिखित के संबंध में सच है फाइनल के लिए लूप:

remainder < results.length

किसी को भी यह साबित कर सकते हैं?

स्रोत

2009-11-05 dan-gph

कहें कि आप एक्स संख्या को वाई भागों में विभाजित करना चाहते हैं। अनुस्मारक एक्स% वाई है जो हमेशा होता है <वाई। मैं इसे काफी स्पष्ट कहूंगा। 3% 2 = 1, 4% 2 = 0 ... –

मुख्य अंतर्दृष्टि यह है कि कुल शेष प्रत्येक result[i] की गणना करते समय व्यक्तिगत रहने वालों के योग के बराबर है।

चूंकि प्रत्येक व्यक्ति शेष गोल करने का नतीजा है, यह सबसे अधिक है। results.length ऐसे रहने वाले हैं, इसलिए कुल शेष results.length पर है।

संपादित करें: जाहिर है यह नहीं कुछ बहुत प्रतीकों के बिना एक सबूत तथ्य

बस का उपयोग है, तो यहाँ कुछ कर रहे हैं ...
alt text

स्रोत

2009-11-05 09:47:11 stevemegson

हाँ, वह हिस्सा था जिसे मैं याद कर रहा था। धन्यवाद। –

+1। ध्यान दें कि अंतिम '<' '' 'होना चाहिए, क्योंकि' \ sum_ {i = 1}^k 1 = k'। – Stephan202

तो यह चाहिए - मुझे यह कम लाइनों पर गिरने के लिए मिलता है। यह मूल रूप से 'शेष stevemegson

मैं कहूंगा कि यह सही नहीं है क्योंकि कुछ उत्सुक अनुपात शेष परिणामों का परिणाम अधिक से अधिक हो सकता है। इसलिए मैं results[i % results.length].amount++; का सुझाव देता हूं।

संपादित करें: मैं अपना उत्तर वापस लेता हूं। लंबे समय तक कोई उत्सुक अनुपात नहीं है और फ्लोटिंग पॉइंट मॉड्यूलो

स्रोत

2009-11-05 09:28:28 DaClown

मुझे असहमत होना होगा। यह उत्सुक राशन गणितीय रूप से असंभव है। –

पूरी संख्या के सेट के लिए कोई "उत्सुक" अनुपात नहीं है। –

हां, लंबे समय तक कोई नहीं है। लेकिन ओपी ने कहा कि लंबे समय तक इस उदाहरण में सादगी के लिए उपयोग किया जाता है। और हम सभी जानते हैं कि किसी को त्रुटि अनुपात के बिना डबल मानों की तुलना नहीं करनी चाहिए।इसलिए एक कंप्यूटर प्रोग्राम में जिज्ञासा अनुपात हो सकता है, क्योंकि इस त्रुटि अनुपात – DaClown

कोई सबूत आवश्यक नहीं है।

आधार मात्रा सरल विभाजन द्वारा आवंटित की जाती है, जो नीचे घूमती है। तो आवंटित राशि हमेशा कुल से कम या बराबर होगी।

अवशेष में आवंटित राशि शामिल है। जो हमेशा 'i' से कम संख्या होगी। तो वह पैसा प्राप्त होने तक प्रत्येक रिसीवर 1 देता है।

स्रोत

2009-11-05 09:31:47

कि आवंटित राशि <= कुल स्पष्ट है, लेकिन यह अनुपात की संख्या से <गारंटी क्यों है? –

इसकी नहीं <=, इसकी बस <('कम')। यदि आवंटित राशि बराबर है तो विभाजन पूरी तरह से परिणाम को विभाजित करेगा, है ना? 4% 2 अनुस्मारक 2 के साथ 1 नहीं है और कभी नहीं होगा। –

यदि आप अनुपात (1,1,1) के साथ $ 99 आवंटित करते हैं, तो एल्गोरिदम का पहला चरण 99 आवंटित करेगा, इसलिए पहले चरण द्वारा आवंटित चरण वास्तव में कुल राशि के बराबर हो सकता है। लेकिन यह वास्तव में मेरा सवाल नहीं है। जो मुझे समझ में नहीं आता है, क्यों नहीं है कि आवंटित राशि (पहले चरण में) # अनुपात से कम है। –

सरल है कि

एक = मंजिल (एक/बी) * बी + (एक% बी)

स्रोत

2009-11-06 09:32:22

सबूत है कि फाउलर का पैसा आवंटन एल्गोरिदम सही है

उत्तर

संबंधित मुद्दे