■

結城さんのサイトを徘徊していてプログラムクイズを見付けた。
既約分数クイズ

問題

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

条件

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

とりあえずRubyで解いてみた。

#Nは引数で与える
n = ARGV.shift.to_i

#Euclidの互除法
def gcd(p, q)
  if p % q == 0
    q
  else
    gcd(q, p % q)
  end
end

1.upto(n) do |q|
  0.upto(q) do |p|
    if gcd(p, q) == 1
      printf "%d/%d\n", p, q
    end
  end
end

ユークリッドの互助法と再帰を使えば簡単だった。こんな簡単に解けていいの？と思っていたのだが、やはり出題者の意図は別のところにあったようだ。模範解答にはスターン・ブロコット木の一部を使ってファレイ(Farey)数列を構成する方法が挙げられている。