MINT lernen

Abituraufgaben: Rekursive Methoden entwerfen

Zwei Aufgaben im Abiturformat — vom Binärsystem bis zum Wechselgeld.

Dein Fortschritt:
0 / 0 Aufgaben
1

Zahlen im Binärsystem

AFB I–II

Ein Lernprogramm zeigt zu jeder eingegebenen Zahl ihre Binärdarstellung. Dazu wird die abgebildete Methode verwendet. In Java hängt + eine Zahl an eine Zeichenkette an, "" + n macht aus der Zahl n eine Zeichenkette.

Material: Methode binaer
static String binaer(int n) {
    if (n < 2) {
        return "" + n;
    }
    return binaer(n / 2) + (n % 2);
}
  1. Wenden Sie die Methode auf n = 13 an. Geben Sie alle Aufrufe und die jeweiligen Rückgabewerte an. 4 BE
  2. Erläutern Sie, warum der Selbstaufruf vor dem Anhängen von n % 2 stehen muss. Geben Sie an, was return (n % 2) + binaer(n / 2); für n = 13 liefern würde. 4 BE
  3. Entwerfen Sie eine rekursive Methode zurBasis(int n, int b), die die Darstellung von \(n \ge 0\) zur Basis \(b\) mit \(2 \le b \le 9\) liefert, z. B. zurBasis(100, 8) = "144". 4 BE
  4. Schätzen Sie ab, wie viele Aufrufe binaer(n) für \(n \ge 1\) benötigt, und begründen Sie Ihre Angabe. 3 BE

Insgesamt 15 BE

Hinweise

Hinweis zu Aufgabe a)
Notieren Sie die Aufrufe untereinander, bis n kleiner als 2 ist, und setzen Sie die Ergebnisse dann von unten nach oben zusammen.
Hinweis zu Aufgabe b)
Welche Binärziffer liefert n % 2 — die höchstwertige oder die niedrigstwertige?
Hinweis zu Aufgabe c)
Ersetzen Sie in binaer die 2 durch den Parameter b.
Hinweis zu Aufgabe d)
Wie oft kann man eine Zahl ganzzahlig halbieren, bis sie kleiner als 2 ist?

Erwartungshorizont

Erwartungshorizont zu Aufgabe a)

binaer(13) → binaer(6) → binaer(3) → binaer(1). Rückgaben: binaer(1) = "1", binaer(3) = "1" + 1 = "11", binaer(6) = "11" + 0 = "110", binaer(13) = "110" + 1 = "1101".

Erwartungshorizont zu Aufgabe b)

n % 2 ist die letzte (niedrigstwertige) Binärziffer; sie muss ganz rechts stehen. Der Selbstaufruf liefert die Darstellung aller vorderen Ziffern, deshalb wird zuerst er ausgewertet und die letzte Ziffer danach angehängt. Mit vertauschter Reihenfolge entstünde die Darstellung rückwärts: für 13 die Zeichenkette "1011".

Erwartungshorizont zu Aufgabe c)
static String zurBasis(int n, int b) {
    if (n < b) {
        return "" + n;
    }
    return zurBasis(n / b, b) + (n % b);
}

Test: zurBasis(100, 8): 100 = 1 · 64 + 4 · 8 + 4 → "144".

Erwartungshorizont zu Aufgabe d)

Jeder Aufruf halbiert n (ganzzahlig), bis n < 2 ist. Das geschieht nach \(\lfloor \log_2 n \rfloor\) Halbierungen; dazu kommt der letzte Aufruf. Also \(\lfloor \log_2 n \rfloor + 1\) Aufrufe — genau so viele, wie n Binärstellen hat, z. B. 4 Aufrufe für 13 = 1101₂.

2

Wechselgeld

AFB II–III

Ein Kassenautomat soll bestimmen, auf wie viele Arten sich ein Betrag in Cent mit Münzen bestimmter Werte zusammensetzen lässt; die Reihenfolge der Münzen spielt keine Rolle. Die Münzwerte stehen absteigend in der Reihung muenzen. Gestartet wird mit wechseln(betrag, muenzen, 0). Für den Betrag 5 und die Münzen {5, 2, 1} gibt es 4 Möglichkeiten: 5; 2 + 2 + 1; 2 + 1 + 1 + 1; 1 + 1 + 1 + 1 + 1.

