ue2

Aus ProgrammingWiki

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.

Umkehrfunktion:

f^{-1}(n) = \begin{cases}1, & n = 1 \\ f^{-1}(n-1) * 2, & n > 1 \\ f^{-1}(\frac{1}{n}) + 1, & sonst\end{cases}

(define f-umkehr 
    (lambda (n) 
        (if (= n 1)
            1
            (if (> n 1)
                (* 2 (f-umkehr (- n 1)))
                (+ 1 (f-umkehr (/ 1 n)))
            )
        )
    )
)

(f-umkehr (/ 3 2))

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

Aufgabe 1

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

(f 9)

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}

Aufgabe 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 6)

ue2

Aufgabe 5 (Jens Heider, Daniel Tasche)

Suche

Aufgabe 5 `(Jens Heider, Daniel Tasche)`