Question

谁能更详细的讲一下辗转相除法(欧几里得算法)

Answer 1

就是把上一轮有余数的除法计算中，
除数变为下一轮计算的被除数，
余数变为下一轮计算的除数，
一直这样计算下去，
直到最后一次计算余数为零，
在最后一轮计算中的被除数，即为所求的最大公约数。
举例：
105和85的最大公约数
第一轮计算
105÷85=1...20
第二轮计算
85÷20=4...5
第三轮计算
20÷5=4
第三轮没有余数，
因此
105和85的最大公约数就是第三轮计算的被除数
5.
至于c语言编程，下边是我自己写的g函数(思想就是辗转相除法求最大公约数)
int
g(int
x,int
y)
{
int
t;
while(y!=0)
{
t=x%y
;
x=y;
y=t;
}
return
x;
}

Answer 2

是为了找出A、B的最大公约数
计算出A除B的余数R
如果R=0那麼B为A、B的最大公约数
如果R不等於0，则把新的除数B作为新的被除数，
把余数R作为新的除数，一直运算，直到余数为0，
此时的除数及为正整数A、B的最大公约数