- भरा जा रहा है
- यहाँ से पढ़ा
- उत्तर
कॉइन चेंज समस्या
कुछ तरह के सिक्के दिए हों, तो किसी सटीक राशि को जितने हो सके उतने कम सिक्कों से कैसे चुकाएँ, और कुल कितने तरीकों से ऐसा किया जा सकता है? ग्रीडी जवाब, यानी सबसे बड़ा सिक्का पहले, असली पैसों के लिए काम करता है, पर कुछ सिक्का-समूहों के लिए विफल हो जाता है। हर राशि को छोटी राशियों से बनाने वाली तालिका हमेशा सही जवाब देती है। ट्रे में किसी सिक्के पर टैप करें ताकि वह काउंटर पर आ जाए, और काउंटर पर किसी सिक्के पर टैप करके उसे वापस लें। मीटर राशि की ओर भरता जाता है: जितने हो सकें उतने कम सिक्कों से राशि ठीक-ठीक बनाएँ। “सबसे कम सिक्के” सबसे अच्छा उत्तर दिखाता है, और “ग्रीडी” दिखाता है कि हमेशा समाने वाला सबसे बड़ा सिक्का लेने से क्या मिलता है, जो हमेशा सबसे कम नहीं होता। पैनल में सिक्के (सेंट में) और राशि बदलें। “टेबल” व्यू दिखाता है कि गतिशील प्रोग्रामिंग सबसे कम सिक्के कैसे ढूँढ़ती है, या राशि बनाने के तरीकों की संख्या कैसे गिनती है: टेबल को भरते देखने के लिए “चलाएँ” दबाएँ, या एक-एक कदम चलने के लिए “आगे” और “पीछे” दबाएँ, और कहीं भी जाने के लिए कदम स्लाइडर खींचें। हर सिक्का जितनी बार चाहें इस्तेमाल हो सकता है। टेबल चुनी होने पर तीर कुंजियाँ एक-एक कदम चलती हैं, स्पेस बार चलाता और रोकता है, और Home और End शुरुआत और अंत पर ले जाते हैं।
यह कैसे काम करता है
- राशि ठीक-ठीक बनाने के लिए ट्रे के सिक्कों पर टैप करें, और देखें कि मीटर सेंट में कैसे भरता है।
- जितने कम सिक्के हो सकें उतने इस्तेमाल करने की कोशिश करें, फिर तुलना के लिए “सबसे कम सिक्के” या “ग्रीडी” दबाएँ।
- “टेबल” दृश्य खोलें और “चलाएँ” दबाएँ, ताकि देख सकें कि हर सेल उस छोटी राशि को कैसे पढ़ता है जिस पर वह निर्भर है।
सबसे कम सिक्के
राशि 0 के लिए कोई सिक्का नहीं चाहिए। हर बड़ी राशि के लिए, हर वह सिक्का आज़माएँ जो उससे बड़ा न हो: उस सिक्के के बाद जो बचता है वह एक छोटी राशि है, जो तालिका में पहले से है, इसलिए एक और सिक्का जोड़ने से एक उम्मीदवार मिलता है। सबसे छोटा उम्मीदवार खाने में जाता है, और जिस सिक्के से वह मिला, वह नीचे वाली पंक्ति में रखा जाता है। तालिका भर जाने पर, सिक्के लक्ष्य से पीछे की ओर पढ़े जाते हैं: उसका आख़िरी सिक्का लें, बची हुई राशि पर जाएँ, और 0 तक यही दोहराएँ।
तरीकों की संख्या
क्रम के बजाय संयोजन गिनने के लिए, तालिका हर पंक्ति में एक सिक्का जोड़ती है। एक खाना अपनी पंक्ति तक के सिक्कों से अपनी राशि बनाने के तरीके गिनता है: सबसे नए सिक्के के बिना तरीके, यानी ऊपर वाला खाना, और सबसे नए सिक्के को कम से कम एक बार इस्तेमाल करने वाले तरीके, यानी उसी पंक्ति में सिक्के के मूल्य जितने स्तंभ बाईं ओर वाला खाना। क्योंकि सिक्के एक तय क्रम में जोड़े जाते हैं, 1 + 2 और 2 + 1 एक ही तरीका हैं और एक बार गिने जाते हैं।
अक्सर पूछे जाने वाले प्रश्न
ग्रीडी तरीका क्यों विफल होता है?
ग्रीडी हमेशा समाने वाला सबसे बड़ा सिक्का लेता है और कभी दोबारा नहीं सोचता। सिक्के 1, 3 और 4 और राशि 6 हो, तो यह 4 लेता है, फिर 1 और 1: तीन सिक्के, जबकि दो 3 काफ़ी होते। यूरो या अमेरिकी डॉलर जैसी सिक्का प्रणालियों में ग्रीडी संयोग से सबसे अच्छा होता है; ऐसी प्रणालियों को कैनोनिकल कहा जाता है।
तरीके गिनने और क्रम गिनने में क्या अंतर है?
तरीकों में 1 + 2 और 2 + 1 एक ही संयोजन माने जाते हैं; क्रमों में उन्हें अलग-अलग गिना जाता है। ऐप सिक्कों को एक-एक पंक्ति में जोड़कर तरीके गिनता है। क्रम गिनने के लिए इसके बजाय राशियों पर क्रम से चलते हैं और हर राशि के लिए हर सिक्का आज़माते हैं।
कॉइन चेंज एल्गोरिदम कितना तेज़ है?
दोनों तालिकाओं में सिक्कों की किस्मों की संख्या गुणा राशि जितने चरण लगते हैं। हज़ारों तक की राशियों के लिए यह तेज़ है, पर राशि बहुत बड़ी संख्या भी हो सकती है, इसलिए अंकों की संख्या से मापें तो यह समस्या आम तौर पर NP-हार्ड है।
अगर कोई राशि न बन सके तो?
उसका खाना ∞ ही रहता है, जैसे सिक्के 2 और 5 के साथ राशियाँ 1 और 3। “तरीकों की संख्या” मोड में उसकी गिनती बस 0 होती है।
क्या कुछ कहीं भेजा जाता है?
नहीं। सब कुछ आपके ब्राउज़र में ही निकाला जाता है, और आपकी पिछली सेटिंग्स इसी ब्राउज़र के लोकल स्टोरेज में रहती हैं।
आज़माने के लिए तैयार?
अपने ब्राउज़र में PictorX खोलें — शुरू करने के लिए इंस्टॉल या क्रेडिट कार्ड की ज़रूरत नहीं।
एडिटर पर जाएँ