Blatt 3
Blatt 3
- 1.
- Das Hugs-System informiert bei entsprechender Einstellung (Kommando ":set +s") über den bei Auswertung eines Ausdrucks anfallenden Aufwand an Berechnungsschritten ("`reductions"') und Speicherplatz ("`cells"'). Eine genaue und vollständige Interpretation der gelieferten Zahlenwerte ist nicht ganz einfach; sie geben aber auch ohne detailliertes Verständnis der Arbeit der Haskell-Maschine eine brauchbare Vorstellung von der Effizienz von Funktionsdefinitionen etc. -- Informieren Sie sich über diese Option und probieren Sie sie anhand der fogenden Aufgaben und auch anderer Beispiele aus!
- 2.
- Die n-te Potenz einer Zahl k ist zu berechnen nach den beiden folgenden (in ihrer Effizienz sehr verschiedenen, vgl. Prog 1) Methoden:
- (a)
- wiederholtes Multiplizieren von k
- (b)
- wiederholtes Quadrieren (unter Halbieren des Exponenten).
Hinweis: Beim Testen verlässt man leicht den implementierten Zahlbereich, was zu einem falschen Ergebnis (ohne Fehlermeldung) führen kann; wenn Sie große Exponenten ausprobieren, sollten Sie deshalb die triviale Basis 1 verwenden. Dabei gibt es dann noch die Möglichkeit, daß das System die Menge der unfertigen rekursiven Aufrufe nicht mehr bewältigen kann. Welche Fehlermeldung ergibt sich dann?
- 3.
- Ein Geldbetrag b sei zu wechseln, d.h. in gebräuchlichen Münzeinheiten (gegeben in einer Liste [m1, m2, ..mn] von Zahlenwerten) darzustellen.
- (a)
- Definieren Sie eine Funktion, die Betrag und Münzwertliste als Parameter hat und eine Darstellung (in Form einer Liste mit Münzanzahlen) des Betrags mit möglichst wenig Münzen liefert. (Nehmen Sie an, daß die Münzwertliste absteigend sortiert sei.)
- (b)
- Definieren Sie eine Funktion, die Betrag und Münzwertliste als Parameter hat und die Zahl aller möglichen Darstellungen des Betrags errechnet. Verwenden sie dazu die offensichtliche (?) Rekursion:
Anzahl für b und Münzwertliste [m1, m2, ..mn] =
Anzahl für b und Münzwertliste [m2, ..mn] + Anzahl für b-m1 und Münzwertliste [m1, m2, ..mn].
Next:Blatt 4Up:ÜbungenPrevious:Blatt 2 Ronald Blaschke
1998-04-19