 |
Didaktik der
Informatik |
 |
Projekttage zum Erwerb eines Scheins zur
Vorlesung Algorithmen, Daten und Programme II, SS 98
Programmierung elementarer Algorithmen
Aufgabe 4
"Stadtmauer"
In den letzten Jahre hat sich gezeigt, dass der Planet Erde2 doch nicht
unbewohnt war. Zum Schutz der Siedlungen sollen diese mit einer Stadtmauer
minimaler Länge umgeben werden.
Schreiben Sie Programme in ML, welche ausgehend von den ganzzahligen
Koordinaten der Mittelpunkte der Häuser die Reihenfolge der Häuser
bestimmt, die mittels Mauern verbunden die Stadtmauer bilden. Vergleichen
Sie die unterschiedlichen Algorithmen!
Beispiel für eine Siedlung:
|
x-Koordinate
|
y-Koordinate
|
Hausnr.
|
|
8
|
17
|
1
|
|
9
|
16
|
2
|
|
12
|
18
|
3
|
|
9
|
19
|
4
|
|
10
|
17
|
5
|
|
7
|
16
|
6
|
|
9
|
15
|
7
|
Stadtmauer: 3,4,6,7
Stichworte: Konvexe Hülle, Package-Wrapping, Divide&Conquer,
Graham-Scan, Interior Elimination
Literatur: Duden Informatik, Algorithmen-Sedgewick S. 411ff,
Mehlhorn Bd. 3 S. 79f
sowie: Turing-Omnibus S. 242
Ergebnisse der Projektgruppe
|
|
Benutzer: gast •
Besitzer: mthomas • Zuletzt geändert am:
|
|
|
