Harvard CS50 : devoirs de la semaine 3 (cours 7 et 8), partie 2

Cours sur les principes fondamentaux de la programmation à Harvard CS50 Matériel supplémentaire : notation asymptotique, algorithmes de tri et de recherche Devoirs de la semaine 3, partie 1. Tri et recherche.

Le jeu commence!

C'est l'heure de jouer! La plupart des gens connaissent le jeu de réflexion "Tag". Pour le formaliser, « Tag » est un champ bidimensionnel 4x4, dans ce champ il n'y a pas 16, mais 15 carrés, c'est-à-dire qu'un emplacement reste vide. Chacune des cases est numérotée et peut se déplacer horizontalement ou verticalement à l'intérieur du champ (si, bien sûr, il y a de la place pour se déplacer). Le but est de classer les nombres dans l'ordre, de 1 à 15, de gauche à droite, de haut en bas. Ensuite, l'espace vide sera dans le coin inférieur droit. Le déplacement d’une tuile (ou de plusieurs) est une « étape » dans cet espace de jeu. La combinaison présentée dans l'image ci-dessus est déjà empilée, mais notez que 12 ou 15 tuiles peuvent être poussées dans l'espace vide. Les règles stipulent qu'une tuile ne peut pas être déplacée en diagonale ou retirée du plateau de jeu. Il existe effectivement beaucoup de configurations pour démarrer le jeu (vous pouvez en compter combien exactement), mais par souci de simplicité, disposons les tuiles dans l'ordre de la plus grande à la plus petite et laissons un espace vide dans le coin inférieur droit du plateau. . La seule chose à faire est d'échanger 1 et 2 pour que le puzzle puisse être résolu. Allez maintenant dans le répertoire ~/ de votre workbench , puis /pset3/fifteen et ouvrez quinze.c . Il contient le code du moteur de jeu. La tâche consiste à ajouter du code au jeu. Mais d'abord, compilons notre « moteur » (vous savez probablement déjà comment faire). Même si le jeu n'est pas terminé, vous pouvez lancer l'application. Il sera plus pratique de l'exécuter dans une fenêtre de terminal plus grande que d'habitude, qui peut être ouverte en cliquant sur le plus vert (+) à côté de l'un des onglets de code et en sélectionnant Nouveau terminal . Ou vous pouvez ouvrir la fenêtre du terminal en plein écran en cliquant sur l' icône Agrandir dans le coin supérieur droit de la console. Vous voyez que certaines choses fonctionnent d’une manière ou d’une autre. Mais en fait, la majeure partie du jeu n’a pas encore été écrite. Et voici – préparez-vous – votre sortie !

Étude

Étudiez le code et les commentaires de quinze.c puis répondez aux questions ci-dessous :

1. En dehors d'une planche 4x4, quelle taille de terrain notre moteur permet-il ?
2. Quelle structure de données est le terrain de jeu ?
3. Quelle fonction est appelée pour saluer le joueur au début de la partie ?
4. Quelles fonctionnalités devez-vous mettre en œuvre ?
5. Remarque : Si vous souhaitez que la vérification automatique vous indique si vous avez répondu correctement aux questions, à côté du fichier quinze.c, recherchez le fichier quinze.txt et notez-y les réponses à ces questions.

Mise en œuvre

