ue2

Aus ProgrammingWiki

Übung 2

Aufgabe 5

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.

Lösung zu 1.:

(define f (lambda (n) (if (= n 1) 1 (if (= (modulo n 2) 0) (+ 1 (f (/ n 2))) (/ 1 (f (- n 1))) ) ) ) )

(f 6)

ausführen

Lösung zu 2.:

$f(1) = 1$

$f(2) = 2$

$f(3) = 0,5$

$f(4) = 3$

$f(5) = \frac{1}{3}$

$f(6) = 1,5$

$f(7) = \frac{2}{3}$

Lösung zu 3.:

(import hashtable) (define table (make-hashtable)) (define false (lambda () #f)) (define f-mem (lambda (n) (let ([resultat (hashtable/get table n false)]) (cond [(= n 1) 1] [(number? resultat) resultat] [else (let([res-berechnet (if (= (modulo n 2) 0) (+ 1 (f-mem (/ n 2))) (/ 1 (f-mem (- n 1))) )]) (hashtable/put! table n res-berechnet) res-berechnet ) ] ) ) ) )

(f-mem 999)

ausführen