FH Darmstadt 
FB Informatik 
Prof.Dr. H.P.Weber
Programmieren I 
Praktikum
5

Ziel: Sie sollen die Verwendung von Zeigern, Arrays, Funktionen und Rekursion üben sowie das Sortierverfahren Quicksort und einen Backtrackingalgorithmus realisieren. 

1    Verbesserter Misch- und Gebe-Algorithmus

  • Im Kartenmisch- und -gebeprogramm der Vorlesung wurde ein ineffizienter Mischalgorithmus verwendet, bei dem es nicht garantiert war, dass er in einer bestimmten Zeit abgeschlossen ist. Dieser Algorithmus soll verbessert werden.
  • Initialisieren Sie das deck Array wie folgt:
      0 1 2 3 4 5 6 7 8 9 10 11 12
    0 1 2 3 4 5 6 7 8 9 10 11 12 13
    1 14 15 16 17 18 19 20 21 22 23 24 25 26
    2 27 28 29 30 31 32 33 34 35 36 37 38 39
    3 40 41 42 43 44 45 46 47 48 49 50 51 52

  • Modifizieren Sie die shuffle Funktion so, dass sie Zeile für Zeile und Spalte für Spalte durch das Array läuft und jedes Element einmal bearbeitet: Jedes Element soll mit einem zufällig ausgewählten Element des Arrays vertauscht werden. Die shuffle Funktion soll so oft ausgeführt werden, bis das Blatt gut gemischt ist. Überprüfen Sie dies durch Ausdrucken des Arrays.
  • Optimieren Sie zusätzlich auch den Gebe-Algorithmus in der deal Funktion: Sobald eine Karte ausgegeben ist, soll nicht weiter nach der Nummer dieser Karte gesucht werden, sondern das Programm soll sofort mit dem Geben der nächsten Karte fortfahren.

2    Sortierverfahren 'Quicksort'

  • Das rekursive Sortierverfahren 'Quicksort' besteht aus zwei Schritten:
    • Partitionierungsschritt: Nimm das erste Element des unsortierten Arrays ('Partitionierungselement') und bestimme seine endgültige Position im sortierten Array (d.h. alle Werte links des Elementes sind kleiner und alle Werte rechts des Elementes sind größer). Ergebnis dieses Schrittes ist ein Element an der richtigen Position und zwei unsortierte Teilarrays.
    • Rekursionschritt: Führe den Partitionierungsschritt für jedes unsortierte Teilarray aus, solange, bis die Teilarrays nur noch aus einem Element bestehen.
  • Die Bestimmung der endgültigen Position des Partitionierungselementes im Partitionierungsschritt läuft folgendermaßen ab:
    • Beginnend beim letzten Element des Arrays wird das erste Element gesucht, das kleiner als das Partitionierungselement ist und dieses wird mit dem Partitionierungselement vertauscht:
      37 2 6 4 89 8 10 12 68 45
      führt also zu
      12 2 6 4 89 8 10 37 68 45
    • Nun wird von links aus (aber ohne das bereits behandelte Element 12) das erste Element gesucht, das größer als das Partitionierungselement ist und dieses wird mit dem Partitionierungselement vertauscht:
      12 2 6 4 37 8 10 89 68 45
    • Wieder von rechts, aber beginnend mit dem Element vor dem gerade behandelten Element 89 wird das erste Element gesucht, das kleiner als das Partitionierungselement ist und dieses wird mit dem Partitionierungselement vertauscht:
      12 2 6 4 10 8 37 89 68 45
    • Wieder von links, aber beginnend mit dem Element hinter dem gerade behandelten Element 10 wird das erste Element gesucht, das größer als das Partitionierungselement ist. Es wird keins mehr gefunden, so dass beim Vergleich von 37 mit sich selbst die endgültige Position von 37 fest steht.
  • Schreiben Sie eine rekursive Funktion quickSort, die ein Array mit 100 zufälligen int-Werten (aus dem Bereich von 1 bis 1000) sortiert. Die Funktion soll als Argumente das int-Array, einen Anfangsindex und einen Endindex erhalten. Eine Funktion partition soll von quickSort zur Durchführung des Partitionierungsschritts aufgerufen werden.

3    Labyrinth (Backtracking)

  • Folgendes Gitter aus Kreuzen(#), Leerstellen( ) und Punkten(.) stellt ein Labyrinth in Form eines doppelt indizierten Arrays dar:

    ..............
    .############.
    .#   #      #.
    .  # # #### #.
    .### #    # #.
    .     ### #  .
    .#### # # # #.
    .#  # # # # #.
    .## # # # # #.
    .#        # #.
    .###### ### #.
    .#      #   #.
    .######## ###.
    ..............

    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 char-Array 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'.

4    Geben und Beurteilen eines Pokerblatts (fakultativ)

  • Modifizieren Sie das Kartenmisch- und -gebeprogramm der Vorlesung, so dass ein Pokerblatt mit fünf Karten gegeben wird. Schreiben Sie zusätzliche Funktionen, die folgendes leisten:
    • Bestimmen, ob das Blatt 'One pair' (z.B. 2 Buben) enthält.
    • Bestimmen, ob das Blatt 'Two pair' enthält.
    • Bestimmen, ob das Blatt 'Three-of-a-kind' (z.B. 3 Damen) enthält.
    • Bestimmen, ob das Blatt 'Straight' (5 direkt aufeinander folgende Karten beliebiger Farbe) enthält.
    • Bestimmen, ob das Blatt 'Flush' (5 Karten der gleichen Farbe) enthält.
    • Bestimmen, ob das Blatt 'Full house' ('One pair' + 'Three of a kind') enthält. 
    • Bestimmen, ob das Blatt 'Four-of-a-kind' (z.B. 4 Asse) enthält.
    • Bestimmen, ob das Blatt 'Straight flush' (5 direkt aufeinander folgende Karten einer Farbe) enthält.
    • Bestimmen, ob das Blatt 'Royal flush' (Zehn, Bube, Dame, König, Ass in einer Farbe) enthält.
  • Wie oft erhalten Sie die angegebenen Pokerblätter von 'One pair' bis 'Royal flush', wenn Sie 1000 Blätter geben lassen? Wie oft, wenn Sie eine Million Blätter (oder mehr) geben lassen? Bestätigen Ihre Ergebnisse die Tatsache, dass die angegebenen neun Blätter von oben nach unten als zunehmend besser gewertet werden?
  • Anmerkung: Um realistischere Ergebnisse zu erhalten, können Sie die Aufgabe auch in der folgenden Variante bearbeiten ('Seven-card stud'): Der Spieler erhält sieben Karten, aus denen er sich sein Blatt mit fünf Karten zusammenstellt.