Binominalkoeffizient

[Carrotze]

Hallihallo,
vorab, ich bin neu hier. Dh ich bin mir nicht ganz sicher ob ich im richtigen Teil des Forums bin, bitte daher um Verständniss.:b

Ich möchte eine Methode zur Berechnung des Binominalkoeffizienten n über k schreiben.
Verwendete Formel ist: n+1 über k+1 = n über k * n/k.
Hier der Code:

public static double binom3(int n, int k)
{
double binom3=1;
if(k==0)
{return 1;}
else{return (n/k)*binom3(n-1,k-1);}

}
Bei 5 über 2 kommt aber statt 10 8 als Ergebniss raus. Ich bin mir relativ sicher, dass der Code auf dem Papier funktioniert, Java sieht das aber wohl anders.:/

Hat jemand eine Idee/Anregung?

Liebe Grüße
Carrotze

 

[Garm]

rufst du da eine methode aus sich selbst heraus auf?

 

[Carrotze]

Ja genau. Ich hab bereits eine rekursive Funktion zur Berechnung des Binominalkoeffizienten geschrieben die einwandfrei klappt, nur hier gehts nicht:/

 

[Gucky]

Sieht ganz so aus. Auch wenn die Formatierung (sorry) gresig ist. Bitte benutze nächstes Mal die Java-Tags.

Methoden aus sich selbst aufzurufen nennt sich "Rekursion" und ist zwar ein bisschen kompliziert aber dennoch ein gängiges Mittel, falls man keine Schleife nehmen will. Die Geschwindigkeit ist nahezu gleich aber der Speicherbedarf ist größer bei mehr Schritten, weshalb dann ein try catch Block sinnvoll wäre, um den StackOverflowError abzufangen.

Ich kriege im Kopf etwas über 45 raus.
Manchmal hilft es, sich das erst als Schleife aufzuzeichnen und diese dann in die Rekursion umwandeln.

 

[jemandzehage]

Moin,

Kein Plan wo du die Formel her hast, aber ich kann mich erinnern dass die rekursion des Binomialkoeffizienten anders aussieht. Wikipedia sagt das auch: Binomialkoeffizient ? Wikipedia
Vielleicht funktioniert es jetzt?

Grüße

 

[Carrotze]

Hey,
sorry für die späte Antwort und danke für die Antworten.:b
Sorry mit den JavaTags, ich werde es nächstes mal berücksichtigen.
Die Formel ist auf jeden Fall richtig.
Mit einer Schleife kriege ich es auch richtig hin, nur eben mit der Rekursion nicht.:/
Bei einer Schleife kann ich es mir auch leichter vorstellen, bei der Rekursion krieg ich es zwar im Kopf auch hin aber finde wie gesagt den Fehler nicht.

Liebe Grüße

Carrotze

 

[Gucky]

Rekursion kannst du dir wie eine Schleife vorstellen, in der der in- oder dekrementierte Zähler immer an die Methode weitergegeben wird. Hat der Zähler einen bestimmten Wert erreicht, so muss das gesondert behandelt werden. Brauchst du ein Beispiel einer funktionierenden und auch mehr oder weniger sinnvollen Rekursion?

 

[jemandzehage]

ups. ja die formel ist richtig. allerdings machts du integer-division von n/k. Das darf natürlich nicht sein. dann kriegst du für 5 über 2 = 2 * 4 * 1 = 8 anstatt 5 über 2 = 2.5 * 4 * 1 = 10.

Grüße

Edit: Achja, deine Rekursion ist irgendwie nicht soooo sinnvoll. Dann kannst du auch einfach den Binomialkoeffizienten nach der Ursprünglichen Formel auflösen. Deshalb ist es spannender die Rekursion von Wikipedia zu implementieren (ob das schneller ist oder nicht, weiß ich allerdings nicht).