RubyでProject Euler - Problem 26

Problem 26 (Project Euler) [原文]

単位分数とは分子が1の分数である。分母が2から10の単位分数を10進数で表記すると次のようになる。

• 1/2 = 0.5
• 1/3 = 0.(3)
• 1/4 = 0.25
• 1/5 = 0.2
• 1/6 = 0.1(6)
• 1/7 = 0.(142857)
• 1/8 = 0.125
• 1/9 = 0.(1)
• 1/10 = 0.1

0.1(6) 0.166666... という数字であり、6が循環節であることを表している。1/7 循環節は6桁ある。

d < 1000 なる 1/d の中で循環節が最も長くなるような d を求めよ。

循環小数と分数に関する高尚な知見はありましょうが、ベタに筆算で割り算するときのことを思い出すのが吉かと思います。

筆算の割り算を行う過程で、余りの値が過去に出現したいずれかと同じ値になれば、それ以上の計算は無意味と悟り、作業を止めてしまうのが普通でしょう。

このような経験を踏まえて以下のようなコードを書きました。ケツ舐めのメソッド"rindex"に働いてもらいました。

  # 循環節の桁数を返すメソッド
  def recur_cycle_length(u, v)
    rests = []
    loop do
      u = u % v
      return 0 if u == 0
      if rests.rindex(u)
        return rests.length - rests.rindex(u)
      end
      rests << u
      u *= 10
    end
  end

  ans = [0, 0]
  (1..999).each do |n|
    tmp = recur_cycle_length(1, n)
    if tmp > ans[0]
      ans = [n, tmp]
    end
  end
  puts "answer : #{ans[0]} -- length : #{ans[1]}"

ご注意

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

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

コメントはありません。

ご注意

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