BuK/IIm11/Studenten/sidatasc/ue2

Wiki-Quelltext dieser Seite.

==== Aufgabe 5 <tt>(Jens Heider, Daniel Tasche)</tt> ====

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}$$

# Schreiben Sie als erstes eine Scheme-Prozedur für $f$ und führen Sie einige rekursive Berechnungen aus.

<code>
(define f 
  (lambda (x) 
    (if (= x 1) 
      1
      (if (= (modulo x 2) 0) 
          (+ (f (/ x 2)) 1)
          (/ 1 (f (- x 1)))
      )
    )
  )
)

</code>



<run>(q 9)</run>

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