« Rubyプログラミング(1) | トップページ | すごい人 »

2007/10/12

ユークリッドのアルゴリズム

今日の暗号理論の講義では、暗号化させる上で必ず必要になるユークリッドのアルゴリズムをやりました。これは二つの整数の最大公約数を求めるためのもので、「ユークリッドの互除法」とも呼ばれます。今回はこのアルゴリズムを再帰を使った関数で表してみます。

/* 二つの整数の最大公約数を求める */

int gcd(int x, int y)
{
   if (y == 0)
      return (x);
   else
      return ( gcd(y,  x%y) );
}

このプログラムを説明するために例を挙げると、二つの整数120と45があったとします。これの最大公約数を求めるには

  • 120 ÷ 45 = 2 あまり 30
  • 45  ÷ 30 = 1 あまり 15
  • 30  ÷ 15 = 2 あまり 0

という操作をします。この操作を上のプログラムに当てはめて考えると理解できると思います。( x % y とは「xでyを割った余りを求める」という演算子)

|

« Rubyプログラミング(1) | トップページ | すごい人 »

Algorithm」カテゴリの記事

C」カテゴリの記事

コメント

コメントを書く



(ウェブ上には掲載しません)


コメントは記事投稿者が公開するまで表示されません。



トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/222903/16739556

この記事へのトラックバック一覧です: ユークリッドのアルゴリズム:

« Rubyプログラミング(1) | トップページ | すごい人 »