fc2ブログ



ユークリッドの互除法

2006.04.26 23:50  整数

ユークリッドの互除法は、

x ≧ y のとき、gcd(x, y) と gcd(y, x%y) は等しい

という定理を用いて、x と y の最大公約数を効率良く求めるアルゴリズムです。
(ここで、x%y は x を y で割った余りを示します)

具体的な例を見てみましょう。

gcd(54, 20) (54 % 20 = 14)
= gcd(20, 14) (20 % 14 = 6)
= gcd(14, 6) (14 % 6 = 2)
= gcd(6, 2) (6 % 2 = 0)
= gcd(2, 0)
= 2

ユークリッドの互除法を実装したプログラム例です。

001 int gcd( int x, int y ){
002     int r;
003     // x ≧ y を満たすことを保障する
004     if ( x < y ) swap( x, y );
005     
006     while ( y > 0 ){
007         r = x % y;
008         x = y;
009         y = r;
010     }
011     
012     return x;
013 }



定理の証明,,,,
スポンサーサイト



| コメント(0) | トラックバック(0) | ↑ページトップ |

この記事へのコメント

コメントを書く


管理人にのみ表示

↑ページトップ

この記事へのトラックバック

この記事にトラックバックする(FC2ブログユーザー)

↑ページトップ