GCD, LCM และอัลกอริทึมยูคลิด
คำนวณตัวหารอย่างรวดเร็วและถูกต้อง
GCD, LCM และอัลกอริทึมยูคลิด เป็นบทเรียน Coding Interview Prep ฟรีบน CoddyKit นี่คือบทเรียนที่ 1 จากทั้งหมด 4 บทเรียน คุณสามารถอ่านบทเรียนทั้งหมดด้านล่างฟรี — จากนั้นลองปฏิบัติด้วยตัวคุณเองในเบราว์เซอร์พร้อมตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7 บทเรียนนี้เป็นส่วนหนึ่งของเส้นทางการเรียน Coding Interview Prep และความก้าวหน้าของคุณจะซิงค์ข้ามเว็บและแอป CoddyKit คอร์ส Coding Interview Prep มีบทเรียนทั้งหมด 4 บทเรียน
เหตุใดตัวหารจึงสำคัญ
โจทย์การแข่งขันจำนวนมากขึ้นอยู่กับตัวประกอบร่วมของตัวเลขสองจำนวน เครื่องมือที่มีประโยชน์ที่สุดในเรื่องนี้คือ GCD หรือตัวหารร่วมมาก 🔢
GCD หมายถึงอะไร
GCD ของจำนวนเต็มสองจำนวนคือจำนวนที่มากที่สุดซึ่งหารทั้งสองจำนวนลงตัว สำหรับ 12 และ 18 ค่าดังกล่าวคือ 6 เพราะ 6 แบ่งทั้งสองจำนวนได้ลงตัว
วิธีที่ช้า
คุณอาจทดสอบทุกจำนวนโดยเริ่มจากค่าที่น้อยกว่าแล้วไล่ลงมาจนกว่าจะพบจำนวนที่หารทั้งสองจำนวนลงตัว วิธีนี้ใช้ได้ แต่ ช้าเกินไปสำหรับข้อมูลนำเข้าขนาดใหญ่
ข้อสังเกตของยุคลิด
ขั้นตอนวิธีแบบยุคลิดเป็นวิธีที่รวดเร็ว แนวคิดสำคัญคือ GCD ของ a และ b เท่ากับ GCD ของ b และเศษเหลือจากการหาร a ด้วย b
ความสัมพันธ์เวียนเกิด
ทำขั้นตอนสลับค่าและหาเศษซ้ำไปจนกว่าเศษเหลือจะเป็นศูนย์ ค่าที่ไม่เป็นศูนย์ตัวสุดท้ายคือคำตอบ หรือก็คือ GCD นั่นเอง
gcd(a, b) = gcd(b, a % b)
gcd(a, 0) = aเขียนโค้ดด้วยตนเอง
ลูปสั้น ๆ จะคอยแทนที่คู่ค่าไปเรื่อย ๆ จนกว่า b จะเป็นศูนย์ วิธีนี้ใช้เวลาประมาณ log ขั้นตอน จึงรวดเร็วมากแม้ใช้กับตัวเลขขนาดใหญ่มาก
def gcd(a, b):
while b:
a, b = b, a % b
return aใช้ไลบรารีมาตรฐาน
โดยทั่วไปคุณแทบไม่จำเป็นต้องเขียนเอง Python มี math.gcd ซึ่งถูกต้อง รวดเร็ว และจัดการอาร์กิวเมนต์ที่เป็นศูนย์ให้คุณ
from math import gcd
print(gcd(12, 18))จาก GCD สู่ LCM
LCM หรือตัวคูณร่วมน้อย คือจำนวนที่น้อยที่สุดซึ่งค่าทั้งสองจำนวนหารลงตัว และมีความเชื่อมโยงโดยตรงกับ GCD ที่คุณเพิ่งคำนวณ
สูตร LCM
คูณตัวเลขทั้งสองจำนวน แล้วหารด้วย GCD ของทั้งคู่ ให้หาร ก่อนเสมอเพื่อหลีกเลี่ยงค่าล้นเมื่อผลคูณมีขนาดใหญ่มาก
def lcm(a, b):
return a // gcd(a, b) * bGCD ของรายการทั้งหมด
หากต้องการคำนวณ GCD ของตัวเลขหลายจำนวน ให้คำนวณต่อกันทีละคู่ Python มี การลดรูปที่ใช้ math.gcd จากซ้ายไปขวาตลอดรายการ
from functools import reduce
from math import gcd
g = reduce(gcd, nums)จัดการกรณีศูนย์
ตามนิยาม gcd(a, 0) เท่ากับ a และ gcd(0, 0) เท่ากับ 0 การรู้จักกรณีขอบนี้ช่วยให้ลูปของคุณไม่ทำงานผิดพลาดเมื่อข้อมูลนำเข้าว่างเปล่า
ตรวจสอบอย่างรวดเร็ว
ได้เวลายืนยันขั้นตอนหลักของวิธีแบบยุคลิด
สรุป
ตอนนี้คุณสามารถคำนวณ GCD ด้วยขั้นตอนวิธีแบบยุคลิดในจำนวนขั้นระดับ log หา LCM จาก GCD และคำนวณทั้งสองค่าต่อเนื่องตลอดรายการได้แล้ว ✅
คำถามที่พบบ่อย
บทเรียน “GCD, LCM และอัลกอริทึมยูคลิด” ฟรีหรือไม่
ใช่ — ข้อความเต็มของ “GCD, LCM และอัลกอริทึมยูคลิด” ฟรีให้อ่านที่นี่บนเว็บ เพื่อปฏิบัติแบบโต้ตอบ (ตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7) และปลดล็อคส่วนที่เหลือของคอร์ส Coding Interview Prep ให้อัปเกรดเป็น CoddyKit PRO คอร์ส Coding Interview Prep มีบทเรียนทั้งหมด 4 บทเรียน
คุณจะเรียนรู้อะไรในบทเรียน “GCD, LCM และอัลกอริทึมยูคลิด”
คำนวณตัวหารอย่างรวดเร็วและถูกต้อง คุณปฏิบัติ Coding Interview Prep ด้วยโค้ดที่ใช้งานได้จริงที่คุณเรียกใช้โดยตรงในเบราว์เซอร์ และติวเตอร์ AI ตลอด 24/7 ตอบคำถามของคุณขณะที่คุณไปผ่านบทเรียน
คุณต้องมีประสบการณ์ก่อนที่จะเริ่มเรียน Coding Interview Prep หรือไม่
ไม่จำเป็นต้องมีประสบการณ์มาก่อน Coding Interview Prep บน CoddyKit ออกแบบมาสำหรับผู้เริ่มต้นไปจนถึงผู้เรียนขั้นสูง คุณสามารถเริ่มต้นที่นี่หรือเริ่มจากตัวแรกและเรียนด้วยความเร็วของคุณเอง นี่คือบทเรียนที่ 1 จากทั้งหมด 4 บทเรียน
บทเรียน “GCD, LCM และอัลกอริทึมยูคลิด” ใช้เวลานานแค่ไหน
บทเรียน CoddyKit ส่วนใหญ่ใช้เวลาประมาณ 5–10 นาที แต่ละบทเรียนจึงสั้นและเป็นแบบโต้ตอบ คุณสามารถก้าวหน้าอย่างต่อเนื่องและกลับมาเรียนต่อจากตรงที่เพิ่งหยุดบนเว็บและแอปได้เลย
ฉันเขียนและรันโค้ดในบทเรียน Coding Interview Prep นี้ได้ไหม
ได้ บทเรียน Coding Interview Prep ทุกบทมีตัวแก้ไขโค้ดในตัว คุณจึงเขียนและรันโค้ดจริงได้เลยในเบราว์เซอร์ และได้รับข้อเสนอแนะจาก AI ในทันที — ไม่ต้องติดตั้งในเครื่องของคุณ
บทเรียนทั้งหมดในหลักสูตรนี้
- GCD, LCM และอัลกอริทึมยูคลิด
- การทดสอบจำนวนเฉพาะถึง sqrt(n)
- ตะแกรงของเอราโตสเทนีส
- การแยกตัวประกอบจำนวนเฉพาะและตัวหาร