またもやProject Eulerネタ。
Problem57にトライ。
def root2_series
(1..1000).inject( [3/2r] ) do |result, i|
result << 1 + 1 / (result.last + 1)
end
end
def bigger_numerators
root2_series.select do |term|
term.numerator.to_s.size > term.denominator.to_s.size
end
end
p bigger_numerators.size
3/2rはRationalのリテラルで、2.1から使えるようになったとのことだ。ちなみに複素数リテラルもできたみたいで、そういえば昔、3+2iって試して、できなかったことがあったのを思い出した。
それと今回は√2の級数を求めるのにinjectを使った。私はinjectは「前の値を使って1つの値を求める」しか頭になかった。しかしある人のコードで、「前の値」に配列を入れることで、まるでmapのように配列を作った例があったので、そのアイデアを使わせてもらった。injectを使うことで漸化式の各要素の入った配列を作ることができるなんて、自分だけではなかなか気づけないと思う。
そうなるとコードはシンプルになる。初項の3/2rが入った配列を初期値にしてやると、前イテレーションの計算結果がresult.lastで取り出せるので、最終的に1000個の項が入った配列になってくれる。
級数配列が完成すれば、Rationalの分母分子の桁数(.to_s.size)で比較すれば終わり、となる。
Rationalすごい?!
このコードをtoRubyで見せたところ、@you_ssk から、この級数の不思議な特徴を教えてもらった。ProjrctEulerにあるように、この級数は以下のように算出できる。
1 + 1/2 = 3/2 = 1.5 1 + 1/(2 + 1/2) = 7/5 = 1.4 1 + 1/(2 + 1/(2 + 1/2)) = 17/12 = 1.41666... 1 + 1/(2 + 1/(2 + 1/(2 + 1/2))) = 41/29 = 1.41379...
この各項を見てみると以下のような規則があるというのだ。
3/2
7/5 = (3+2*2)/(3+2)
17/12 = (7+2*5)/(7+5)
41/29 = (17+2*12)/(17+12)
つまり、
an/bn = (an-1 + 2 * bn-1)/(an-1 + bn-1)
なのである。これはすごいと、早速コードを書き直した。
def root2_series
(1..1000).inject( [ [3,2] ] ) do |result, n|
result << [result.last[0] + 2 * result.last[1], result.last[0] + result.last[1]]
end
end
def bigger_numerators
root2_series.select do |term|
term[0].to_s.size > term[1].to_s.size
end
end
p bigger_numerators.size
コード的にはほとんど変わらないのだけど、Rationalクラスを使わずに済んでいるのでなんとなく節約できた気になった。そこで処理時間を測ってみた。以下に結果を載せる。(100回動かした合計時間と100で割った平均時間)
user system total real Without Rational 3.323000 0.000000 3.323000 ( 3.315948) Avg 0.033230 0.000000 0.033230 ( 0.033159) Rational 1.700000 0.000000 1.700000 ( 1.697862) Avg 0.017000 0.000000 0.017000 ( 0.016979)
Rational使った方が早い。。。これはどういうこと?
分数を使わずにできることをたまたま人から教わったからいいけど、自分で必死に思いついてたら、Rubyに「時間返せ」と言ってたかもしれない。かっこいいなぁ、Rational。
