โปรแกรม Python สำหรับ Extended Euclidean Algorithm (อัลกอริทึมยุคลิดขยาย)

ในบทความนี้ เราจะเรียนรู้วิธีการแก้ปัญหาต่อไปนี้:

ข้อความปัญหา — กำหนดตัวเลข 2 ตัว ให้คำนวณ GCD (ตัวหารร่วมมาก) ของตัวเลขทั้งสองและแสดงผล

GCD (Greatest Common Divisor) ของตัวเลข 2 ตัวคือตัวเลขที่มากที่สุดที่หารทั้งสองตัวลงตัว ที่นี่เราใช้วิธี Euclidean ในการคำนวณ GCD คือ หารซ้ำๆ จนกว่าจะได้เศษเป็นศูนย์ ที่นี่เราขยายอัลกอริทึมโดยอิงจากค่าที่ได้จากการเรียกซ้ำ (recursion) ก่อนหน้า

มาเปลี่ยนดูโค้ดตัวอย่างด้านล่างนี้:

ตัวอย่างโค้ด

# Extended Euclidean Algorithm
def gcdExtended(a, b, x, y):
    # Base Case
    if a == 0:
        x = 0
        y = 1
        return b
    x1 = 1
    y1 = 1  # เก็บผลลัพธ์
    gcd = gcdExtended(b % a, a, x1, y1)
    # อัปเดต x และ y ด้วยค่าที่คำนวณได้ก่อนหน้า
    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

ตัวแปรทั้งหมดถูกประกาศในขอบเขตท้องถิ่น (local scope) และการอ้างอิงของมันแสดงในรูปภาพด้านบน

สรุป

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