โปรแกรมหา ห.ร.ม. กับการเขียนฟังก์ชัน gcd

| ไอที | Java | 14233

โปรแกรมหา ห.ร.ม. กับการเขียนฟังก์ชัน gcd

บทความนี้เราจะมาเขียนโปรแกรม เพื่อหาค่า ห.ร.ม. กันครับ
ห.ร.ม. คือ อะไร และหาได้ยังไง ดูได้ตามลิ้ง การหา ห.ร.ม. กับ อัลกอริทึมของยุคลิด

โปรแกรมหา ห.ร.ม. แบบแยกตัวประกอบ

public static void main(String[] args) {
	Scanner in = new Scanner(System.in);
	System.out.print("Input First for GCD : ");
	int first = in.nextInt();
	System.out.print("Input Second for GCD : ");
	int second = in.nextInt();
	System.out.println(gcd(first, second));
}
public static int gcd(int first, int second){
	List<Integer> compoundFirst = new ArrayList<Integer>(); // แยกตัวประกอบตัวแรก
	int num = 2;
	while(num < first){
		if(first%num == 0){
			compoundFirst.add(num);
			first = first/num;
			num = 1;
		}
		num++;
	}
	compoundFirst.add(first);
	List<Integer> compoundSecond = new ArrayList<Integer>(); // แยกตัวประกอบตัวที่สอง
	num = 2;
	while(num < second){
		if(second%num == 0){
			compoundSecond.add(num);
			second = second/num;
			num = 1;
		}
		num++;
	}
	compoundSecond.add(second);
	int result = 1;
	for (int i = 0; i < compoundFirst.size(); i++) {
		for (int j = 0; j < compoundSecond.size(); j++) {
			if(compoundFirst.get(i) == compoundSecond.get(j)){ // เช็คว่าเหมือนกันหรือเปล่า
				result *= compoundSecond.get(j);
				compoundSecond.remove(j);
				break;
			}
		}
	}
	return result;
}

โปรแกรมหา ห.ร.ม. แบบหารสั้น

public static void main(String[] args) {
	Scanner in = new Scanner(System.in);
	System.out.print("Input First for GCD : ");
	int first = in.nextInt();
	System.out.print("Input Second for GCD : ");
	int second = in.nextInt();
	System.out.println(gcd(first, second));
}
public static int gcd(int first, int second){
	if(first%second == 0 || second%first == 0) {
		return Math.min(first, second);
	}
	int result = 1;
	int num = 2;
	int min = Math.min(first, second);
	while(num < min){
		if(first%num == 0 && second%num == 0){ // เช็คว่าหารทั้งสองตัวลงตัว
			result = num*result;
			first = first/num;
			second = second/num;
			num = 1;
		}
		num++;
	}
	return result;
}

โปรแกรมหา ห.ร.ม. แบบอัลกอริทึมของยุคลิด

หา ห.ร.ม. โดยวิธีอัลกอริทึมของยุคลิด แบบใช้ while
public static void main(String[] args) {
	Scanner in = new Scanner(System.in);
	System.out.print("Input First for GCD : ");
	int first = in.nextInt();
	System.out.print("Input Second for GCD : ");
	int second = in.nextInt();
	System.out.println(gcd(first, second));
}
public static int gcd(int first, int second){
	if(first%second == 0) {
		return Math.min(first, second);
	}
	int result = 1;
	while(first%second != 0){
			result = first%second;
			first = second;
			second = result;
	}
	return result;
}
หา ห.ร.ม. โดยวิธีอัลกอริทึมของยุคลิด แบบการเขียนฟังก์ชัน แบบ recursive
public static void main(String[] args) {
	Scanner in = new Scanner(System.in);
	System.out.print("Input First for GCD : ");
	int first = in.nextInt();
	System.out.print("Input Second for GCD : ");
	int second = in.nextInt();
	System.out.println(gcd(first, second));
}
public static int gcd(int a, int b){
	if(a%b == 0) {
		return b;
	}
	//System.out.println(a + " = " + b + "*" + a/b + " + " + a%b);
	return gcd(b, a%b);
}
comments