อัลกอริทึม Euclid ใน Python
แทนคู่จำนวนด้วยตัวหารและเศษซ้ำ ๆ
อัลกอริทึม Euclid ใน Python คืออะไร?
แทนคู่จำนวนด้วยตัวหารและเศษซ้ำ ๆ
หาตัวหารร่วมมากของจำนวนสองจำนวน
ควรใช้เมื่อใด?
- ทำความเข้าใจอัลกอริทึมและโครงสร้างข้อมูล
- สังเกตแต่ละขั้นตอนและกรณีขอบ
- เปรียบเทียบเวลาและหน่วยความจำ
โค้ดตัวอย่าง
main.py
def gcd(first, second):
while second:
first, second = second, first % second
return abs(first)
print(gcd(48, 18))ผลลัพธ์ที่คาดหวัง
6หลักการทำงาน
เมื่อเศษเป็นศูนย์ อีกค่าคือ ห.ร.ม. และมีความซับซ้อนแบบ logarithmic
เปลี่ยนค่าและรันโปรแกรมด้วย คอมไพเลอร์ Python ออนไลน์ของ CodeUtility โดยไม่ต้องติดตั้ง Python
แบบฝึกหัด
ลองเปลี่ยน input และทดสอบกรณีขอบก่อนใช้ชุดข้อมูลที่ใหญ่ขึ้น
- ทดสอบ input ว่าง หนึ่งสมาชิก และค่าซ้ำ
- แสดงสถานะหลังแต่ละขั้นตอน
- เปรียบเทียบประสิทธิภาพกับวิธีอื่น