ue2

Aus ProgrammingWiki
< BuK < IIm11 < Studenten < sidatasc
Archivierte Version vom 2012-03-21T13:41:54+00:00. Aktuelle Version

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.
  2. Berechnen Sie f(n) für n = 1,2,....,7 mit Hand.
  3. Verbessern Sie die Effizienz der Prozedur für f mittels memoizing.

Aufgabe 1



 Aufgabe 2 
f(1) = 1
f(2) = 2
f(3) = \frac{1}{2}
f(4) = 3
f(5) = \frac{1}{3}
f(6) = \frac{3}{2}
f(7) = \frac{2}{3}