アルゴリズム百選 - ユークリッドの互除法 : 404 Blog Not Found

2007年12月11日16:30 カテゴリアルゴリズム百選Math アルゴリズム百選 - ユークリッドの互除法 今回は、ユークリッドの互除法を取り上げます。 ユークリッドの互除法とは何か。小学校の時に実は習っているはずですが、忘れている方は思い出してみてください。最大公約数(Greatest Common Divisor)を確実に計算する方法です。古代から有名なこのアルゴリズムは、かつては"The Algorithm"といえばこれをさすほど有名なアルゴリズムです。 それは、コードではなく普通の言葉でも簡単に書くことが出来ます。gcd(m, n)を出すには、 mをnで割り、余りがrだとする 余りrが0なら、nがGCD。 そうでなければ、nとrのGCDを求める 互い違いに割っていくので、互除法というわけです。 function gcd(m, n){ if (m < n) return gcd(

[agw]

"if (m < n) return gcd(n, m);"が好き。 Lispっぽい。

[boxeur]

互除法が最も苦戦するのは、数の対が隣り合うフィボナッチ数になっている時なのです。互除法での繰り返しは、(F(n+1), F(n))の組み合わせの時に、n回となります。

[hassylin]

フィボナッチ数列と互除法の意外な関係

[riywo]

ユークリッドの互除法とフィボナッチ数列がつながるとは思わなかった。良文だが、余りがn-1となるmを出すところがパンピーには分かりにくいかも。

[Nean]

個人的に懐かしいなぁ。でもホントに小学校で教えてるんですか？ ちょっとそこは怪しいと思います。