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

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

समस्या कथन - दो संख्याओं को देखते हुए हमें उन दो संख्याओं की gcd की गणना करने और उन्हें प्रदर्शित करने की आवश्यकता है।

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

आइए अब नीचे दिए गए कार्यान्वयन में समाधान देखें -

उदाहरण

# extended Euclidean Algorithm
def gcdExtended(a, b, x, y):
   # Base Case
   if a == 0 :
      x = 0
      y = 1
      return b
   x1 = 1
   y1 = 1 # storing the result
   gcd = gcdExtended(b%a, a, x1, y1)
   # Update x and y with previous calculated values
   x = y1 - (b/a) * x1
   y = x1
   return gcd
x = 1
y = 1
a = 11
b = 15
g = gcdExtended(a, b, x, y)
print("gcd of ", a , "&" , b, " is = ", g)

आउटपुट

gcd of 11 & 15 is = 1

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

निष्कर्ष

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