Finden Sie jede Zahl im Pascal-Dreieck in der 1500. Reihe?

Question

Ich habe gerade eine weitere Frage zum Pascal-Dreieck gestellt, um die Summe der 1500. Zeile zu ermitteln.Ich bin so froh, dass die Leute so schnell geantwortet haben, aber leider wurde mir später klar, dass ich jede einzelne Nummer in der 1500. Zeile brauche.

Hier habe ich eine einfache Möglichkeit gefunden, eine beliebige Zahl im Pascal-Dreieck zu berechnen, aber wenn ich versuche, eine Formel in meinem Code zu verwenden, stürzt das Programm beim Start ab.

#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

Für die Ergebnisse benötigen Sie eine Biginteger-Bibliothek

binom(1500,750) = 722462892448930217028116073228485295944376343040546523665632913653613596406381727723198055046187955623124069093412562720869577867557610868874271130828359513282184417776042792372322074253393127328396528996120053749558122610911178218582669317535346728464707661495135518682519172221470420360910320792434869988224466647627642393919250205687942318888922893189087379790541907686956429837978631252775258630376332505697937034877619012586751274240109457111424

übertrifft sogar das Übliche double Reichweite.

Aber mit einem solchen Typ ist die Beziehung verfügbar

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

ermöglicht eine einfache, relativ effiziente Implementierung:

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

Wo output ist die Ausgabemethode, die die Bibliothek bereitstellt.

Der value = value*numerator/denominator Teil muss angepasst werden, wenn die Bibliothek keine Überladungen zum Multiplizieren/Dividieren großer Ganzzahlen und normaler Zahlen bietet intS.

Answer 2

Verwenden Sie stattdessen einen linearen Algorithmus für das Fachelement, um den Überlauf nicht durch Rekursion zu stapeln: generasacodicetagpre.