Harvard CS50: Aufgaben der Woche 3 (Vorlesungen 7 und 8), Teil 2

Harvard Programming Fundamentals Lectures CS50 Zusätzliche Materialien: Asymptotische Notation, Sortier- und Suchalgorithmen. Aufgaben für Woche 3, Teil 1. Sortieren und Suchen.

Das Spiel beginnt!

Es ist Zeit zu spielen! Die meisten Menschen kennen das Puzzlespiel „Tag“. Um es formal auszudrücken: „Tag“ ist ein zweidimensionales 4x4-Feld, in diesem Feld gibt es nicht 16, sondern 15 Quadrate, das heißt, ein Feld bleibt leer. Jedes der Quadrate ist nummeriert und kann sich innerhalb des Feldes horizontal oder vertikal bewegen (sofern natürlich Platz zum Bewegen vorhanden ist). Das Ziel besteht darin, die Zahlen in der Reihenfolge von 1 bis 15 von links nach rechts und von oben nach unten anzuordnen. Dann befindet sich der leere Raum in der unteren rechten Ecke. Die Bewegung eines beliebigen Plättchens (oder mehrerer) ist in diesem Spielfeld ein „Schritt“. Die im Bild oben gezeigte Kombination ist bereits gestapelt. Beachten Sie jedoch, dass 12 oder 15 Spielsteine ​​in den leeren Raum geschoben werden können. Die Regeln besagen, dass ein Spielstein nicht diagonal verschoben oder vom Spielbrett entfernt werden darf. Es gibt tatsächlich viele Konfigurationen, um das Spiel zu starten (Sie können genau zählen, wie viele), aber der Einfachheit halber ordnen wir die Kacheln in der Reihenfolge vom größten zum kleinsten an und lassen einen leeren Platz in der unteren rechten Ecke des Spielbretts . Das Einzige ist, lasst uns 1 und 2 vertauschen, damit das Rätsel lösbar ist. Gehen Sie nun in das ~/ -Verzeichnis Ihrer Workbench , dann /pset3/fifteen und öffnen Sie twenty.c . Es enthält den Code für die Spiel-Engine. Die Aufgabe besteht darin, dem Spiel Code hinzuzufügen. Aber zuerst kompilieren wir unsere „Engine“ (Sie wissen wahrscheinlich bereits, wie das geht). Auch wenn das Spiel noch nicht fertig ist, können Sie die Anwendung starten. Bequemer ist es, es in einem größeren Terminalfenster als üblich auszuführen, das Sie öffnen können, indem Sie auf das grüne Pluszeichen (+) neben einer der Code-Registerkarten klicken und „ Neues Terminal“ auswählen . Oder Sie können das Terminalfenster im Vollbildmodus öffnen, indem Sie auf das Symbol „Maximieren“ in der oberen rechten Ecke der Konsole klicken. Man sieht, dass manche Dinge irgendwie funktionieren. Tatsächlich ist der Großteil des Spiels jedoch noch nicht geschrieben. Und hier – machen Sie sich bereit – ist Ihr Ausgang!

Studie

Studieren Sie den Code und die Kommentare von twenty.c und beantworten Sie dann die folgenden Fragen:

1. Welche Feldgröße erlaubt unser Motor, abgesehen von einem 4x4-Board?
2. Welche Datenstruktur hat das Spielfeld?
3. Welche Funktion wird aufgerufen, um den Spieler zu Beginn des Spiels zu begrüßen?
4. Welche Funktionen müssen Sie implementieren?
5. Hinweis: Wenn Sie eine automatische Überprüfung wünschen, die Ihnen mitteilt, ob Sie die Fragen richtig beantwortet haben, suchen Sie neben der Datei fünfzehn.c nach der Datei fünfzehn.txt und notieren Sie darin die Antworten auf diese Fragen.

Implementierung

