समस्या को स्पष्ट करना: इनपुट, आउटपुट और चरण
कोड लिखने से पहले समस्या को ठीक-ठीक लिखो। यह विनिर्देश (specification) है।
- इनपुट: कौन-सा डेटा मिलेगा, उसका प्रकार और सीमा (जैसे "n पूर्ण संख्याएँ, 1 ≤ n ≤ 1000")।
- आउटपुट: क्या लौटाना है (जैसे "उनमें सबसे बड़ी")।
- शर्तें: पहले क्या सच है (पूर्व-शर्त) और बाद में (पश्च-शर्त)।
चरण लिखना
एल्गोरिदम साफ़ चरणों की सीमित सूची है जो हर सही इनपुट को सही आउटपुट में बदलती है। इसे ऐसे लिखो:
- सामान्य भाषा: "हर संख्या देखो; अगर अब तक की सबसे बड़ी से बड़ी है, याद रखो।"
- क्रमांकित चरण सूची: 1. best ← पहली संख्या। 2. हर अगली संख्या x के लिए: अगर x > best तो best ← x। 3. best दिखाओ।
- ज़्यादा सटीकता के लिए स्यूडोकोड या फ़्लोचार्ट।
छोटे इनपुट पर हाथ से जाँचो, मुश्किल वाले भी (सब बराबर, ऋणात्मक संख्याएँ, सिर्फ़ एक संख्या)।
ऊपर से नीचे और नीचे से ऊपर डिज़ाइन
ऊपर से नीचे (top-down), क्रमिक परिशोधन: पूरे काम से शुरू करो, उसे कुछ बड़े चरणों में बाँटो, फिर हर चरण को फिर बाँटो जब तक हर भाग आसानी से कोड न हो। उदाहरण: "रिपोर्ट कार्ड बनाओ" → अंक पढ़ो → औसत निकालो → ग्रेड दो → छापो।
नीचे से ऊपर (bottom-up): पहले छोटे, दोबारा काम आने वाले टुकड़े बनाओ और जाँचो (सबसे बड़ा खोजने वाला फ़ंक्शन, क्रम से लगाने वाला), फिर उन्हें जोड़कर पूरा प्रोग्राम बनाओ।
असली प्रोजेक्ट दोनों मिलाते हैं: योजना ऊपर से नीचे, बनाना और जाँचना नीचे से ऊपर।
विभाजन और विजय, और आधा करने की विधि
विभाजन और विजय के तीन कदम: समस्या को उसी तरह के छोटे भागों में बाँटो, हर भाग हल करो (अक्सर पुनरावर्तन/recursion से), उत्तरों को जोड़ो।
- बाइनरी सर्च (आधा करना): क्रमबद्ध सूची में बीच वाले से तुलना करो और आधा फेंक दो। n चीज़ों के लिए लगभग log₂ n जाँच: 16 → 4, 10 लाख → 20।
- मर्ज सॉर्ट: सूची को दो में बाँटो, हर आधा क्रम में लगाओ, मिलाओ: O(n log n)।
- तेज़ घात: a⁸ = ((a²)²)²: 7 की जगह 3 गुणा।
- द्विभाजन से मूल खोजना: उस अंतराल को आधा करते जाओ जहाँ फ़ंक्शन का चिह्न बदलता है।
लालची एल्गोरिदम
लालची (greedy) एल्गोरिदम वह चुनाव करता है जो अभी सबसे अच्छा दिखे और उसे कभी नहीं बदलता।
- 50, 20, 10, 5, 2, 1 से छुट्टे देना: पहले सबसे बड़ा सिक्का। इस तरह की सिक्का प्रणाली में सबसे अच्छा।
- एक दिन में सबसे ज़्यादा गतिविधियाँ चुनना: हमेशा वह लो जो सबसे पहले खत्म हो। सबसे अच्छा।
- भिन्नात्मक नैपसैक: पहले प्रति kg सबसे ज़्यादा मूल्य वाली चीज़ें। सबसे अच्छा।
पर लालची हमेशा सही नहीं: 1, 3, 4 के सिक्कों से 6 देने पर 4 + 1 + 1 (3 सिक्के), जबकि 3 + 3 में 2। लालची तरीके पर भरोसा करने के लिए उसे सिद्ध करना या पक्के तरीके से जाँचना होता है।
डायनेमिक प्रोग्रामिंग और बैकट्रैकिंग
डायनेमिक प्रोग्रामिंग (DP)
जब वही छोटी समस्याएँ बार-बार आएँ, हर एक को एक बार हल करके उत्तर तालिका में रखो। रकम a के लिए सबसे कम सिक्के: best[a] = 1 + min(best[a - c]), सभी सिक्कों c ≤ a पर, शुरुआत best[0] = 0। सिक्के 1, 3, 4 के लिए: best = 0, 1, 2, 1, 1, 2, 2। छोटे से बड़े की ओर तालिका भरना bottom-up है; याददाश्त वाला पुनरावर्तन top-down (memoization)। ज़्यादा के लिए अलग "डायनेमिक प्रोग्रामिंग" पाठ देखो।
बैकट्रैकिंग
हल को एक-एक चुनाव से बनाओ। अगर कोई चुनाव नियम तोड़े या बंद गली में ले जाए, उसे वापस लो और अगला विकल्प आज़माओ। भूलभुलैया, सुडोकू, N-क्वीन पहेली और सारे उपसमुच्चय गिनने में काम आता है। यह सावधान ब्रूट फ़ोर्स है: जो शाखाएँ काम नहीं कर सकतीं उन्हें पूरा छोड़ देता है।
ब्रूट फ़ोर्स
हर संभव उत्तर आज़माओ। हमेशा सही, पर अक्सर बहुत धीमा (2ⁿ उपसमुच्चय, n! क्रम)।
तकनीक चुनना: सही होना, दक्षता और डेटा संरचनाएँ
| तकनीक | कब | उदाहरण | आम समय |
|---|---|---|---|
| ब्रूट फ़ोर्स | इनपुट बहुत छोटा | 3 अंकों के सारे पासवर्ड | अक्सर 2ⁿ या n! |
| विभाजन और विजय | भाग स्वतंत्र हों | बाइनरी सर्च, मर्ज सॉर्ट | O(log n), O(n log n) |
| लालची | स्थानीय सबसे अच्छा चुनाव सुरक्षित सिद्ध हो | गतिविधि चयन, छुट्टे | O(n log n) |
| डायनेमिक प्रोग्रामिंग | उप-समस्याएँ दोहराएँ | सिक्का समस्या, सबसे छोटे रास्ते | तालिका का आकार |
| बैकट्रैकिंग | नियमों वाली खोज | भूलभुलैया, सुडोकू | घातांकी, पर छँटाई के साथ |
सिद्ध करो
सही होना: दिखाओ कि एल्गोरिदम हमेशा रुकता है और सही आउटपुट देता है (लूप इनवेरिएंट, प्रमाण, या किनारे वाले मामलों पर जाँच)। दक्षता: n बढ़ने पर चरण गिनो (Big O) और दूसरे तरीकों से तुलना करो।
डेटा संरचनाएँ मदद करती हैं
तालिका (DP) के लिए ऐरे, बैकट्रैकिंग के लिए स्टैक (कहाँ लौटना है याद रखने को), स्तर-दर-स्तर खोज के लिए क्यू। बाइनरी ट्री में हर नोड के अधिकतम दो बच्चे होते हैं; बाइनरी सर्च ट्री में छोटी कुंजियाँ बाएँ और बड़ी दाएँ जाती हैं, इसलिए हर स्तर पर खोज का काम आधा होता है, बिल्कुल बाइनरी सर्च की तरह।
करके देखो: सिक्के और अनुमान का खेल
- दोस्त के साथ 1-100 अनुमान का खेल खेलो। हमेशा बीच वाली पूछो। क्या 7 सवालों में हमेशा जीत सकते हो? (2⁷ = 128।)
- 1, 3, 4 के सिक्कों के लिए 0 से 10 तक की DP तालिका कागज़ पर लिखो। लालची कहाँ गलत होता है?
- 3D का आख़िरी कदम खोलो। सिक्के 1, 7, 10 और रकम 14 लो। लालची 10 + 1 + 1 + 1 + 1 देता है; DP 7 + 7।
- "सूची में सबसे छोटी संख्या खोजो" की चरण सूची लिखो और 5, 5, 5 तथा सिर्फ़ एक संख्या पर जाँचो।
मुख्य सूत्र और परिभाषाएँ
- विनिर्देश = इनपुट + आउटपुट + शर्तें
- आधा करना: लगभग log₂ n चरण (16 → 4, 1024 → 10)
- सिक्का DP: best[0] = 0; best[a] = 1 + min best[a - c]
- विभाजन और विजय = बाँटो + हल करो + जोड़ो
- लालची तेज़ है पर सबसे अच्छा होना सिद्ध करना पड़ता है
हल किए गए उदाहरण
1. n संख्याओं में सबसे बड़ी खोजने का विनिर्देश और चरण सूची लिखो।
इनपुट: n ≥ 1 संख्याएँ। आउटपुट: सबसे बड़ी। चरण: 1. best ← पहली संख्या। 2. हर दूसरी संख्या x के लिए: अगर x > best, best ← x। 3. best दिखाओ। 4, 9, 2, 7, 12, 5, 10, 3 के लिए 7 तुलनाओं के बाद आउटपुट 12।
2. 1 से 1000 में संख्या खोजने के लिए आधा करने वाले कितने सवाल चाहिए?
हर सवाल सीमा आधी करता है: 1000 → 500 → 250 → 125 → 63 → 32 → 16 → 8 → 4 → 2 → 1। यानी 10 सवाल (2¹⁰ = 1024 ≥ 1000)।
3. 50, 20, 10, 5, 2, 1 के सिक्कों से 87 लालची तरीके से दो।
50 (37 बचे), 20 (17), 10 (7), 5 (2), 2 (0): 50 + 20 + 10 + 5 + 2 = 5 सिक्के।
4. सिक्के 1, 3, 4 के लिए 7 तक DP तालिका भरो।
best[0]=0, [1]=1, [2]=2, [3]=1, [4]=1, [5]=min(best4, best2, best1)+1=2, [6]=min(best5, best3, best2)+1=2, [7]=min(best6, best4, best3)+1=2 (3 + 4)।
5. गतिविधियाँ (शुरू-खत्म): A 9-11, B 10-12, C 11-13, D 12-14, E 13-15। बिना टकराए सबसे ज़्यादा गतिविधियाँ चुनो।
सबसे पहले खत्म होने वाली के लालची नियम से: A (11 पर खत्म), फिर C (11 से 13), फिर E (13 से)। 3 गतिविधियाँ: A, C, E।
6. ऊपर से नीचे योजना बनाओ: एक प्रोग्राम जो कक्षा का औसत और टॉपर बताए।
स्तर 1: डेटा पढ़ो → गणना → छापो। स्तर 2: नाम और अंक सूचियों में पढ़ो; कुल और औसत निकालो; सबसे बड़ा अंक और उसका नाम खोजो; दोनों छापो। फिर हर टुकड़ा नीचे से ऊपर कोड और जाँच होता है।
आम गलतियाँ
- इनपुट और आउटपुट लिखे बिना कोड शुरू करना। कई 'बग' असल में अस्पष्ट विनिर्देश होते हैं।
- मान लेना कि लालची तरीका हमेशा सबसे अच्छा है। यह तभी चलता है जब सिद्ध हो (सिक्के 1, 3, 4 इसे तोड़ देते हैं)।
- बिना क्रम वाली सूची पर बाइनरी सर्च लगाना। आधा करने के लिए क्रमबद्ध डेटा चाहिए।
- DP को विभाजन-विजय समझना। DP दोहराई जाने वाली उप-समस्याओं के लिए है जिन्हें सहेजते हैं; विभाजन-विजय स्वतंत्र भागों में बाँटता है।