1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
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>
|
