Encontre cada número no triângulo pascal na linha 1.500?

Question

Acabei de fazer outra pergunta sobre o triângulo de Pascal sobre como encontrar a soma da 1.500ª linha.Estou tão feliz que as pessoas responderam tão rapidamente, mas infelizmente mais tarde percebi que preciso de cada número individual na linha 1.500.

Aqui encontrei uma maneira fácil de calcular qualquer número no triângulo pascal, mas quando tento usar a fórmula no meu código, o programa trava na inicialização.

#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

Você precisa de uma biblioteca biginteger para os resultados, já que

binom(1500,750) = 722462892448930217028116073228485295944376343040546523665632913653613596406381727723198055046187955623124069093412562720869577867557610868874271130828359513282184417776042792372322074253393127328396528996120053749558122610911178218582669317535346728464707661495135518682519172221470420360910320792434869988224466647627642393919250205687942318888922893189087379790541907686956429837978631252775258630376332505697937034877619012586751274240109457111424

excede até mesmo o habitual double faixa.

Mas com esse tipo disponível, a relação

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

permite uma implementação simples e relativamente eficiente:

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

onde output é qualquer método de saída fornecido pela biblioteca.

O value = value*numerator/denominator parte precisa ser adaptada se a biblioteca não oferecer sobrecargas para multiplicação/divisão de números inteiros grandes e normais intS.

Answer 2

Use um algoritmo linear para o fatorial, para não estourar a pilha por meio de recursão:

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

    int result = x;

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

    return result;
}