7.3.2: Stack (gb.data)

[tux_]

Uebungen zum Kapitel 7.3.2. (03.08.2014)

1. [212] Stellt man sich einen Stack als einen realen Stapel vor, so wuerde man den Punkt, an dem Push, Pop und Peek operieren, „oben am Stapel” nennen. Schreiben Sie drei analoge Funktion, die „unten am Stapel” operieren.
2. [400] Angenommen, Sie haetten ein Alphabet mit k Symbolen und jedem Symbol ist eine eindeutige Zahl aus 1..k zugewiesen. Diese Zuweisung induziert auf Ihrem Alphabet eine Sortierung der Symbole nach aufsteigendem Zahlwert (eine strikte Totalordnung). Nehmen Sie an, dass die Eingaben Ihrer IsPalindrome()-Funktion in diesem Sinne geordnete Zeichensequenzen sind. Was sind die einzigen Palindrome unter diesen Voraussetzungen? Durch welchen Einzeiler ersetzen Sie Ihre Funktion?
3. [220] Schreiben Sie die IsTPalindrome()-Funktion so um, dass sie mit Indizes über einem String arbeitet -- ohne Stacks. Diese Funktion wird speicherplatz- und zeitsparender sein.
4. [725] Erklaeren Sie, wie man jede rekursive Funktion unter Zuhilfenahme eines Stacks in eine iterative Funktion umwandeln kann. Nehmen Sie diese Umwandlung in drei Schritten am Beispiel der Fakultaetsfunktion fuer nicht-negative ganze Zahlen vor. Die Fakultaet ist dann definiert als mit .
   1. Schreiben Sie eine rekursive Funktion zur Berechnung der Fakultaet.
   2. Ersetzen Sie rekursive Aufrufe der Funktion (Argument-Uebergabe und Erhalt des Rueckgabewerts) durch Stack-Operationen.
   3. Aendern Sie das Vorgehen ggf. so, dass stets entweder 0 oder 1 Element im Stack ist. Verzichten Sie nun auf den Stack und benutzen Sie stattdessen eine Integer-Variable.
5. [764] Verfahren Sie analog zu (d) mit den Binomial-Koeffizienten und , wobei . Wieso ist die Adaption des letzten Schritts in o.a. Vorgehensweise schwierig? Recherchieren Sie zum Thema "Dynamische Programmierung".