पायथन प्रोग्राम एक्सटेंडेड यूक्लिडियन एल्गोरिदम के लिए

इस लेख में, हम नीचे दिए गए समस्या कथन के समाधान के बारे में जानेंगे।

समस्या कथन - दी गई दो संख्याओं का GCD (महत्तम समापवर्तक) गणना करके प्रदर्शित करना है।

दो संख्याओं का GCD वह सबसे बड़ी संख्या है जो दोनों को विभाजित कर सके। यहां हम यूक्लिडियन दृष्टिकोण का पालन करते हैं: बार-बार संख्याओं को विभाजित करें और तब रुकें जब शेषफल शून्य हो जाए। यहां हम पुनरावृत्ति में प्राप्त पिछले मानों के आधार पर एल्गोरिदम को विस्तारित करते हैं।

उदाहरण

# एक्सटेंडेड यूक्लिडियन एल्गोरिदम\ndef gcdExtended(a, b, x, y):\n    # बेस केस\n    if a == 0:\n        x = 0\n        y = 1\n        return b\n    x1 = 1\n    y1 = 1  # परिणाम संग्रहीत करने के लिए\n    gcd = gcdExtended(b % a, a, x1, y1)\n    # पिछले गणना किए गए मानों के साथ x और y को अपडेट करें\n    x = y1 - (b / a) * x1\n    y = x1\n    return gcd\n\nx = 1\ny = 1\na = 11\nb = 15\ng = gcdExtended(a, b, x, y)\nprint("gcd of", a, "&", b, "is =", g)

आउटपुट

gcd of 11 & 15 is = 1

सभी वेरिएबल्स स्थानीय स्कोप में घोषित हैं और उनके संदर्भ ऊपर दिए गए चित्र में देखे जा सकते हैं।

निष्कर्ष

इस लेख में, हमने सीखा कि पायथन में एक्सटेंडेड यूक्लिडियन एल्गोरिदम के लिए प्रोग्राम कैसे बनाया जाए।