Trova ciascun numero nel triangolo Pascal il 1500 ° riga?

Question

Ho appena fatto un'altra domanda sul triangolo Pascal sulla ricerca della somma della 15.1a riga. Sono così felice che la gente abbia risposto così velocemente, ma sfortunatamente in seguito mi sono reso conto, ho bisogno di ogni singolo numero sulla 15.1a riga.

Qui ho trovato un modo semplice per calcolare qualsiasi numero sul triangolo Pascal, ma quando provo ad usare la formula nel mio codice, il programma si blocca nell'avvio.

#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

Hai bisogno di una libreria Biginteger per i risultati, dal momento che

binom(1500,750) = 722462892448930217028116073228485295944376343040546523665632913653613596406381727723198055046187955623124069093412562720869577867557610868874271130828359513282184417776042792372322074253393127328396528996120053749558122610911178218582669317535346728464707661495135518682519172221470420360910320792434869988224466647627642393919250205687942318888922893189087379790541907686956429837978631252775258630376332505697937034877619012586751274240109457111424

.

supera anche la solita gamma double.

Ma con un tale tipo disponibile, la relazione

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

.

consente un'implementazione semplice e relativamente efficiente:

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

.

Dove output è qualsiasi metodo di output che la libreria fornisce.

La parte value = value*numerator/denominator deve essere adattata se la libreria non offre sovraccarichi per moltiplicando / divisione biginti e generatori normali.

Answer 2

Utilizzare invece un algoritmo lineare per il fattoriale, per non impilare traboccare attraverso la ricorsione:

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

    int result = x;

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

    return result;
}

.