ruby - Ruby中二项式系数（nCr）的算法

Question

我被赋予了解决这个问题的任务：

五选三，12345，正好有十种方式：

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，价值超过一百万：23C10 = 1144066。

nCr, for , 有多少（不一定不同）的值1 ≤ n ≤ 100大于一百万？

我必须在 Ruby 中提出一个算法来解决这个问题，但我似乎不明白它是如何完成的。

Answer 1

这是一个项目欧拉问题。您需要应用帕斯卡三角形来解决这个问题。帕斯卡三角形是对称的，所以我们只需要计算一半就可以得到结果，这会让你的程序运行得更快。

另一种方法是缓存先前计算的阶乘结果并使用它们以避免不必要的计算过载。

@@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