Алгоритм биномиального коэффициента (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, для 1 ≤ n ≤ 100, - больше одного миллиона?

Мне нужно разработать алгоритм в Ruby для решения этой проблемы, но я, похоже, не понимаю, как это делается.

Answer 1

Это проблема Эйлера проекта. Чтобы решить эту проблему, вам необходимо применить треугольник паскаля. Треугольник pascal симметричен, поэтому нам нужно вычислить половину его, чтобы получить результат, это заставит вашу программу работать быстрее.

Другой способ кэширования ранее вычисленных факториальных результатов и использовать их во избежание излишней перегрузки вычислений.

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