โปรแกรมหาตัวหารร่วมมากโดยใช้การเรียกซ้ำ
โจทย์
Write a recursive function to calculate the greatest common divisor (GCD) of two integers, x and y. The GCD of x and y is the largest integer that evenly divides both x and y. The GCD is defined recursively as follows: If y is equal to 0, then gcd(x,y)
is x; otherwise, gcd(x,y) is gcd(y,x%y), where % is the remainder operator.
| Input | Output |
|---|---|
| 48 18 | 6 |
โค้ด
import java.util.Scanner;
public class Program {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int x = scanner.nextInt();
int y = scanner.nextInt();
System.out.println(gcd(x, y));
}
public static int gcd(int x, int y) {
if (y == 0) return x;
return gcd(y, x % y);
}
}หลักการทำงาน
Euclidean Algorithm
- หาเศษ (remainder) จากการหาร x ด้วย y
- ถ้าเศษเป็น 0 แสดงว่า y คือ GCD
- ถ้าไม่ใช่ ให้แทนที่ x ด้วย y และ y ด้วยเศษที่ได้
- ทำซ้ำจนกว่าจะได้เศษเป็น 0
สูตรคณิตศาสตร์
gcd(x,y) = x เมื่อ y = 0
gcd(x,y) = gcd(y, x mod y) เมื่อ y ≠ 0คำอธิบาย
การนำเข้าไลบรารี่
import java.util.Scanner; // สำหรับรับข้อมูลจากผู้ใช้1. เมธอด main
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int x = scanner.nextInt(); // รับค่าตัวเลขแรก
int y = scanner.nextInt(); // รับค่าตัวเลขที่สอง
System.out.println(gcd(x, y)); // เรียกใช้เมธอด gcd และแสดงผล
}2. เมธอด gcd
public static int gcd(int x, int y) {
if (y == 0) return x; // เงื่อนไขจบการเรียกซ้ำ (base case)
return gcd(y, x % y); // เรียกซ้ำด้วยค่าใหม่ (recursive case)
}ตัวอย่างการทำงาน
ตัวอย่าง: หา GCD ของ 48 และ 18
การทำงานแบบเรียกซ้ำ:
1. gcd(48, 18)
- x = 48, y = 18
- 48 ÷ 18 = 2 เหลือเศษ 12
→ gcd(18, 12)
2. gcd(18, 12)
- x = 18, y = 12
- 18 ÷ 12 = 1 เหลือเศษ 6
→ gcd(12, 6)
3. gcd(12, 6)
- x = 12, y = 6
- 12 ÷ 6 = 2 เหลือเศษ 0
→ gcd(6, 0)
4. gcd(6, 0)
- เนื่องจาก y = 0
- return x = 6
ดังนั้น GCD(48, 18) = 6ปรับปรุงล่าสุด