UC知道关于最大公约数的算法
来源：百度知道 编辑：UC知道 时间：2024/05/22 12:32:37
int gcd(int a,int b)
{
int t = 0;
int c = 0;
if(a==0)
return b;
if(b==0)
return a;
if(a < b)
{
t=a;
a=b;
b=t;
}
c = a % b;
while(c != 0)
{
a = b;
b = c;
c = a % b;
}
return b;
}
--------------------------------------------------
c = a % b;
while(c != 0)
{
a = b;
b = c;
c = a % b;
}
为什么这么算能得出结果？求解释
{
int t = 0;
int c = 0;
if(a==0)
return b;
if(b==0)
return a;
if(a < b)
{
t=a;
a=b;
b=t;
}
c = a % b;
while(c != 0)
{
a = b;
b = c;
c = a % b;
}
return b;
}
--------------------------------------------------
c = a % b;
while(c != 0)
{
a = b;
b = c;
c = a % b;
}
为什么这么算能得出结果？求解释
这是贪心算法。
设最大公约数为X，则存在整数i，j使得：
a = i*X，b = j*X
又因为c = a % b 所以存在整数k使得：
c = a-k*b = i*X - k*j*X = (i-j*k)*X
即X也是c的公约数，然后a = b; b = c;
如此循环，总有b = k*a的时侯，这时b就是最大公约数。
我平常用碾转相除法,这程序太长没劲