スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

拡張Euclid互除法のC言語によるプログラム例

与えられた整数 a, b に対して、方程式 a x + b y = gcd(a, b) は必ず整数解 (x, y) をもつことが知られています。Euclid の互除法は最大公約数 gcd(a, b) を求めるアルゴリズムですが、gcd(a, b) だけでなく整数解 (x, y) も同時に求めるように拡張することができます。

プログラム例

#include <stdio.h>

void extgcd( int a, int b, int* x, int* y, int* d )
{
  int u, v, q, tmp; 

  *x = 1; *y = 0; u = 0; v = 1;
  while ( b > 0 ) {
    q = a / b; 
    tmp = u; u = *x - q * u; *x = tmp;
    tmp = v; v = *y - q * v; *y = tmp;
    tmp = b; b = a - q * b; a = tmp;
  }
  *d = a;
}

int main(void)
{
  int a, b, x, y, d;

  a = 6; b = 10;
  extgcd( a, b, &x, &y, &d );

  printf( "a = %d\n", a );
  printf( "x = %d\n", x );
  printf( "b = %d\n", b );
  printf( "y = %d\n", y );
  printf( "gcd(a, b) = %d\n", d );

  return 0;
}

実行結果:

a = 6
x = 2
b = 10
y = -1
gcd(a, b) = 2

【theme : プログラミング
【genre : コンピュータ

プロフィール

よしいず

Author:よしいず
MATHEMATICS.PDFというウェブサイトを運営しています。

管理の都合上、トラックバックとコメントはオフにしてあります。ブログ経験者なら分かっていただけると思いますが、スパム(アダルトやその他の宣伝)ばかりなのが現実です。

リンクは自由です。当サイトの記事に対する間違いの指摘・意見・感想などを述べた記事からのリンクは歓迎です。ただし、ブログ記事アップ直後はミスが多く、頻繁に修正します。場合によっては削除する可能性もあります。その際、何も断りもなく修正・削除しますがご了承ください。内容を参考にする場合には投稿後一週間ほど様子を見てからにしてください(笑)。

記事の間違いを指摘するときは、その具体的箇所、理由(仕様に反するなど)・根拠(参考にした文献など)、代替案(同じ結果を得るための正しいやり方)も教えてください。そうしないと、(指摘される側および第三者はその時点では無知の状態なので、)どこが間違いなのか分かりませんし、本当に間違っているのかどうかが判断・検証できません。実際、間違いだと指摘されたことが結局は正しかったというケースもありますので。

このブログのタイトル一覧

リンク
月別アーカイブ
カテゴリ
最新記事
検索フォーム
RSSリンクの表示
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。