Grundlagen der Programmkonstruktion SS 2013 Übungen

Wenn Sie zu einer freiwilligen Übungsgruppe angemeldet sind, lösen Sie die hier gestellten Aufgaben und kommen Sie mit diesen Lösungen in die Übungsgruppe, in die sie sich angemeldet haben.

Wenn Sie nicht in einer Ubungsgruppe sind, lösen Sie diese Aufgaben zur Vorbereitung auf den ersten Test.

Freiwillige Übung 1

Ausdrücke

Was ist das Ergebnis folgender Ausdrücke? Berechnen Sie das Ergebnis zuerst ohne Zuhilfenahme von Racket, und überprüfen Sie es dann mit Racket.

(+ (* 2 4) (- 4 6))
(* (+ 2 2) (/ (* (+ 3 5) (/ 30 10)) 2)))
(- 9)
(- 9 1 2)
(= (+ (* 9 9) (* 12 12)) (* 15 15))

Schreiben Sie folgende Ausdrücke in Racket und werten Sie sie durch Racket aus (* steht fuer die Multiplikation):

3+(4*5)
(3+4)*5
3+4*5*6+7-8

Funktionen

Gegeben sind die Funktionen

(define (f x)
   (- 2 x))

(define (g x)
   (* 3 (f (* x 2))))

Berechnen Sie das Ergebnis folgender Ausdrücke zuerst ohne Zuhilfenahme von Racket, und überprüfen Sie es dann mit Racket:

(f 5)
(g 3)
(g2 3)

Berechnen Sie, welches Ergebnis Aufrufe von f, g und g2 ergeben, wenn Sie die letzte Ziffer ihrer Matrikelnummer als Argument übergeben.

Schreiben Sie eine Funktion schilling-euro, die aus einem gegebenen Schilling-Wert die Menge an Euro berechnet (muss nicht auf zwei Nachkommastellen gerundet werden), und eine Funktion euro-schilling für die umgekehrte Berechnung.

Schreiben Sie eine Funktion (ringflaeche1 raussen rinnen), die die Fläche eines Rings mit dem Aussenradius raussen und dem Radius des freibleibenden Kreises rinnen berechnet. Schreiben Sie eine Funktion (ringflaeche2 radius breite), bei der die Masse des Rings durch einen Radius radius angegeben sind, um den herum auf beiden Seiten eine jeweils breite/2 breite Fläche bedeckt ist.

Bedingungen

Gegeben ist die Funktion

(define (foo x)
  (if (< x 2)
      (* x x)
      (+ x 3)))

Berechnen Sie das Ergebnis folgender Ausdrücke zuerst ohne Zuhilfenahme von Racket, und überprüfen Sie es dann mit Racket:

(foo 0)
(foo 1)
(foo 2)
(foo 3)

Schreiben Sie eine Funktion (myabs x), die den Absolutwert von x zurückgibt. Schreiben Sie eine Funktion (mysgn x), die für positive Werte 1, für negative Werte -1, und für 0 0 zurückgibt. Rufen sie dabei nicht abs oder sgn auf.

Rekursion

Gegeben ist die Funktion

(define (bar x y)
   (if (= x 0)
        0
        (+ x (* y (bar (- x 1) y)))))

Berechnen Sie das Ergebnis folgender Ausdrücke zuerst ohne Zuhilfenahme von Racket, und überprüfen Sie es dann mit Racket:

(bar 0 10)
(bar 1 10)
(bar 2 10)
(bar 3 10)

Schreiben Sie eine Funktion (fact n), die n!, also die Faktorielle von n berechnet. Schreiben Sie eine Funktion

(ggt a
b)

, die den größten gemeinsamen Teiler mit dem Euklidischen Algorithmus berechnet.

Freiwillige Übung 2

Aufrufbäume

Zeichnen Sie Aufrufbäume (mit Argumenten und Resultaten) für folgende Aufrufe der von Ihnen in der letzten Übung geschriebenen Funktionen:

(ringflaeche2 11 4)
(fact 5)
(ggt 42 18)
(ggt 18 42)

Gegeben ist die Funktion

(define (tarai x y z)
   (if (< y x)
       (tarai (tarai (- x 1) y z) (tarai (- y 1) z x) (tarai (- z 1) x y))
       y))

Zeichnen Sie den Aufrufbaum des Aufrufs (tarai 3 2 1).

Invarianten

Geben Sie Invarianten für die von Ihnen im Rahmen des ersten Übungsblatts geschriebenen Funktionen fact und ggt an.

Verschachtelte Funktionen

Schreiben Sie eine Variante von (fact n), die eine Hilfsfunktion (f i z) aufruft, wobei die Invariante gilt:

i! * z = n!

Schreiben Sie diese Variante von fact als verschachtelte Funktion.

Schreiben Sie eine andere Variante von fact, die eine verschachtelte Hilfsfunktion (g j z) aufruft, mit der Invariante:

z = j!

Funktionen höherer Ordnung

Betrachten Sie die Funktionen

(define (sum f n)
   (if (= n 0)
       0
       (+ (f n) (sum f (- n 1)))))

(define (prod f n)
   (if (= n 0)
       1
       (* (f n) (prod f (- n 1)))))

Definieren Sie fact als Aufruf von prod mit passenden Parametern. Definieren Sie hoch als Aufruf von prod mit passenden Parametern.

Definieren Sie eine Funktion acc, mit der man sum und prod nachbilden kann, indem man sie mit entsprechenden Parametern aufruft. Definieren Sie sumqu, fact, und hoch mit hilfe von acc.

Unbenannte Funktionen

Definieren Sie sum, fact, und hoch mit Hilfe von acc, aber ohne eine benannte Hilfsfunktion zu definieren.

Rückgabe von Funktionen

Schreiben sie cacc, eine gecurryte Version von acc. Definieren Sie sum, fact und hoch mit Hilfe von cacc, ohne in dieser Definition Parameter zu erwähnen. Dazu dürfen Sie allerdings benannte Hilfsfunktionen definieren, in denen Parameter vorkommen (ähnlich wie curry2 und swap bei der Definition von hochn).