問題:https://codeiq.jp/ace/nabetani_takenori/q649
解説:http://nabetani.hatenablog.com/entry/codeiq_gcfibo_q649
RubyによるO((logn)2)の実装例です。
とりあえず、nlognから(logn)2に縮められたことは収穫でした。
gcfibo()の最適化はしていません。3つ以上の数のgcfiboを求めたいときに使えなくなってしまうので。
ところで。
オーダー | Ruby 1.8.7 | Ruby 2.0.0 |
---|---|---|
O(nlogn) | 0.59s | 0.38s |
O((logn)2) | 0.01s | 0.06s |
Ruby 1.8の方が速い場合ってあるんですね。。
codeiq649.rb
#!/usr/bin/ruby
class Fixnum
def fibo
return to_enum(:fibo) if !block_given?
yield 1
a=1
b=self
loop{
yield b
a,b=b,a+b
}
end
def dfibo
h={}
if false #O(nlogn)
1.step(self-1){|i|
a=i.fibo.take_while{|e|e<=self}
if a.last==self
a.each{|e|h[e]=1}
end
}
else #O((logn)2)
1.fibo.take_while{|e|e<self}.each_cons(2){|e,f|
if (self-e)%f==0
((self-e)/f).fibo.take_while{|g|g<=self}.each{|g|h[g]=1}
end
}
end
return h.keys.sort
end
end
DATA.each{|e|
a=e.split.map(&:to_i)
puts "GCFibo( #{a.join(', ')} ) = "+a.map(&:dfibo).reduce(:&).last.to_s
}
__END__
10 14
18 14
73 97
23 25
308 320
6168 9877
18518 19942
追伸
1を特別扱いしていませんが、それでもdfiboは一応求められる模様。