Variable ist zu klein
-
Hallo Leute,
ich habe 2 Funktionen geschrieben, eine, um die Fakultät auszurechnen (also n*(n-1)*(n-2) ... *2*1) und eine, um binomische Formeln auszugeben. Der Binomische Satz braucht die Fakultät, um den Binomialkoeffizienten zu berechnen. Insgesamt sieht der Binomische Satz so aus:
\sum_{k=0}^n \left({n \atop {k}}\right) a^{n-k}b^k
Ich habs mal so probiert:unsigned long fakultaet(unsigned int a) { if(a==0 || a==1) return 1; else { unsigned long n=1; unsigned int x; for(x=1;x<=a;x++) { n=n*x; } return n; } } void binomAnzeigen(unsigned int n) { switch(n) { case 0: cout << "1"; break; case 1: cout << "a + b"; break; case 2: cout << "a^2 + 2ab + b^2"; break; default: unsigned int k; unsigned long x, y; cout << "a^" << n << " + "; for(k=1;k<n;k++) { x=fakultaet(n); // Zähler vom Binomialkoeffizienten y=fakultaet(k)*fakultaet(n-k); // Nenner vom Binomialkoeffizienten if(k==1) cout << n << "a^" << (n-1) << "b + "; else { if(k==(n-1)) cout << n << "ab^" << k << " + "; else cout << (x/y) << "a^" << (n-k) << "b^" << k << " + "; } } cout << "b^" << k; break; } }Wenn n jetzt aber größer als 12 ist, ist unsigned long zu klein. Wie kann ich es anstellen, dass trotzdem das richtige Ergebnis rauskommt?
-
unsigned long long binom(int n, int k) { unsigned long long ret=1; for(int i=n;i>(k>n-k?k:n-k);i--) ret*=i; for(int i=(k>n-k?n-k:k);i>1;i--) ret/=i; return ret; }Hiermit müßte man schon ein Stückchen weiter kommen...
(falls long long nicht gehen sollte, mußt du halt mit long vorlieb nehmen
)
-
Könnte mir einer mal bitte den Code kommentieren? Die Parameter der Schleife kapier ich nicht ganz...
-
ist (i) größer als der größere von (k) und (n-k)?
-
Ich weiß nicht, wieso "binom" zwei Parameter bekommen soll. Wenn
(a+b)^4
dann ist n=4. k ist am Anfang immer 0. Deshalb braucht das auch nicht angegeben zu werden.
-
Könnte mir einer mal bitte den Code kommentieren? Die Parameter der Schleife kapier ich nicht ganz...
http://www.ica1.uni-stuttgart.de/~hilfer/de/lehre/100-online/skriptum/node34.html
Ich weiß nicht, wieso "binom" zwei Parameter bekommen soll.
binom berechnet n über k und nicht die Fakultät...
-
binom berechnet n über k und nicht die Fakultät...
Für die Fakultät habe ich ja extra eine eigene Funktion geschrieben. binom kriegt nur den einen Parameter n, die Grundform ist ja
(a+b)^n
Das k ist immer gleich, ganz egal wie groß n ist.
Aber danke für den Link!
-
So hatte ich das gedacht:
void binomAnzeigen(unsigned int n) { switch(n) { case 0: cout << "1"; break; case 1: cout << "a + b"; break; case 2: cout << "a^2 + 2ab + b^2"; break; default: unsigned int k; unsigned long x, y; cout << "a^" << n << " + "; for(k=1;k<n;k++) { if(k==1) cout << n << "a^" << (n-1) << "b + "; else { if(k==(n-1)) cout << n << "ab^" << k << " + "; else cout << binom(n,k) << "a^" << (n-k) << "b^" << k << " + "; } } cout << "b^" << k; break; } }
-
Dann hatte ich dich falsch verstanden, fubar.
Jetzt könnte man auch x und y aus binomAnzeigen rauswerfen, um noch ein bisschen Platz zu sparen.
Danke für deine Hilfe!!!
-
mit double sollte es gehen... z.b. so:
double fakDouble(double x)
{
if(x<0)
return 0;
if(x==0)
return 1;
else
return x * (fakDouble(x-1));
}
-
Eine schöne Möglichkeit ist auch sich ne Abschätzung für n über k zu besorgen und dann noch eine Primzahl p, die größer als diese Schranke ist. Mann kann dann nämlich einfach alle Schritte modulo p rechnen, also immer den Rest bezüglich Division durch p. (Mathematiker würden sagen man projiziert auf Z/pZ)
Der Rest liegt dann zwischen 0 und p-1. Weil ja aber das Ergebnis sowieso < p ist, ist dieser Rest gerade das Ergebnis. Auf diese Art und Weise kann man auch noch für ziemlich große n rechnen, weil die Fakultät ja immer wieder mit mod p klein gehalten wird.MfG Jester
-
Ich hab mich grad mal hingesetzt und noch ein bißchen rumgerechnet.
Ohne große Klimmzüge komme ich mit dieser Version wohl bis n=34.MfG Jester
-
Kannste mal Code posten dann wieß ich auch wat du mit Abchätzung meins. Bin net so gut in Mathe.
-
Also ich benutze immer folgende Funktion
template<typename T> T Binomial(unsigned n, unsigned k) { if(k > n) return 0; if(k == n) return 1; T rval = 1; for(unsigned i = n; i != k; --i) rval *= i; for(unsigned i = n - k; i != 1; --i) rval /= i; return rval; }
-
Hab den Code grad nicht greifbar. Kommt heute abend (nacht) irgendwann oder morgen früh.
MfG Jester
-
Man könnte ja auch eine zu große Zahl durch 65535 teilen, den Ganzzahlwert in einer unsigned _int64 und den Rest in einer unsigned int-Variable speichern. Zur Ausgabe mit cout rechnet man dann rückwärts
-
*knock* *knock*. Ich habe doch eine funktionierende Lösung gepostet. Wenn du die so aufrufst...
unsigned long long x = Binomial<unsigned long long>(n, k); unsigned __int64 y = Binomial<unsigned __int64>(n, k);...dann solltest du relativ hohe Werte erhalten können. Deine Idee mit dem dividieren funktioniert auch nur begrenzt und ist viel aufwändiger (NR sux
).
-
MaSTaH schrieb:
unsigned long long x = Binomial<unsigned long long>(n, k);unsigned long long funktioniert bei mir nicht
unsigned __int64 y = Binomial<unsigned __int64>(n, k);Mit der Variante kommst du bis 20!. Wenn du es aber machst, wie ich beschrieben hab (bloß mit zwei unsigned _int64), dann kommt man bis 34!.
(NR sux
).Was heißt das???
-
Für die Praxis: Einfach logarithmisch rechnen mit double-Werten. Damit kommt man sehr weit!
ln(k!) = Sum(i=1..k){ln(i)}#include <math.h> double LogFak(int k) { double dLogSum = 0; while(k > 1) { dLogSum += log((double) k); --k; } return dLogSum; }
-
#define MERKE_ERSTE 1000 //Zum Beschleunigen die ersten paar Werte merken double LogFak(int k) { static int siValid = 1; //Index, bis zu dem Array-Inhalt gueltig ist static double sadLogFak[MERKE_ERSTE] = { 0 }; if(k <= siValid) return sadLogFak[k]; double dLogSum = saLogFak[siValid]; int i = siValid + 1; while(i < MERKE_ERSTE) { dLogSum += log((double) i); sadLogFak[i] = dLogSum; ++i; } siValid = i - 1; while(i <= k) { dLogSum += log((double) i); ++i; } return dLogSum; }