ユークリッドの互除法
2006.04.26 23:50 整数
ユークリッドの互除法は、
x ≧ y のとき、gcd(x, y) と gcd(y, x%y) は等しい
という定理を用いて、x と y の最大公約数を効率良く求めるアルゴリズムです。
(ここで、x%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) | ↑ページトップ |