c++ - 编写计算 nCr 值的程序 (C++)

Question

我在下面编写了代码来计算 n 个 testCount 值的 nCr。它似乎适合我的值(value)观，但 hacker earth 的测试用例失败，问题链接 http://www.hackerearth.com/problem/golf/minimal-combinatorial/description/ 谁能告诉我我的逻辑中潜在的谬误是什么

`#include <iostream>
 using namespace std;

 int main()
{
    int testCount; 
    int n , r;
    cin >> testCount;
    for (int i = 0 ; i < testCount ; i++)
    {

        long int a=1;
        long int b=1;
        long int c=1;
        cin >> n;
        cin >> r;
        for (int i = n ; i > 1 ; i--)
        {
             a = a * i;
        }
        for (int i = n-r; i >= 1 ; i--)
        {
            b=b*i;
        }
       for (int i=r;i >=1;i--)
       {
           c=c*i;
       }
       long int result=a/(b*c);
       cout << result<<"\n";
    }

    return 0;
}

` 简化分子和分母的情况

 `#include <iostream>
  using namespace std;

int main()
{
   int testCount; 
   int n , r;
   cin >> testCount;
  for (int i = 0 ; i < testCount ; i++)
  {

       long int numerator=1;
       long int denominator=1;
       cin >> n;
       cin >> r;
       for (int i = n ; i > r ; i--)
       {
          numerator = numerator * i;
       }
       for (int i = n-r; i >= 1 ; i--)
       {
           denominator=denominator*i;
       } 

       long int result=numerator/denominator;
       cout << result;
   }

    return 0;

} `

Answer 1

你的两个代码都可能溢出(即使结果应该适合 64 位整数)

你可以试试:

std::uint64_t cnr(int n, int r)
{
    std::uint64_t ans = 1;
    r = std::min(r, n - r);

    for(int j = 1; j <= r; j++, n--) {
        // all following do: ans = (ans * n) / j;
        // but the 2 first cases do some simplifications
        // to reduce the possibility of overflow

        if (n % j == 0) {
            ans *= n / j; 
        } else if (ans % j == 0) {
            ans = (ans / j) * n;
        } else {
            ans = (ans * n) / j;
        }
    }
    return ans;
}