スポンサーサイト

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

任意有限個の整数の最大公約数を求めるCプログラムの例

任意有限個の整数の最大公約数を求める C プログラムの例。

3つの整数 s, t, u に対して、次の式が成り立つ。

gcd(s, t, u) = gcd(gcd(s, t), u). 

4つの整数 s, t, u, v に対しても、次の式が成り立つ。

gcd(s, t, u, v) = gcd(gcd(gcd(s, t), u), v). 

もっと多くの整数についても同様である。

このことを利用して、3つ以上の整数の最大公約数を計算する。

配列を引数にとる関数による例

#include <stdio.h>

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

int ngcd( int size, const int a[] ) 
{
  int i, d; 

  d = 0;
  for ( i = 0; i < size; i++ ) {
    d = gcd( d, a[i] );
  }

  return d;
}

int main(void) 
{
  int a[4] = { 120, 210, 42, 33 };

  printf( "%d\n", ngcd( 4, a ) );  /* => 3 */

  return 0;
}

可変長引数の関数による例

#include <stdio.h>
#include <stdarg.h>

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

int ngcd( int size, ... ) 
{
  va_list ap;
  int i, d;  

  d = 0; va_start( ap, size );
  for ( i = 1; i <= size; i++ ) {
    d = gcd( d, va_arg( ap, int ) );
  }
  va_end(ap);

  return d;
}

int main(void) 
{
  printf( "%d\n", ngcd( 4, 120, 210, 42, 33 ) );  /* => 3 */

  return 0;
}

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

プロフィール

よしいず

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

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

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

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

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

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