CINTA作业3-编程题（GCD、EGCD）

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;
}