算法二項式係數（NCR）在Ruby中

-2

正好有十種方法從五個選擇三，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，1 ≤ n ≤ 100, 的數值有多少，未必是截然不同的值大於一百萬？

我必須在Ruby中提出一個算法來解決這個問題，但我似乎並不明白它是如何完成的。

來源

2013-06-21 Oscar Swanros

是否必須是一個「聰明」的算法？如果沒有，您可以隨時解決所有問題，並計算出超過一百萬的解決方案數量。 –

目前還不清楚你的意思，直到n = 23，價值超過一百萬：23C10 = 1144066.'。 '10'從哪裏來？你的意思是'爲了一些r'？如果是這樣，你需要寫這個。 – sawa

@sawa其實，它從實際問題頁複製粘貼：http://projecteuler.net/problem=53 –

這是一個項目歐拉問題。你需要應用帕斯卡的三角形來解決這個問題。帕斯卡三角形是對稱的，所以我們只需計算一半就可以得到結果，這將使您的程序運行得更快。

另一種方法可以緩存以前計算的階乘結果並使用它們以避免不必要的計算過載。

@@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-21 03:06:36

算法二項式係數（NCR）在Ruby中

回答

相關問題