studyklar
GdI 1 · Beispielklausur · Aufgabe 5

Binomialkoeffizient: von Hand, rekursiv in Java und die Klasse BinKoeff

Auf wie viele Arten kann man 2 von 4 Dingen auswählen? Das sagt der Binomialkoeffizient (4 über 2). In a) rechnen wir ihn mit der rekursiven Formel von Hand aus. In b) wird die Formel zur Java-Methode bin, die sich selbst aufruft. In c) liest ein Programm n und k ein, prüft sie und gibt das Ergebnis aus. Rechts steht in a) und b) der Baum der Rechnung, in c) das Ablaufdiagramm. Mit Weiter geht es Schritt für Schritt voran.

Die Aufgabe

Aufgabe 5

Der Binomialkoeffizient (nk)\binom{n}{k} (sprich: „n über k“) ist eine mathematische Funktion, die verwendet wird, um die Anzahl der Möglichkeiten zu bestimmen, k Objekte aus n Objekten auszuwählen. Er kann durch die rekursive Formel

(nk)={1,wenn k=0 oder k=n(n−1k−1)+(n−1k),wenn 0<k<n\binom{n}{k} = \begin{cases} 1, & \text{wenn } k = 0 \text{ oder } k = n \\[4pt] \binom{n-1}{k-1} + \binom{n-1}{k}, & \text{wenn } 0 < k < n \end{cases}

berechnet werden. Dabei muss k ≥ 0 und n ≥ k sein.

a) Berechnen Sie nachvollziehbar (42)\binom{4}{2}.

b) Schreiben Sie die rekursive Methode bin zur Berechnung des Binomialkoeffizienten (nk)\binom{n}{k} in Java so, dass sie aus der Main-Methode mittels

long b = bin(n, k);

aufgerufen werden kann!

c) Gegeben ist die noch unvollständige Klasse BinKoeff (siehe Lösungsblatt Seite 14), welche die beiden Zahlen n und k von der Tastatur liest, die gelesenen Zahlen auf Zulässigkeit prüft und – falls sie zulässig sind – die Methode bin aufruft. Die Ausgabe des Binomialkoeffizienten soll in der folgenden Form auf dem Bildschirm erscheinen:

(n über k) = Ergebnis

Darin sind „n“ und „k“ die eingegebenen Zahlenwerte und „Ergebnis“ der berechnete Binomialkoeffizient. Ergänzen Sie die fehlenden Codezeilen auf dem Lösungsblatt (Seite 14).

Hinweise: Die Klassen In und Out aus der Vorlesung/Übung werden als verfügbar vorausgesetzt.

Unser Gerüst für die Klasse BinKoeff (Lösungsblatt Seite 14 liegt nicht vor):

class BinKoeff {     // Methode bin aus b)     public static void main (String[ ] args) {        // n und k von der Tastatur lesen         // n und k prüfen; falls zulässig: bin aufrufen und        // das Ergebnis in der Form (n über k) = Ergebnis ausgeben     }}

Gegeben ist eine Formel, die auf sich selbst zurückgreift: Um (n über k) zu bekommen, braucht man zwei Binomialkoeffizienten mit kleinerem n. Eine solche Formel heißt rekursiv. Nur in zwei Fällen steht der Wert direkt da: wenn k = 0 oder k = n ist.

a) verlangt die Rechnung von Hand für n = 4 und k = 2. „Nachvollziehbar“ heißt: Jede Anwendung der Formel steht auf dem Papier, nicht nur das Ergebnis. b) verlangt eine Java-Methode, die genau zum Aufruf long b = bin(n, k); passt. c) verlangt die fehlenden Zeilen einer Klasse BinKoeff: einlesen, prüfen, aufrufen, ausgeben.

Klausur: Ohne Rechner und ohne Computer, alles von Hand. Punkte nennt die Beispielklausur für diese Aufgabe nicht. Es kommt an auf: die Zwischenschritte in a), den passenden Methodenkopf in b) und in c) die Prüfung von n und k sowie die Ausgabe genau in der verlangten Form.

Annahme: Die unvollständige Klasse BinKoeff („Lösungsblatt Seite 14“) liegt uns nicht vor. Wir legen deshalb selbst ein Gerüst fest (unten). Stehen auf dem echten Lösungsblatt schon einige Zeilen, fallen die entsprechenden Schritte weg.

Merke: Eine rekursive Rechnung braucht einen Basisfall, der den Wert direkt liefert, und einen Rekursionsfall, der die Aufgabe auf kleinere Aufgaben derselben Art zurückführt.
  1. a) Die Formel lesen.
  2. a) (4 über 2) in zwei Teile zerlegen.
  3. a) Den linken Teil (3 über 1) ausrechnen.
  4. a) Den rechten Teil (3 über 2) ausrechnen.
  5. a) Beide Teile zusammensetzen.
  6. b) Der Kopf der Methode bin.
  7. b) Der Basisfall.
  8. b) Der Rekursionsfall.
  9. b) Der Ablauf für bin(4, 2).
  10. c) Das Gerüst der Klasse BinKoeff.
  11. c) n und k einlesen.
  12. c) n und k prüfen.
  13. c) bin aufrufen.
  14. c) Das Ergebnis ausgeben.
  15. c) Unzulässige Eingabe melden.
  16. c) Das fertige Programm testen.

Die Formel lesen

oben der Basisfall, unten der Rekursionsfall
(nk)={1,wenn k=0 oder k=n(n−1k−1)+(n−1k),wenn 0<k<n\binom{n}{k} = \begin{cases} 1, & \text{wenn } k = 0 \text{ oder } k = n \\[4pt] \binom{n-1}{k-1} + \binom{n-1}{k}, & \text{wenn } 0 < k < n \end{cases}

Die Formel hat zwei Zeilen. Die erste ist der Basisfall: Ist k = 0 oder k = n, ist der Wert 1. Anschaulich: Keins oder alle von n Dingen auswählen geht auf genau eine Art.

Die zweite Zeile gilt, wenn k echt zwischen 0 und n liegt. Dann ist der Wert die Summe von zwei Binomialkoeffizienten, beide mit n − 1 oben. Einmal steht unten k − 1, einmal k. Weil n bei jeder Anwendung um 1 kleiner wird, landet man irgendwann bei einem Basisfall.

(4 über 2) in zwei Teile zerlegen

zweite Zeile der Formel mit n = 4 und k = 2
(42)=(4−12−1)+(4−12)=(31)+(32)\binom{4}{2} = \binom{4-1}{2-1} + \binom{4-1}{2} = \binom{3}{1} + \binom{3}{2}

Hier ist n = 4 und k = 2. k ist weder 0 noch 4, also gilt die zweite Zeile: 0 < 2 < 4. Eingesetzt wird n − 1 = 3, k − 1 = 1 und k = 2.

Beide Teile sind noch unbekannt. Wir rechnen sie nacheinander aus, erst den linken, dann den rechten.

Noch 15 Schritte bis zum Ergebnis
Den ganzen Lösungsweg sehen Studierende und Lehrende der HS KL. Registriere dich mit deiner Adresse @stud.hs-kl.de oder @hs-kl.de, dann geht es hier direkt weiter.
Registrieren

Abbildung 1a) (4 über 2) von Hand

die Formel so lange anwenden, bis nur Basisfälle übrig sind

4 über 2= ?
LegendeGesucht in a): der Wert von 4 über 2. „?“ heißt: noch nicht ausgerechnet.