C++ 组合函数总是结果为 0

Question

谁能告诉我为什么我的 Combination 函数的结果总是 0 ？ 我还尝试让它在不使用置换函数但使用阶乘的情况下计算组合，但结果仍然为 0；

#include <iostream>
#include <cmath>

using namespace std;

int factorial(int& n)
{
  if (n <= 1)
  {
     return 1;
  }
  else 
  {
    n = n-1;
    return (n+1) * factorial(n);
  }
}
int permutation(int& a, int& b)
{
  int x = a-b;
  return factorial(a) / factorial(x);
}
int Combination(int& a, int& b)
{
   return permutation(a,b) / factorial(b);
}

int main()
{
   int f, s;
   cin >> f >> s;

   cout << permutation(f,s) << endl;
   cout << Combination(f,s);


  return 0;
 }

Answer 1

您的直接问题是您向您的函数传递了一个可修改的引用。这意味着你在这里有未定义的行为:

return (n+1) * factorial(n);
//      ^^^             ^^^

因为factorial(n)修改 n , 并且不确定地排序为 (n+1) . Combination() 中也存在类似的问题, 其中b在同一个表达式中被修改了两次:

return permutation(a,b) / factorial(b);
//                  ^^^            ^^^

如果您通过 n，您将得到正确的结果, a和 b 按值，像这样:

int factorial(int n)

现在，factorial()获取它自己的 n 的拷贝，并且不影响 n+1你在乘以它。

---

既然我们在这里，我应该指出代码中的其他一些缺陷。

• 避免 using namespace std; - 它为粗心的人设置了陷阱(甚至为谨慎的人设置了陷阱!)。

• 你可以写成factorial()不修改n一旦按值(而不是按引用)传递:

  int factorial(const int n)
  {
      if (n <= 1) {
          return 1;
      } else {
          return n * factorial(n-1);
      }
  }
  

• 考虑使用迭代代码来计算阶乘。

• 我们可能应该使用 unsigned int ，因为操作对负数没有意义。您可能会考虑 unsigned long或 unsigned long long范围更广。

• 计算一个阶乘并除以另一个阶乘不仅效率低下，而且还有不必要的溢出风险(当 a 低至 13，32 位 int 时)。相反，我们可以乘以另一个数字:

  unsigned int permutation(const unsigned int a, const unsigned int b)
  {
      if (a < b) return 0;
  
      unsigned int permutations = 1;
      for (unsigned int i = a;  i > a-b;  --i) {
          permutations *= i;
      }
  
      return permutations;
  }
  

  这适用于更高的 a , 当 b很小。

• 我们不需要 <cmath>任何内容的标题。

---

建议的固定代码:

unsigned int factorial(const unsigned int n)
{
    unsigned int result = 1;

    for (unsigned int i = 2;  i <= n;  ++i) {
        result *= i;
    }

    return result;
}

unsigned int permutation(const unsigned int a, const unsigned int b)
{
    if (a < b) return 0;

    unsigned int result = 1;
    for (unsigned int i = a;  i > a-b;  --i) {
        result *= i;
    }

    return result;
}

unsigned int combination(const unsigned int a, const unsigned int b)
{
    // C(a, b) == C(a, a - b), but it's faster to compute with small b
    if (b > a - b) {
        return combination(a, a - b);
    }

    return permutation(a,b) / factorial(b);
}