結城浩さんと言えばプログラマーで数学でクリスチャンな方で、結構な有名人ですが、実は彼の数学ガールが密かにお気に入りだ。いや、実は最近知ったんだけど。
たぶん一番人気であろう、ミルカさんシリーズもいいのだが、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の時の答えがイベントログに残されるようになる。ソートはめんどくさいので、やらない。
