所謂互質為兩個或兩個以上的整數彼此之間的最大公因數是1，而最簡分 數為分子和分母互質的分數。 請使用C語言完成函數int coprime (int a, int…

題目

所謂互質為兩個或兩個以上的整數彼此之間的最大公因數是1，而最簡分 數為分子和分母互質的分數。 請使用C語言完成函數int coprime (int a, int b)，來檢查正整數a與b是否 互質。如果互質，則函數回傳值為1，反之回傳0。（10分） 使用上述函數，寫一個C語言程式，來找出一最簡分數，其分子與分母 的和為70，且該分數化為小數並四捨五入後為0.6。（15分）

參考解答（AI 生成，非官方）

• 一、互質（coprime）與解題策略：兩正整數 a、b 若最大公因數（greatest common divisor, gcd）為 1，即稱互質。實作上採輾轉相除法（Euclidean algorithm），反覆以餘數取代除數，直到餘數為 0，此時非零的除數即為 gcd；若 gcd 等於 1 則回傳 1，否則回傳 0。須注意邊界條件：gcd(a,0)=a，故 a=1 時與任何 b 互質；輸入為負數時宜先取絕對值，避免取餘运算出現負值。
• 二、函數程式碼：int coprime(int a, int b){ if(a<0) a=-a; if(b<0) b=-b; while(b!=0){ int t=a%b; a=b; b=t; } return (a==1)?1:0; }　此寫法時間複雜度為 O(log min(a,b))，不需遞迴、不會有堆疊溢位風險；若 a、b 皆為 0，迴圈不執行且 a==0，回傳 0，符合「非互質」的直覺。
• 三、第二小題的數學分析：設最簡分數為 a/b，且 a+b=70，因分數值約 0.6 小於 1，故為真分數且 a<b，得 a=70−b。四捨五入至小數第一位為 0.6，表示 0.55 ≤ a/b < 0.65；代入 a=70−b 得 1.55 ≤ 70/b < 1.65，即 42.42 < b ≤ 45.16，故 b 只能為 43、44、45，對應 a 為 27、26、25。
• 四、逐一驗證：27/43 = 0.6279，四捨五入為 0.6，且 gcd(27,43)=1，符合最簡；26/44 = 0.5909，四捨五入亦為 0.6，但 gcd=2 非最簡（化簡為 13/22，分子分母和為 35）；25/45 = 0.5556，四捨五入為 0.6，但 gcd=5 非最簡（化簡為 5/9，和為 14）。故符合條件的唯一解為 27/43。
• 五、程式碼範例：int main(void){ for(int b=2;b<70;++b){ int a=70-b; if(a<=0||a>=b) continue; if(!coprime(a,b)) continue; double v=(double)a/b; if(round(v*10)==6) printf("%d/%d=%.4f\n",a,b,v); } return 0; }　執行後輸出 27/43=0.6279。為避免浮點誤差，判定宜改用整數運算 20*a>=11*b 且 20*a<13*b（因 0.55=11/20、0.65=13/20），或使用 round(v*10.0)==6；在 Linux 環境編譯時須加 -lm 連結數學函式庫。

AI 依官方試題文字產生的參考解答，非考選部公告答案，內容僅供備考參考。

官方資料

• 官方試題 PDF