C++组合函数总是产生0

Question

谁能告诉我为什么我的组合功能总是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);
}