Binomialkoeffizient rekursiv berechnen

[khstgt]

bin gerade dabei zu versuchen ein programm zu schreiben, welches den binomialkoeffizient für zwei übergebene zahlen berechnet.


Fehlermeldung:
Exception in thread "main" java.lang.RuntimeException: Uncompilable source code - cannot find symbol
symbol: variable calculateBinomialCoefficient
location: class grundlagenuebungen.BinomialCoefficient

kann mirjemand sagen woran es liegt?

vielen Dank

 

[mmeyer1987]

Du hast die Klammern vergessen und die Parameter nicht übergeben. Probiers mal so:

package grundlagenuebungen;
 
import javax.swing.JOptionPane;
 
public class BinomialCoefficient {
 
    public static void main (String [] args){
 
  int n = Integer.parseInt (JOptionPane.showInputDialog ("Bitte geben Sie n ein: "));
  int k = Integer.parseInt (JOptionPane.showInputDialog ("Bitte geben sie k ein: "));
 
  JOptionPane.showMessageDialog (null, "Binomialkoeffizient " + calculateBinomialCoefficient(n,k));
 
    }
  public static int calculateBinomialCoefficient (int n, int k)
   {
      if (k == 1)
         return n;
      else if (n >= k && k == 0)
         return 1;
      else
         return (n * calculateBinomialCoefficient(n - 1, k - 1) / k);
 
   }
}

Wobei ich glaube, das das inhaltlich nicht stimmt. Wikipedia gibt folgenden Pseudocode:

binomialkoeffizient(n, k)
1 wenn k = 0 dann rückgabe 1
2 wenn 2k > n
3 dann führe aus ergebnis \leftarrow binomialkoeffizient(n, n-k)
4 sonst führe aus ergebnis \leftarrow n
5 von i \leftarrow 2 bis k
6 führe aus ergebnis \leftarrow ergebnis \cdot (n + 1 - i)
7 ergebnis \leftarrow ergebnis : i
8 rückgabe ergebnis

Quelle: Wikipedia

Gruß!

 

[bademaister]

Hallo,
ich hab einmal eine Frage und zwar:

(n * calculateBinomialCoefficient(n - 1, k - 1) / k)

Was macht diese Zeile genau? Ich versteh das irgendwie nicht.
Ich hoffe da kann mir jmd helfen ???:L

 

[SlaterB]

ein Methodenaufruf mit irgendwelchen Parametern und der Rückgabewert int wird noch weitergerechnet,
was kann man denn daran prinzipiell nicht verstehen?

warum man das so macht und der Gesamtablauf von zig Aufrufen zum richtigen Ergebnis führt,
ist dagegen schon etwas schwieriger, dazu muss man Rekursion kennen und eine Vorstellung für den Gesamtalgorithmus haben

 

[bademaister]

Ja, das ist mir shcon klar. Nur wie kann der mit dieser Zeile 6 aus 49 ausrechnen?
/e
Also wie man prinzipiell den Binomialkoeffezienten ausrechnet ist mir schon klar.
Ich würde dies allerdings mit Fakultäten machen.
Andere Programme die ich hier im forum gesehen habe sind mit einer for schleife geschrieben wurden und sind deutlich länger.
Kannst du mir vllt den ersten schritt nennen wie der das hier ausrechnet?

 

[eRaaaa]

Mit der Zeile alleine nicht. Das ist ja ein rekursiver Aufruf, d.h. die methode würde (in deinem Beispiel) sich 5 mal selber aufrufen, bzw Allgemein gesagt, bis irgendwann einer der beiden vorherigen if-Abfragen zutreffen, weil dann wird ja nicht noch mal rekursiv, sondenr direkt n oder 1 zurückgegeben.

In dem Pseudocode von oben (der von Wiki) könnte man 6 aus 49 auch ohne Rekursion berechnen, was Performance-mäßig daher irgendwie schöner ist 😀

 

[bademaister]

Rechnet er dann also folgendermaßen?
49*BC(48,5)/6.....->springe wieder hoch.
Im nächsten Schritt dann:
48*BC(47,4)/5....
47*BC(46,3)/4....
46*BC(45,2)/3....
45*BC(44,1)/2....
44*BC(43,2)/1....
und speichert die ergebnisse sodass zum schluss: (49/6)*(48/5)*(47/4)*(46/3)*(45/2)*(44/1) stehen bleibt?

 

[SlaterB]

was genau gerechnet wird, kannst du doch durch ein System.out.println() auf jeden einzelnen Schritt genau herausfinden,
evtl. temporär zusätzliche Variablen/ Parameter einfügen wie Runde/ Rekursionstiefe,

 

[eRaaaa]

Rechnet er dann also folgendermaßen?
49*BC(48,5)/6.....->springe wieder hoch.
Im nächsten Schritt dann:
48*BC(47,4)/5....
47*BC(46,3)/4....
46*BC(45,2)/3....
45*BC(44,1)/2....
44*BC(43,2)/1....
und speichert die ergebnisse sodass zum schluss: (49/6)*(48/5)*(47/4)*(46/3)*(45/2)*(44/1) stehen bleibt?

Nein nicht ganz. Bei k==1 ist ja Schluß! Da wird ja dann in dem Beispiel direkt n also 44 zurückgegeben, so dass du dann folgenden Term eig. stehen hast:

49*(48*(47*(46*(45*44/2)/3)/4)/5)/6