「ユークリッドの互除法」とやらが最古のアルゴリズムらしい
去年の基本情報技術者試験(秋)の問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
アルゴリズムはきっちりコードと一緒に覚えよう。うん、そうしよう。