Вычислить значение n выбрать k

Ответ 1

Вы можете использовать для этого мультипликативную формулу:

http://en.wikipedia.org/wiki/Binomial_coefficient#Multiplicative_formula

Ответ 2

Вот моя версия, которая работает чисто в целых числах (деление на k всегда производит целочисленное частное) и быстро в O (k):

function choose(n, k)
    if k == 0 return 1
    return (n * choose(n - 1, k - 1)) / k

Я написал это рекурсивно, потому что это так просто и красиво, но вы можете преобразовать его в итеративное решение, если хотите.

Ответ 3

Вероятно, самым простым способом вычисления биномиальных коэффициентов (n choose k) без переполнения является использование треугольника Паскаля. Никаких фракций или умножений не требуется. (n choose k). Значение строки nth и kth треугольника Паскаля дает значение.

Взгляните на эту страницу. Это операция O(n^2) с только добавлением, которую вы можете решить с помощью динамического программирования. Он будет молниеносно для любого числа, которое может поместиться в 64-битное целое число.

Ответ 4

Если вы собираетесь рассчитать множество комбинаций, подобных этому, вычисление 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]

Ответ 5

Если у вас есть таблица поиска факториалов, то вычисление C (n, k) будет очень быстрым.

Ответ 6

Проблема с подходом n!/k!(n-k)! заключается не столько в стоимости, сколько в том, что проблема с ! растет очень быстро, так что даже для значений nCk, которые находятся в пределах, скажем, 64-битных целые числа, промежуточные вычисления - нет. Если вам не нравится подход с каверно-рекурсивным добавлением, вы можете попробовать мультипликативный подход:

nCk == product(i=1..k) (n-(k-i))/i

где product(i=1..k) означает произведение всех членов, когда i принимает значения 1,2,...,k.

Ответ 7

Самый быстрый способ - это, вероятно, использовать формулу, а не треугольник паскалей. Пусть начнут не делать умножения, когда мы знаем, что мы будем делить на тот же номер позже. Если 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 между числами, которые мы должны умножить, и теми, которые мы должны разделить. Я попытаюсь отредактировать позже.

Ответ 8

"Самый эффективный" - это плохой запрос. Что вы пытаетесь сделать эффективным? Стек? Память? Скорость? В целом, я считаю, что рекурсивный метод наиболее эффективен, потому что он использует только добавление (дешевая операция), и рекурсия не будет слишком плохой для большинства случаев. Функция:

nchoosek(n, k)
{
    if(k==0) return 1;
    if(n==0) return 0;
    return nchoosek(n-1, k-1)+nchoosek(n-1,k);
}