-2

この問題を解決するタスクが与えられました。

5 つから 3 つを選択する方法は 12345 で、ちょうど 10 通りあります。

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

組み合わせ論では、表記法を使用し5C3 = 10ます。一般に、

nCr = n! / r!(n−r)!

ここr ≤ nで、、、n! = n×(n−1)×...×3×2×1および0! = 1。

n = 23値が 100 万を超えるのは、までではありません23C10 = 1144066。

、 、 、 の値のうちnCr、1 ≤ n ≤ 100100 万より大きい値はいくつありますか?

その問題を解決するために Ruby でアルゴリズムを考え出さなければなりませんが、それがどのように行われるかを理解していないようです。

4

1 に答える 1

4

プロジェクトのオイラー問題です。この問題を解決するには、パスカルの三角形を適用する必要があります。パスカルの三角形は対称であるため、半分を計算するだけで結果が得られます。これにより、プログラムの実行が速くなります。

不必要な計算の過負荷を避けるために、以前に計算された階乗結果をキャッシュし、それらを使用する別の方法があります。

@@fact_table = []
@@fact_table[0] = 1;
@@fact_table[1] = 1;

for i in (2..100)
  @@fact_table[i] = i * @@fact_table[i-1]
end

def ncr(n, r)
return @@fact_table[n] / (@@fact_table[r] * @@fact_table[n-r])
end

num = 0 
for n in (1..100)
  for r in (1..n)
    if ncr(n, r) > 1000000
      num += 1
    end
  end
end

print "Count exceeding 1 million: ", num, "\n"

出力

Count exceeding 1 million: 4075
于 2013-06-21T03:06:36.320 に答える