ue2

Aus ProgrammingWiki
< BuK < IIm11 < Studenten < sijeheid
Archivierte Version vom 2012-03-21T12:58:55+00:00. Aktuelle Version

Übung 2

Aufgabe 5 (Jens Heider, Daniel Tasche)

Verifizieren Sie, dass die folgende Funktion f:\N^+ \rightarrow \Q^+ eine bijektive Funktion ist und implementieren Sie eine Prozedur, die die zugehörige Umkehrfunktion f^{-1} berechnet.

f(n) = \begin{cases} 1, & \text{wenn } n=1;\\ f(\frac{n}{2})+1, & \text{wenn } n \text{ gerade};\\ \frac{1}{f(n-1)}, & \text{wenn } n \text{ ungerade}. \end{cases}
  1. Schreiben Sie als erstes eine Scheme-Prozedur für f und führen Sie einige rekursive Berechnungen aus.

Lösung:


  1. Berechnen Sie f(n) für n = 1,2,....,7 mit Hand.
  2. Verbessern Sie die Effizienz der Prozedur für f mittels memoizing.