RubyでProject Euler - Problem 53

Problem 53 (Project Euler) [原文]

12345から3つ選ぶ選び方は10通りである.

123, 124, 125, 134, 135, 145, 234, 235, 245, 345.

組み合わせでは, 以下の記法を用いてこのことを表す: ₅C₃ = 10.

一般に, r <= n について_nC_r = n!/(r!(n-r)!) である. ここで, n! = n×(n-1)×...×3×2×1, 0! = 1と階乗を定義する.

n = 23になるまで, これらの値が100万を超えることはない: ₂₃C₁₀ = 1144066.

1 <= n <= 100について, 100万を超えるnCrは何通りか?

Rubyに関する限り、この程度の問題で数値のオーバーフローを気にする必要はありません。導入も親切な問題ですし、そのまま書いて終わりです。

スペースが余ったのでコードを載せます。

  def fact(n)  # 階乗
    return 1 if n == 0 || n == 1
    (2..n).to_a.inject(1){|v, i| v*i}
  end

  def combination(n, r) # 組み合わせ(コンビネーション)
    fact(n) / (fact(r) * fact(n-r))
  end

  cnt = 0

  (1..100).each do |n|
    (1..n).each do |r|
      cnt += 1 if combination(n, r) > 100_0000
    end
  end

  puts cnt

ご注意

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

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

コメントはありません。

ご注意

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