ニコニコ大百科

int G(a,b){return b>0?G(b,a%b):a;}
で動くと思うが

最古のアルゴリズムだって事も書いた方がいいのでは。
その所為かアルゴリズムの本では最初に出てくる事が多いし。

{例}

728と693の最大公倍数

はネタですよね

エラトステネスの篩の記事もほしいな

しかし互除法の記事あるのにユークリッド先生の記事がないのは台パンものですわぁ…

DとCでまったく同じことやってて、どちらも同じ書き方できるのに
わざわざ違う書き方で並べるのは何の嫌がらせかとｗ

>>1
すげー綺麗だな
引数に型だけ足そう
int GetGcd(int a, int b){return a<b?GetGcd(b,a):(b>0?GetGcd(b,a%b):a);}

>>7
>>1が言いたいのは「aとbの大小比較をする必要が無い」ってことでは？
（b>0 よりも b!=0 か単に b の方が良いとは思うが）

>>8
最初の一回だけ必要なんだよな。
（前提として、最初に与えられる値が a ≧ b としてるから）

まあ、実際に実装する場合はラッパー関数で最初だけ大小比較するんだろうが。

>>9
その前提、本当に必要？

記事の例を逆さにして、「693と728の最大公約数」を求めてみよう。
0. 693 ÷ 728 → 0 あまり 693
1. 728 ÷ 693 → 1 あまり 35
2. 693 ÷ 35 → 19 あまり 28
3. 35 ÷ 28 → 1 あまり 7
4. 28 ÷ 7 → 4 あまり 0
よって、693と728の最大公約数は7。

大小比較によって手順を1回だけ減らせはするけど、果たしてコードが増える苦労に見合うか…

互除法の拡張（改造物）っていろいろあるけど
この記事の拡張ユークリッド互除法は「互除法の逆行」という名前で呼んでいるpdfがあってなかなかよかった

台風ひまひま