RubyでProject Euler - Problem 57

Problem 57 (Project Euler) [原文]

2の平方根は無限に続く連分数で表すことができる.

√ 2 = 1 + 1/(2 + 1/(2 + 1/(2 + … ))) = 1.414213…

(中略)

第8項は1393/985である. これは分子の桁数が分母の桁数を超える最初の例である.

最初の1000項を考えたとき, 分子の桁数が分母の桁数を超える項はいくつか?

とりあえず、連分数部分の分母・分子の数列をそれぞれ a_n, b_n とすると、以下の漸化式が成立します。

• a_n = 2a_n-1 + b_n-1, a₁ = 2
• b_n = a_n-1, b₁ = 1

プログラムで漸化式を扱う場合、そのまま関数にすると再帰呼び出しによる再計算量が異常に多くなり、実行効率が激減します。

メモリを上手に使うのがうまいやりかたでしょう。

  seq_a = [2] # 分母
  seq_b = [1] # 連分数部分の分子
  ans = 0       # カウンタ

  (1..1000).each do |i|
    seq_a << seq_a[i-1] * 2 + seq_b[i-1]
    seq_b << seq_a[i-1]
    ans += 1 if seq_a[-1].to_s.length < (seq_a[-1] + seq_b[-1]).to_s.length
  end
  puts ans

ご注意

当分の間、トラックバックの受信を行わないことといたしました。過去に戴いたトラックバックのリストについてはそのまま保持いたします。

トラックバックはありません

コメントはありません。

ご注意

当分の間、JavaScript が有効でないとコメント投稿できないようにします。スパム対策であって、投稿される方の個人情報を取得する目的ではありません。悪しからずご了承ください。