Question

辗转相除法求最大公约数采用的是________算法。

Answer 1

一，原题解释：
问题：辗转相除法求最大公约数采用的是________算法。
答案：欧几里德算法
二，辗转相除法的定义
辗转相除法，又称欧几里德算法，是求两个数的最大公约数的一种方法。用较大的数除以较小的数，再以除数和余数反复做除法运算，当余数为0时，取当前算式除数为最大公约数。

三，辗转相除法的原理
1.a/b=q余r，除数b和余数r能被同一个数整除，那么被除数a也能被这个数整除。或者说，除数与余数的最大公约数，就是被除数与除数的最大公约数。
2.即被除数与除数的最大公约数，就是除数与余数的最大公约数。

四，辗转相除法的程序设计
1.辗转相除法是利用以下性质来确定两个正整数 a 和 b 的最大公因子的：
（1）若 r 是 a ÷ b 的余数，且r不为0， 则gcd(a,b) = gcd(b,r)
（2）a 和其倍数之最大公因子为 a。
2.另一种写法是：
（1） 令r为a/b所得余数（0≤r）若 r= 0，算法结束；b 即为答案。
（2） 互换：置 a←b，b←r，并返回第一步。