Finden Sie jede Zahl im Pascal-Dreieck in der 1500. Reihe?
-
11-12-2019 - |
Frage
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);
}
}
Lösung
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 int
S.
Andere Tipps
Verwenden Sie stattdessen einen linearen Algorithmus für das Fachelement, um den Überlauf nicht durch Rekursion zu stapeln: generasacodicetagpre.