7.3.2: Stack (gb.data)

Aufgaben begleitend zum Buch

7.3.2: Stack (gb.data)

Beitragvon tux_ » So 3. Aug 2014, 14:10

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 n vor. Die Fakultaet ist dann definiert als n! \, := \, n \,*\,(n-1)! mit 0! \, := \, 1.
    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 {n \choose k} \, := \, {n-1 \choose k} \, + \, {n-1 \choose k-1} und {n \choose 0} \, := \, {n \choose n} \, := \, 0, wobei n, \, k \, \in \, \mathbb{Z}, \; 0 \, \le \, k \, \le \, n. Wieso ist die Adaption des letzten Schritts in o.a. Vorgehensweise schwierig? Recherchieren Sie zum Thema "Dynamische Programmierung".
Achtung: Es passiert, dass ich einen frisch geschrieben Beitrag innerhalb von 10 Minuten noch 3-4 Mal aendere!
tux_
Site Admin
 
Beiträge: 941
Registriert: Di 11. Nov 2008, 20:05

Zurück zu Aufgabensammlung

Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder und 1 Gast

cron