[メモ][Java][JavaScript] ユークリッドの互除法

スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

[メモ][Java][JavaScript] ユークリッドの互除法

よく使うので、ユークリッドの互除法で二つの整数の最大公約数を求める関数をメモ。

/** 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

トラックバック

コメント

コメントの投稿

お名前
コメント
編集キー
 
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。