โปรแกรม Java หาตัวหารร่วมมาก (GCD) ด้วย Recursion

ในบทความนี้ เราจะทำความเข้าใจวิธี หาตัวหารร่วมมาก (Greatest Common Divisor - GCD) ด้วย Recursion โดยใช้ อัลกอริธึมยุคลิด (Euclidean Algorithm)

หลักการ: GCD(a, b) = GCD(b, a % b) จนกว่า b จะเป็น 0 แล้วคำตอบคือ a

ตัวอย่าง Input และ Output

Input:

Enter two numbers: 24 and 36

Output:

The G.C.D of 24 and 36 is 12.

อัลกอริธึม

ขั้นตอนที่ 1 - เริ่มต้น
ขั้นตอนที่ 2 - ประกาศตัวแปร my_input_1, my_input_2, my_result
ขั้นตอนที่ 3 - อ่านค่าจากผู้ใช้ หรือกำหนดค่าเริ่มต้น
ขั้นตอนที่ 4 - สร้างฟังก์ชัน CommonFactor แบบ recursive รับ 2 ตัวเลข
ขั้นตอนที่ 5 - ถ้า my_input_2 != 0 เรียก CommonFactor(my_input_2, my_input_1 % my_input_2)
ขั้นตอนที่ 6 - ถ้า my_input_2 == 0 คืนค่า my_input_1
ขั้นตอนที่ 7 - เรียกฟังก์ชันและแสดงผล
ขั้นตอนที่ 8 - หยุด

ตัวอย่างที่ 1: รับค่าจากผู้ใช้

import java.util.Scanner;
public class GCD {
    public static void main(String[] args) {
        int my_input_1, my_input_2, my_result;
        System.out.println("Required packages have been imported");
        Scanner my_scanner = new Scanner(System.in);
        System.out.println("A reader object has been defined");
        System.out.print("Enter the first number : ");
        my_input_1 = my_scanner.nextInt();
        System.out.print("Enter the second number : ");
        my_input_2 = my_scanner.nextInt();
        my_result = CommonFactor(my_input_1, my_input_2);
        System.out.printf("The G.C.D of %d and %d is %d.", my_input_1, my_input_2, my_result);
    }
    public static int CommonFactor(int my_input_1, int my_input_2) {
        if (my_input_2 != 0)
            return CommonFactor(my_input_2, my_input_1 % my_input_2);
        else
            return my_input_1;
    }
}

Output

Required packages have been imported
A reader object has been defined
Enter the first number : 24
Enter the second number : 36
The G.C.D of 24 and 36 is 12.

ตัวอย่างที่ 2: กำหนดค่าไว้ล่วงหน้า

public class GCD {
    public static void main(String[] args) {
        int my_input_1, my_input_2, my_result;
        my_input_1 = 24;
        my_input_2 = 36;
        System.out.println("The numbers are defined as " + my_input_1 + " and " + my_input_2);
        my_result = CommonFactor(my_input_1, my_input_2);
        System.out.printf("The G.C.D of %d and %d is %d.", my_input_1, my_input_2, my_result);
    }
    public static int CommonFactor(int my_input_1, int my_input_2) {
        if (my_input_2 != 0)
            return CommonFactor(my_input_2, my_input_1 % my_input_2);
        else
            return my_input_1;
    }
}

Output

The numbers is defined as 24 and 36
The G.C.D of 24 and 36 is 12.