RubyでProject Euler - Problem 9

Problem 9 (Project Euler) [和訳])

A Pythagorean triplet is a set of three natural numbers, a < b < c, for which,

a² + b² = c²

For example, 3² + 4² = 9 + 16 = 25 = 5².

There exists exactly one Pythagorean triplet for which a + b + c = 1000.

Find the product abc.

プログラムミングの課題でお馴染み「ピタゴラス数」が関連するので、例の置換を行うわけですね。

置換を行わないのが「遅い版」。行ったのが「速い版」。実行時間の差をご賞味ください。

遅い版

  begin_time = Time.now
  limit = 1000
  1.upto(limit) do |a|
    1.upto(limit) do |b|
      next if a >= b
      c = 1000 - (a + b)
      if c ** 2 == a ** 2 + b ** 2
        printf("* [%8d] : %4d - %4d - %4d\n", a*b*c, a, b, c)
        puts " -- #{Time.now - begin_time}sec"
      end
    end
  end

速い版

  begin_time = Time.now
  limit = 1 + Math::sqrt(1000).floor
  1.upto(limit) do |u|
    1.upto(limit) do |v|
      next if u >= v
      c = u ** 2 + v ** 2
      next if c > 1000
      a = v ** 2 - u ** 2
      b = 2 * u * v
      a, b = b, a if a > b
      if a + b + c == 1000
        printf("* [%8d] : %4d - %4d - %4d\n", a*b*c, a, b, c)
        puts " -- #{Time.now - begin_time}sec"
      end
    end
  end

ご注意

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

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

コメントはありません。

ご注意

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