diff options
Diffstat (limited to 'Bachelor/Prog1/Prakt5/index.htm')
| -rw-r--r-- | Bachelor/Prog1/Prakt5/index.htm | 414 |
1 files changed, 414 insertions, 0 deletions
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 @@ +<html>
+
+<head>
+<meta http-equiv="Content-Type" content="text/html; charset=windows-1252">
+<meta name="GENERATOR" content="Microsoft FrontPage 4.0">
+<meta name="ProgId" content="FrontPage.Editor.Document">
+<title>Praktikum 5</title>
+</head>
+
+<body>
+
+
+<table BORDER CELLSPACING=0 WIDTH="100%" >
+<caption> </caption>
+
+<tr>
+<td WIDTH="25%" BGCOLOR="#EFEFDE">FH Darmstadt
+<br>FB Informatik
+<br>Prof.Dr. H.P.Weber</td>
+
+<td>
+<center><font size="+3">Programmieren I </font>
+<br><font size=+3>Praktikum</font></center>
+</td>
+
+<td WIDTH="25%" BGCOLOR="#EFEFDE">
+<center><font size=+4>5</font></center>
+</td>
+</tr>
+</table>
+
+<br>
+<table border WIDTH="100%" >
+<tr VALIGN=TOP>
+<td>Ziel:</td><td>
+ Sie sollen die Verwendung von Zeigern, Arrays, Funktionen und Rekursion üben
+ sowie das Sortierverfahren Quicksort und einen Backtrackingalgorithmus
+ realisieren.
+</td>
+</tr>
+</table>
+
+<br>
+<table BORDER CELLSPACING=0 WIDTH="100%" >
+<tr>
+<td>
+<h3>
+<b>1 Verbesserter Misch- und Gebe-Algorithmus</b></h3>
+<ul>
+<li>
+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.</li>
+
+<li>
+Initialisieren Sie das <font face="Courier New"><b> deck</b></font> Array wie folgt:
+<table border="1">
+ <tr>
+ <td> </td>
+ <td><i>0</i></td>
+ <td><i>1</i></td>
+ <td><i>2</i></td>
+ <td><i>3</i></td>
+ <td><i>4</i></td>
+ <td><i>5</i></td>
+ <td><i>6</i></td>
+ <td><i>7</i></td>
+ <td><i>8</i></td>
+ <td><i>9</i></td>
+ <td><i>10</i></td>
+ <td><i>11</i></td>
+ <td><i>12</i></td>
+ </tr>
+ <tr>
+ <td><i>0</i></td>
+ <td><b>1</b></td>
+ <td><b>2</b></td>
+ <td><b>3</b></td>
+ <td><b>4</b></td>
+ <td><b>5</b></td>
+ <td><b>6</b></td>
+ <td><b>7</b></td>
+ <td><b>8</b></td>
+ <td><b>9</b></td>
+ <td><b>10</b></td>
+ <td><b>11</b></td>
+ <td><b>12</b></td>
+ <td><b>13</b></td>
+ </tr>
+ <tr>
+ <td><i>1</i></td>
+ <td><b>14</b></td>
+ <td><b>15</b></td>
+ <td><b>16</b></td>
+ <td><b>17</b></td>
+ <td><b>18</b></td>
+ <td><b>19</b></td>
+ <td><b>20</b></td>
+ <td><b>21</b></td>
+ <td><b>22</b></td>
+ <td><b>23</b></td>
+ <td><b>24</b></td>
+ <td><b>25</b></td>
+ <td><b>26</b></td>
+ </tr>
+ <tr>
+ <td><i>2</i></td>
+ <td><b>27</b></td>
+ <td><b>28</b></td>
+ <td><b>29</b></td>
+ <td><b>30</b></td>
+ <td><b>31</b></td>
+ <td><b>32</b></td>
+ <td><b>33</b></td>
+ <td><b>34</b></td>
+ <td><b>35</b></td>
+ <td><b>36</b></td>
+ <td><b>37</b></td>
+ <td><b>38</b></td>
+ <td><b>39</b></td>
+ </tr>
+ <tr>
+ <td><i>3</i></td>
+ <td><b>40</b></td>
+ <td><b>41</b></td>
+ <td><b>42</b></td>
+ <td><b>43</b></td>
+ <td><b>44</b></td>
+ <td><b>45</b></td>
+ <td><b>46</b></td>
+ <td><b>47</b></td>
+ <td><b>48</b></td>
+ <td><b>49</b></td>
+ <td><b>50</b></td>
+ <td><b>51</b></td>
+ <td><b>52</b></td>
+ </tr>
+</table>
+<br>
+</li>
+
+<li>
+Modifizieren Sie die <font face="Courier New"><b>shuffle</b></font> 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 <font face="Courier New"><b>shuffle</b></font>
+Funktion soll so oft ausgeführt werden, bis das Blatt gut gemischt ist.
+Überprüfen Sie dies durch Ausdrucken des Arrays.</li>
+
+<li>
+Optimieren Sie zusätzlich auch den Gebe-Algorithmus in der <font face="Courier New"><b>deal</b></font>
+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.</li>
+
+</ul>
+
+</td>
+</tr>
+</table>
+
+<br>
+<table BORDER="1" CELLSPACING=0 WIDTH="100%" >
+<tr>
+<td>
+<h3>
+<b>2 Sortierverfahren 'Quicksort'</b></h3>
+
+<ul>
+<li>
+Das rekursive Sortierverfahren 'Quicksort' besteht aus zwei Schritten:
+<ul>
+<li>
+<b>
+Partitionierungsschritt:</b> 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.
+</li>
+
+<li>
+<b>Rekursionschritt:</b> Führe den Partitionierungsschritt für jedes
+unsortierte Teilarray aus, solange, bis die Teilarrays nur noch aus einem
+Element bestehen.</li>
+
+</ul>
+<li>Die Bestimmung der endgültigen Position des Partitionierungselementes im
+ Partitionierungsschritt läuft folgendermaßen ab:
+<ul>
+<li>
+
+Beginnend beim letzten Element des Arrays wird das erste Element gesucht, das
+kleiner als das Partitionierungselement ist und dieses wird mit dem
+Partitionierungselement vertauscht:
+<table border="1">
+ <tr>
+ <td><b>37</b></td>
+ <td>2</td>
+ <td>6</td>
+ <td>4</td>
+ <td>89</td>
+ <td>8</td>
+ <td>10</td>
+ <td><i>12</i></td>
+ <td>68</td>
+ <td>45</td>
+ </tr>
+</table>
+führt also zu
+<table border="1">
+ <tr>
+ <td><i>12</i></td>
+ <td>2</td>
+ <td>6</td>
+ <td>4</td>
+ <td>89</td>
+ <td>8</td>
+ <td>10</td>
+ <td><b>37</b></td>
+ <td>68</td>
+ <td>45</td>
+ </tr>
+</table>
+
+</li>
+<li>
+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:
+<table border="1">
+ <tr>
+ <td>12</td>
+ <td>2</td>
+ <td>6</td>
+ <td>4</td>
+ <td><b>37</b></td>
+ <td>8</td>
+ <td>10</td>
+ <td><i>89</i></td>
+ <td>68</td>
+ <td>45</td>
+ </tr>
+</table>
+</li>
+<li>
+
+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:
+<table border="1">
+ <tr>
+ <td>12</td>
+ <td>2</td>
+ <td>6</td>
+ <td>4</td>
+ <td><i>10</i></td>
+ <td>8</td>
+ <td><b>37</b></td>
+ <td><i>89</i></td>
+ <td>68</td>
+ <td>45</td>
+ </tr>
+</table>
+</li>
+<li>
+
+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 <b>37</b> mit sich selbst die
+endgültige Position von <b>37</b> fest steht.
+
+</ul>
+<li>Schreiben Sie eine rekursive Funktion <font face="Courier New"><b>quickSort</b></font>,
+ 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 <font face="Courier New"><b>partition</b></font>
+ soll von <b><font face="Courier New">quickSort</font> </b>zur Durchführung
+ des
+ Partitionierungsschritts aufgerufen werden.</li>
+</ul>
+</td>
+</tr>
+</table>
+
+<br>
+<table BORDER CELLSPACING=0 WIDTH="100%" >
+<tr>
+<td>
+<h3>
+3<b> Labyrinth (Backtracking)</b></h3>
+<ul>
+
+<li>
+Folgendes Gitter aus Kreuzen(<font face="Courier New"><b>#</b></font>),
+Leerstellen(<font face="Courier New"><b> </b></font>) und Punkten(<font face="Courier New"><b>.</b></font>) stellt ein Labyrinth in Form eines
+doppelt indizierten Arrays dar:
+<br>
+<br>
+<font face="Courier New"><b>..............<br>
+.############.<br>
+.# # #.<br>
+. # # #### #.<br>
+.### # # #.<br>
+. ### # .<br>
+.#### # # # #.<br>
+.# # # # # #.<br>
+.## # # # # #.<br>
+.# # #.<br>
+.###### ### #.<br>
+.# # #.<br>
+.######## ###.<br>
+..............</b></font>
+<br>
+<br>
+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.
+</li>
+
+<li>
+Schreiben Sie eine rekursive Funktion <font face="Courier New"><b>mazeTraverse</b></font>
+zum Durchlaufen des Labyrinths. Die Funktion soll als Argumente ein 14mal14 <b>
+<font face="Courier New">ch</font></b><font face="Courier New"><b>ar</b></font>-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 <font face="Courier New"><b>
+mazeTraverse</b></font> versucht, den Ausgang aus dem Labyrinth zu finden, soll
+jede Leerstelle auf dem gelaufenen Weg durch ein <font face="Courier New"><b>x</b></font>
+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.</li>
+
+<li>
+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 <font face="Courier New"><b>
+mazeTraverse</b></font> 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'.</li>
+
+</ul>
+
+</td>
+</tr>
+</table>
+
+<br>
+
+<table BORDER CELLSPACING=0 WIDTH="100%" >
+<tr>
+<td>
+<h3>4<b> Geben und Beurteilen eines Pokerblatts </b>
+ <b>(fakultativ)</b>
+</h3>
+
+<ul>
+<li>
+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:
+<ul>
+
+<li>Bestimmen, ob das Blatt 'One pair' (z.B. 2 Buben) enthält.</li>
+<li>Bestimmen, ob das Blatt 'Two pair' enthält.</li>
+
+<li>
+Bestimmen, ob das Blatt 'Three-of-a-kind' (z.B. 3 Damen) enthält.</li>
+
+<li>
+Bestimmen, ob das Blatt 'Straight' (5 direkt aufeinander folgende Karten
+beliebiger Farbe)
+enthält.</li>
+
+<li>
+Bestimmen, ob das Blatt 'Flush' (5 Karten der gleichen Farbe) enthält.</li>
+
+<li>
+Bestimmen, ob das Blatt 'Full house' ('One pair' + 'Three of a kind') enthält. </li>
+
+<li>
+Bestimmen, ob das Blatt 'Four-of-a-kind' (z.B. 4 Asse) enthält.</li>
+
+<li>
+Bestimmen, ob das Blatt 'Straight flush' (5 direkt aufeinander folgende Karten
+einer Farbe)
+enthält.</li>
+
+<li>
+Bestimmen, ob das Blatt 'Royal flush' (Zehn, Bube, Dame, König, Ass in einer
+Farbe)
+enthält.</li>
+</ul>
+<li>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?</li>
+<li>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.</li>
+</td>
+</tr>
+</table>
+
+</body>
+</html>
\ No newline at end of file |