У меня есть код, который вычисляет биномиальный коэффициент, но когда число больше 20, оно начинает вычисляться неправильно, в чем проблема? Спасибо
#include <iostream>
using namespace std;
long int bin(long int x)
{
if(x==0)
return 1;
long int r = x;
for(int i = r-1;i>0;i--)
{
r = r*i;
}
return r;
}
int main()
{
cout << "Write n and k: " << endl;
long int n=0;
long int k=0;
cin >> n;
cin >> k;
long int result = 0;
long int fn = bin(n);
long int fk = bin(k);
long int fnk = bin(n-k);result = fn/(fk*fnk);
cout << endl << "C = " << result << endl;return 0;
}
например 12 и 5 = 792, что правильно, но 20 и 4 = -2, что не правильно
Ваш bin
Функция вычисляет факториал. Факториал 21 не вписывается в long
,
Вы уже полагаетесь на детали реализации. long
требуется только 32 бита, но в вашей системе это 64. Если бы это было только 32, то вы потерпели бы неудачу гораздо раньше.
20! = 2432902008176640000, что намного выше long int
может держать (обычно 2147483647). использование double
вместо.
Вы вычисляете факториал n, используя
bin(n);
Вы бежите за предел long, когда n> 20.
Как отметил @SteveJessop в комментариях, вы превысите лимит, даже если вы использовали без знака длинный длинный (самый длинный тип с фиксированной точкой), который имеет диапазон
от 0 to 18446744073709551615
Вы можете использовать int-массив для хранения вашего результата как подробно Вот.