Question

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

Answer 1

答案：略
解析：

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