[Java] UVa 11827 Maximum GCD

題目連結

題意:
一序列兩兩計算最大公因數(GCD)，求出最大值

解法:
主要是 GCD 的計算，在自定義的 getGCD 方法中
用遞迴的手法實現類似輾轉相除法求 GCD

參數 a, b
若 a > b，a % b就是 a 一直扣掉 b直到剩下小於b的數
當這個數為0，則輸出 b (表示當下的 b是 a 的因數，更是 a b的GCD)

若 a < b， a % b = a
getGCD(b, a%b); 等於把兩數交換放參數再做一次
也因此此方法可適用所有情況(不論a b誰較大)

依序倆倆呼叫 getGCD 方法，最後輸出最大值即可

程式(Java):

	package uva;
	import java.util.*;
	public class UVa11827 {
	public static int getGCD(int a, int b) {
	if (b == 0)
	return a;
	else
	return getGCD(b, a%b);
	}
	public static void main(String args[]) {
	Scanner sc = new Scanner(System.in);
	int N = Integer.valueOf(sc.nextLine());
	while (N-- > 0) {
	StringTokenizer st = new StringTokenizer(sc.nextLine());
	int data[] = new int[st.countTokens()];
	for (int i = 0; i < data.length; i++)
	data[i] = Integer.parseInt(st.nextToken());
	int max = 0;
	for (int i = 0; i < data.length - 1; i++) {
	for (int j = i + 1; j < data.length; j++) {
	max = getGCD(data[i], data[j]) > max ? getGCD(data[i], data[j]) : max;
	}
	}
	System.out.println(max);
	}
	}
	}

view raw UVa11827.java hosted with ❤ by GitHub