@chawuciren
2019-09-15T04:52:30.000000Z
字数 679
阅读 648
CINTA
1、实现GCD算法的迭代版本;
/*
* Input: two integers (a and b)
* Output: the greatest common divisor of a and b
* Method: iteration
*/
int gcd(int a, int b){
int temp;
do{
temp = a%b;
a = b;
b = temp;
}while(b);
return a;
}
2、实现EGCD的C语言版本;
/*
* Input: integers a and b(a>b)
* Output: d(the greatest common divisor of a and b),s and *r(Bézout's coefficient)
* Method: iteration
*/
void egcd(int a, int b, int* s, int * r,int*d){
int r0=1,s1 = 1;
int r1=0,s0=0,q = 0,temp=0;
while (b){
q = a / b; //Seeking quotient
a = a%b;
swap(&a,&b);//Gcd algorithm on the right side of the equation
r0 = r0-(q*r1);//Gcd algorithm on the left side of the equation
swap(&r0,&r1);
s0 = s0 - (q*s1);
swap(&s0,&s1);
}
*s = s0;
*r = r0;
*d = a;
}
void swap(int*a,int *b){//Exchange the values of a and b
int temp=*a;
*a=*b;
*b=temp;
}