RubyでProject Euler - Problem 39

Problem 39 (Project Euler) [原文]

辺の長さが{a,b,c}と整数の3つ組である直角三角形を考え, その周囲の長さをpとする. p = 120のときには3つの解が存在する:

• {20,48,52}
• {24,45,51}
• {30,40,50}

p < 1000 で解の数が最大になる p を求めよ

ピタゴラス数を求める場合、得られる3数が互いに素となるようにしますが、この問題ではその整数倍の数の組み合わせも許容されます。

といって、重複カウントもいやなので、互いに素なピタゴラス数の組み合わせを求めてから各数の整数倍も吟味することにしました。

Problem 9のときにはぼやかしてコードを載せなかったので、今回は記載します。

vを２ずつカウントダウンしているところがミソですね。これを1ずつにすると、互いに素の判断をa,b についてしなければいけなくなり、実行速度が低下します。過去に得た知識の受け売りですが…。

  def gcm(m, n) # m.nの最大公約数を返す
    gcm(n, m) if n > m
    u = m % n
    return n if u == 0
    gcm(n, u)
  end

  limit = 1000
  ulimit = Math::sqrt(1000) + 1
  ans = Array.new(1000, 0)
  (2..ulimit).each do |u|
    (u-1).step(1, -2) do |v|      # vはuより小
      c = u ** 2 + v ** 2         # 置換
      next if c > limit || gcm(u, v) != 1
      a = u ** 2 - v ** 2         # 置換
      b = 2 * u * v               # 置換
      s = a + b + c
      while s < limit
        ans[s] += 1
        s += a + b + c
      end
    end
  end

  puts ans.max

ご注意

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

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

コメントはありません。

ご注意

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