Nun, beginnen wir mit der Umsetzung des Spiels. Denken Sie daran, dass wir in kleinen Schritten vorgehen. Versuchen Sie nicht, alles auf einmal zu erledigen. Stattdessen implementieren wir die Funktionen einzeln und stellen sicher, dass sie funktionieren, bevor wir fortfahren. Insbesondere empfehlen wir Ihnen, die Spielfunktionen in der folgenden Reihenfolge auszuführen: init (Initialisierung), Draw (Ziehen), Move (einen Schritt machen), Won (Sieg). Designentscheidungen (z. B. wie viel Platz zwischen unseren Zahlenkacheln eingefügt werden soll) liegen bei Ihnen. Das Spielfeld sollte in etwa so aussehen: 15 14 13 12 11 10 9 8 7 6 5 4 3 1 2 _ Bitte beachten Sie noch einmal, dass in der Startposition 1 und 2 in umgekehrter Reihenfolge liegen (dies gilt für das klassische 4x4-Feld, wenn die Anzahl der Spielsteine ​​ungerade ist). Wenn die Anzahl der Spielsteine ​​gerade ist und das Feld 3x3 groß ist, ist es nicht nötig, die beiden „untersten“ Spielsteine ​​zu vertauschen. 8 7 6 5 4 3 2 1 _ Um Ihre Implementierung von „Tag“ zu testen, müssen Sie versuchen, sie abzuspielen (vergessen Sie nicht, dass Sie das Programm vor seinem natürlichen Abschluss beenden können, indem Sie die Tastenkombination Strg+C drücken). Stellen Sie sicher, dass das Programm funktioniert, wenn falsche Zahlen eingegeben werden. Und denken Sie daran: So wie Sie die Eingabe in „find“ automatisiert haben, können Sie auch die „Komplettlösung“ des Spiels automatisieren. Tatsächlich gibt es im Ordner ~cs50/pset3 die Dateien 3x3.txt und 4x4.txt , die alle Schrittfolgen zum Gewinnen auf 3x3- und 4x4-Feldern enthalten. Um das Programm beispielsweise mit der ersten Datei zu testen, führen Sie den folgenden Befehl aus: ./fifteen 3 < ~cs50/pset3/3x3.txt Richten Sie das Argument ein, das Sie benötigen, um die Animation zu beschleunigen. Und im Allgemeinen können Sie das Spiel jederzeit ändern, wenn Sie möchten. Viel Spaß mit „ANSI-Escape-Sequenzen“ inklusive Farbe. Schauen Sie sich unsere Implementierung von clear an und schauen Sie sich http://isthe.com/chongo/tech/comp/ansi_escapes.html an , um neue Tricks zu lernen. Wenn Sie möchten, schreiben Sie Ihre eigenen Funktionen oder ändern Sie die Prototypen der von uns geschriebenen Funktionen. Die einzige Einschränkung besteht darin, dass Sie die Logik der Hauptfunktion nicht ändern, da wir sonst einige automatische Tests nicht durchführen können, um zu bestätigen, dass Ihr Programm ordnungsgemäß funktioniert. Insbesondere muss main genau dann 0 zurückgeben, wenn der Benutzer das Rätsel gelöst hat. Für alle Fehleroptionen müssen Werte ungleich Null zurückgegeben werden. Sollten Fehler auftreten, schreiben Sie uns. Nun, wenn Sie mit der Implementierung der von den CS50-Assistenten vorbereiteten Anwendung spielen möchten, führen Sie den folgenden Befehl aus: ~cs50/pset3/fifteen Wenn Sie an einer cooleren Implementierung mit automatischer Rätsellösung interessiert sind, schauen Sie sich die „Hacker“-Version des Programms an: ~cs50/hacker3/fifteen Anstatt eine Zahl in das Spielfenster einzugeben, geben Sie das Wort GOTT ein. Großartig, nicht wahr? Wenn Sie die Korrektheit Ihres Programms offiziell mit check50 überprüfen möchten, beachten Sie, dass check50 davon ausgeht, dass der leere Raum des Spielfelds mit 0 gefüllt ist; Wenn Sie einen anderen Wert gewählt haben, ersetzen Sie ihn zur korrekten Überprüfung durch Null. Außerdem geht check50 davon aus, dass Sie die Board-Felder in der Reihenfolge [Zeile] [Spalte] und nicht in der Reihenfolge Board [Spalte] [Zeile] indizieren. check50 2015.fall.pset3.fifteen fifteen.c

Erfahren Sie mehr über die Implementierung von Fifteen Spielfunktionen

• init (Initialisierung)
• ziehen
• bewegen (einen Schritt machen)
• Gewonnener Gewinn)

