« Project Euler - Problem 55, 56 | トップページ | "math_tool.rb" の改良 »

2009年8月19日 (水)

Project Euler - Problem 57

問題はこちらをご覧ください。


最初にこの問題を考えたとき、何も良いアイデアが浮かばなくて、とりあえず「文字列の置換を使う」というほとんど反則っぽい方法で解いてみました。

# -*- coding: utf-8 -*- require 'mathn' # * num の桁数が den の桁数を越えていれば true を返す。 def check(num, den) while den > 0 num = num.div(10) den = den.div(10) end return num > den end count = 0 str = "1 + 1/2" 1000.times do rat = eval(str) num = rat.numerator den = rat.denominator count = count + 1 if check(num, den) str = str.sub("1/2", "1/(2 + 1/2)") end puts count

これでも答えは出たのですが、非常に遅い……。Ruby 1.9 で約 20 秒もかかってしまいます。


「これではいけない」と思い、数式をいろいろいじりながら考えていたら、以下のような漸化式に気づきました。

n 番目の項を Tn とすると、Tn = 1 + 1 / (1 + Tn - 1)

この式を使ったコードは次の様になりました。

require 'mathn' count = 0 rat = 3/2 1000.times do num = rat.numerator den = rat.denominator count = count + 1 if num.to_s.size > den.to_s.size rat = 1 + 1 / (1 + rat) end puts count

このコードでは答えが 0.3 秒で出ました。


さらに "Tn = An / Bn" と置くと、

An / Bn = (2 * Bn - 1 + An - 1) / (An - 1 + Bn - 1)

という漸化式が導き出されます。ここまでくると、分子と分母を別々に計算できるので、mathn.rb もいらなくなります。

count = 0 a, b = 3, 2 1000.times do count = count + 1 if a.to_s.size > b.to_s.size a, b = a + 2 * b, a + b end puts count

このコードでは答えが 0.2 秒ででました。


Project Euler をうまく解こうと思ったら、しっかりした数学的考察が必要なんでしょうね。

« Project Euler - Problem 55, 56 | トップページ | "math_tool.rb" の改良 »

Project Euler」カテゴリの記事

Ruby」カテゴリの記事

コメント

コメントを書く

コメントは記事投稿者が公開するまで表示されません。

(ウェブ上には掲載しません)

トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/112020/45972299

この記事へのトラックバック一覧です: Project Euler - Problem 57:

« Project Euler - Problem 55, 56 | トップページ | "math_tool.rb" の改良 »

2016年7月
          1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31            
フォト

最近のトラックバック

無料ブログはココログ