Python में Euclidean Algorithm
दो numbers का greatest common divisor निकालें।
में Euclidean Algorithm क्या है?
समस्या क्या है
भिन्न को सरल करना, चीज़ों को बराबर समूहों में बाँटना और कई पहेलियों में वह सबसे बड़ी संख्या चाहिए जो दो संख्याओं को पूरा-पूरा भाग दे। बड़ी संख्याओं के लिए हर संभावित संख्या आज़माना धीमा है; Euclid ने 2,000 साल से भी पहले इससे कहीं तेज़ तरीका खोज लिया था।
ऐसे समझें
Euclid का तरीका ऐसा है जैसे किसी आयत को सबसे बड़ी संभव वर्गाकार टाइलों से भरना। 48 × 18 के आयत से जितना बड़ा वर्ग काट सकते हैं, काटिए, फिर बचे हुए हिस्से से, और ऐसे ही चलते रहिए। जब टुकड़े बिना कुछ बचे पूरे फ़िट हो जाएँ, तो आख़िरी वर्ग की भुजा ही जवाब है।
first, second▭ आयत: 48 × 18first % second✂️ छोटी भुजा के वर्ग काटने के बाद जो बचाfirst, second = second, first % second🔁 बचे हुए टुकड़े के साथ दोहराइएwhile second:✅ कुछ नहीं बचा: भुजा ही GCD है, 6दो पूर्णांकों का greatest common divisor (GCD) वह सबसे बड़ा धनात्मक पूर्णांक है जो दोनों को भाग देता है; Euclid का एल्गोरिदम जोड़ी (a, b) को (b, a % b) से बदलता रहता है जब तक b 0 न हो जाए।
मुख्य बातें
first, second = second, first % secondजोड़ी को छोटी संख्या और शेषफल से बदल देता है।- 48 और 18 के लिए जोड़ियाँ हैं (48, 18), (18, 12), (12, 6), (6, 0)।
while second:तब रुकता है जब शेषफल 0 हो जाए।return abs(first)negative इनपुट पर भी धनात्मक नतीजा देता है।
इसका उपयोग कब करें?
- भिन्न और अनुपात को सरल करना।
- लघुत्तम समापवर्त्य (LCM) निकालना: a * b
//gcd(a, b)। - संख्याओं की पहेलियाँ, modular arithmetic और cryptography की बुनियादी बातें।
कब ज़रूरत नहीं
- असली कोड:
math.gcdbuilt-in है और नए Python वर्ज़न में कितने भी arguments संभालता है। - सारे common divisors ढूँढना: GCD सिर्फ़ सबसे बड़ा देता है।
उदाहरण कोड
def gcd(first, second):
while second:
first, second = second, first % second
return abs(first)
print(gcd(48, 18))
अपेक्षित आउटपुट
6
यह कैसे काम करता है
Remainder zero होने पर दूसरा value GCD होता है; समय जटिलता logarithmic है।
मान बदलें और Python इंस्टॉल किए बिना CodeUtility ऑनलाइन Python कंपाइलर में प्रोग्राम चलाएँ।
अभ्यास के कार्य
बड़े dataset पर जाने से पहले input बदलें और edge cases की जाँच करें।
- खाली input, एक element और duplicate values जाँचें।
- हर चरण के बाद state दिखाएँ।
- Performance को दूसरे solution से तुलना करें।
आम गलतियाँ
शेषफल की जगह घटाना इस्तेमाल करना
बार-बार घटाने से वही जवाब मिलता है, लेकिन बहुत दूर-दूर की संख्याओं के लिए यह बहुत धीमा है।
while first != second:
if first > second:
first -= second
else:
second -= first
while second:
first, second = second, first % second
यह पाठ पूरा कर लिया?
अपनी प्रगति ट्रैक करने के लिए इसे सीखा हुआ मार्क करें।
चैलेंज से अभ्यास करें
इस पाठ में सीखी बात से एक असली समस्या हल करें। हर चैलेंज ब्राउज़र में चलता है, तुरंत टेस्ट और AI रिव्यू के साथ।
- महत्तम समापवर्तक (GCD) दोनों मानों को विभाजित करने वाली सबसे बड़ी संख्या ज्ञात करें। आसान
- लघुत्तम समापवर्त्य (LCM) दोनों मानों से विभाजित होने वाली सबसे छोटी धनात्मक संख्या ज्ञात करें। आसान
- सटीक भिन्न अंकगणित भिन्नों पर गणनाएँ करें और एक सरलीकृत भिन्न लौटाएँ। मध्यम