อัลกอริทึม Python

หา ห.ร.ม. ด้วยขั้นตอนวิธีของยุคลิดใน Python

ในบทเรียนนี้ คุณจะหาตัวหารร่วมมาก (ห.ร.ม.) ของตัวเลขสองตัวด้วยขั้นตอนวิธีของยุคลิด

  • ระดับกลาง
  • อ่าน 2 นาที
  • ตัวอย่างที่รันได้ 1 ตัวอย่าง

บทนำ

ปัญหาที่ต้องแก้

การทำเศษส่วนให้เป็นเศษส่วนอย่างต่ำ การแบ่งของเป็นกลุ่มเท่า ๆ กัน และปริศนาตัวเลขอีกมาก ล้วนต้องหาจำนวนที่ใหญ่ที่สุดที่หารตัวเลขทั้งสองลงตัว ถ้าตัวเลขใหญ่ การไล่ลองทุกจำนวนจะช้ามาก ยุคลิดค้นพบวิธีที่เร็วกว่ามากตั้งแต่กว่า 2,000 ปีก่อน

ลองนึกภาพแบบนี้

วิธีของยุคลิดเหมือนการปูแผ่นกระเบื้องสี่เหลี่ยมจัตุรัสให้เต็มสี่เหลี่ยมผืนผ้า โดยใช้แผ่นที่ใหญ่ที่สุดเท่าที่ทำได้ เริ่มจากตัดสี่เหลี่ยมจัตุรัสที่ใหญ่ที่สุดออกจากสี่เหลี่ยมผืนผ้า 48 × 18 แล้วตัดแบบเดียวกันจากส่วนที่เหลือไปเรื่อย ๆ เมื่อตัดได้พอดีโดยไม่มีเศษเหลือ ความยาวด้านของสี่เหลี่ยมจัตุรัสสุดท้ายคือคำตอบ

จากการตัดสี่เหลี่ยมจัตุรัสสู่โค้ด
first, second▭ สี่เหลี่ยมผืนผ้า: 48 × 18
first % second✂️ ส่วนที่เหลือหลังตัดสี่เหลี่ยมจัตุรัสขนาดด้านที่สั้นกว่า
first, second = second, first % second🔁 ทำซ้ำกับชิ้นที่เหลือ
while second:✅ ไม่มีเศษเหลือ: ด้านนั้นคือ GCD คือ 6
gcd(a, b) = gcd(b, a % b) จนเศษเป็น 0
สรุปในประโยคเดียว

ตัวหารร่วมมาก (GCD) ของจำนวนเต็มสองตัว คือจำนวนเต็มบวกที่ใหญ่ที่สุดที่หารทั้งสองตัวลงตัว อัลกอริทึมของยุคลิดหาค่านี้โดยแทนคู่ (a, b) ด้วย (b, a % b) ไปเรื่อย ๆ จนกว่า b จะเป็น 0

ประเด็นสำคัญ

  1. first, second = second, first % second แทนคู่เดิมด้วยตัวที่เล็กกว่าและเศษจากการหาร
  2. สำหรับ 48 และ 18 คู่คือ (48, 18), (18, 12), (12, 6), (6, 0)
  3. while second: หยุดเมื่อเศษเป็น 0
  4. return abs(first) ทำให้ผลลัพธ์เป็นบวกเสมอ แม้อินพุตจะติดลบ

ใช้เมื่อไร?

  • ทำเศษส่วนและอัตราส่วนให้เป็นอย่างต่ำ
  • หาตัวคูณร่วมน้อย: a * b // gcd(a, b)
  • ปริศนาตัวเลข เลขคณิตมอดุลาร์ และพื้นฐานการเข้ารหัส

เมื่อไรยังไม่จำเป็น

  • โค้ดใช้งานจริง: math.gcd มีให้ในตัว และใน Python รุ่นใหม่รับอาร์กิวเมนต์กี่ตัวก็ได้
  • หาตัวหารร่วมทั้งหมด: GCD ให้แค่ตัวที่ใหญ่ที่สุด

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

รันโค้ด →
main.py
def gcd(first, second):
    while second:
        first, second = second, first % second
    return abs(first)

print(gcd(48, 18))
สร้างปุ่ม Run สำหรับตัวอย่างนี้

ผลลัพธ์จากการรัน

6

อธิบายโค้ด

ในแต่ละขั้น คู่ (first, second) จะถูกแทนด้วย (second, first % second) เมื่อเศษเป็น 0 ค่าที่เหลือใน first คือ ห.ร.ม. ห.ร.ม. ของ 48 และ 18 จึงเป็น 6 ฟังก์ชัน abs() ทำให้ผลลัพธ์เป็นบวกเสมอ จำนวนขั้นเพิ่มขึ้นช้ามากเมื่อเทียบกับขนาดตัวเลข ประมาณ O(log n)

เปลี่ยนค่าและรันโปรแกรมด้วย คอมไพเลอร์ Python ออนไลน์ของ CodeUtility โดยไม่ต้องติดตั้ง Python

แบบฝึกหัดเพิ่มเติม

ลองแก้โค้ดตามคำแนะนำด้านล่าง การเปลี่ยนโค้ดแล้วดูผลลัพธ์จะช่วยให้เข้าใจบทเรียนได้ดีกว่าการอ่านอย่างเดียวมาก

  1. ทดสอบกับลิสต์ว่าง ลิสต์ที่มีสมาชิกตัวเดียว และลิสต์ที่มีค่าซ้ำ
  2. แสดงสถานะหลังแต่ละขั้นเพื่อดูการทำงานของอัลกอริทึม
  3. จับเวลาการทำงานกับข้อมูล 100, 1,000 และ 10,000 ตัว แล้วเทียบกับวิธีอื่น
รันในคอมไพเลอร์ Python →

ข้อผิดพลาดที่พบบ่อย

ใช้การลบแทนการหาเศษ

การลบซ้ำ ๆ ให้คำตอบเดียวกัน แต่ช้ามากเมื่อตัวเลขสองตัวต่างกันมาก

ปัญหา
while first != second:
    if first > second:
        first -= second
    else:
        second -= first
วิธีแก้
while second:
    first, second = second, first % second

เรียนบทนี้จบแล้วใช่ไหม

ทำเครื่องหมายว่าเรียนแล้วเพื่อติดตามความคืบหน้า

ฝึกด้วยโจทย์

ใช้สิ่งที่เรียนในบทนี้แก้ปัญหาจริง ทุกโจทย์รันในเบราว์เซอร์ พร้อมการทดสอบทันทีและรีวิวจาก AI

โจทย์ทั้งหมด