计算的N值选择k（闭合）(Calculate value of n choose k [closed

什么是评价值n选择k最有效的方法？该蛮力方式，我认为是找到N个因子/ K因子/（NK）阶乘。

一个更好的策略可以是根据这个使用DP 递推公式。有没有其他更好的方法来评估ň选择k？

Answer 1:

你可以使用这个乘法公式：

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

Answer 2:

这里是我的版本，这在整数纯粹的作品（用K师总是产生一个整数商），并快速在O（K）：

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

我写的递归，因为它是如此简单和漂亮，但如果你喜欢，你可以将其转换为一个迭代的解决方案。

Answer 3:

大概计算二项式系数的最简单的方法(n choose k)不会溢出是利用帕斯卡三角。没有分数或乘法是必要的。 (n choose k) 在nth行和kth帕斯卡三角的条目提供的价值。

看看这个页面。这是一个O(n^2)与只此外，它可以与动态规划解决操作。这将是快如闪电的任何数量的可以容纳一个64位整数。

Answer 4:

如果你要计算多组合这样的，在计算杨辉三角肯定是最好的选择。正如你已经知道的递推公式，我想我可以过去这里的一些代码：

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]

Answer 5:

与这个问题n!/k!(nk)! 做法是没有这么多的成本与问题! 非常迅速，使得生长，即使是值nCk其是很好的，比方说，64位整数的范围内，中间计算都没有。如果你不喜欢kainaw的递归另外的方法，你可以尝试乘的方法：

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

其中product(i=1..k)是指所有的术语的产品时i所采用的值1,2,...,k 。

Answer 6:

最快的方式可能是使用的公式，而不是杨辉三角形。让我们先不要做乘法时，我们知道，我们将在由相同数量后分裂。如果k <N / 2，让我们K = N - K。我们知道，C（N，K）= C（N，NK）现在：

n! / (k! x (n-k)!) = (product of numbers between (k+1) and n) / (n-k)!

至少这种技术，你永远由你使用之前乘以一个数除以。你有（NK）乘法，和（NK）部门。

我想办法避免所有部门，通过寻找，我们必须乘以数字之间GCDS，和那些我们必须分配。我会尝试以后编辑。

Answer 7:

如果你有阶乘的查找表，然后在C（n，k）的计算将非常快。

Answer 8:

“最有效”是一个贫穷的请求。什么是你想使高效？堆栈？记忆？速度？总的来说，我的看法是，递归方法是最有效的，因为它仅使用加法（便宜的操作）和递归不会为大多数情况下，太糟糕了。该功能是：

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

文章来源: Calculate value of n choose k [closed]