¿Encuentra cada número en el triángulo pascal en la fila 1500?

Question

Acabo de hacer otra pregunta sobre el triángulo de Pascal sobre cómo encontrar la suma de la fila 1500.Me alegra mucho que la gente haya respondido tan rápido, pero desafortunadamente más tarde me di cuenta de que necesito cada número individual en la fila 1500.

Aquí encontré una manera fácil de calcular cualquier número en el triángulo de Pascal, pero cuando intento usar la fórmula en mi código, el programa falla al iniciar.

#include"stdio.h"
int factorial(int);

int main()
{
    int i=0;
    for(i=0; i<1501; i++)
    {
       printf("%d \n" , (factorial(1500)/factorial(1500-i))/factorial(i) );
    }
}
int factorial(int x)
{
    if(x<2)
    return 1;
    else
    {
        return x*factorial(x-1);
    }
}

Answer 1

Necesita una biblioteca biginteger para los resultados, ya que

binom(1500,750) = 722462892448930217028116073228485295944376343040546523665632913653613596406381727723198055046187955623124069093412562720869577867557610868874271130828359513282184417776042792372322074253393127328396528996120053749558122610911178218582669317535346728464707661495135518682519172221470420360910320792434869988224466647627642393919250205687942318888922893189087379790541907686956429837978631252775258630376332505697937034877619012586751274240109457111424

supera incluso lo habitual double rango.

Pero con un tipo de este tipo disponible, la relación

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

permite una implementación simple y relativamente eficiente:

bigint value = 1;
int numerator = 1500 + 1, denominator = 0;
for(; denominator <= 1500; --numerator, ++denominator, value = value*numerator/denominator)
{
    output(value);
}

dónde output es cualquier método de salida que proporcione la biblioteca.

El value = value*numerator/denominator parte debe adaptarse si la biblioteca no ofrece sobrecargas para multiplicar/dividir números enteros grandes y normales ints.

Answer 2

Use un algoritmo lineal para el factorial en su lugar, no apilar el desbordamiento a través de la recursión:

int factorial(int x) {
    if (x < 2) return 1;

    int result = x;

    while (--x) {
        result *= x;
    }

    return result;
}