旧gaaamiiのブログ

間違ったことを書いている時があります。コメントやTwitter、ブコメなどでご指摘ください

「ユークリッドの互除法」とやらが最古のアルゴリズムらしい

f:id:shgam:20130316013447j:plain

去年の基本情報技術者試験(秋)の問2で、最大公約数を求めるアルゴリズムに関する問題が出てた。

与えられた正の整数x0,x1(x0>x1)の最大公約数を,次の手順で求める。x0=175,x1=77の場合,手順(2)は何回実行するか。ここで,"A→B"は,AをBに代入することを表す。
〔手順〕
2→i
xi-2をxi-1で,割った剰余→xi
xi=Oならばxi-1を最大公約数として終了する。
i+1→i として(2)に戻る。

問題には無いけど、どうせならコード書いて理解したいなってことで「最大公約数 c」とかでぐぐってる。いろいろ出てきて面白い。

function gcd(m, n){
  if (m < n)  return gcd(n, m); // 常に m > n にしておく
  var r = m % n;                // 余りrが....
  if (r == 0) return n;         // 0 なら n がGCD
  return gcd(n, r);             // でなければnとrのGCD
}

アルゴリズム百選 - ユークリッドの互除法

while((r = x % y) != 0)  // yで割り切れるまでループ
    {
        x = y;
        y = r;
    }
    return y;

ユークリッドの互除法で最大公約数を求める


ユークリッドの互除法なんて知らなかった(高校のとき習ったのかもしれないけど)...。最古のアルゴリズムとして知られてるとかなんとか。

ユークリッドの互除法ユークリッドのごじょほう)は、2 つの自然数または整式の最大公約数を求める手法の一つである。
...中略
明示的に記述された最古のアルゴリズムとしても知られ、紀元前300年頃に記されたユークリッドの『原論』第 7 巻、命題 1 から 3 がそれである。
ユークリッドの互除法 - Wikipedia

アルゴリズムはきっちりコードと一緒に覚えよう。うん、そうしよう。