drin

In dieser Funktion stellen wir das Spielfeld vor. Dazu verwenden wir ein zweidimensionales Array aus ganzen Zahlen. Die Array-Dimension beträgt MAX x MAX, wobei MAX eine Konstante ist, die die maximale Anzahl von Kacheln angibt, die in eine Zeile oder Spalte eines Felds passen. Daher müssen wir die Variable int board[MAX][MAX] definieren . Bedenken Sie jedoch, dass die Größe des Spielfelds vom Benutzer bestimmt wird. Daher müssen wir eine Variable definieren, die die Boardgröße angibt, die der Benutzer eingeben muss. Das ist int d . Dabei ist d die Platinenabmessung, d <= MAX. Allerdings kann man in C die Größe eines Arrays nicht ändern, man muss sich also mit der maximalen Größe zufrieden geben. In init müssen Sie die Werte auf die Tafel setzen. Lesen Sie mehr über zweidimensionale Arrays, wenn Sie noch nicht damit gearbeitet haben. Kurz gesagt, sie haben zwei Indizes, der erste gibt die Zeilennummer an, der zweite die Spaltennummer. Für unser Problem beginnen wir mit der maximalen Zahl und enden im Fall von d = 3 („Achten“) mit einer Eins und einer leeren Ecke. Wenn wir noch „Tag“ haben, dann tauschen wir 1 und 2. Was tun mit dem leeren Raum? Unser Array besteht aus ganzen Zahlen, daher muss die Lücke mit einer ganzen Zahl gefüllt werden. Daher müssen Sie eine Ganzzahl auswählen, um das leere Plättchen zu initialisieren (oder, im Fall eines physischen Spiels, das Fehlen eines Plättchens). Schleifen können verwendet werden, um das Spielbrett zu initialisieren und es mit einem Startsatz an Spielsteinen zu füllen. Wir durchlaufen die Indizes i und j, wobei board[i][j] eine Kachel ist, die sich in Zeile Nummer i und Spalte Nummer j befindet. Wir füllen die Tafel in absteigender Reihenfolge. Wenn die Anzahl der Plättchen (ohne leere) ungerade ist, tauschen Sie 1 und 2.

ziehen

