评估 n 选择 k 值的最有效方法是什么？我认为的蛮力方法是找到 n factorial / k factorial / (nk) factorial 。
更好的策略可能是根据这个递归公式使用 dp 。还有其他更好的方法来评估 n 选择 k 吗？
问问题
58987 次
8 回答
48
这是我的版本，它纯粹以整数工作（除以 k 总是产生整数商）并且在 O(k) 时速度很快：
function choose(n, k)
if k == 0 return 1
return (n * choose(n - 1, k - 1)) / k
我递归地写了它，因为它是如此简单和漂亮，但如果你愿意，你可以将它转换为迭代解决方案。
于 2013-03-08T20:10:08.527 回答
38
于 2013-03-08T20:06:44.713 回答
7
计算二项式系数(n choose k)而不溢出的最简单方法可能是使用帕斯卡三角形。不需要分数或乘法。(n choose k). 帕斯卡三角形的nth行和kth条目给出了值。
看看这个页面。这是一个O(n^2)只有加法的操作，你可以用动态规划来解决。对于任何可以放入 64 位整数的数字来说，这将是闪电般的速度。
于 2013-03-08T20:02:36.933 回答
5
如果你要计算很多这样的组合，计算帕斯卡三角形肯定是最好的选择。正如您已经知道递归公式一样，我想我可以在这里传递一些代码：
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]
于 2013-03-08T20:08:10.067 回答
1
该n!/k!(n-k)!方法的问题与其说是成本问题，不如说是!快速增长的问题，因此，即使其值nCk在 64 位整数范围内，中间计算也不是。如果您不喜欢 kainaw 的递归加法方法，您可以尝试乘法方法：
nCk == product(i=1..k) (n-(k-i))/i
where表示取值product(i=1..k)时所有项的乘积。i1,2,...,k
于 2013-03-08T19:54:59.797 回答
1
最快的方法可能是使用公式，而不是帕斯卡三角形。当我们知道以后要除以相同的数字时，让我们开始不做乘法。如果 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) 除法。
我正在考虑一种避免所有除法的方法，通过在我们必须相乘的数字和我们必须除的数字之间找到 GCD。我稍后会尝试编辑。
于 2013-03-08T20:20:23.520 回答
0
如果您有一个阶乘查找表，那么 C(n,k) 的计算将非常快。
于 2013-03-08T19:53:09.440 回答
-4
“最有效”是一个糟糕的要求。你想提高什么效率？堆栈？记忆？速度？总的来说，我认为递归方法是最有效的，因为它只使用加法（一种廉价的操作），并且对于大多数情况，递归不会太糟糕。功能是：
nchoosek(n, k)
{
if(k==0) return 1;
if(n==0) return 0;
return nchoosek(n-1, k-1)+nchoosek(n-1,k);
}
于 2013-03-08T19:45:52.260 回答