หา ห.ร.ม. ด้วยขั้นตอนวิธีของยุคลิดใน Python
ในบทเรียนนี้ คุณจะหาตัวหารร่วมมาก (ห.ร.ม.) ของตัวเลขสองตัวด้วยขั้นตอนวิธีของยุคลิด
บทนำ
ปัญหาที่ต้องแก้
การทำเศษส่วนให้เป็นเศษส่วนอย่างต่ำ การแบ่งของเป็นกลุ่มเท่า ๆ กัน และปริศนาตัวเลขอีกมาก ล้วนต้องหาจำนวนที่ใหญ่ที่สุดที่หารตัวเลขทั้งสองลงตัว ถ้าตัวเลขใหญ่ การไล่ลองทุกจำนวนจะช้ามาก ยุคลิดค้นพบวิธีที่เร็วกว่ามากตั้งแต่กว่า 2,000 ปีก่อน
ลองนึกภาพแบบนี้
วิธีของยุคลิดเหมือนการปูแผ่นกระเบื้องสี่เหลี่ยมจัตุรัสให้เต็มสี่เหลี่ยมผืนผ้า โดยใช้แผ่นที่ใหญ่ที่สุดเท่าที่ทำได้ เริ่มจากตัดสี่เหลี่ยมจัตุรัสที่ใหญ่ที่สุดออกจากสี่เหลี่ยมผืนผ้า 48 × 18 แล้วตัดแบบเดียวกันจากส่วนที่เหลือไปเรื่อย ๆ เมื่อตัดได้พอดีโดยไม่มีเศษเหลือ ความยาวด้านของสี่เหลี่ยมจัตุรัสสุดท้ายคือคำตอบ
first, second▭ สี่เหลี่ยมผืนผ้า: 48 × 18first % second✂️ ส่วนที่เหลือหลังตัดสี่เหลี่ยมจัตุรัสขนาดด้านที่สั้นกว่าfirst, second = second, first % second🔁 ทำซ้ำกับชิ้นที่เหลือwhile second:✅ ไม่มีเศษเหลือ: ด้านนั้นคือ GCD คือ 6ตัวหารร่วมมาก (GCD) ของจำนวนเต็มสองตัว คือจำนวนเต็มบวกที่ใหญ่ที่สุดที่หารทั้งสองตัวลงตัว อัลกอริทึมของยุคลิดหาค่านี้โดยแทนคู่ (a, b) ด้วย (b, a % b) ไปเรื่อย ๆ จนกว่า b จะเป็น 0
ประเด็นสำคัญ
first, second = second, first % secondแทนคู่เดิมด้วยตัวที่เล็กกว่าและเศษจากการหาร- สำหรับ 48 และ 18 คู่คือ (48, 18), (18, 12), (12, 6), (6, 0)
while second:หยุดเมื่อเศษเป็น 0return abs(first)ทำให้ผลลัพธ์เป็นบวกเสมอ แม้อินพุตจะติดลบ
ใช้เมื่อไร?
- ทำเศษส่วนและอัตราส่วนให้เป็นอย่างต่ำ
- หาตัวคูณร่วมน้อย: a * b
//gcd(a, b) - ปริศนาตัวเลข เลขคณิตมอดุลาร์ และพื้นฐานการเข้ารหัส
เมื่อไรยังไม่จำเป็น
- โค้ดใช้งานจริง:
math.gcdมีให้ในตัว และใน Python รุ่นใหม่รับอาร์กิวเมนต์กี่ตัวก็ได้ - หาตัวหารร่วมทั้งหมด: GCD ให้แค่ตัวที่ใหญ่ที่สุด
โค้ดตัวอย่าง
def gcd(first, second):
while second:
first, second = second, first % second
return abs(first)
print(gcd(48, 18))
ผลลัพธ์จากการรัน
6
อธิบายโค้ด
ในแต่ละขั้น คู่ (first, second) จะถูกแทนด้วย (second, first % second) เมื่อเศษเป็น 0 ค่าที่เหลือใน first คือ ห.ร.ม. ห.ร.ม. ของ 48 และ 18 จึงเป็น 6 ฟังก์ชัน abs() ทำให้ผลลัพธ์เป็นบวกเสมอ จำนวนขั้นเพิ่มขึ้นช้ามากเมื่อเทียบกับขนาดตัวเลข ประมาณ O(log n)
เปลี่ยนค่าและรันโปรแกรมด้วย คอมไพเลอร์ Python ออนไลน์ของ CodeUtility โดยไม่ต้องติดตั้ง Python
แบบฝึกหัดเพิ่มเติม
ลองแก้โค้ดตามคำแนะนำด้านล่าง การเปลี่ยนโค้ดแล้วดูผลลัพธ์จะช่วยให้เข้าใจบทเรียนได้ดีกว่าการอ่านอย่างเดียวมาก
- ทดสอบกับลิสต์ว่าง ลิสต์ที่มีสมาชิกตัวเดียว และลิสต์ที่มีค่าซ้ำ
- แสดงสถานะหลังแต่ละขั้นเพื่อดูการทำงานของอัลกอริทึม
- จับเวลาการทำงานกับข้อมูล 100, 1,000 และ 10,000 ตัว แล้วเทียบกับวิธีอื่น
ข้อผิดพลาดที่พบบ่อย
ใช้การลบแทนการหาเศษ
การลบซ้ำ ๆ ให้คำตอบเดียวกัน แต่ช้ามากเมื่อตัวเลขสองตัวต่างกันมาก
while first != second:
if first > second:
first -= second
else:
second -= first
while second:
first, second = second, first % second
เรียนบทนี้จบแล้วใช่ไหม
ทำเครื่องหมายว่าเรียนแล้วเพื่อติดตามความคืบหน้า
ฝึกด้วยโจทย์
ใช้สิ่งที่เรียนในบทนี้แก้ปัญหาจริง ทุกโจทย์รันในเบราว์เซอร์ พร้อมการทดสอบทันทีและรีวิวจาก AI
- ตัวหารร่วมมาก หาค่ามากที่สุดที่หารทั้งสองค่าลงตัว ง่าย
- ตัวคูณร่วมน้อยที่สุด หาค่าบวกที่น้อยที่สุดที่หารด้วยทั้งสองค่าลงตัว ง่าย
- การคำนวณเศษส่วนอย่างแม่นยำ ดำเนินการกับเศษส่วนและคืนค่าเศษส่วนที่ย่อส่วนแล้ว ปานกลาง