i

Aufwandsbetrachtung

Den Rechen- und Verwaltungsaufwand analysieren

Wir betrachten die rekursive Funktionsdefinition aus dem letzten Abschnitt zusammen mit einem Funktionsaufruf.

anzahlWege : Int -> Int -> Int
anzahlWege n k =
    if k == 0 || k == n then
        1

    else
        anzahlWege (n - 1) (k - 1) + anzahlWege (n - 1) k
> anzahlWege 5 2
10 : number

Wie wird ein solcher Funktionsaufruf ausgewertet? Die folgende Übersicht verdeutlicht die einzelnen Berechnungsschritte, die Elm bei dem vorgegebenen Funktionsaufruf ausführt.

anzahlWege 5 2 ->
anzahlWege 4 1 + anzahlWege 4 2 ->
(anzahlWege 3 0 + anzahlWege 3 1) + anzahlWege 4 2 ->
(1 + anzahlWege 3 1) + anzahlWege 4 2 ->
(1 + (anzahlWege 2 0 + anzahlWege 2 1)) + anzahlWege 4 2 ->
(1 + (1 + (anzahlWege 1 0 + anzahlWege 1 1))) + (anzahlWege 4 2) ->
(1 + (1 + (1 + 1))) + (anzahlWege 4 2) ->
...

Aufgabe 1

  1. Erkläre die angegebenen Berechnungsschritte.
  2. Ergänze die noch fehlenden Berechnungsschritte.
  3. Begründe, warum das Berechnungsverfahren ineffizient ist.
  4. Finde durch Experimente heraus, für welche Zahlen die Funktion schnell genug ist und bei welchen Zahlen die Funktion sehr langsam wird.

Aufgabe 2 (für Experten)

Die Verarbeitungsschritte kann man mit der folgenden Funktion nachvollziehen. Erkläre wie das Ergebnis zustande kommt und wie es mit den oben gezeigten Berechnungsschritten zusammenhängt.

wege : Int -> Int -> String -> String
wege n k aufrufe =
    let
        aufrufeNeu =
            aufrufe ++ "|" ++ String.fromInt n ++ String.fromInt k
    in
    if k == 0 || k == n then
        aufrufeNeu

    else
        wege (n - 1) (k - 1) aufrufeNeu ++ wege (n - 1) k aufrufeNeu
> wege 5 2 ""
"|52|41|30|52|41|31|20|52|41|31|21|10|52|41|31|21|11|52|42|31|20|52|42|31|21|10|52|42|31|21|11|52|42|32|21|10|52|42|32|21|11|52|42|32|22" : String

Suche

v
8.2.2.10.4.1.4
inf-schule.de/deklarativ/fp_elm/elm_programme/rekursion/galton/lernstrecke/aufwand
inf-schule.de/8.2.2.10.4.1.4
inf-schule.de/@/page/1CvpAginLDHmoxLZ

Rückmeldung geben