nekoTheShadow’s diary
id:nekoTheShadow
rubyでユークリッドの互除法を短く実装しよう。
最近いろいろなアルゴリズムを短く短くすることにはまっています。今日はその一環でユークリッドの互除法を扱いました。 ユークリッドの互除法とは何か ユークリッドの互除法は最大公約数を探す定番アルゴリズムです。シンプルながら非常に強力で、しかも世界最古のアルゴリズムというすごいやつです。 具体的な手順は次の…