高二伪代码,急啊!!
来源:百度知道 编辑:UC知道 时间:2024/05/03 11:48:39
怎么用伪代码表示求a,b,c这三个数的最大公约数?
定理:gcd(a,b) = gcd(b,a mod b)
证明:a可以表示成a = kb + r,则r = a mod b
假设d是a,b的一个公约数,则有
d|a, d|b,而r = a - kb,因此d|r
因此d是(b,a mod b)的公约数
下面是c++描述
void swap(int & a, int & b){
int c = a;
a = b;
b = c;
}
int gcd(int a,int b){
if(0 == a ){
return b;
}
if( 0 == b){
return a;
}
if(a > b){
swap(a,b);
}
int c;
for(c = a % b ; c > 0 ; c = a % b){
a = b;
b = c;
}
return b;
}
给你一个链接网站,上面是介绍辗转相除法求最大公约数:http://baike.baidu.com/view/255668.htm