[AppleScript]

AppleScriptで最大公約数 - いまさら既約分数クイズ / 2006-02-21 (火)

結城浩さんと言えばプログラマーで数学でクリスチャンな方で、結構な有名人ですが、実は彼の数学ガールが密かにお気に入りだ。いや、実は最近知ったんだけど。

たぶん一番人気であろう、ミルカさんシリーズもいいのだが、Where is the truth?シリーズも捨て難いものが。その中に、2003年末〜2004年初頭にかけて既約分数クイズというものがあった。問題自体は非常にシンプル。

問題:正の整数Nが与えられているとき、 以下の条件を満たす既約分数p/qを「すべて」求めるアルゴリズムを示してください。条件は:

  • p, qは整数(pは0以上で、qは1以上N以下).
  • gcd(p, q) = 1 (pとqの最大公約数は1).
  • 0 <= p/q <= 1.

これだけ。まぁ詳しくは原文を読んで頂くとして、AppleScript版の回答を作成してみたので、ここに書いておく。

on run
    my frac(9)
end run


on frac(n)
    set ans to {}
    repeat with q from 1 to n
        repeat with p from 0 to q
            if my gcd(p, q) = 1 then --(1)
                set end of ans to (p & "/" & q) as string
            end if
        end repeat
    end repeat
    return ans
end frac

on gcd(p, q)
    repeat until q = 0
        set {p, q} to {q, p mod q} --(2)
    end repeat
    return p
end gcd

ポイントはgcdハンドラの(2)。AppleScriptで最大公約数って?とか悩んだんだが、ユークリッドの互除法という方法を知り、AppleScriptで書いてみたのがこれ。WikipediaにはPythonでの例が掲載されていたが、入力された2数のmodを入れておく変数がp,qの他に必要だった。一方我らがAppleScriptにはリストがあるおかげですっきりと書く事が出来た。実質2行。fracハンドラでも、分子になるpの値を最大qまでと制限する事で計算量を減らすのは常套手段だね。qを1からnまで、pを0からqまでとする事で、0 <= p/q <= 1の検証はしなくて済んでいるし。実際はp,qの大小・qが0でない事の保証などをしなければならないのだろうが、今回は面倒なので見送り。そして他の人がやっている小さい順に並べるのも省略(ソートはAppleScriptには向かない気がするし。出来るけど)。

なお、runハンドラを

on run
    repeat with i from 1 to 9
        log my frac(i)
    end repeat
end run

とすれば、N=1〜9の時の答えがイベントログに残されるようになる。ソートはめんどくさいので、やらない。

[ ツッコミの受付は終了しています ]
1: ぐるり (06-02-21 04:52)
--一応N=1〜9の時の結果。
{"0/1","1/1"}
{"0/1","1/1","1/2"}
{"0/1","1/1","1/2","1/3","2/3"}
{"0/1","1/1","1/2","1/3","2/3","1/4","3/4"}
{"0/1","1/1","1/2","1/3","2/3","1/4","3/4","1/5","2/5","3/5","4/5"}
{"0/1","1/1","1/2","1/3","2/3","1/4","3/4","1/5","2/5","3/5","4/5","1/6","5/6"}
{"0/1","1/1","1/2","1/3","2/3","1/4","3/4","1/5","2/5","3/5","4/5","1/6","5/6","1/7","2/7","3/7","4/7","5/7","6/7"}
{"0/1", "1/1", "1/2", "1/3", "2/3", "1/4", "3/4", "1/5", "2/5", "3/5", "4/5", "1/6", "5/6", "1/7", "2/7", "3/7", "4/7", "5/7", "6/7", "1/8", "3/8", "5/8", "7/8"}
{"0/1", "1/1", "1/2", "1/3", "2/3", "1/4", "3/4", "1/5", "2/5", "3/5", "4/5", "1/6", "5/6", "1/7", "2/7", "3/7", "4/7", "5/7", "6/7", "1/8", "3/8", "5/8", "7/8", "1/9", "2/9", "4/9", "5/9", "7/9", "8/9"}

「AppleScriptで最大公約数 - いまさら既約分数クイズ」のリンク用URL