โปรแกรม Python สำหรับ Basic Euclidean Algorithm (อัลกอริทึมยุคลิดพื้นฐาน)

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

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

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

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

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

# Euclidean algorithm สำหรับคำนวณ Greatest Common Divisor
def gcd(a, b):
    if a == 0:
        return b
    return gcd(b % a, a)

a = 11
b = 15
print("gcd of", a, "&", b, "is =", gcd(a, b))

ผลลัพธ์

gcd of 11 & 15 is = 1

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

สรุป

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