Python एल्गोरिदम

Python में Euclidean Algorithm

दो numbers का greatest common divisor निकालें।

  • मध्यम
  • 2 मिनट में पढ़ें
  • 1 चलाने योग्य उदाहरण

में Euclidean Algorithm क्या है?

समस्या क्या है

भिन्न को सरल करना, चीज़ों को बराबर समूहों में बाँटना और कई पहेलियों में वह सबसे बड़ी संख्या चाहिए जो दो संख्याओं को पूरा-पूरा भाग दे। बड़ी संख्याओं के लिए हर संभावित संख्या आज़माना धीमा है; Euclid ने 2,000 साल से भी पहले इससे कहीं तेज़ तरीका खोज लिया था।

ऐसे समझें

Euclid का तरीका ऐसा है जैसे किसी आयत को सबसे बड़ी संभव वर्गाकार टाइलों से भरना। 48 × 18 के आयत से जितना बड़ा वर्ग काट सकते हैं, काटिए, फिर बचे हुए हिस्से से, और ऐसे ही चलते रहिए। जब टुकड़े बिना कुछ बचे पूरे फ़िट हो जाएँ, तो आख़िरी वर्ग की भुजा ही जवाब है।

वर्ग काटने से कोड तक
first, second▭ आयत: 48 × 18
first % second✂️ छोटी भुजा के वर्ग काटने के बाद जो बचा
first, second = second, first % second🔁 बचे हुए टुकड़े के साथ दोहराइए
while second:✅ कुछ नहीं बचा: भुजा ही GCD है, 6
gcd(a, b) = gcd(b, a % b), जब तक शेषफल 0 न हो।
एक वाक्य में

दो पूर्णांकों का greatest common divisor (GCD) वह सबसे बड़ा धनात्मक पूर्णांक है जो दोनों को भाग देता है; Euclid का एल्गोरिदम जोड़ी (a, b) को (b, a % b) से बदलता रहता है जब तक b 0 न हो जाए।

मुख्य बातें

  1. first, second = second, first % second जोड़ी को छोटी संख्या और शेषफल से बदल देता है।
  2. 48 और 18 के लिए जोड़ियाँ हैं (48, 18), (18, 12), (12, 6), (6, 0)।
  3. while second: तब रुकता है जब शेषफल 0 हो जाए।
  4. return abs(first) negative इनपुट पर भी धनात्मक नतीजा देता है।

इसका उपयोग कब करें?

  • भिन्न और अनुपात को सरल करना।
  • लघुत्तम समापवर्त्य (LCM) निकालना: a * b // gcd(a, b)।
  • संख्याओं की पहेलियाँ, modular arithmetic और cryptography की बुनियादी बातें।

कब ज़रूरत नहीं

  • असली कोड: math.gcd built-in है और नए Python वर्ज़न में कितने भी arguments संभालता है।
  • सारे common divisors ढूँढना: GCD सिर्फ़ सबसे बड़ा देता है।

उदाहरण कोड

कोड चलाएँ →
main.py
def gcd(first, second):
    while second:
        first, second = second, first % second
    return abs(first)

print(gcd(48, 18))
इस उदाहरण के लिए Run बटन बनाएँ

अपेक्षित आउटपुट

6

यह कैसे काम करता है

Remainder zero होने पर दूसरा value GCD होता है; समय जटिलता logarithmic है।

मान बदलें और Python इंस्टॉल किए बिना CodeUtility ऑनलाइन Python कंपाइलर में प्रोग्राम चलाएँ।

अभ्यास के कार्य

बड़े dataset पर जाने से पहले input बदलें और edge cases की जाँच करें।

  1. खाली input, एक element और duplicate values जाँचें।
  2. हर चरण के बाद state दिखाएँ।
  3. Performance को दूसरे solution से तुलना करें।
Python IDE में चलाएँ →

आम गलतियाँ

शेषफल की जगह घटाना इस्तेमाल करना

बार-बार घटाने से वही जवाब मिलता है, लेकिन बहुत दूर-दूर की संख्याओं के लिए यह बहुत धीमा है।

समस्या
while first != second:
    if first > second:
        first -= second
    else:
        second -= first
सुधार
while second:
    first, second = second, first % second

यह पाठ पूरा कर लिया?

अपनी प्रगति ट्रैक करने के लिए इसे सीखा हुआ मार्क करें।

चैलेंज से अभ्यास करें

इस पाठ में सीखी बात से एक असली समस्या हल करें। हर चैलेंज ब्राउज़र में चलता है, तुरंत टेस्ट और AI रिव्यू के साथ।

सभी चैलेंज