Programmieren II - Praktikum 2: Sudoku, Game of Live
2. Praktikum zum Programmieren II
Ablauf:
-
a) Bearbeiten Sie die Aufgaben in Teams zu zwei Personen. Sie erzeugen aber eine Lösung pro Team.
-
b) Achten Sie bei der Teamzusammenstellung darauf, dass Beide an der Lösung der Aufgabe tatsächlich arbeiten und sich gegenseitig kontrollieren und ergänzen.
Nicht gewünscht ist es, dass eine Person die Aufgabe(n) erledigt und die zweite Person wohlwollend aber passiv zuschaut. -
c) Zum vereinbarten Termin melden Sie sich im MS Teams an und besprechen Ihre Lösung mit dem Praktikumsleiter.
-
d) Wenn Sie eine Aufgabe ergänzen bzw. Wiederholen sollen, so besprechen Sie die „alte“ Aufgabe zuerst.
-
e) Beginnen Sie die Lösung so früh wie möglich, warten Sie nicht bis kurz vor Ultimo. Erstens ist der Lerneffekt dann nur gering und Sie können die Aufgabe auch nicht mit der nötigen Sorgfalt lösen. Gewöhnen Sie sich gar nicht erst an, Dinge zu verschieben.
-
f) Prüfen Sie vor Abgabe folgender Checkliste:
-
i) Jedes Programm ist kommentiert.
-
ii) Jede Datei enthält im Kopf einen Kommentar. Als Autor des Programmes führen Sie alle
Team-Mitglieder auf.
-
iii) Der Programmcode lässt sich übersetzen und zwar fehlerfrei und ohne Warnings. Prüfen
sie das mit dem Befehl „Projektmappe neu erstellen“.
-
iv) Sie haben das Programm ausprobiert und auch einmal im Debugger Schritt-für-Schritt
verfolgt?
-
v) Sie halten die Codierungsrichtlinien ein?
Einstimmung ins Thema
-
In diesem Praktikum soll vor allem der Anfang des Programmierens geübt werden:
-
Mehrdimensionale Arrays und Strings
-
Entwicklung von etwas komplexeren Algorithmen
1/4
Georg Westerkamp Programmieren II WS 2020/2021
Aufgabe 2.1 – Sudoku
Beim Sudoku-Spiel muss ein 9 × 9-Spielfeld so mit den Zahlen 1 bis 9 gefüllt werden, dass
-
a) in jeder Zeile jede Zahl genau einmal vorkommt,
-
b) in jeder Spalte jede Zahl genau einmal vorkommt und
-
c) in jedem 3 × 3-Block jede Zahl genau einmal vorkommt.
Ein Beispiel für ein korrekt gelöstes Sudoku ist dieses Feld:
638749251 795621348 241385679 364852917 987413562 152976483 516297834 879534126 423168795
-
(a) ProgrammierenSieeineFunktionmitdieserSignatur:
int ausgabe(int feld[9][9]);Die Funktion soll das Sudoku-Feld auf dem Bildschirm so ausgeben, dass man die Struktur des
Sudokus wiedererkennt.
-
(b) ProgrammierenSieeineFunktionmitdieserSignatur:
int istLoesung(int feld[9][9]);Die Funktion soll eine 1 zurückliefern, wenn das übergebene Feld eine korrekte Sudoku-Lösung darstellt. Andernfalls soll sie eine 0 zurückliefern.
Tipp: Es ist ausreichend, wenn Sie für eine Zeile (Spalte, Block) nur testen, ob jede Zahl mindes- tens einmal vorkommt. Wenn das nämlich für alle Zahlen 1 bis 9 der Fall ist, dann kann jede Zahl nur genau einmal vorgekommen sein.
Hinweis: Sie können Ihr Programm so erweitern, dass es den Inhalt des Sudoku-Feldes vom Benutzer abfragt oder Sie verwenden das o.a. Standardbeispiel.
Prüfen Sie Ihre Funktionen aber unbedingt mit „ungültigen“ Feldbelegungen.
Aufgabe 2.2 Game of Live.
Im Jahr 1968 wurde von J. H. Conway an der Universität Cambridge das ”game of life“ erfunden und
1970 von M. Gardner im Scientific American einem breiten Publikum vorgestellt.
Dabei handelt es sich um einen Algorithmus, der das Wachstum von fiktiven Lebewesen (Bakterien)
simuliert. Infolge der interessanten Muster, die dabei entstehen, ist das game of life weit über
Biologenkreise hinaus bekannt geworden. Es ist ein Beispiel für einen sogenannten zellulären
Automaten.
Schauplatz des game of life ist eine zweidimensionale Matrix aus Zellen, die entweder tot (’ ’) oder
lebendig (’X’) sind. Wie sich eine Zelle weiterentwickelt, hängt von ihren acht Nachbarn ab, und zwar
gelten folgende Regeln:
-
Eine lebende Zelle überlebt in der nächsten Generation, wenn sie zwei oder drei Nachbarn hat. Sind es weniger bzw. mehr, so stirbt sie an Vereinsamung bzw. Überbevölkerung.
-
Eine tote Zelle wird immer dann in der nächsten Generation zum Leben erweckt, wenn sie genau drei lebendige Nachbarn hat, ansonsten bleibt sie tot.
-
Als Nachbar zählen alle acht direkt oder diagonal benachbarten Felder.
Die Zeit verstreicht dabei in diskreten Schritten, d.h. jede Zelle verharrt in ihrem zuvor eingenommenen
Zustand, bis gewissermaßen bei einem Gongschlag alle gleichzeitig in den neuen Zustand übergehen.
Anders ausgedrückt:
Es wird für jede Zelle nachgeschaut, wie ihr Zustand und der ihrer Nachbarn zu einer bestimmten Zeit n
ist und berechnet, wie ihr Zustand zur nächsten Zeit n + 1 sein wird. Hat man dies für alle Zellen getan, so
werden alle gleichzeitig auf den neuen Zustand gesetzt.
-
(a) GestaltensiedasProgrammso,dassmanalsAusgangsmusterentwedereinsderfolgendenfünf auswählen kann, oder über die Angabe der Koordinaten (Zeile, Spalte) ein eigenes Ausgangs- muster lebendiger Zellen eingeben kann.
-
(b) WählensiefürdasgameoflifeeinFeldderGrösse:22Zeilenund78Spalten.ÜberdemFeld sollte die Nummer der aktuellen Generation angezeigt werden. Jede neue Generation soll auf dem Bildschirm ausgegeben werden, wobei die vorhergehende Generation immer durch die aktuelle überschreiben werden soll.
Mit folgendem Aufruf können Sie die den Inhalt der Konsole löschen. Verwenden Sie dazu den Header stdlib.h.
system("cls");
(c) DieEntwicklungsollfortlaufendangezeigtwerden.DasProgrammsollsolangelaufen,biseine
Taste gedrückt wird. Unter Verwendung der beiden Header Windows.h und conio.h lässt sich
dafür folgende Schleife nutzen:
(d) ErweiternSiedieAuswahlderAusgangsformationnunumdieGleiterkanone:
Die Gleiterkanone wurde 1970 entdeckt von R. W. Gosper, der damals Student am Massachusetts Insti- tut of Technologie (MIT) war, und sich unbedingt den 50-Dollar-Preis verdienen wollte, den Conway aus- gelobt hatte. Den Preis sollte der erhalten, der als erster beweisen würde, dass eine Ausgangsstellung unbegrenzt wachsen kann. Gospers Gleiterkanone spuckt jeweils nach 30 Zeitschritten einen neuen Glei- ter aus, wobei sie selbst in den Ausgangszustand zurückkehrt.
while (!_kbhit()) / Abbruch bei Tastendruck {
Sleep(1000); // Das Programm pausiert für x Millisekunden
... }
Quellen: Prof. Dr. S. Rohjans, „Praktikumsaufgaben für PR1 und 2, HAW Hamburg. 4/4
