Praktikum 5

From 33613a85afc4b1481367fbe92a17ee59c240250b Mon Sep 17 00:00:00 2001 From: Sven Eisenhauer Date: Fri, 10 Nov 2023 15:11:48 +0100 Subject: add new repo --- Bachelor/Prog1/Prakt5/index.htm | 414 ++++++++++++++++++++++++++++++++++++++++ 1 file changed, 414 insertions(+) create mode 100644 Bachelor/Prog1/Prakt5/index.htm (limited to 'Bachelor/Prog1/Prakt5/index.htm') diff --git a/Bachelor/Prog1/Prakt5/index.htm b/Bachelor/Prog1/Prakt5/index.htm new file mode 100644 index 0000000..a96b249 --- /dev/null +++ b/Bachelor/Prog1/Prakt5/index.htm @@ -0,0 +1,414 @@ + + + + + + +Praktikum 5 + + + + + + + + + + + + + + + +


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.

+ + + \ No newline at end of file -- cgit v1.2.3