Übung AFB I

Die Methode aus dem Unterricht berechnet die Anzahl der Dosen einer Pyramide mit n Reihen:

static int dosen(int n) {
    if (n == 0) {
        return 0;
    }
    return n + dosen(n - 1);
}

Geben Sie den Wert von dosen(5) und die Anzahl aller Aufrufe von dosen an.

static long fakultaet(int n) {
    if (n <= 1) {
        return 1;
    }
    return n * fakultaet(n - 1);
}

Nennen Sie den Rückgabewert von fakultaet(5) und die Rekursionstiefe, also die größte Zahl gleichzeitig offener Aufrufe.

static int fib(int n) {
    if (n <= 1) {
        return n;
    }
    return fib(n - 1) + fib(n - 2);
}

Stellen Sie den Aufrufbaum von fib(5) dar und geben Sie den Rückgabewert sowie die Anzahl der Knoten (Aufrufe) an.

static int quersumme(int n) {
    if (n < 10) {
        return n;
    }
    return n % 10 + quersumme(n / 10);
}

Bestimmen Sie quersumme(90817) und die Anzahl der Aufrufe.

static int zaehle(String s, char c) {
    if (s.length() == 0) {
        return 0;
    }
    int rest = zaehle(s.substring(1), c);
    if (s.charAt(0) == c) {
        return 1 + rest;
    }
    return rest;
}

Wenden Sie die Methode auf zaehle("Banane", 'a') an. Geben Sie das Ergebnis und die Anzahl der Aufrufe an.

Die rekursive binäre Suche aus dem Unterricht wird auf die sortierte Reihung

static int binSuche(int[] a, int x, int links, int rechts) {
    if (links > rechts) {
        return -1;
    }
    int mitte = (links + rechts) / 2;
    if (a[mitte] == x) {
        return mitte;
    }
    if (a[mitte] < x) {
        return binSuche(a, x, mitte + 1, rechts);
    }
    return binSuche(a, x, links, mitte - 1);
}

mit dem Startaufruf binSuche(a, x, 0, 14) angewendet. Ermitteln Sie die Anzahl der Aufrufe für x = 58 und für x = 12.

Das rekursive Maximum maximum(a, links, rechts) aus 3.3.1 teilt jeden Bereich bei mitte in zwei Hälften. Berechnen Sie für eine Reihung mit 12 Elementen die Anzahl aller Aufrufe und die Anzahl der Vergleiche.

Beim Mergesort werden die sortierten Hälften 5, 14, 20 und 9, 11, 30 gemischt. Erstellen Sie die gemischte Folge und geben Sie die Anzahl der Vergleiche an.

Quicksort zerlegt {17, 42, 8, 31, 25} mit zerlege(a, 0, 4); das Pivot ist das letzte Element. Untersuchen Sie den Ablauf: Welchen Rückgabewert liefert zerlege, und welches Element steht danach an Index 4?

Vergleichen Sie für \(n = 512\) die Werte \(n\cdot\log_2 n\) (Mergesort) und \(\frac{n(n-1)}{2}\) (Selectionsort), indem Sie beide berechnen.