[メモ][Java][JavaScript] ユークリッドの互除法
- 2008-04-06
- カテゴリ: Client Side
- タグ: JavaScript Java アルゴリズム Tips
よく使うので、ユークリッドの互除法で二つの整数の最大公約数を求める関数をメモ。
/** Java */
int gcd(int x, int y) {
int g = Math.max(Math.abs(x), Math.abs(y));
int l = Math.min(Math.abs(x), Math.abs(y));
while (l != 0) l = g % (g = l);
return g;
}
/** JavaScript */
function gcd(x, y) {
var g = Math.max(Math.abs(x), Math.abs(y));
var l = Math.min(Math.abs(x), Math.abs(y));
while (l != 0) l = g % (g = l);
return g;
}
再帰は使わない。再帰を使っていなければ、関数化しないでインラインで使うこともできて便利。大小関係がはっきりしている正整数が二つある場合、ユークリッドの互除法は本質的にはwhile (l != 0) l = g % (g = l);だけで表現できるんだね。
まずJavaで書いて、それをほぼそのままJavaScriptに移植したから、JavaScript側のコードは引数のチェックをしていない。必要な場合は整数かどうかのチェックをしておいたほうがいいと思う。
追記
/** Java */ int g = Math.max(Math.abs(x), Math.abs(y)); int l = Math.min(Math.abs(x), Math.abs(y));
/** JavaScript */ var g = Math.max(Math.abs(x), Math.abs(y)); var l = Math.min(Math.abs(x), Math.abs(y));
という部分は、↓のように書き直すことができる。二行に分けたのは、均整の取れた美しさを求めただけ。
/** Java */ int g = Math.max(x = Math.abs(x), y = Math.abs(y)), l = Math.min(x, y);
/** JavaScript */ var g = Math.max(x = Math.abs(x), y = Math.abs(y)), l = Math.min(x, y);
無駄な処理とコード行数を削減したければ↑のように書いてしまえばいいでしょう。
トラックバックURL
- http://liosk.blog103.fc2.com/tb.php/100-6ee97c2d