Каков наиболее эффективный метод для оценки значения n select k? Скорее всего, я бы хотел найти n факториал/факториал/(n-k) факториал.
Лучшей стратегией может быть использование dp в соответствии с этой рекурсивной формулой. Есть ли другой лучший метод для оценки n select k?
Вы можете использовать для этого мультипликативную формулу:
http://en.wikipedia.org/wiki/Binomial_coefficient#Multiplicative_formula
Вот моя версия, которая работает чисто в целых числах (деление на k всегда производит целочисленное частное) и быстро в O (k):
function choose(n, k)
if k == 0 return 1
return (n * choose(n - 1, k - 1)) / k
Я написал это рекурсивно, потому что это так просто и красиво, но вы можете преобразовать его в итеративное решение, если хотите.
Вероятно, самым простым способом вычисления биномиальных коэффициентов (n choose k) без переполнения является использование треугольника Паскаля. Никаких фракций или умножений не требуется. (n choose k). Значение строки nth и kth треугольника Паскаля дает значение.
Взгляните на эту страницу. Это операция O(n^2) с только добавлением, которую вы можете решить с помощью динамического программирования. Он будет молниеносно для любого числа, которое может поместиться в 64-битное целое число.
Если вы собираетесь рассчитать множество комбинаций, подобных этому, вычисление Pascal Triangle - это лучший вариант. Поскольку вы уже знаете рекурсивную формулу, я думаю, что могу пропустить код здесь:
MAX_N = 100
MAX_K = 100
C = [[1] + [0]*MAX_K for i in range(MAX_N+1)]
for i in range(1, MAX_N+1):
for j in range(1, MAX_K+1):
C[i][j] = C[i-1][j-1] + C[i-1][j];
print C[10][2]
print C[10][8]
print C[10][3]
Если у вас есть таблица поиска факториалов, то вычисление C (n, k) будет очень быстрым.
Проблема с подходом n!/k!(n-k)! заключается не столько в стоимости, сколько в том, что проблема с ! растет очень быстро, так что даже для значений nCk, которые находятся в пределах, скажем, 64-битных целые числа, промежуточные вычисления - нет. Если вам не нравится подход с каверно-рекурсивным добавлением, вы можете попробовать мультипликативный подход:
nCk == product(i=1..k) (n-(k-i))/i
где product(i=1..k) означает произведение всех членов, когда i принимает значения 1,2,...,k.
Самый быстрый способ - это, вероятно, использовать формулу, а не треугольник паскалей. Пусть начнут не делать умножения, когда мы знаем, что мы будем делить на тот же номер позже. Если k < n/2, пусть k = n - k. Мы знаем, что C (n, k) = C (n, n-k) Теперь:
n! / (k! x (n-k)!) = (product of numbers between (k+1) and n) / (n-k)!
По крайней мере, с помощью этой техники вы никогда не делите на число, которое вы раньше использовали для умножения. У вас есть (n-k) умножения и (n-k) деления.
Я думаю о том, как избежать всех разногласий, найдя GCD между числами, которые мы должны умножить, и теми, которые мы должны разделить. Я попытаюсь отредактировать позже.
"Самый эффективный" - это плохой запрос. Что вы пытаетесь сделать эффективным? Стек? Память? Скорость? В целом, я считаю, что рекурсивный метод наиболее эффективен, потому что он использует только добавление (дешевая операция), и рекурсия не будет слишком плохой для большинства случаев. Функция:
nchoosek(n, k)
{
if(k==0) return 1;
if(n==0) return 0;
return nchoosek(n-1, k-1)+nchoosek(n-1,k);
}