BuK/IIm11/Studenten/sidatasc/ue2

Wiki-Quelltext dieser Seite.

<language>Scheme</language>
==== 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.
# 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'''
<code id="4f69d969d359a">
(define f 
  (lambda (x) 
    (if (= x 1) 
      1
      (if (= (modulo x 2) 0) 
          (+ (f (/ x 2)) 1)
          (/ 1 (f (- x 1)))
      )
    )
  )
)

</code>

<run id="4f69d969d3638">(f 9)</run>

''' 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'''

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

# 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.


'''Lösung zu 1.:'''
<code id="4f69d94623146">
(define f 
    (lambda (n) 
        (if (= n 1)
            1
            (if (= (modulo n 2) 0)
                (+ 1 (f (/ n 2)))
                (/ 1 (f (- n 1)))
            )
        )
    )
)
</code>
<run id="4f69d946231b0">(f 6)</run>

'''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.:'''
<code>
(define table (make-hash-table))
(define false (lambda () #f))
(define f-mem
    (lambda (n) 
        (let ([resultat (hash-table-ref 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)))
                    )])
                    (hash-table-set! table n res-berechnet)
                    res-berechnet
                  )
                ]
            )
        )
    )
)
</code>

<run>(f-mem 999)</run>