我试图通过用Pascal三角形进行递归来计算二项式系数。它适用于少量数字，但是20以上的速度真的很慢，或者根本不起作用。
我试图查找一些优化技术，例如“ chaching”，但是它们似乎并没有很好地集成在C ++中。
如果可以，请使用以下代码。
int binom(const int n, const int k)
{
double sum;
if(n == 0 || k == 0){
sum = 1;
}
else{
sum = binom(n-1,k-1)+binom(n-1,k);
}
if((n== 1 && k== 0) || (n== 1 && k== 1))
{
sum = 1;
}
if(k > n)
{
sum = 0;
}
return sum;
}
int main()
{
int n;
int k;
int sum;
cout << "Enter a n: ";
cin >> n;
cout << "Enter a k: ";
cin >> k;
Summe = binom(n,k);
cout << endl << endl << "Number of possible combinations: " << sum <<
endl;
}
我的猜测是该程序浪费了很多时间来计算已经计算出的结果。它必须以某种方式记住过去的结果。
我的猜测是该程序浪费了很多时间来计算已经计算出的结果。
确实是这样
关于这个主题，我建议您看看动态编程主题。
有一类问题需要指数的运行时复杂性，但是可以用动态编程技术解决。这样可以将运行时复杂度降低为多项式复杂度（大多数情况下，以增加空间复杂度为代价）。
动态编程的常见方法是：
以下是我自下而上的解决方案（快速而紧凑）：
int BinomialCoefficient(const int n, const int k) {
std::vector<int> aSolutions(k);
aSolutions[0] = n - k + 1;
for (int i = 1; i < k; ++i) {
aSolutions[i] = aSolutions[i - 1] * (n - k + 1 + i) / (i + 1);
}
return aSolutions[k - 1];
}
该算法具有运行时复杂度O(k)和空间复杂度O(k)。确实，这是线性的。
此外，该解决方案比递归方法更简单，更快捷。这对CPU缓存非常友好。
注意也没有依赖n。
我通过简单的数学运算并获得以下公式获得了此结果：
(n, k) = (n - 1, k - 1) * n / k
注意
该算法实际上不需要空间复杂度为O(k)。实际上，第i步的解决方案仅取决于（i-1）-th。因此，无需存储所有中间解决方案，只需存储上一步中的解决方案即可。那将使算法O(1)在空间复杂度方面。
但是，我希望将所有中间解决方案保留在解决方案代码中，以更好地展示动态编程方法论的原理。
本文收集自互联网，转载请注明来源。
如有侵权，请联系 [email protected] 删除。
我来说两句