17/07/27 00:12:38.86 qteH6K3e.net
そもそも>>412のfarey_sequenceは定義が間違ってたわ
んでもって再帰にすると>>412より遅くなるという
Ruby
class Farey
def self.[](m)
if m == 1
[0r, 1r]
else
succ(m - 1)
end
end
def self.succ(m)
self[m].each_cons(2).inject([0r]){|s, (a, b)|
x = a.denominator + b.denominator
s << 1r*(a.numerator + b.numerator)/x if x == m + 1
s << b
}
end
end
Farey[3] # => [(0/1), (1/3), (1/2), (2/3), (1/1)]
Farey[5] # => [(0/1), (1/5), (1/4), (1/3), (2/5), (1/2), (3/5), (2/3), (3/4), (4/5), (1/1)]