关于最大公约数的算法
题目
关于最大公约数的算法
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;
}
为什么这么算能得出结果?求解释
答案
这是贪心算法.设最大公约数为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...
举一反三
已知函数f(x)=x,g(x)=alnx,a∈R.若曲线y=f(x)与曲线y=g(x)相交,且在交点处有相同的切线,求a的值和该切线方程.
我想写一篇关于奥巴马的演讲的文章,写哪一篇好呢?为什么好
最新试题
热门考点
- We shell help our mother do the housework tomorrow(对do the housework 提问)
- 日常生活中,你听过的生动语言有哪些?选几句写下来.
- 井然有序的序是什么意思?帮帮忙吧!
- 抽象代数:G是循环群,G-是群,G与G-同态,则G-是循环群.
- 詹天佑课文 示意图怎么画
- 补充词语,再分类,有些词填好的
- 一个“6V 3W”的灯泡接在9V的电压下,要使他正常发光,应接入阻值多大的电阻?(三种解法)若不接电阻,灯泡实际功率多大?
- 磁通量的全部导出单位有哪些?
- 6筐放相等鸡蛋从各筐拿150鸡蛋,6筐剩鸡蛋总和等于原两筐鸡蛋总和.问原各筐多少
- 压力管道水压试验注水为什么从下游向上游注水?