EmptyRoom

実家に帰ってキャッキャウフフです(謎

コミケ行った人はお疲れ様でした。
なんか平和なコミケだったみたいで。…つまんねぇ(ぉ

実家に帰ると基本的にやることが無いんですが、
今日はちょっと学問的なことを(ぉ
ユークリッドの互除法について考えてた。まぁ、アルゴリズムですな…
超有名なアルゴリズムで確かセンター試験に使われたこともあったはず…
ただ、センター試験での言語はBASICで関数の再帰呼び出しとか出来ないので、
ちょっと再帰を使って書いてみようかなって思ったのですよ。

まず、ユークリッドの互除法について説明。

ユークリッドの互除法は任意の2つの自然数の最大公約数を
機械的に見つけることが出来るアルゴリズムで、
自然数m,n(ただしm>n)の最大公約数はm-nとnとの最大公約数と等しい、
という原理に基づいている。
つまり、この引き算を延々と繰り返して、どちらかが0になったときの
もう片方の値が最大公約数なワケです。
簡単にソースを書いてみると

int euclid(int a, int b){
  if(a < b) swap(&a, &b);
  while(b != 0){
    a -= b;
    if(a < b) swap(&a, &b);
  }
  return a;
}
(注: swapは2つの変数の内容を入れ替える関数)

これを再帰法で書き直すと、
int euclid(int a, int b){
  if(a < b) swap(&a, &b);
  if(b == 0) return a;
  else return euclid(b, a % b);
}

まぁ、あんまりかわらんね…ちょっとソースが短くなったけどね。
ちなみに、a -= b;を何回も繰り返すことは、aをbで割った余りを
aに入れることに等しいので、換えてます。

同じ機能を実現するプログラムでも書き方を換えるとちょっと面白いよね。
今日はそんなお話でした。

再帰法の方は、初期値でa > bが保証されていれば、
最初のswapが要らなくて、2行のプログラムになるのにねぇ。

…あ、三項演算子使えば1行か。すげぇ。
int euclid(int a, int b){
  return (b == 0) ? a: euclid(b, a % b);
}
こんな具合に。

脳汁、出た？

(今回のプログラムは、自然数以外の数値入れると死にます。注意。)