Statement

เพื่อไม่ให้สับสนกับปัญหาจึงขอทบทวนและขยายความปัญหาอีกครั้งดังนี้ มีจำนวนเต็ม $2$ ตัวชื่อ $a$ และ $b$ จงแสดงตัวหารร่วมมาก (ห.ร.ม.) ของ $a$ และ $b$

โดย greatest common divisor (gcd) หรือ ห.ร.ม คือจำนวนเต็มที่มากที่สุดที่หารทั้ง $a$ และ $b$ ลงตัว ทั้งนี้ $a$ และ $b$ ต้องไม่เป็น $0$ พร้อมกัน เพราะถ้า $a = b = 0$ แล้ว ไม่ว่าจำนวนเต็มใด ๆ ก็หารทั้ง $a$ และ $b$ ลงตัวเสมอ ทำให้หาค่ามากสุดไม่ได้ เราจึงถือว่าไม่มี ห.ร.ม. ในกรณีดังกล่าว

พิจารณากรณีที่ $a$ หรือ $b$ เป็น $0$ เพียงตัวใดตัวหนึ่ง เราสามารถตอบได้ทันทีว่า ห.ร.ม. คือ $a + b$ ตัวอย่างเช่น $a = 0, b = 97$ จะได้ว่า ห.ร.ม ก็คือ $a + b = 0 + 97 = 97$ กล่าวได้ว่าตัวเลข $97$ เป็นจำนวนเต็มที่มากที่สุดที่หารทั้ง $a = 0$ และ $b = 97$ ลงตัว

Solution

พิจารณากรณีทั่วไปที่ $a > 0$ และ $b > 0$ สามารถใช้ขั้นตอนวิธีของ Euclid มาแก้ได้ กล่าวคือ ให้ $\gcd(a, b)$ เป็นฟังก์ชันที่คืนค่าตัวหารร่วมมากของจำนวนเต็ม $a$ และ $b$ จากนั้น Euclid ได้นิยามความสัมพันธ์ของฟังก์ชัน $\gcd$ ดังกล่าวไว้ดังนี้

จากนิยามดังกล่าวยังครอบคลุมกรณี $a$ หรือ $b$ ตัวใดตัวหนึ่งเป็น $0$ ด้วย ตัวอย่างเช่น $\gcd(0, 97) = \gcd(97, 0 \mod 97) = \gcd(97, 0) = 97$

ในเชิงของการเขียนโปแกรม เราสามารถใช้หลักการของฟังก์ชันเรียกตัวเอง (recursive function) เพื่อเลียนแบบพฤติกรรมของนิยามฟังก์ชันของ Euclid ได้โดยตรง เพียงแต่ต้องระวังเรื่องลำดับเงื่อนไขให้ดี ๆ เช่นการเขียนกรณีฐาน (base case) มักจะเขียนไว้บรรทัดแรกสุดของ recursive function เพื่อให้มีจังหวะการหยุดการทำงาน

Code

#include <stdio.h>

int gcd(int a, int b) {
  if (b == 0) // กรณีฐาน
    return a;
  return gcd(b, a % b); // กรณีเรียกตัวเอง
}

int main() {
  int a, b;
  scanf("%d%d", &a, &b);
  printf("%d", gcd(a, b));
  return 0;
}