โปรแกรม Python สำหรับอัลกอริธึมแบบยุคลิดขยาย

ในบทความนี้ เราจะเรียนรู้เกี่ยวกับวิธีแก้ปัญหาตามที่ระบุด้านล่าง

แจ้งปัญหา − ให้ตัวเลขสองตัวนั้น เราจำเป็นต้องคำนวณ gcd ของตัวเลขสองตัวนั้นและแสดงออกมา

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

ตัวแปรทั้งหมดได้รับการประกาศในขอบเขตท้องถิ่นและการอ้างอิงของตัวแปรนั้นดูได้จากรูปด้านบน

บทสรุป

ในบทความนี้ เราได้เรียนรู้เกี่ยวกับวิธีการสร้างโปรแกรม Python สำหรับอัลกอริธึม Extended Euclidean