关于最大公约数的算法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; }--
来源:学生作业帮助网 编辑:作业帮 时间:2024/07/11 19:32:17
![关于最大公约数的算法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; }--](/uploads/image/z/11259463-31-3.jpg?t=%E5%85%B3%E4%BA%8E%E6%9C%80%E5%A4%A7%E5%85%AC%E7%BA%A6%E6%95%B0%E7%9A%84%E7%AE%97%E6%B3%95int+gcd%28int+a%2Cint+b%29%7B+int+t+%3D+0%3B+int+c+%3D+0%3B+if%28a%3D%3D0%29++return+b%3B+if%28b%3D%3D0%29++return+a%3B+if%28a+%3C+b%29+%7B++++++t%3Da%3B++++a%3Db%3B++++b%3Dt%3B++%7D+c+%3D+a+%25+b%3B+while%28c+%21%3D+0%29+%7B+++++++a+%3D+b%3B++++++++b+%3D+c%3B++++++++c+%3D+a+%25+b%3B+++++%7D+return+b%3B+++++%7D--)
关于最大公约数的算法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; }--
关于最大公约数的算法
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 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; }--
这是贪心算法.
设最大公约数为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就是最大公约数.