2008年3月10日星期一

Bezout Equation

今晚做了一个小练习,用欧几里得算法计算两个正整数的最大公约数。同时计算出Bezout等式的系数。递归描述更紧凑,突出欧几里得算法的核心内容,迭代描述算系数比较方便。
#include<stdio.h>
int gcd(a, b)
{
    if (a>=b)
        if (b>0)
            return gcd(b, a%b);
        else
            return a;
    else
        return gcd(b, a);
}

int gcdp(int x, int y, int* a, int* b) {
    int r=0, k=0, i=1;
    int ai=0, aii=0, bi=0, bii=0;
    int t=0, reverted=0;
    if (y>x) {
        t=x;
        x=y;
        y=t;
        reverted=1;
    }
    while (1) {
        r=x%y;
        k=x/y;
        if (r==0) {
            if (i==1)
                *b=1;
            if (reverted) {
                t=*a;
                *a=*b;
                *b=t;
            }
            return y;
        }
        x=y;
        y=r;
        switch (i) {
        case 1:
            *a=1;
            *b=-k;
            break;
        case 2:
            ai=*a;
            bi=*b;
            *a=-k;
            *b=1-bi*k;
            break;
        default:
            aii=ai;
            bii=bi;
            ai=*a;
            bi=*b;
            *a=aii-k*ai;
            *b=bii-k*bi;
            break;
        }
        i++;
    }
}

void test(x, y)
{
    int a=0, b=0;
    int r=gcdp(x, y, &a, &b);
    printf("%d * %d + %d * %d = %d\n", a, x, b, y, r);
    if (a*x+b*y!= r)
        printf("Error %d = %d\n", a*x+b*y, r);
}
int main() {
    test(12, 34);
    test(1, 2);
    test(4, 6);
    test(32465, 18078);
    test(36465, 18278);
    return 0;
}

没有考虑负数和零的情况。

没有评论: