Übung 8

12. Januar 2004 (Abgabe 21. Januar 2004)

Aufgabe 1 (9 Punkte)

In einem Kiste sind n Geschenke von unterschiedlichem Wert. Sie dürfen ein Geschenk aus der Kiste nehmen und es entweder annehmen oder ablehnen. Wenn Sie es ablehnen dürfen Sie ein weiteres Geschenk aus der Kiste nehmen usw.. Wenn Sie ein Geschenk annehmen, ist das Spiel zu Ende. Die beste Strategie ist es, erst m Geschenke abzulehnen und sich den Wert des wertvollsten Geschenks dieser m Geschenke zu merken. Dann wählt man das erste Geschenk der letzten n-m Geschenke, das einen größeren Wert als das bisher beste Geschenk hat. Wenn dies nicht vorkommt, dann wählt man das letzte Geschenk aus.

Zur Vereinfachung sollen die Geschenke alle Werte von 1 bis n haben. Schreiben Sie ein Programm in Haskell, das zu gegebenen n und m den prozentualen Anteil der Permutationen ausgibt, mit denen man das optimale Geschenk bekommt.

Aufgabe 2 (7 Punkte)

Beschreiben Sie den Perfect Shuffle Algorithmus und implementieren Sie ihn in Haskell.

Aufgabe 3 (14 Punkte)

Geben Sie die primitiv-rekursive Definitionen der folgenden Funktionen an und implementieren Sie die Funktionen in dem in der Vorlesung vorgestellten Haskell-Framework.

1. x OR y
2. x≤y
3. x!
4. x mod y
5. x^y
6. x div y
7. f (0) = 0
   f (1) = 2
   f (2) = 5
   f (x) = 7