Ошибка в выводе бинома ньютона(c++)

#cpp

Написал программу для вычисления бинома Ньютона. При вводе аргумента в диапазоне
[1,13] все работает. Если вводить больший аргумент, то программа работает неправильно.
В чем проблема?

#include 
#include 

using namespace std;

int fact(int n) {
    int k = 1;
    if (n == 0)
        return 1;
    for (int i = 1; i <= n; i++)
        k = k*i;
    return k;
}

void func(int n) {
    for (int j = 0; j < n; j++) {
        for (int i = 0; i <= j; i++)
            cout << (fact(j) / (fact(i)*fact(j - i))) << " ";
        cout << endl;
    }
}

int main() {
    int n;
    cin >> n;
    func(n);
    system("pause");
}


Также вот вариант в онлайн компиляторе.
    

Ответы

Ответ 1

13! = 6227020800

14! = 87178291200

int (4 байта) имеет диапазон [−2147483648; +2147483647], поэтому числа просто не влезают

Чтобы расширить возможности, не меняя алгоритма, можно поменять тип на unsigned long
long (8 байт)


Ответ 2

У вас происходит так называемое переполнение типа. int имеет ограниченный диапазон
значений (обычно от −2147483648 до +2147483647 знаковый, либо от 0 до 4294967295, если
беззнаковый). В случае переполнения значение "перескакивает" от максимального к минимальному
(при сложении и умножении положительных чисел), это связанно с удобством аппаратной
реализации, но в целом это явление называется неопределённым поведением (undefined
behavior) и когда подобное происходит, то компилятор снимает с себя всю ответственность
за корректность выполнения такой программы.

Вы можете использовать типы, которые имеют более широкий диапазон значений (например
unsigned long long размером 8 байт и имеющий диапазон значений от 0 до 18446744073709551615).

В случае, если требуемое значение всё равно не помещается в диапазон, то можно сделать
свою реализацию длинной арифметики либо использовать библиотечные реализации (учитывайте,
что эти библиотеки не являются сандартными, их нужно отдельно скачивать)

#include 
boost::multiprecision::cpp_int very_long_number;
// или
#include 
mpz_class very_long_number;


в этих случаях диапазон значений ограничивается лишь размером вашей оперативной памяти.


Ответ 3

Работа по обычной формуле - через факториал: для int в 4 байта - предел - 13, для
unsigned long long в 8 байт - 21. При этом для int сам бином вполне записывается до
17 степени, для unsigned long long - до 29 (т.е. все коэффициенты помещаются в указанные
типы).


Ответ 4

Вообще не надо лучше считать факториалы - слишком сильно Вы себя ограничиваете в
вычислении коэффициентов. При их вычислении бОльшая часть сокращается. Я бы либо придумал
систему сокращения числителя и знаменателя или, что проще, строить треугольник паскаля
(здесь да, придется 1 раз потратить ресурсы, зато потом вычисление коэффициентов будет
О(1))

P.S. можно рекурсивно всегда вычислять коэффициент через предыдущие по известной формуле.