Eh bien, commençons à implémenter le jeu. N’oubliez pas que nous avançons par petites étapes, n’essayez pas de tout faire en même temps. Au lieu de cela, implémentons les fonctionnalités une par une et assurons-nous qu'elles fonctionnent avant de continuer. Nous vous proposons notamment d'implémenter les fonctions du jeu dans l'ordre suivant : init (initialisation), draw (dessiner), déplacer (faire un pas), gagné (gagner). Les décisions de conception (telles que l’espace à insérer entre nos tuiles numériques) vous appartiennent. Le terrain de jeu devrait ressembler à ceci : 15 14 13 12 11 10 9 8 7 6 5 4 3 1 2 _ Encore une fois, veuillez noter qu'en position de départ, 1 et 2 sont situés dans l'ordre inverse (cela s'applique au terrain 4x4 classique si le nombre de tuiles est impair). Si le nombre de tuiles est pair et que le champ est de 3x3, il n'est pas nécessaire d'échanger les deux tuiles « les plus basses ». 8 7 6 5 4 3 2 1 _ Pour tester votre implémentation de « Tag », vous devez essayer de les lire (n'oubliez pas que vous pouvez quitter le programme avant son achèvement naturel en appuyant sur la combinaison de touches crtl+c). Assurez-vous que le programme fonctionnera si des numéros incorrects sont saisis. Et rappelez-vous que tout comme vous avez automatisé la saisie dans Find, vous pouvez automatiser la « procédure pas à pas » du jeu. En fait, dans le dossier ~cs50/pset3 se trouvent les fichiers 3x3.txt et 4x4.txt , qui contiennent toutes les séquences d'étapes pour gagner sur les champs 3x3 et 4x4. Pour tester le programme, par exemple en utilisant le premier des fichiers, exécutez la commande suivante : ./fifteen 3 < ~cs50/pset3/3x3.txt Définissez l'argument dont vous avez besoin pour accélérer l'animation. Et en général, si vous le souhaitez, vous pouvez toujours changer la donne. Pour s'amuser avec les "séquences d'échappement ANSI" incluant la couleur. Jetez un œil à notre implémentation de clear et consultez http://isthe.com/chongo/tech/comp/ansi_escapes.html pour apprendre de nouvelles astuces. Si vous le souhaitez, écrivez vos propres fonctions ou modifiez les prototypes des fonctions que nous avons écrites. La seule limitation est que vous ne modifiez pas la logique de la fonction principale, sinon nous ne pourrons pas lui appliquer certains tests automatiques pour confirmer que votre programme fonctionne correctement. En particulier, main doit renvoyer 0 si et seulement si l'utilisateur a résolu le puzzle. Des valeurs différentes de zéro doivent être renvoyées pour toutes les options d'erreur. Si des erreurs surviennent, écrivez-nous. Eh bien, si vous voulez jouer avec l'implémentation de l'application préparée par les assistants du CS50, exécutez la commande suivante : ~cs50/pset3/fifteen Si vous êtes intéressé par une implémentation plus cool, avec résolution automatique d'énigmes, consultez la version « Hacker » du programme : ~cs50/hacker3/fifteen Au lieu de saisir un chiffre dans la fenêtre de jeu, tapez le mot DIEU. Super, n'est-ce pas ? Si vous souhaitez vérifier officiellement l'exactitude de votre programme avec check50, notez que check50 suppose que l'espace vide du terrain de jeu est rempli de 0 ; si vous avez choisi une valeur différente, remplacez-la par zéro pour une vérification correcte. De plus, check50 suppose que vous indexez les champs du tableau dans l'ordre [ligne] [colonne], et non dans l'ordre [colonne] [ligne]. check50 2015.fall.pset3.fifteen fifteen.c

En savoir plus sur la mise en œuvre des fonctions du jeu Fifteen

• init (initialisation)
• dessiner
• bouger (faire un pas)
• gagné (gagner)

initialisation

Dans cette fonction, nous introduisons le terrain de jeu. Pour ce faire, nous utilisons un tableau d’entiers bidimensionnels. La dimension du tableau est MAX x MAX, où MAX est une constante indiquant le nombre maximum de tuiles pouvant tenir dans une ligne ou une colonne d'un champ. Ainsi, nous devons définir la variable int board[MAX][MAX] Cependant, rappelez-vous que la taille du terrain de jeu est déterminée par l'utilisateur. Par conséquent, nous devons définir une variable qui indiquerait la taille du tableau que l'utilisateur doit saisir. C'est int d . où d est la dimension de la planche, d <= MAX. Cependant, en C, vous ne pouvez pas modifier la taille d'un tableau, vous devez donc vous contenter de la taille maximale. Dans init , vous devez mettre les valeurs au tableau. En savoir plus sur les tableaux bidimensionnels si vous n'avez pas encore travaillé avec eux. En bref, ils ont deux indices, le premier désigne le numéro de ligne, le second le numéro de colonne. Pour notre problème, nous commençons par le nombre maximum et terminons dans le cas de d = 3 (« Huit ») avec un et un coin vide. Si nous avons encore « Tag », alors nous échangeons 1 et 2. Que faire de l'espace vide ? Notre tableau est constitué d'entiers, le vide doit donc être rempli par un entier. Vous devez donc choisir un nombre entier pour initialiser la tuile vide (ou, dans le cas d'un jeu physique, l'absence de tuile). Les boucles peuvent être utilisées pour initialiser le plateau de jeu et le remplir avec un jeu de tuiles de départ. Nous parcourons les indices i et j, où board[i][j] est une tuile située dans la ligne numéro i et la colonne numéro j. Nous remplissons le tableau par ordre décroissant. Si le nombre de tuiles (sans celles vides) est impair, échangez 1 et 2.

dessiner

Cette fonction devrait imprimer l'état actuel du terrain de jeu. N'oubliez pas que nous pouvons avoir des valeurs à un ou deux chiffres, donc pour un beau formatage après les nombres 1 à 9, la fonction doit imprimer un espace ( #s ). Cela peut être fait en utilisant l' espace réservé %2d . printf (“%2d”, board[i][j]); N'oubliez pas non plus la cellule vide. Sélectionnez le caractère qui le représentera (dans notre exemple, il s'agit d'un trait de soulignement). La fonction draw devrait dessiner ce caractère dès que vous frappez une cellule vide. Notre boucle ressemblerait donc à ceci : for каждой строки for каждого element строки print meaning и пробел print новую строку rappelez-vous que l'ordre dans lequel la fonction draw dessine les tuiles à l'écran doit refléter l'ordre dans lequel elles se trouvent dans le tableau défini dans la fonction init .

se déplacer

Une fois que vous avez initialisé le terrain de jeu et dessiné les positions initiales des tuiles, vous devez permettre à l'utilisateur de modifier la position des tuiles, c'est-à-dire d'effectuer des mouvements. Ainsi, dans Fifteen.c , le programme prend la sortie de l'utilisateur, construit le plateau de jeu, puis appelle la fonction de déplacement et lui indique quelle tuile il souhaite déplacer. Attention : vous appliquez la fonction spécifiquement au numéro sur la tuile, et non à sa position sur le plateau (dans le tableau). Vous devez donc trouver la position réelle de la tuile. De plus, vous ne devez autoriser l’utilisateur à déplacer la vignette que lorsque cela est possible. Dans l’image ci-dessus, on ne peut déplacer que les tuiles numéro 2, 5 et 8. Comment déterminer cela ? Par la valeur d'une tuile vide. La fonction move fonctionne donc à peu près comme ceci :

• Accepte le numéro de tuile que l'utilisateur souhaite déplacer
• Recherche la position dans le tableau (sur le terrain de jeu) de cette tuile
• Se souvient de la position d'une tuile vide
• Si une tuile vide est adjacente à celle que l'utilisateur souhaite déplacer, elles sont échangées dans le tableau.

gagné

Cette fonction vérifie si le jeu est terminé après chaque étape de l'utilisateur. Il renvoie vrai si les tuiles sont dans le bon ordre (y compris la position de la tuile vide dans le coin inférieur droit). Dans ce cas, le programme peut être arrêté. Si les tuiles sont toujours dispersées, la fonction renvoie false et passe les rênes à la fonction move . Comment organiser un contrôle ? Comme dans le cas de l'initialisation et du dessin du tableau - en utilisant deux boucles for imbriquées. Par exemple, vous pouvez définir une condition selon laquelle chaque nombre suivant du tableau doit être supérieur au précédent. Notez quelle valeur est écrite dans la vignette vide. Ou d'une autre manière - utilisez un compteur pour vous assurer que toutes les tuiles sont en place, si vous pouvez le manipuler et écrivez la formule pour l'obtenir. Nous vous souhaitons bonne chance dans vos expériences !

Comment valider votre code et obtenir des notes

Attention! S'il est important pour vous de vérifier uniquement l'exactitude des tâches, utilisez cs50check. Si vous souhaitez obtenir des notes sur la plateforme edx, suivez la procédure décrite ci-dessous. Gardez à l’esprit que cette procédure utilise le même cs50check pour vérifier les tâches. La seule différence est qu'il mémorise les résultats et calcule le score global.

1. Connectez-vous à l'IDE CS50
2. Près du coin supérieur gauche de l'IDE CS50 , là où se trouve son navigateur de fichiers (pas dans la fenêtre du terminal), cliquez avec le bouton droit sur votre répertoire pset3 et cliquez sur Télécharger . Vous devriez voir que le navigateur a téléchargé l' archive pset3.tar.gz .
3. Dans une fenêtre ou un onglet séparé, connectez-vous à CS50
4. Cliquez sur l' icône Soumettre dans le coin supérieur gauche de l'écran
5. Dans la liste des dossiers à gauche, cliquez sur le répertoire Problem Set 3 , puis cliquez sur le bouton Télécharger une nouvelle soumission. C'est sur la droite.
6. Sur l'écran qui apparaît, cliquez sur le bouton Ajouter des fichiers .... Une fenêtre de sélection de fichiers sur votre ordinateur s'ouvrira.
7. Accédez au dossier dans lequel vous avez enregistré pset3.tar.gz. Il se trouve probablement dans votre dossier Téléchargements ou à l'endroit où votre navigateur place les fichiers par défaut. Lorsque vous trouvez pset3.tar.gz , cliquez une fois dessus pour le sélectionner, puis cliquez sur Ouvrir .
8. Cliquez sur Démarrer le téléchargement . Vos fichiers seront téléchargés sur les serveurs CS50 .
9. Sur l'écran qui apparaît, vous devriez voir la fenêtre Aucun fichier sélectionné . Si vous déplacez le curseur de votre souris vers la gauche, vous verrez une liste des fichiers téléchargés. Pour confirmer, cliquez sur chacun d'eux. Si vous n'êtes pas sûr de quelque chose, vous pouvez télécharger à nouveau les fichiers en répétant les mêmes étapes. Vous pouvez le faire autant de fois que vous le souhaitez jusqu'à fin 2016.