Praktikum 4

Programmieren 1
Praktikum
4
Prof.Dr.H.P.Weber
Ziel:
Sie sollen die Verwendung von arrays, Funktionen und Funktionstemplates üben sowie Sortierverfahren und einen
Backtrackingalgorithmus realisieren.
1
Analyse von Craps
Schreiben Sie ein Programm, das 1 000 000-mal das in der Vorlesung besprochene Würfelspiel Craps simuliert. Ihr
Programm soll folgende Fragen beantworten:





2
Wie viele Spiele werden gewonnen beim ersten Wurf, beim zweiten Wurf, ...(usw.)..., beim 20. Wurf und nach
dem 20.Wurf?
Wie viele Spiele werden verloren beim ersten Wurf, beim zweiten Wurf, ...(usw.)..., beim 20. Wurf und nach
dem 20.Wurf?
Wie groß sind die Chancen Craps zu gewinnen? (Sie sollten herausfinden, dass Craps eines der fairsten in
Spielkasinos gespielten Spiele ist. Was bedeutet diese Aussage?)
Wie lang dauert (d.h. aus wie vielen Würfen besteht) ein Craps-Spiel im Durchschnitt?
Erhöhen sich die Gewinnchancen mit der Dauer eines Craps-Spieles?
Sortierverfahren 'Direktes Vertauschen (Bubble-Sort)'
und 'Direkte Auswahl (Selection-Sort)'

Beim Sortierverfahren 'Direktes Vertauschen (Bubble-Sort)' finden für eine aufsteigende Sortierung eines Arrays mit n Elementen mehrere Durchläufe durch das Array statt. In jedem Durchlauf werden jeweils benachbarte Paare von Werten verglichen. Falls ein Paar die falsche Reihenfolge hat (der kleinere Wert ist weiter hinten), werden die beiden Werte innerhalb des Arrays vertauscht. Falls ein Paar schon die richtige Reihenfolge
hat, wird nichts gemacht. Da auf diese Weise ein kleiner Wert in jedem Durchlauf nur um eine Position nach
vorn wechseln kann, sind im ungünstigsten Fall (n-1) Durchläufe für eine vollständige Sortierung erforderlich.
Schreiben Sie ein Funktionstemplate bubbleSort, das ein array-Objekt mit Elementen vom Typ T als
Parameter übernimmt und den beschriebenen Algorithmus auf das Array anwendet, um es aufsteigend (d.h.
genauer gesagt: 'nicht absteigend': der auf einen Wert folgende Wert ist größer oder gleich) zu sortieren.

Das Sortierverfahren 'Direkte Auswahl (Selection-Sort)' durchsucht ein unsortiertes Array nach dem kleinsten
Element in dem Array. Danach wird das kleinste Element mit dem ersten Element des Arrays ausgetauscht.
Dieser Prozess wird für das unsortierte Teilarray, das mit dem zweiten Element des Arrays beginnt, wiederholt. Jeder derartige Durchlauf durch das Array bewirkt, dass ein weiteres Element an die Stelle kommt, an die
es gehört. Sobald das unsortierte Teilarray nur noch ein Element enthält, ist das Array sortiert. Im ungünstigsten Fall sind auch hier (n-1) Durchläufe erforderlich.
Schreiben Sie ein Funktionstemplate selectionSort, das ein array-Objekt mit Elementen vom Typ T
als Parameter übernimmt und diesen Algorithmus auf das Array anwendet, um es nicht absteigend zu sortieren.

Schreiben Sie außerdem ein Funktionstemplate lessEqualSorted, das ein array-Objekt mit Elementen
vom Typ T als Parameter übernimmt und true zurückgibt, falls das Array aufsteigend (d.h. 'nicht absteigend')
sortiert ist, false falls dies nicht der Fall ist.

Alternativ zur Verwendung des Typparameters T als Typ der Elemente eines array-Objektes können Sie als
Typparameter T bei allen beschriebenen Funktionstemplates auch den Containertyp verwenden, so dass Ihre
Funktionstemplates z.B. auch mit vector-Objekten arbeiten könnten.
Hinweis: Für den Typ der Elemente können Sie dann T::value_type oder einfach auto verwenden.

Testen Sie Ihre Sortierfunktionen, indem Sie ein mit zufälligen Werten gefülltes array< int, 100 > und
ein mit zufälligen Werten gefülltes array< string, 100 > sortieren und die Sortierergebnisse mit
lessEqualSorted überprüfen.
3
Labyrinth: Backtracking (fakultativ)
Nebenstehendes Gitter aus Kreuzen(#), Leerstellen( ) und Punkten(.) stellt ein Labyrinth in Form eines doppelt indizierten Arrays
dar (wahlweise array-Objekt oder C-Array).
In dem doppelt indizierten Array repräsentieren die Kreuze die
Mauern des Labyrinths, die Leerstellen die möglichen Wege durch
das Labyrinth und die Punkte die Welt außerhalb des Labyrinths.
Man kann also nur zu einem Ort im Array 'laufen', der eine Leerstelle enthält und man hat einen Ausgang gefunden, sobald man
auf einen Punkt trifft.
..............
.############.
.#
#
#.
. # # #### #.
.### #
# #.
.
### # .
.#### # # # #.
.# # # # # #.
.## # # # # #.
.#
# #.
.###### ### #.
.#
#
#.
.######## ###.
..............

Schreiben Sie eine rekursive Funktion mazeTraverse zum Durchlaufen des Labyrinths. Die Funktion soll als
Argumente ein 14mal14-Array mit Elementen vom Typ char für das Labyrinth und außerdem die Koordinaten
für einen Ort innerhalb des Labyrinths (beim ersten Aufruf der Eingang) übernehmen.
Während mazeTraverse versucht, den Ausgang aus dem Labyrinth zu finden, soll jede Leerstelle auf dem gelaufenen Weg durch ein x ersetzt werden. Die Funktion soll das Labyrinth bei jedem Schritt ausgeben, so dass
der Nutzer des Programms zusehen kann, wie das Labyrinth durchlaufen wird. Die Anzahl der gefundenen Ausgänge soll mitgezählt werden und jeder Ausgang mit seiner laufenden Nummer gekennzeichnet werden.

Hinweis: Von einem gegebenen Ort im Labyrinth kann man versuchen nach rechts, unten, links oder oben weiterzulaufen. Jeder dieser Versuche wird durch einen rekursiven Aufruf von mazeTraverse realisiert. Ist ein
Weiterlaufen möglich, folgt der nächste rekursive Aufruf. Wird hingegen ein Ort erreicht, von dem aus kein Weiterlaufen mehr möglich ist, wird eine Rekursionsstufe zurückgenommen. Dies hat den Effekt, dass von einem
früher erreichten Ort eine neue Möglichkeit des Weiterkommens ausprobiert wird. Einen solchen Algorithmus
bezeichnet man als 'Backtracking'.

Download Report