Question

求兩個數的最大公約數的方法有很多，其中一種是輾轉相除法，用輾轉相除法求a、b的最大公約數的步驟是：計算出a÷b的余數r．若r＝0，則b為a的最大公約數；若r0，則把前面的除數b作為新的被除數，把余數r作為新的除數，繼續運算，直到余數為零，此時的除數即為a，b的最大公約數．(1)請寫出輾轉相除法求a，b的最大公約數的算法步驟；(2)用該方法求204與85的最大公約數．

Answer 1

答案：略
解析：

解：(1)輾轉相除法的算法步驟如下： ①輸入兩個數a，b： ②令r為a除以b的余數； ③若r0，則令a：＝b，b：＝r(把b的值賦給a，把r的賦給b)，轉②；否則執行④； ④輸出最大公約數b． (2)用輾轉相除法求204與85的最大公約數： 204＝85×2＋34；85＝34×2＋17； 34=17×2，所以204與85的最大公約數是17．