ユークリッドのアルゴリズムの拡張
任意の 2 つの整数 a と b に対して、+ bt = gcd(a,b) のような整数 s と t が存在することは既にわかっています。つまり、gcd(a,b) は a と b の線形結合です。gcd(a,b) は、2 つの整数の最小の正の組み合わせです。a と b 自体は自明な組み合わせとして表されます: a = 1·+ 0·b および b = 0·a + 1·b。これらの 2 つから始めて、ユークリッドのアルゴリズムの拡張により、これまで正式な方法でのみ存在が確立されていた s と t が見つかります。
列に 2 つの線形結合を書き、ユークリッドのアルゴリズムの 1 つのステップを左辺に適用します。a = bp + r と仮定します。2 番目の式に p を掛けて、最初の式から引きます: a = 1·a + 0·b b = 0·a + 1·b r = 1·a + (-p)·b
最後の 2 つの方程式に同じ手順を適用します。左側の Euclid のアルゴリズムが停止するまで、この方法を続けます。右側には、私たちが求めている線形結合があります。これを例で確認してみましょう: a = 2322, b = 654 です。線形方程式を解く通常の規則を採用し、線形結合のすべての項を省略しますが、左側と右側の 2 つの係数は省略します。結果は、4 番目の列が p に等しい表に配置されます (a = bp + r から、各ステップで変化します。p の左側にある 3 つの数値に p を掛けて、そのすぐ上の数値からそれらを減算します。記録します。記録次の行の結果。
int algoritmoeuclides(int a,int b)
if (a%b==0)
return b;
return algoritmoeuclides(b,a%b);
}
int main(array<System::String ^> ^args)
{
int a=525;
int b=231;
printf("%d",algoritmoeuclides(a,b));
getch();
}
これはこれまでのところ私のコードです。完璧に動作します。問題は、s と t を見つけようとするときです。私はそれを見つける方法を知りません.フォーラムで検索しましたが、SとTを見つけるためにこのアルゴリズムをプログラムする最良の方法は何ですか.私はあなたにアイデアを与えるためにすべての説明をしました. PD:私の英語は英語話者ではないので申し訳ありません。どんなアイデアでも高く評価されます。