Trouver chaque nombre dans le triangle de pascal sur le 1500e ligne?

Question

J'ai juste posé une autre question à propos de pascal triangle de trouver la somme de 1500e ligne.Je suis tellement heureux que des gens répondu si rapidement, Mais malheureusement j'ai compris plus tard, j'ai besoin de chaque numéro de 1500e ligne.

Ici, j'ai trouvé un moyen facile de calculer le nombre sur le triangle de pascal, mais lorsque j'essaie d'utiliser la formule dans mon code, le programme se bloque au démarrage.

#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

Vous avez besoin d'un biginteger bibliothèque pour les résultats, car

binom(1500,750) = 722462892448930217028116073228485295944376343040546523665632913653613596406381727723198055046187955623124069093412562720869577867557610868874271130828359513282184417776042792372322074253393127328396528996120053749558122610911178218582669317535346728464707661495135518682519172221470420360910320792434869988224466647627642393919250205687942318888922893189087379790541907686956429837978631252775258630376332505697937034877619012586751274240109457111424

dépasse même l'habitude double gamme.

Mais avec un tel type disponible, la relation

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

permet un simple, relativement efficace de mise en œuvre:

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

où output est quelle que soit la méthode de sortie de la bibliothèque.

L' value = value*numerator/denominator le cadre doit être adapté si la bibliothèque n'offre pas de surcharges pour la multiplication/division de bigintegers et normal ints.

Answer 2

Utilisez un algorithme linéaire pour la factorielle à la place, pour ne pas empiler déborder par récursivité:

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

    int result = x;

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

    return result;
}