國家安全情報人員考試五等考試-資訊組資料處理大意110 年第 6 題單選題
請問以下之程式中,f(1542, 66)的值為何?
int f(int m, int n){
if (n == 0) return m;
else if (m >= n)return f(m-n, n);
else return f(n-m, m);
}
C正確答案
此函式為輾轉相減法求 GCD,gcd(1542,66)=6。
為什麼答案是 C
正確。1542=6×257、66=6×11,且 gcd(257,11)=1,故最大公因數為 6。
載入中…
完整詳解
Pro · 無限重點 此函式為輾轉相減法求 GCD,gcd(1542,66)=6。
觀察函式:n=0時回傳m;m≥n時遞迴(m-n,n);否則(n-m,m)。此即輾轉相減版的歐幾里得演算法,結果為 gcd(m,n)。
計算 gcd(1542, 66):
1542 = 66×23 + 24 → gcd(66, 24)
66 = 24×2 + 18 → gcd(24, 18)
24-18=6 → gcd(18, 6)
18 = 6×3 + 0 → gcd 為 6。
逐選項分析
A✕
2 並非 1542 與 66 的最大公因數,雖為公因數但非最大。
B✕
4 不能整除 66(66/4 非整數),不是公因數。
C✓ 正確
正確。1542=6×257、66=6×11,且 gcd(257,11)=1,故最大公因數為 6。
別誤認此為取餘數版;它是「相減版」,但結果仍為 GCD。勿被大數字嚇到,直接用質因數分解最快。