Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


5. Rekursion



Übungen

  1. Schreiben Sie ein rekursives Programm zum Zeichnen eines binären Baumes derart, daß die Wurzel in der Mitte der Seite erscheint, die Wurzel des linken Unterbaumes in der Mitte der linken Hälfte der Seite usw.
  2. Schreiben Sie ein rekursives Programm zur Berechnung der äußeren Weglänge eines binären Baumes.
  3. Schreiben Sie ein rekursives Programm zur Berechnung der äußeren Weglänge eines Baumes, der als binärer Baum dargestellt ist.
  4. Geben Sie die Koordinaten an, die erzeugt werden, wenn die im Text angegebene rekursive Prozedur zum Zeichnen eines Baumes auf den binären Baum in Abbildung 4.2 angewandt wird.
  5. Beseitigen Sie auf mechanischem Wege die Rekursion aus dem im Text angegebenen Programm fibonacci, so daß Sie eine nichtrekursive Implementation erhalten.
  6. Beseitigen Sie auf mechanischem Wege die Rekursion aus dem rekursiven Algorithmus für die Inorder-Traversierung eines Baumes, so daß Sie eine nichtrekursive Implementation erhalten.
  7. Beseitigen Sie auf mechanischem Wege die Rekursion aus dem rekursiven Algorithmus für die Postorder-Traversierung eines Baumes, so daß Sie eine nichtrekursive Implementation erhalten.
  8. Schreiben Sie ein rekursives Programm vom Typ »Teile und Herrsche« zum Zeichnen einer Approximation des Geradenabschnitts, welcher zwei Punkte (x1, y1) und (x2, y2) verbindet, durch Zeichnen von Punkten mit ganzzahligen Koordinaten. (Hinweis: Zeichen Sie zuerst einen Punkt in der Nähe der Mitte.)
  9. Schreiben Sie ein rekursives Programm zur Lösung des Problems des Josephus (siehe Kapitel 3).
  10. Schreiben Sie eine rekursive Implementation des Euklidischen Algorithmus (siehe Kapitel 1).


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]