RubyでProject Euler - Problem 14

Problem 14 (Project Euler) [和訳])

The following iterative sequence is defined for the set of positive integers:

n → n/2 (n is even)

n → 3n + 1 (n is odd)

Using the rule above and starting with 13, we generate the following sequence:

13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.

Which starting number, under one million, produces the longest chain?

NOTE: Once the chain starts the terms are allowed to go above one million.

コラッツの問題 (Wikipedia)

賞金は500ドル。併せて記載のある角谷は「かくたに」と読むのであって「ふぉぉー」の人とは系統が異なります、念のため。

さて、愚直なコードを書くと答えが出るまでに２分ぐらいかかりました。問われているのは1に収束するまでの項数なので、辞書となるハッシュを用意し、重複した計算を行わないようにするのが定石だそうです。

  begin_time = Time.now

  def get_seq_len(num)
      tmp = num
      cnt = 1
      while tmp > 1
        if $dictionary[tmp]
          cnt += $dictionary[tmp]
          break
        end

        if tmp % 2 == 0
          tmp /= 2
        else
          tmp = 3*tmp + 1
        end

        cnt += 1
      end
      $dictionary[num] = cnt
  end

  $dictionary = {1=>1, 2=>2} # 初期値は入れておく
  max_vals = [0, 0]

  3.upto(100_0000) do |i|
    len = get_seq_len(i)
    if len > max_vals[1]
      max_vals = [i, len] 
      p max_vals
    end
  end
  puts "↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑"
  puts " -- #{Time.now - begin_time}sec"

これによって実行時間は半分ぐらいになりました。ちなみにハッシュの代わりに配列を用いると10万を過ぎたところで怒られます。

ご注意

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

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

コメントはありません。

ご注意

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