ตัวหารร่วมมาก (G.C.D.) เขียนด้วยตัวเองทำยังไงดี

โจทย์

ในคณิตศาสตร์ ตัวหารร่วมมาก หรือ ห.ร.ม. (greatest common divisor: gcd) ของจำนวนเต็มสองจำนวนซึ่งไม่เป็นศูนย์พร้อมกัน คือจำนวนเต็มที่มากที่สุดที่หารทั้งสองจำนวนลงตัว

โจทย์ จงเขียนโปรแกรมหา ห.ร.ม. ของจำนวนเต็ม 2 จำนวนที่กำหนดให้

ข้อมูลนำเข้า บรรทัดแรกระบุจำนวนเต็มสามจำนวน $a$ และ $b$ มีค่าไม่เกิน $2\times10^9$

ข้อมูลส่งออก มีบรรทัดเดียวเป็นห.ร.ม. ของทั้งสองจำนวน

ตัวอย่างข้อมูลนำเข้าและข้อมูลส่งออก

Input	Output
12 14	2
7 3	1

วิเคราะห์โจทย์

เชื่อว่าหลายคนที่เขียนโปรแกรมมานิดหน่อยก็คงรู้อยู่แล้วว่าการหา ห.ร.ม. เนี่ยมันมีฟังก์ชัน built-in มาให้ใน C++ หรือ ภาษาอื่นๆอยู่แล้ว (Python นี่ยิ่งง่ายเลย)

แต่ถ้าใช้อันนั้นมันก็ไม่ได้ทำให้เราเข้าใจวิธีการหา ห.ร.ม. อ่ะนะ ดังนั้นรอบนี้เลยจะเอาวิธีอื่นๆมาใช้กัน

แบบ 1: หาตัวประกอบทั้งหมด

ข้อสังเกตแรกคือถ้าสมมติเราดูค่าตัวนึงอยู่ สมมติให้เป็น $S$ เป็นค่าที่เราดูอยู่ จะได้ว่า

S=p\times q

ถ้าเราสมมติให้ $p\leq q$ จะได้ว่า $p$ จะมีค่าไม่เกิน $\sqrt{S}$ เพราะถ้าเกินไปแล้วจะผิดเงื่อนไขที่สมมติขึ้นมา ทำให้ได้ว่าเราก็แค่ลูปค่า $p$ ตั้งแต่ 1 ถึง $\sqrt{S}$

กลับมาที่โจทย์ดั้งเดิม เราจะได้ว่าการหาตัวประกอบร่วมของ $a$ และ $b$ สามารถทำได้ด้วยการลูปค่าถึง $\sqrt{a}$ เพื่อหาค่าตัวประกอบของ $a$ แล้วเอาค่าตัวประกอบแต่ละตัวของ $a$ มาดูค่าว่ามีตัวไหนบ้างที่เป็นตัวประกอบของ $b$ บ้าง แล้วเอาค่ามากที่สุดมาเป็นคำตอบ

แบบ 2: ใช้ Euclidean Algorithm

สังเกตนิดนึงก่อนโดย สมมติว่าแทนให้ $g$ เป็น ห.ร.ม. ของ $a$ และ $b$ และ $a < b$

สิง่ที่เราจะได้คือ

b = a \times q_1 + r_1

เรารู้ว่า $g$ หารทั้ง $a$ และ $b$ ลงตัวแปลว่า $g$ ก็ต้องหาร $r_1$ ลงตัวด้วย นั่นแปลว่า ห.ร.ม. ของ $a$ กับ $b$ ก็มีค่าเท่ากับ ห.ร.ม. ของ $a$ กับ $r_1$ ซึ่งถ้าใช้วิธีเดิมคิดต่อก็จะได้ว่า

a = r_1 \times q_2 + r_2

ซึ่งแน่นอนว่า $g$ ก็ต้องหาร $r_2$ ลงตัวด้วย นั่นแปลว่า $g$ ก็ยังเป็น ห.ร.ม. ของ $r_1$ กับ $r_2$ ด้วย

และเราสามารถทำวิธีนี้ซ้ำไปเรื่อยๆได้ เลขที่เราต้องใช้คำนวณก็จะค่อยๆลดลงไปเรื่อยๆเหมือนกัน จนกระทั่งมีเลขนึงกลายเป็น $0$ ซึ่งมันจะได้สมการแบบนี้มา

r_n = r_{n+1} \times q_n + 0

ซึ่งแปลว่า $g$ ก็ต้องเป็น ห.ร.ม ของ $r_{n+1}$ และ $0$ ซึ่งก็คือ $r_{n+1}$ นั่นแหละ และก็แปลว่าขอแค่เราหา $r_{n+1}$ ได้ เราก็สามารถหา ห.ร.ม. ของ $a$ และ $b$ ได้นั่นเอง

เขียนเป็นโค้ดกัน

เราก็จะใช้หลักการเดียวกับที่อธิบายข้างต้นเลย ก็คือ

เราต้องการให้ตัวหลังเป็น 0 เพื่อที่ตัวที่เหลือจะเป็นห.ร.ม. ของ a และ b
ถ้าตัวหลังไม่ใช่ 0 แปลว่าเรายังไม่เจอห.ร.ม. เราก็จะค่อยๆหารไปตามสมการข้างต้น

1
uint_8 _gcd(uint_8 a, uint_8 b) {
2
  if (b == 0) return a;
3
  return _gcd(b, a % b);
4
}

อ้างอิง

ลองทำเองได้ที่ Programming.in.th

https://programming.in.th/tasks/0014

Wikipedia - Euclidean Algorithm

https://en.wikipedia.org/wiki/Euclidean_algorithm

The Euclidean Algorithm by Khan Academy

https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/the-euclidean-algorithm

แชร์หน่อยก๊าบ ⊹

คัดลอกแล้ว!