最終更新: 2011-03-15T00:15+0900
「HCF(n,d)=1」には用語の説明があると思ったんだけどなかった。n/dの nと dは最大公約数が 1の既約分数だとすると意味がとおるので HCF=Highest Common Factorだと決めた(でっちあげ)。
分数とはなんぞやだとか切断だとか小難しく考えてしまったが(実際には考えられるほど知らない)、ワンライナーだった。3/7より少し小さい100万個の分数を小数になおして、一番小さいものを見つける。有理数にして比較しないのは時間がかかるから。公約数をみつけたりする時間だろうか。
require 'rational' p Rational(*(2..1_000_000).inject([0,1]){|answer,d| answer[0]/answer[1].to_f < (d*3-1)/7/d.to_f ? [(d*3-1)/7,d] : answer })
Project Euler Problem #71 « KeyZero Conversation
分数を初めてならった小学生が必ず間違える分数の足し算(通分せずに分母どうし分子どうしを加算する)にこんな意味があるとか!
分単位のお時間がかかります。(訳:一時間はかからないけど……)
何倍も速くなるので「Integer#prime_division」を使う代わりに 100万要素の配列を使ってる。トレードオフで使用メモリは数MBから 100MB超になるが。 小手先のチューンよりアルゴリズムを改良しろってのはもっともだけど、かなしいかな、できることとできないことがあるのです。
LIMIT = 1_000_000 pfs = Array.new(LIMIT+1){ [] } count = 0 2.upto(LIMIT){|d| # 0) LIMIT以下のすべての分母 d に対して、 print d,"\r" count += d-1 # 1) とりあえず d-1 通りの分子を計上し、 d.step(LIMIT, d){|_| pfs[_] << d } if pfs[d].empty? # 2) 8分の6など通分可能なものを差し引きする。 (1..(pfs[d].size)).each{|r| cms = pfs[d].combination(r).map{|pf| pf.inject(&:*) } count -= (-1)**(r%2+1) * cms.map{|cm| (d-1)/cm }.inject(&:+) } } p count
Ruby 1.9からバックポートされてきた(のだと思われる見覚えのないメソッド) cycle, tap, combination, permutation, productといったメソッドが便利だ。あとは自然数を無限に生成し続ける無限リストのようなものをどれだけ簡単に書けるかだ。なにかショートカットがあるのだろうか。これでは長すぎる。
Enumerable::Enumerator.new(lambda{|&block| n=0; loop{ block.call n+=1 } }, :call).each{|x| p x }
それと、block.callの部分を yieldにできないのもわかりにくい。Procと blockと lambdaの微妙な違いによるものなのだろうか。
Rubyによる他所の Project Eulerの解答をみていてこういう書き方も知ってるけど、カウンタが Floatになっちゃうのが不満。
1.upto(1/0.0){|n| p n }
あれ? Fixnumだ。Floatになるのは stepだった。
1.step(1/0.0){|n| p n } # 1.0, 2.0, 3.0,...
明示的に Fixnumの増分: 1を指定しても n は Float. この違いはなんだろう。
cycleの使い道として zipを想定していたが拒否されてしまった。
irb> [1,2,3,4,5].zip([0]) => 1, 0], [2, nil], [3, nil], [4, nil], [5, nil irb> [1,2,3,4,5].zip([0].cycle) TypeError: can't convert Enumerable::Enumerator into Array from (irb):2:in `zip' from (irb):2 from :0 irb> RUBY_DESCRIPTION => "ruby 1.8.7 (2010-01-10 patchlevel 249) [i386-mswin32]"