große Zahlen bei Fakultätsberechnung

ruhig_brauner

Hallo. Beschäftige mich seit 3 Tagen mit C++. Hab sonnst bloß in der Schule (Gymnasium) in nem Grundkurs mt Delphi gebastelt. Jetzt lerne ich auch aus Spaß und Interesse halt C++, für einen eventuellen späteren Job.

Genug zu mir, jetzt kommt die Frage.

Ich will zur Übung ein Programm zur Wahrscheinlichkeitsberechnung machen, dabei spielt "n über k" eine wichtige Rolle, was wiederum aus einigen n! und k! und so weiter besteht. Also Fakultäten.

Habe ne Funktion für Potenzberechnung und für Fakultäten geschrieben und dann ne Funktion für ne Kettenlänge. Quelltext scheint richtig zu sein. Bei dem ersten Testlauf habe ich dann mit ner Kettenlänge von 20 gerechnet und nicht verstanden, weshalb das Ergebnis nicht weiter von dem meines Taschenrechners entfernt sein könnte.

Inzwischen habe ich die problematische Stelle gefunden, 20! ist in etwas 2,4E18 (um es mal in C++ auszudrücken :D)
Meine Variable macht aber schon wesentlich früher Schluss. Dann wird wieder von unten gezählt und das Ergebniss landet bei -24324bla.

Kennt jemand eine Lösung? (Ich schreibe den Murks (das Programm, net den Thread) vor allem weil ich so meine Mathe Hausaufgaben abkürzen kann )

Wenn net, kann man "n über k" zusammenfassen, sodass solche Werte nicht abgespeichert werden müssen?

(Fettes EDIT!): Also der Funktion den Rückgabetyp float zu geben, hat schonmal geholfen. Aber trozdem bleibt der Bereich der möglichen Kettenlängen kleiner als erhofft. Gibt es ne groooße Alternative zu float?

Dann hätte ich nochmal ne andere Frage, an Leute, die beruflich mit C++ arbeiten. Macht das Spaß? (Mich würde mal die rein subjektive Antwort interessieren. Will auch kein "kommt auf den Bereich an" hören. )

Grüße

ruhig_brauner schrieb:

Wenn net, kann man "n über k" zusammenfassen, sodass solche Werte nicht abgespeichert werden müssen?

Kürzen

ruhig_brauner

Na (n über k) ist

n! / ( k!*(n-k)!)

viel kürzen kann man da net, man könnte es ja in einem Rutsch ausrechnen, aber ich denke mal net, dass C++ ne funktion für Fakultäten hat. so muss ich den Wert speichern und extern ausrechnen lassen (Funktion halt)

vario-500

hier http://de.wikipedia.org/wiki/Binomialkoeffizient#Algorithmus_zur_effizienten_Berechnung ist effizienter algorithmus. du bekommst produkte die du alle schön einzeln ausrechnen kannst und am ende miteinander multiplizieren musst

ruhig_brauner

ouch.... Das könnte helfen Danke.

ruhig_brauner schrieb:

Hallo. Beschäftige mich seit 3 Tagen mit C++. Hab sonnst bloß in der Schule (Gymnasium) in nem Grundkurs mt Delphi gebastelt. Jetzt lerne ich auch aus Spaß und Interesse halt C++, für einen eventuellen späteren Job.

Genug zu mir, jetzt kommt die Frage.

Ich will zur Übung ein Programm zur Wahrscheinlichkeitsberechnung machen, dabei spielt "n über k" eine wichtige Rolle, was wiederum aus einigen n! und k! und so weiter besteht. Also Fakultäten.

Nennt sich Binominalkoeffizient. Keine Sorge, wir können Mathe

ruhig_brauner schrieb:

Inzwischen habe ich die problematische Stelle gefunden, 20! ist in etwas 2,4E18 (um es mal in C++ auszudrücken :D)

Nennt sisch Wissenschaftliche Schreibweise.

ruhig_brauner schrieb:

(Fettes EDIT!): Also der Funktion den Rückgabetyp float zu geben, hat schonmal geholfen. Aber trozdem bleibt der Bereich der möglichen Kettenlängen kleiner als erhofft. Gibt es ne groooße Alternative zu float?

double und long double .

Zum Spaß: PI zum Beispiel ist schon süchtig, also besser garnicht erst anfangen

ruhig_brauner

Hab gerade mal nachgeguckt, wie groß long double ist. Die Typen sagen mir ja schon was, hab aber vergessen wie verdammt groß long double sein kann.

Najut, das Problem ist ja jetzt trozdem gelöst

Die andere Frage bleibt bestehen, falls jemand Lust hat, drauf zu antworten. Mach C++-Programmierer als Job spaß, oder trifft der unschöne Begriff "Codeäffchen" es doch manchmal? (Beim Lesen von dem Begriff war ich letztens ziemlich niedergeschlagen... :/)

ruhig_brauner schrieb:

Na (n über k) ist

n! / ( k!*(n-k)!)

viel kürzen kann man da net