Material: Methode wechseln
static int wechseln(int betrag, int[] muenzen, int k) {
    if (betrag == 0) {
        return 1;
    }
    if (betrag < 0 || k == muenzen.length) {
        return 0;
    }
    return wechseln(betrag - muenzen[k], muenzen, k)
         + wechseln(betrag, muenzen, k + 1);
}
  1. Erläutern Sie die Bedeutung der beiden Abbruchbedingungen und der beiden Selbstaufrufe im Sachzusammenhang. 4 BE
  2. Bestimmen Sie wechseln(4, {2, 1}, 0) mithilfe eines Aufrufbaums. 5 BE
  3. Begründen Sie, dass die Methode für jeden Betrag \(\ge 0\) und positive Münzwerte terminiert. 3 BE
  4. Erweitern Sie die Methode um einen Parameter m, sodass nur Zerlegungen mit höchstens m Münzen gezählt werden. 5 BE

Insgesamt 17 BE

Hinweise

Hinweis zu Aufgabe a)
Der erste Selbstaufruf verwendet Münze k, der zweite verzichtet endgültig auf sie. Was bedeutet Betrag 0 bzw. ein negativer Betrag?
Hinweis zu Aufgabe b)
Kürzen Sie ab: w(Betrag, k). Jeder Knoten hat zwei Kinder, bis eine Abbruchbedingung greift.
Hinweis zu Aufgabe c)
Betrachten Sie den Betrag und den Index k: Was passiert mit ihnen bei jedem der beiden Aufrufe?
Hinweis zu Aufgabe d)
Eine zusätzliche Abbruchbedingung und ein Parameter, der nur beim Verwenden einer Münze kleiner wird.

Erwartungshorizont

Erwartungshorizont zu Aufgabe a)

betrag == 0: Der Betrag ist genau bezahlt — eine gültige Möglichkeit (1). betrag < 0: Es wurde zu viel bezahlt; k == muenzen.length: Es sind keine Münzsorten mehr übrig — beides zählt nicht (0). Erster Selbstaufruf: Eine Münze der Sorte k wird verwendet, dieselbe Sorte darf danach noch einmal benutzt werden. Zweiter Selbstaufruf: Auf Sorte k wird ab jetzt verzichtet, es geht mit der nächsten Sorte weiter. Da jede Zerlegung eine Münze k entweder noch einmal enthält oder nicht, werden alle Möglichkeiten genau einmal gezählt.

Erwartungshorizont zu Aufgabe b)

Kurz w(Betrag, k) mit k = 0 für Münze 2, k = 1 für Münze 1:

w(4,0) = w(2,0) + w(4,1); w(2,0) = w(0,0) + w(2,1) = 1 + w(2,1); w(2,1) = w(1,1) + w(2,2) = w(0,1) + w(1,2) + 0 = 1 + 0 = 1; also w(2,0) = 2. w(4,1) = w(3,1) + w(4,2) = … = 1 (nur 1+1+1+1). Ergebnis 3: 2+2, 2+1+1, 1+1+1+1.

Erwartungshorizont zu Aufgabe c)

Bei jedem Selbstaufruf wird entweder der Betrag um einen positiven Münzwert kleiner (erster Aufruf) oder k um 1 größer (zweiter Aufruf). Der Betrag kann nur endlich oft sinken, bevor er 0 oder negativ wird; k kann nur bis muenzen.length steigen. Also erreicht jede Aufrufkette nach höchstens betrag + Anzahl der Münzsorten Schritten eine Abbruchbedingung.

Erwartungshorizont zu Aufgabe d)
static int wechseln(int betrag, int[] muenzen, int k, int m) {
    if (betrag == 0) {
        return 1;
    }
    if (betrag < 0 || k == muenzen.length || m == 0) {
        return 0;
    }
    return wechseln(betrag - muenzen[k], muenzen, k, m - 1)
         + wechseln(betrag, muenzen, k + 1, m);
}

betrag == 0 muss vor m == 0 geprüft werden: Wer mit der letzten erlaubten Münze genau bezahlt, hat eine gültige Möglichkeit. Test: wechseln(5, {5, 2, 1}, 0, 3) liefert 2 (5 und 2 + 2 + 1).