拡張ユークリッドアルゴリズム-再帰と非再帰の実現

拡張ユークリッドアルゴリズム(一)——リード
前言
ユークリッドアルゴリズムの目的は,正整数a,bの最大公因数を求め,gcd(a,b)と記すことである.このアルゴリズムの原理は言うまでもなく、初等数論の教科書には詳しく紹介されています.今回の一連の文章の重点はどのように実際のコードでこれらのアルゴリズムを実現するかに置いて、私たちは数学の細部を無視して、コードの編纂に専念します.ユークリッドアルゴリズムの実現は非常に簡単で,その再帰的実現は

int gcd(int a, int b)
{
    return (b == 0) ? a : gcd(b, a % b);
}

同じアルゴリズムでは、異なる実装が可能であり、ユークリッドアルゴリズムはこのような生きた例である.再帰的に実現する利点は,コードが簡潔明瞭で分かりやすく,スタックを呼び出すために時間的に非再帰アルゴリズムほど効率的ではないことにある.非再帰アルゴリズムを用いてユークリッドアルゴリズムを実現することもできる.

int gcd(int a, int b)
{
    if (b == 0)
        return a;
    int r = a % b;
    while (r) {
        a = b; 
        b = r;
        r = a % b;
    }
    return b;
}

では、拡張されたユークリッドアルゴリズムとは何でしょうか.最大公因数には、整数xが存在し、yはax + by = gcd(a, b)に拡張されたユークリッドアルゴリズムが条件を満たすxとyのセットを求めることができる.もちろん、このような整数対(x,y)は一意ではない.
インプリメンテーション
拡張されたユークリッドアルゴリズムの原理を述べる前に、私は先に実現を与えて、このように忍耐力のない友达が直接私のところからcopyコードを送ることができて、これも功徳の1つです(笑).
拡張ユークリッドアルゴリズムの一般的な実装は一面の再帰的実装であり,その原理は非常に簡単であるべきである.整数対(x,y)がax + by = gcd(a, b)，(b ！= 0)を満たすことが要求されるならば、(x’,y’)が(a % b)x' + by' =gcd(a, b)を満たすことを知っていれば、a % b = a - (a / b)*b, ( '/' )を知ることができる.
再帰的な実装は次のとおりです.

int e_gcd(int a, int b, int *x, int *y)
{
    if (b == 0) {
        *x = 1; *y = 0;
        return a; 
    } else {
        int r = e_gcd(b, a%b, y, x);
        *y -= (*x)*(a/b);
        return r;
    }
}

もちろん,拡張ユークリッドアルゴリズムにも非再帰的な実装があり,その原理は「リスト法」である.実装コードは以下に示す.

int e_gcd(int a, int b, int *x, int *y)
{
    int r, q, s1 = 1, s2 = 0;

    if (b == 0) {
        *x = 1; *y = 0;
        return a;
    }
    *x = 0, *y = 1;
    r = a % b;
    q = a / b;
    while (r) {
        int m = *x, n = *y;
        *x = s1 - (*x)*q;
        *y = s2 - (*y)*q;
        s1 = m; s2 = n;
        a  = b; b  = r;
        q = a / b;
        r = a % b;
    }
    return b;
}

コード実装において,拡張ユークリッドアルゴリズムはユークリッドアルゴリズムに基づいて整数対(x,y)の反復解を増やしただけであることが分かる.全体的に、実現は難しくない.
次回予告

いったい何が“リスト法”が整数対(x,y)を求めるのですか?

リスト法の原理は何ですか?

紙の上でどのようにリスト法でxを求めて、y

私の次のブログを楽しみにしてください!今度また話しましょう.