Öhm, ich behaupte mal das Gegenteil: (n+x)! = n! * (n+1) * (n+2) * ... (n+x).
Angenommen, wir wollen 5!/3! rechnen. Dann ist das Ganze nur noch (k+1) * (k+2).

Hacker schrieb:

double und long double .

Man nimmt doch keine Gleitkommazahl, wenn es sich um Ganzzahlen handelt.

Gugelmoser schrieb:

Man nimmt doch keine Gleitkommazahl, wenn es sich um Ganzzahlen handelt.

versteh nicht ganz.
Größer als int wirst du keinen Integralen BDT finden, außer long und vielleicht long long (was nicht überall erlaubt ist).

Gibt es ne groooße Alternative zu float?

Wenn er integrale Typen verwenden will, soll er doch int und nicht float nehmen

ruhig_brauner

Gugelmoser schrieb:

Hacker schrieb:

double und long double .

Man nimmt doch keine Gleitkommazahl, wenn es sich um Ganzzahlen handelt.

Es sei denn, unsigned long reicht nicht für die Zahlen aus oder man ist noch ein blutiger Anfänger.

314159265358979

Gibt da noch unsigned long long und wenn das nicht reicht, nimmt man Bigint Bibliotheken, z.B. GMP.

Hacker schrieb:

Gugelmoser schrieb:

Man nimmt doch keine Gleitkommazahl, wenn es sich um Ganzzahlen handelt.

versteh nicht ganz.
Größer als int wirst du keinen Integralen BDT finden, außer long und vielleicht long long (was nicht überall erlaubt ist).

Jetzt verstehe ich nicht ganz, was du mir damit sagen willst.

Sorry, ich hätte ihn zitieren sollen, anstatt dich. Es kam mir im ersten Moment nur so vor, als würdest du ihn dabei unterstützen.

314159265358979 schrieb:

Gibt da noch unsigned long long

Ist das nicht nur auf manchen Systemen erlaubt? Könnte schwören, Ideones GCC 4.3.1 (glaub die haben LAMP) hat mich da mal böse überrascht.

Gugelmoser schrieb:

Hacker schrieb:

Gugelmoser schrieb:

Man nimmt doch keine Gleitkommazahl, wenn es sich um Ganzzahlen handelt.

versteh nicht ganz.
Größer als int wirst du keinen Integralen BDT finden, außer long und vielleicht long long (was nicht überall erlaubt ist).

Jetzt verstehe ich nicht ganz, was du mir damit sagen willst.

Sorry, ich hätte ihn zitieren sollen, anstatt dich. Es kam mir im ersten Moment nur so vor, als würdest du ihn dabei unterstützen.

BDT = Basis-DatenTyp (char, float, usw.)
Integral: Kann nur Ganze Zahlen Speichern (hoffe du kannst Mathe )

314159265358979

Hacker schrieb:

314159265358979 schrieb:

Gibt da noch unsigned long long

Ist das nicht nur auf manchen Systemen erlaubt? Könnte schwören, Ideones GCC 4.3.1 (glaub die haben LAMP) hat mich da mal böse überrascht.

Ist seit C++11 Standard.

314159265358979 schrieb:

Hacker schrieb:

314159265358979 schrieb:

Gibt da noch unsigned long long

Ist das nicht nur auf manchen Systemen erlaubt? Könnte schwören, Ideones GCC 4.3.1 (glaub die haben LAMP) hat mich da mal böse überrascht.

Ist seit C++11 Standard.

Mmhh, danke!

Da Fließkommaberechnung scheinbar kein Problem für den TE darstellt, wäre

double bincoeff(int n, int k) {
  return tgamma(n + 1) / tgamma(k + 1) / tgamma(n - k + 1);
}

eine einfache Möglichkeit.

ruhig_brauner

Hätte doch noch ne Frage.

Wie sorgt man für ne Eingabewiederhohlung, wenn z.B. keine Zahlen sonder Buchstaben oder keine ganzen Zahlen eingegeben werden?

Also wenn z.B. nur mit y oder n geantwortet werden soll, ist das ja kein Problem. Bei einstelligen Zahlen würde ich auch wissen, wie man die Eingabe von Buchstaben vermeidet. Aber bei 0.52 oder 30 habe ich keine Ahnung

ruhig_brauner schrieb:

Wie sorgt man für ne Eingabewiederhohlung, wenn z.B. keine Zahlen sonder Buchstaben oder keine ganzen Zahlen eingegeben werden?

int ganzzahl;
	cout << "Bitte eine Ganzzahl eingeben: ";
	while( !(cin>>ganzzahl) )
	{
		cin.clear();
        cin.ignore(numeric_limits<streamsize>::max(),'\n'); // #include <limits>
        cout << "Bitte eine Ganzzahl eingeben: ";
	}

Michael E.

Hacker schrieb:

Integral: Kann nur Ganze Zahlen Speichern (hoffe du kannst Mathe )

Integrale sind Nudeln. Keine Ahnung, was man alles in Mathe können muss, um was mit ganzen Zahlen anfangen zu können.

Ich hab auch noch nen Vorschlag:

\begin{align*} n! = 2^{\sum_{i=1}^n \log_2 i} \end{align*}