биномиальные коэффициенты — Программа, написанная для вычисления значения nCr (C ++)
Я написал ниже код для расчета nCr для n значений testCount. Кажется, это работает нормально для моих значений, но тестовые случаи хакерской земли не удается, ссылка проблемы 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;
}
`
Решение
Оба ваших кода могут переполниться (даже если результат должен соответствовать 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;
}
Другие решения