Diese Funktion sollte den aktuellen Status des Spielfelds drucken. Denken Sie daran, dass wir Werte mit einer oder zwei Ziffern haben können. Für eine schöne Formatierung nach den Zahlen 1-9 sollte die Funktion daher ein Leerzeichen ( #s ) ausgeben. Dies kann mit dem Platzhalter %2d erfolgen . printf (“%2d”, board[i][j]); Vergessen Sie auch nicht die leere Zelle. Wählen Sie das Zeichen aus, das es darstellen soll (in unserem Beispiel ist dies ein Unterstrich). Die Zeichenfunktion sollte dieses Zeichen zeichnen, sobald Sie eine leere Zelle treffen. Unsere Schleife würde also etwa so aussehen: for каждой строки for каждого Element строки print Bedeutung и пробел print новую строку Denken Sie daran, dass die Reihenfolge, in der die Draw-Funktion die Kacheln auf den Bildschirm zeichnet, die Reihenfolge widerspiegeln sollte, in der sie sich in dem in der Init- Funktion definierten Array befinden .

bewegen

Nachdem Sie das Spielfeld initialisiert und die ersten Spielsteinpositionen gezeichnet haben, müssen Sie dem Benutzer erlauben, die Position der Spielsteine ​​zu bearbeiten, also Bewegungen auszuführen. In Fifteen.c nimmt das Programm also die Ausgabe des Benutzers entgegen, erstellt das Spielbrett, ruft dann die Move-Funktion auf und teilt ihr mit, welches Plättchen er verschieben möchte. Seien Sie vorsichtig: Sie wenden die Funktion speziell auf die Zahl auf der Kachel an und nicht auf ihre Position auf der Tafel (im Array). Sie müssen also die tatsächliche Position der Kachel ermitteln. Darüber hinaus sollten Sie dem Benutzer nur dann erlauben, die Kachel zu verschieben, wenn dies möglich ist. Im Bild oben können wir nur die Kacheln Nummer 2, 5 und 8 verschieben. Wie stellt man das fest? Nach dem Wert einer leeren Kachel. Die Move- Funktion funktioniert also etwa so:

• Akzeptiert die Kachelnummer, die der Benutzer verschieben möchte
• Sucht nach der Position dieser Kachel im Array (auf dem Spielfeld).
• Merkt sich die Position einer leeren Kachel
• Wenn eine leere Kachel an eine Kachel angrenzt, die der Benutzer verschieben möchte, werden sie im Array ausgetauscht.

gewonnen

Diese Funktion prüft nach jedem Benutzerschritt, ob das Spiel beendet ist. Es gibt true zurück, wenn die Kacheln in der richtigen Reihenfolge sind (einschließlich der Position der leeren Kachel in der unteren rechten Ecke). In diesem Fall kann das Programm beendet werden. Wenn die Kacheln immer noch verstreut sind, gibt die Funktion false zurück und übergibt die Zügel an die Move- Funktion . Wie organisiert man eine Inspektion? Wie beim Initialisieren und Zeichnen des Boards – mit zwei verschachtelten for-Schleifen. Sie können beispielsweise eine Bedingung festlegen, dass jede nachfolgende Zahl im Array größer als die vorherige sein muss. Beachten Sie, welcher Wert in die leere Kachel geschrieben ist. Oder anders: Verwenden Sie einen Zähler, um sicherzustellen, dass alle Kacheln vorhanden sind, wenn Sie damit umgehen können, und schreiben Sie die Formel, um sie zu erhalten. Wir wünschen Ihnen viel Erfolg bei Ihren Experimenten!

So validieren Sie Ihren Code und erhalten Noten

Aufmerksamkeit! Wenn es für Sie wichtig ist, nur die Richtigkeit von Aufgaben zu überprüfen, dann verwenden Sie cs50check. Wenn Sie Noten auf der edx-Plattform erhalten möchten, befolgen Sie die unten beschriebene Vorgehensweise. Beachten Sie, dass dieses Verfahren denselben cs50check zum Überprüfen von Aufgaben verwendet. Der einzige Unterschied besteht darin, dass es sich die Ergebnisse merkt und die Gesamtpunktzahl berechnet.

1. Melden Sie sich bei der CS50-IDE an
2. Klicken Sie in der oberen linken Ecke der CS50-IDE , wo sich der Dateibrowser befindet (nicht im Terminalfenster), mit der rechten Maustaste auf Ihr pset3-Verzeichnis und klicken Sie auf „ Herunterladen“ . Sie sollten sehen, dass der Browser das pset3.tar.gz- Archiv heruntergeladen hat .
3. Melden Sie sich in einem separaten Fenster oder Tab bei CS50 Submit an
4. Klicken Sie auf das Senden- Symbol in der oberen linken Ecke des Bildschirms
5. Klicken Sie in der Ordnerliste auf der linken Seite auf das Verzeichnis „Problem Set 3“ und dann auf die Schaltfläche „Neue Einreichung hochladen“. Es ist auf der rechten Seite.
6. Klicken Sie auf dem angezeigten Bildschirm auf die Schaltfläche Dateien hinzufügen .... Es öffnet sich ein Fenster zum Auswählen von Dateien von Ihrem Computer.
7. Navigieren Sie zu dem Ordner, in dem Sie pset3.tar.gz gespeichert haben. Es befindet sich höchstwahrscheinlich in Ihrem Download- Ordner oder dort, wo Ihr Browser standardmäßig Dateien ablegt. Wenn Sie pset3.tar.gz finden , klicken Sie einmal darauf, um es auszuwählen, und klicken Sie dann auf Öffnen .
8. Klicken Sie auf Hochladen starten . Ihre Dateien werden auf CS50- Server hochgeladen .
9. Auf dem angezeigten Bildschirm sollte das Fenster „Keine Datei ausgewählt“ angezeigt werden . Wenn Sie den Mauszeiger nach links bewegen, wird eine Liste der heruntergeladenen Dateien angezeigt. Klicken Sie zur Bestätigung auf die einzelnen Elemente. Wenn Sie sich bei etwas nicht sicher sind, können Sie die Dateien erneut hochladen, indem Sie dieselben Schritte wiederholen. Sie können dies bis Ende 2016 so oft tun, wie Sie möchten.