Бином Ньютона — не работает для больших чисел

Я написал программу, которая должна печатать значение бинома Ньютона.
число — количество тестов, t[i][0] - n, t[i][1] - k, Кажется, что это хорошо для небольших чисел n и k, но когда я хочу набрать большее число, он печатает 0, 1 или маленькое, отрицательное целое число. В основном я использовал long intead int, поэтому он должен работать с большими числами. Не могли бы вы объяснить, почему это так?

#include <iostream>
long fact(int x);
using namespace std;
int main()
{
int number;
cin>>number;
int t[number][2];

for(int i=0; i<number; i++)
{
cin>>t[i][0];
cin>>t[i][1];
if (t[i][0]<t[i][1]) return 0;
}

for(int i=0; i<number; i++)
{
cout<<fact(t[i][0])/(fact(t[i][0]-t[i][1])*fact(t[i][1]))<<endl;
}
return 0;
}
long fact(int x)
{
long factt=1;
for(int i=1; i<=x; i++)
{
factt=factt*i;
}
return factt;
}

@редактировать

Спасибо за совет. Я пытался реализовать это, но это не очень хорошо вычисляет бином. Он печатает 11 для n = 4 и k = 2. Можете ли вы взглянуть на это?

#include <iostream>

long fact(int n, int k);
using namespace std;
int main()
{
int number;
cin>>number;
int t[number][2];

for(int i=0; i<number; i++)
{
cin>>t[i][0];
cin>>t[i][1];
if (t[i][0]<t[i][1]) return 0;
}
for(int i=0; i<number; i++)
{
cout<<fact(t[i][0],t[i][1])<<endl;
}
return 0;
}

long fact(int n, int k)
{
if(n==0 || n==k)
return 1;
else if(n>k)
return fact(n-1,k-1)+fact(n-1, k);
else
return 0;
}

3

Решение

Факториал растет очень быстро и даже переполнение 64-битных целых чисел без знака n! за n>20, Свободный от переполнения способ реализации биномиального коэффициента заключается в использовании этого рекурсивного определения:

binom(n, k) = binom(n-1, k-1) + binom(n-1, k)

Это гарантирует, что вы получите переполнение только тогда, когда binom(n,k) слишком велик, чтобы соответствовать размеру вашего целого типа.

2

Другие решения

В Linux 32-битная длина совпадает с int и вписывается в 32-битную. В Linux длина 64 бита равна длине 64 бита.
В Windows 32-битная и 64-битная длина — 32-битная сущность

Вы должны использовать long long гарантированно использовать 64 бит, хотя этого может быть недостаточно для преодоления переполнения. Используйте рекурсивную формулу для биноминала, если это возможно

0