Transcript
Prof. Dr. Manfred Schmidt-Schauß K¨ unstliche Intelligenz/Softwaretechnologie
Fachbereich Informatik und Mathematik/ Institut f¨ ur Informatik Goethe-Universit¨ at Frankfurt am Main
Grundlagen der Programmierung 2 Sommersemester 2016
Aufgabenblatt Nr. 4 Abgabe: Mittwoch 11. Mai 2016 vor! der Vorlesung
Aufgabe 1 (20 Punkte) Berechnen Sie (Rechenweg erforderlich!) jeweils die Menge der freien sowie die Menge der gebundenen Variablen f¨ ur die folgenden Ausdr¨ ucke: a) \z -> z (y 5) (y (let y = 2 in y))
(10 Punkte)
b) x (\w -> w) (let f a b = a in f)
(10 Punkte)
Aufgabe 2 (50 Punkte) Geben Sie jeweils List Comprehensions in Haskell an, welche die folgenden Listen erzeugen. a) Die unendliche Liste aller Zahlen n (n ∈ N>0 ), die gerade sind, geteilt durch 7 den Rest 2 ergeben und durch 5 ohne Rest teilbar sind, d.h. [30,100,170,240,310,380,450,520,590,660,... Die Funktion take kann beim Testen n¨ utzlich sein.
(5 Punkte)
b) Die unendliche Liste aller Zahlen der Form 3 · x2 · y mit x ∈ {2, 4, 6, . . . }, y ∈ {1, 3, 5, . . . } und x + y > 10, d.h. [108,132,156,180,204,228,252,276,300,324,... (6 Punkte) c) Zu einer gegebenen endlichen Liste [e1 , e2 , . . . , en ] die Liste der Teillisten von folgender Form: [[e1 ],[e1 , e2 ], . . .,[e1 ,. . .,en ]]. D.h. f¨ ur [’a’,’b’,’c’] ist die Ergebnisliste ["a","ab","abc"]. (7 Punkte) d) Die unendliche Liste aller Primzahlen. Zur Pr¨ ufung, ob eine Zahl n > 1 eine Primzahl ist, reicht es vollkommen aus, zu pr¨ ufen, ob es ein k mit 2 ≤ k ≤ n − 2 gibt, das n teilt: Gibt es kein solches k, so ist n prim. (11 Punkte) e) Die endliche Liste aller Tripel (x, y, z) f¨ ur alle x ∈ {’a’,’b’,’c’,’d’,’e’}, y ∈ {0, 5, 10, 15, 20} und z ∈ {True, False} und zwar in der Reihenfolge, sodass zun¨achst die Zahlen wechseln, danach die Wahrheitswerte und zuletzt die Buchstaben, d.h. die Ausgabe beginnt mit: [(’a’,0,True),(’a’,5,True),(’a’,10,True),(’a’,15,True),(’a’,20,True),(’a’,0,False), (’a’,5,False),(’a’,10,False),(’a’,15,False),(’a’,20,False),(’b’,0,True),(’b’,5,True)... (8 Punkte)
f) Die unendliche Liste aller Paare (a, b) von nat¨ urlichen Zahlen a und b, wobei a durch drei teilbar ist und b eine Quadratzahl ist. Hierbei sollen die Paare in einer fairen Reihenfolge generiert werden. Fair bedeutet: Jedes Element wird in endlicher Zeit generiert, oder auch: Wenn xs die Liste der Paare ist, dann terminiert (a,b) ‘elem‘ xs f¨ ur alle Zahlen a, b mit a ist durch drei teilbar und b ist eine Quadratzahl. (13 Punkte) 1
Aufgabe 3 (30 Punkte) Ein Berg sei durch die folgenden Attribute repr¨asentiert • • • •
Name als Zeichenkette H¨ohe in Metern u ¨ber Normalnull Dominanz in Kilometern Prominenz (auch bekannt als Schartenh¨ohe) in Metern
In Haskell sei ein Berg dementsprechend durch den folgenden Datentyp Berg1 und die Typsynonyme Name, Hoehe, Dominanz und Prominenz dargestellt: data Berg = Berg Name Hoehe Dominanz Prominenz deriving(Eq,Show) type Name = String type Hoehe = Float type Dominanz = Float type Prominenz = Float Außerdem sei ein Gebirge in Haskell durch den folgenden Datentyp Gebirge repr¨asentiert: data Gebirge = Gebirge Name [Berg] deriving(Eq,Show) a) Geben Sie ein Gebirge Ihrer Wahl unter Verwendung der Datentypen Berg und Gebirge an. Dabei gen¨ ugt es nur drei Berge zu ber¨ ucksichtigen. (5 Punkte) b) Implementieren Sie Zugriffsfunktionen – getName :: Berg -> Name – getHoehe :: Berg -> Hoehe – getDominanz :: Berg -> Dominanz – getProminenz :: Berg -> Prominenz die f¨ ur einen Berg dessen Name, H¨ ohe, Dominanz und Prominenz extrahieren.
(6 Punkte)
c) Implementieren Sie in Haskell eine Funktion maxHoehe :: Gebirge -> Hoehe, welche die H¨ ohe des h¨ochsten Berges eines Gebirges berechnet. (9 Punkte) d) Implementieren Sie in Haskell eine Funktion hoechsterBerg :: Gebirge -> Name, die den Namen des h¨ ochsten Berges eines Gebirges berechnet. (10 Punkte)
1
Die Zeile deriving(Eq,Show) f¨ uhrt dabei dazu, dass Objekte des entsprechenden Datentyps angezeigt und verglichen werden k¨ onnen.
2
