एल्गोरिदम और योग की विधि
रेसिपी चरण क्रम से देती है ताकि कोई भी वही व्यंजन बना सके। गणितीय एल्गोरिदम ऐसी रेसिपी है जो सदा सही उत्तर दे।
एल्गोरिदम किसी समस्या को हल करने वाले, समाप्त होने वाले स्पष्ट क्रमबद्ध चरणों की सीमित सूची है। स्तंभ-योग एक है : दाईं ओर से अंक जोड़ें, इकाई अंक लिखें और शेष हासिल रखें।
सूत्र : एल्गोरिदम = स्पष्ट चरण + क्रम + अंत
आकृति में : 478 + 365 : 8 + 5 = 13 (3 लिखें, 1 हासिल); 7 + 6 + 1 = 14 (4 लिखें, 1 हासिल); 4 + 3 + 1 = 8। उत्तर 843।
नियम 1 : एल्गोरिदम का पालन करें — हर चरण लिखे अनुसार करें, हासिल न छोड़ें।
- आसान : 59 + 27 = 86।
- मध्यम : 999 + 1 = 1000 (हासिल हर जगह)।
- परीक्षा-प्रकार : 1234 + 4321 = 5555 (हासिल नहीं)।
नियम 2 : अच्छा एल्गोरिदम कैसा — स्पष्ट चरण, हर बार वही उत्तर और अंत में रुकना।
- आसान : "1 जोड़ते रहो" एल्गोरिदम नहीं; यह खत्म नहीं होता।
- मध्यम : "लगभग सही कर लो" पर्याप्त स्पष्ट नहीं।
- परीक्षा-प्रकार : चरण क्रम में हों : अगले स्तंभ से पहले हासिल।
एक ही समस्या के कई सही एल्गोरिदम हो सकते हैं।
हासिल भूलना या गलत स्तंभ में जोड़ना।
"दाएँ से बाएँ, हासिल साथ।"
अभ्यास के प्रश्न
- 1प्रत्येक एल्गोरिथ्म की कौन-सी विशेषता आवश्यक है?
- 270 + 21 को इकाई से स्तंभ-दर-स्तंभ जोड़ते समय दहाई के स्तंभ में कौन-सा हासिल जाता है?
- 3638 + 833 को स्तंभ-दर-स्तंभ जोड़ने पर हासिल कितनी बार आता है?
- 4259 + 608 जोड़ने पर दहाई के स्तंभ में कौन-सा अंक लिखा जाता है और सैकड़े के स्तंभ में कौन-सा हासिल जाता है?
- 5एक 5-अंकीय संख्या और एक 1-अंकीय संख्या के योग में अधिकतम कितने अंक हो सकते हैं?
- 6माया ने 754 + 638 जोड़ा और उसे 1192 मिला। उसके उत्तर में पहला गलत अंक (दाईं ओर से गिनने पर) किस स्तंभ में है?
- 74885 + 7024 को स्तंभ-दर-स्तंभ (इकाई, दहाई, सैकड़ा, हज़ार) जोड़ने पर हासिल कितनी बार आता है?
- 854 + 93 + 16 जोड़ने पर इकाई के स्तंभ से दहाई के स्तंभ में कौन-सा हासिल जाता है?
उत्तर देखें (पहले खुद हल करें)
- 1प्रत्येक चरण स्पष्ट और सटीक होता है
- 20
- 32
- 4अंक 6, हासिल 0
- 56
- 6सैकड़े का स्तंभ
- 72
- 81
भाजक ज्ञात करना
36 छात्र समान पंक्तियों में बिठाने को 36 को भाग देने वाली संख्याएँ चाहिए : 1, 2, 3, 4, 6, 9, 12, 18 या 36।
n का भाजक वह है जो उसे पूरा भाग दे। भाजक जोड़ियों में आते हैं जिनका गुणनफल n है। केवल √n तक जाँचें : हर d ≤ √n का साथी n ÷ d।
सूत्र : d | n ⇒ (n ÷ d) | n; d ≤ √n जाँचें
आकृति में : 36 के लिए 6 तक जाँचें; हर सफलता जोड़ी देती है : 1 और 36, 2 और 18, 3 और 12, 4 और 9, 6 और 6।
नियम 1 : सभी भाजक लिखें — 1, 2, 3, … √n तक जाँचें और दोनों साथी लिखें।
- आसान : 12 : 1, 2, 3, 4, 6, 12।
- मध्यम : 30 : 1, 2, 3, 5, 6, 10, 15, 30।
- परीक्षा-प्रकार : 17 (अभाज्य) : केवल 1 और 17।
नियम 2 : भाजक गिनें — पूर्ण वर्ग के विषम भाजक होते हैं क्योंकि वर्गमूल स्वयं से जोड़ी बनाता है।
- आसान : 36 के 9 भाजक (विषम, पूर्ण वर्ग)।
- मध्यम : 97 के लिए 9 तक जाँचें : कोई भाग नहीं देता, अतः अभाज्य।
- परीक्षा-प्रकार : हर संख्या के भाजक 1 और वह स्वयं।
√n पर रुकने से बहुत जाँच बचती है।
साथी भाजक भूलना, जैसे 12 के लिए 1, 2, 3, 4, 6 लिखकर 12 छोड़ना।
"एक खोजो, एक मुफ़्त।"
अभ्यास के प्रश्न
- 1कौन-सी संख्या प्रत्येक प्राकृत संख्या का भाजक होती है?
- 2किस सूची में 18 के सभी भाजक दिए गए हैं?
- 336 के कितने भाजक हैं?
- 46, 180 का एक भाजक है। 180 का और कौन-सा भाजक है (6 की जोड़ीदार संख्या)?
- 54, 48 का एक भाजक है। 48 का और कौन-सा भाजक है (4 की जोड़ीदार संख्या)?
- 61 से बड़ा 253 का सबसे छोटा भाजक कौन-सा है?
- 71 से बड़ा 161 का सबसे छोटा भाजक कौन-सा है?
- 860 के सभी भाजकों का योग क्या है?
उत्तर देखें (पहले खुद हल करें)
- 11
- 21, 2, 3, 6, 9, 18
- 39
- 430
- 512
- 611
- 77
- 8168
उभयनिष्ठ भाजक और म.स.
12 m और 18 m के फीतों को बिना बर्बादी समान टुकड़ों में काटने को टुकड़े की लंबाई दोनों को भाग दे। सबसे बड़ा ऐसा टुकड़ा म.स. है।
उभयनिष्ठ भाजक दोनों संख्याओं को भाग देता है। म.स. (GCD) उनमें सबसे बड़ा। म.स. 1 वाली संख्याएँ सह-अभाज्य।
सूत्र : म.स.(12, 18) = 6; म.स.(a, b) = 1 ⇒ सह-अभाज्य
आकृति में : 12 और 18 के भाजक 1, 2, 3, 6 में उभयनिष्ठ; सबसे बड़ा 6।
नियम 1 : म.स. ज्ञात करें — दोनों के भाजक लिखकर सबसे बड़ा उभयनिष्ठ लें, या अभाज्य गुणनखंड लगाएँ।
- आसान : म.स.(8, 12) = 4।
- मध्यम : म.स.(15, 28) = 1, इसलिए सह-अभाज्य।
- परीक्षा-प्रकार : म.स.(36, 48) = 12।
नियम 2 : म.स. का उपयोग — बिना शेष सबसे बड़े समान समूह या टाइलें : म.स.।
- आसान : 24 पेन और 36 पेंसिलें अधिकतम किट में समान : 12 किट।
- मध्यम : 120 cm × 80 cm फर्श के लिए वर्ग टाइलें : भुजा 40 cm।
- परीक्षा-प्रकार : 18/24 सरल करें : 6 से भाग देकर 3/4।
म.स. छोटी संख्या से बड़ा नहीं होता।
म.स. (बड़ा भाजक) और ल.स. (छोटा गुणज) में गड़बड़ी।
"दोनों में जाने वाला सबसे बड़ा।"
अभ्यास के प्रश्न
- 124 और 36 के कितने उभयनिष्ठ भाजक हैं?
- 216 और 24 का म.स. (महत्तम समापवर्तक) क्या है?
- 378 और 117 का म.स. ज्ञात कीजिए।
- 4क्या 72 और 16 सह-अभाज्य हैं (क्या उनका एकमात्र उभयनिष्ठ भाजक 1 है)?
- 5म.स. की सहायता से 15/21 को सबसे सरल रूप में लिखिए।
- 6एक क्लब में 56 लड़के और 98 लड़कियाँ हैं। उनकी टीमें इस प्रकार बनानी हैं कि प्रत्येक टीम में लड़कों की संख्या बराबर हो और लड़कियों की संख्या भी बराबर हो, तथा कोई भी शेष न रहे। अधिकतम कितनी टीमें बन सकती हैं?
- 760, 90 और 150 को पूरा-पूरा भाग देने वाली सबसे बड़ी संख्या ज्ञात कीजिए।
- 8दो संख्याओं का म.स. 8 है। वे 8 × 5 और 8 × 6 हैं, जहाँ 5 और 6 सह-अभाज्य हैं। उनका योग क्या है?
उत्तर देखें (पहले खुद हल करें)
- 16
- 28
- 339
- 4नहीं
- 55/7
- 614
- 730
- 888
यूक्लिड का एल्गोरिदम
अनुमान से सबसे बड़ी वर्ग टाइल खोजना धीमा है। यूक्लिड का विचार : शेष पट्टी तब तक काटते रहें जब तक कुछ न बचे।
यूक्लिड का एल्गोरिदम : बड़ी संख्या को छोटी से भाग दें, फिर (a, b) की जगह (b, शेषफल) लें। शेषफल 0 होने तक दोहराएँ; अंतिम अशून्य शेषफल म.स. है।
सूत्र : म.स.(a, b) = म.स.(b, a ÷ b का शेषफल)
आकृति में : 48 ÷ 18 शेष 12, 18 ÷ 12 शेष 6, 12 ÷ 6 शेष 0, इसलिए म.स.(48, 18) = 6।
नियम 1 : एल्गोरिदम चलाएँ — हर पंक्ति : बड़ी = भागफल × छोटी + शेषफल।
- आसान : म.स.(100, 75) : 100 = 1×75 + 25, 75 = 3×25 + 0, इसलिए 25।
- मध्यम : म.स.(252, 105) = 21।
- परीक्षा-प्रकार : म.स.(17, 5) : 17 = 3×5 + 2, 5 = 2×2 + 1, 2 = 2×1 + 0, इसलिए 1।
नियम 2 : यह क्यों काम करता है — a और b को भाग देने वाली संख्या शेषफल को भी भाग देती है, इसलिए जोड़ी वही म.स. रखकर छोटी होती जाती है।
- आसान : म.स.(a, b) = म.स.(a − b, b)।
- मध्यम : शेषफल छोटे होते जाते, इसलिए रुकना ही है।
- परीक्षा-प्रकार : विशाल संख्याओं के लिए चलता है जहाँ भाजक लिखना असंभव।
यूक्लिड की विधि सभी भाजक लिखने से बहुत तेज़।
अंतिम शेषफल 0 को उत्तर लेना, उससे पहले का अशून्य शेषफल नहीं।
"भाग दो, शेष लो, दोहराओ।"
अभ्यास के प्रश्न
- 1147 को 13 से भाग देने पर शेषफल क्या बचता है?
- 2यूक्लिड की एल्गोरिथ्म के अनुसार म.स.(263, 62) = म.स.(?, ?)। अगली जोड़ी कौन-सी है?
- 3यूक्लिड की एल्गोरिथ्म से म.स.(252, 99) ज्ञात कीजिए।
- 4म.स.(432, 101) ज्ञात करने के लिए (शेषफल 0 होने तक) यूक्लिड की एल्गोरिथ्म को भाग के कितने चरण लगते हैं?
- 5403 और 125 के लिए यूक्लिड की एल्गोरिथ्म में पहले भाग से शेषफल 28 मिलता है। दूसरा शेषफल (125 को 28 से भाग देने पर) क्या है?
- 6यूक्लिड की एल्गोरिथ्म से म.स.(361, 228) ज्ञात कीजिए।
- 7क्रमागत फिबोनाची संख्याएँ यूक्लिड की एल्गोरिथ्म के लिए सबसे कठिन स्थिति होती हैं। म.स.(233, 144) ज्ञात करने में भाग के कितने चरण लगते हैं?
- 8150 को 48 से भाग देने पर शेषफल 6 बचता है। यदि म.स.(48, 6) = 6 दिया हो, तो म.स.(150, 48) क्या है?
उत्तर देखें (पहले खुद हल करें)
- 14
- 2(62, 15)
- 39
- 47
- 513
- 619
- 711
- 86
यूक्लिड का एल्गोरिदम
ऐप में इस आकृति को हाथ से हिलाकर देख सकते हैं।
ऐप में खोलेंचरण गिनना और दक्षता
दो रास्ते एक ही गाँव; कम मोड़ वाला बेहतर। अच्छा एल्गोरिदम वही उत्तर कम चरणों में देता है।
एल्गोरिदम की दक्षता इससे आँकी जाती है कि उसे कितने चरण लगते हैं। समान निवेश पर चरण गिनकर एल्गोरिदम की तुलना करें। चरण प्रायः निवेश के आकार के साथ बढ़ते हैं।
सूत्र : समान उत्तर के लिए कम चरण = अधिक दक्ष
आकृति में : यूक्लिड GCD(1071, 462) = 21 को 3 भागों में निकालता है; भाजक सूची में कहीं अधिक काम।
नियम 1 : चरण गिनें — हर भाग (या जाँच) को एक चरण गिनें।
- आसान : 97 के लिए 9 तक : 9 जाँच, 96 नहीं।
- मध्यम : यूक्लिड से म.स.(48, 18) : 3 भाग।
- परीक्षा-प्रकार : 100 संख्याएँ एक-एक करके जोड़ना : 99 जोड़।
नियम 2 : एल्गोरिदम की तुलना — बड़े निवेश के लिए कम चरण वाला एल्गोरिदम चुनें।
- आसान : जोड़ी बनाकर 1 + 100, 2 + 99 … 50 जोड़ियाँ; एक-एक करके 99।
- मध्यम : √n तक भाजक जाँचना n तक से बेहतर।
- परीक्षा-प्रकार : निवेश का आकार दुगुना करने पर चरण प्रायः बढ़ते हैं।
बहुत बड़ी संख्याओं के लिए दक्ष एल्गोरिदम सबसे महत्त्वपूर्ण।
एल्गोरिदम को लिखने में छोटा होने से आँकना, चरणों से नहीं।
"कम चरण, तेज़ उत्तर।"
अभ्यास के प्रश्न
- 1एक सूची में 26 अलग-अलग संख्याएँ हैं। सबसे बड़ी संख्या ज्ञात करने के लिए प्रत्येक संख्या की अब तक की सर्वश्रेष्ठ संख्या से तुलना की जाती है। कितनी तुलनाएँ करनी पड़ेंगी?
- 215 संख्याओं का कुल योग एक-एक करके जोड़ने पर कितने जोड़ करने पड़ते हैं?
- 325 और 8 प्रविष्टियों वाली दो सूचियों में उभयनिष्ठ वस्तुएँ खोजने के लिए पहली सूची की प्रत्येक प्रविष्टि की दूसरी सूची की प्रत्येक प्रविष्टि से तुलना की जाती है। कुल कितनी तुलनाएँ होती हैं?
- 4दो सूचियों में 50 और 20 प्रविष्टियाँ हैं। आप पहली सूची की प्रत्येक प्रविष्टि एक बार पढ़ते हैं और फिर दूसरी सूची की प्रत्येक प्रविष्टि एक बार पढ़ते हैं। कुल कितनी प्रविष्टियाँ पढ़ी जाती हैं?
- 5विधि A, 15 प्रविष्टियों वाली सूची की प्रत्येक वस्तु की 18 प्रविष्टियों वाली सूची की प्रत्येक वस्तु से तुलना करती है। विधि B दोनों सूचियों को केवल एक बार पढ़ती है। विधि A को विधि B से कितने चरण अधिक लगते हैं?
- 6एक चरण में 5 मिलीसेकंड लगते हैं। m × n = 200 × 50 चरणों वाली विधि को कितने मिलीसेकंड लगेंगे?
- 7दोनों सूचियों में प्रत्येक में 1000 प्रविष्टियाँ हैं। विधि A को 1000×1000 चरण लगते हैं और विधि B को 1000+1000 चरण। A को B से कितने गुना चरण लगते हैं?
- 8दो क्लर्क एक साथ दो सूचियाँ पढ़ते हैं, प्रत्येक सूची के लिए एक क्लर्क। सूचियों में 60 और 55 प्रविष्टियाँ हैं। दोनों सूचियाँ पूरी पढ़ी जाने तक कितने चक्र (प्रति चक्र प्रत्येक क्लर्क की एक प्रविष्टि) लगेंगे?
उत्तर देखें (पहले खुद हल करें)
- 125
- 214
- 3200
- 470
- 5237
- 650000
- 7500
- 860