Avant d'aborder les problèmes, regardez les conférences 7-8 , lisez et approfondissez les « Matériels supplémentaires de la troisième semaine ». Ils sont consacrés aux algorithmes de recherche (linéaire et binaire), au tri (ils sont nombreux !), ainsi qu'au travail d'un débogueur (la capacité de travailler avec un débogueur pour déboguer des programmes est une compétence extrêmement importante !). Si tout s'est bien passé avec les cours et la théorie, vous pouvez facilement répondre aux questions du test :
Pourquoi la recherche binaire nécessite-t-elle un tableau trié ?
Pourquoi le tri à bulles est-il estimé à O(n2) ?
Pourquoi l'estimation du tri par insertion est-elle Ω(n) ?
Comment fonctionne le tri par sélection ? Décrivez en trois phrases (ou moins).
Quelle est la limite supérieure (dans le pire des cas) de la durée d’exécution du tri par fusion ?
Le débogueur GDB vous permet de déboguer un programme. Et si vous formulez plus précisément, qu’est-ce que cela vous permet de faire exactement ?
Objectifs
Apprenez à travailler avec des projets contenant plusieurs fichiers
Apprenez à lire le code source de quelqu'un d'autre
Comprendre divers algorithmes et fonctions récursives
La plupart de ces objectifs sont pratiquement impossibles à évaluer formellement. Par conséquent, du point de vue de la vérification formelle des problèmes, peu de choses vous sembleront difficiles. Cependant, nous vous le rappelons : vous ne pouvez apprendre la programmation qu’en pratiquant constamment ! Par conséquent, nous vous encourageons non seulement à résoudre les tâches, mais également à consacrer du temps et des efforts supplémentaires et à mettre en œuvre tous les algorithmes discutés cette semaine. Avant!
Commencer
Rappelez-vous que pour les problèmes pratiques des semaines un et deux, vous avez écrit des programmes à partir de zéro et créé vos propres répertoires pset1 et pset2 à l'aide de la commande mkdir . Pour le devoir pratique de la troisième semaine, vous devez télécharger la distribution (ou « distribution » comme nous l'appelons) que nous avons écrite et y ajouter vos propres lignes de code. Tout d’abord, lisez notre code et essayez de le comprendre. La compétence la plus importante cette semaine est d’apprendre à lire le code des autres. Alors, connectez-vous à cs50.io et exécutez la commande update50 dans une fenêtre de terminal pour vous assurer que la version de l'espace de travail est à jour. Si vous avez accidentellement fermé la fenêtre du terminal et que vous ne la trouvez pas, allez dans le menu Affichage et assurez-vous que l'option Console est cochée (cochez-la si ce n'est pas le cas). Cliquez sur (+), à l'intérieur du cercle vert sur le cadre de la fenêtre du terminal, sélectionnez Nouveau terminal . Après cela, exécutez la commande cd ~/workspace et assurez-vous que vous êtes dans le répertoire de l'espace de travail (c'est votre répertoire). Après cela, exécutez la commande : wget http://cdn.cs50.net/2015/fall/psets/3/pset3/pset3.zip pour télécharger l'archive ZIP du livre de problèmes dans votre espace de travail (wget est la commande de téléchargement Linux). Si tout va bien, vous verrez la phrase suivante dans la ligne : 'pset3.zip' saved Assurez-vous que vous avez bien téléchargé pset3.zip en exécutant la commande : ls puis exécutez unzip pset3.zip pour décompresser le fichier. Si vous exécutez à nouveau la commande ls , vous verrez également le répertoire pset3 . Accédez-y en exécutant la commande cd pset3 puis demandez à visualiser à nouveau le contenu du répertoire : ls vous verrez qu'il y a deux sous-répertoires dans ce répertoire : fifteen find Déjà intriguant !
Recherche
Passons maintenant à l'un de ces sous-répertoires. Pour ce faire, nous allons exécuter la commande : cd ~/workspace/pset3/find Si vous affichez le contenu de ce dossier à l'écran (vous vous souvenez probablement déjà comment faire cela), voici ce que vous devriez voir : helpers.c helpers.h Makefile find.c generate.c Wow, il y a beaucoup de fichiers. Mais ne vous inquiétez pas, nous allons nous en occuper maintenant. Le fichier generate.c contient le code d'un programme qui utilise un "générateur de nombres pseudo-aléatoires" (généré par la fonction drand48 ) pour générer un grand nombre de nombres aléatoires (en fait pseudo-aléatoires, les ordinateurs ne peuvent pas gérer le pur hasard !) , et placez-les un à la fois en ligne. Compilez le programme : make generate Exécutez-le maintenant en exécutant la commande : ./generate Le programme vous donnera le message suivant : Usage: generate n [s] Cela signifie que le programme attend un ou deux arguments de ligne de commande. En utilisant le premier, n, est obligatoire ; ce nombre indique le nombre de nombres pseudo-aléatoires que vous souhaitez créer. Le paramètre s est facultatif, comme indiqué par les crochets. Le nombre s peut être appelé la « graine » pour le générateur de nombres pseudo-aléatoires. Par « graine » nous entendons les données d'entrée du générateur de nombres pseudo-aléatoires qui affectent sa sortie. Par exemple, si vous utilisez drand48, d'abord en appelant srand48 (une autre fonction dont le but est de "grainer" drand48) avec un argument de, disons, 1, et puis en appelant drand48 trois fois, drand48 pourrait renvoyer 2728, puis 29785, puis 54710. Si au lieu du précédent, en utilisant drand48, vous appelez d'abord srand48 avec un argument de, disons, 2, puis utilisez à nouveau drand48 trois fois, drand48 pourrait retournez 59797, puis 10425, puis 37569. Mais si vous revoyez drand48 en appelant à nouveau srand48 avec un argument de 1, le résultat des trois prochains appels à drand48 vous obtiendrez à nouveau 2728, puis 29785, puis 54710 ! Vous voyez, tout arrive pour une raison. Exécutez à nouveau le programme, cette fois, disons n=10, comme indiqué ci-dessous ; vous verrez une liste de 10 nombres pseudo-aléatoires. ./generate 10 Exécutons le programme une troisième fois avec la même valeur de n ; vous devriez voir une autre liste de 10 numéros. Essayez maintenant d'exécuter le programme avec deux paramètres. Prenons s=0 comme indiqué ci-dessous. ./generate 10 0 Maintenant, réexécutez la même commande : ./generate 10 0 vous ne pouvez même pas discuter : vous avez revu la même séquence "aléatoire" de dix chiffres. C'est ce qui se produit si vous ne modifiez pas les graines du générateur de nombres pseudo-aléatoires. Regardons maintenant le programme generate.c lui-même(tu te souviens comment ?). Les commentaires au début de ce fichier expliquent la fonctionnalité générale du programme. Mais il semble que nous ayons oublié de commenter le code lui-même. Lisez attentivement le code et lisez-le jusqu'à ce que vous compreniez la signification de chaque ligne. Commentez ensuite ce code pour nous, en remplaçant chaque TODO par une phrase décrivant le but ou la fonctionnalité de la ou des lignes de code correspondantes. (Remarque : un int non signé est un int « non signé », ce qui signifie qu'il ne peut pas être négatif). Pour obtenir plus d'informations sur rand ou srand, exécutez : man drand48 ou man srand48 Après avoir commenté autant que possible dans generate.c, recompilez le programme pour vous assurer que vous n'avez rien cassé : make generate Si generate ne compile plus, corrigez ce que vous avez cassé: )! Pour rappel, la commande make automatise la compilation du code, vous n'avez donc pas besoin d'exécuter la commande clang en insérant manuellement un tas de commutateurs. Mais en fait, make simplifie simplement notre saisie, mais en fait, derrière cela se cache le même bruit avec les paramètres dont nous avons besoin. Cependant, à mesure que vos programmes deviennent plus volumineux, make ne peut plus comprendre à partir du contexte comment compiler le code. Dans ce cas, vous devrez indiquer à make comment compiler les programmes, surtout s'ils impliquent l'utilisation de fichiers sources différents (comme .c). Pour résoudre ce problème, nous utiliserons des fichiers de configuration (Makefiles) qui indiquent exactement quoi faire. Comment la commande make a-t-elle su comment compiler et générer ? En fait, l'équipe a utilisé un fichier de configuration que nous avions déjà écrit. Ce fichier s'appelle Makefile et se trouve dans le même répertoire que generate.c . Makefile est une liste de règles spécifiant comment créer le fichier généré à partir de generate.c. Dans le fichier vous trouverez notamment les lignes pertinentes : generate: generate.c clang -ggdb3 -O0 -std=c11 -Wall -Werror -o generate generate.c La première ligne indique à make qu'une "cible" appelée generate doit être créée en appelant la commande depuis la deuxième ligne. De plus, la première ligne indique à make que generate dépend de generate.c, ce qui signifie que make ne reconstruira generate que lors des exécutions suivantes si ce fichier a été modifié. Ce n’est pas une mauvaise astuce pour gagner du temps, n’est-ce pas ? En fait, exécutez à nouveau la commande ci-dessous si vous n'avez pas modifié generate.c . make generate Vous serez informé que generate a déjà été mis à jour vers la version actuelle. Remarque : L'indentation au début de la deuxième ligne n'est pas une séquence d'espaces, mais plutôt un caractère de tabulation. Malheureusement, make nécessite que les commandes soient précédées de tabulations, alors faites attention à ne pas les remplacer par des espaces, sinon vous rencontrerez des erreurs étranges ! L' indicateur -Werror indique la commande clangtraitez les avertissements (mauvais) comme des erreurs (encore pires), vous serez donc obligé (de manière positive et éducative !) de les corriger. Regardons maintenant le fichier find.c . Notez que ce programme attend un argument de ligne de commande : "igloo", qui doit être trouvé dans une "botte de foin" de valeurs. Après cela, examinez le code et compilez le programme en exécutant la commande ci-dessous. make find make nous a essentiellement donné ce qui suit : clang -ggdb3 -O0 -std=c11 -Wall -Werror -o find find.c helpers.c -lcs50 -lm Faites attention ! Vous venez de compiler une application composée d'un, mais de deux fichiers : helpers.c et find.c . Comment avez-vous appris cela ? Pour comprendre cela, ouvrez à nouveau le Makefile pour voir ce qui s'y passe réellement. Les lignes pertinentes sont ci-dessous. find: find.c helpers.c helpers.h clang -ggdb3 -O0 -std=c11 -Wall -Werror -o find find.c helpers.c -lcs50 -lm Ce que nous entendons par dépendance (après les deux points), c'est que toute modification apportée à find.c , helpers.c ou helpers.h forcera make à reconstruire find la prochaine fois qu'il sera appelé à ces fins. Maintenant, exécutez ce programme en faisant, par exemple, ce qui suit : ./find 13 Après cela, il vous sera demandé de fournir une certaine pile (c'est-à-dire des nombres entiers) et de les nourrir une paille à la fois. Une fois que vous en avez assez de taper des chiffres, appuyez sur la combinaison de touches Ctrl-D . Cette combinaison enverra au programme un caractère de fin de fichier (EOF). Le symbole forcera la fonction GetInt de la bibliothèque CS50 à renvoyer la constante INT_MAX , et ceci, à son tour, dans find.c forcera find à arrêter de taper "stack". Le programme va maintenant chercher l'aiguille dans la botte de foin que vous avez fournie et il vous dira éventuellement si elle a été trouvée. En bref, le programme recherche une valeur dans un tableau. Au moins, elle devrait le faire, mais le problème, c'est qu'elle ne trouvera encore rien ! Mais voilà, vous venez à la rescousse ! Nous parlerons de l’importance de votre rôle un peu plus tard. En fait, le processus de fourniture d'une botte de foin peut être automatisé, au moins en "fusionnant" la sortie de generate dans find comme entrée. Par exemple, la commande ci-dessous transmet 1 000 nombres pseudo-aléatoires à rechercher, qui recherche ensuite 42 parmi ces valeurs. ./generate 1000 | ./find 42 Notez que lorsque generate transmet les données brutes à rechercher, vous ne verrez pas le numéro généré, mais vous verrez find en cours d'exécution. . Alternativement, vous pouvez « rediriger » la sortie de generate vers un fichier avec une commande comme celle-ci : ./generate 1000 > numbers.txt Le contenu de ce fichier peut être redirigé vers l'entrée de find avec la commande : ./find 42 < numbers.txt Regardons à nouveau le code dans le Makefile et notons le ligne suivante : all: find generate Cela signifie que vous pouvez build generate et find en exécutant la commande suivante : make all De plus, la commande en dessous de cette ligne est équivalente à la commande au-dessus, puisque make construit par défaut la première entrée du Makefile. make Si seulement vous pouviez résumer toutes ces tâches pratiques en une seule commande ! Mais hélas! Enfin, faites attention à ces dernières lignes du Makefile : clean: rm -f *.o a.out core find generate Cette entrée permet de supprimer tous les fichiers qui se terminent par .o ou qui sont appelés core (on vous expliquera cela dans un instant !), et aussi d'exécuter simplement la recherche ou la génération de programmes. en exécutant la ligne : Si vous voulez make clean expérimenter , alors voici une chose à laquelle il faut faire attention : n'ajoutez pas, disons, *.c à cette dernière ligne du Makefile ! (pourquoi ?) Toutes les lignes commençant par le signe # ne sont que des commentaires.
Tâche 1 : Rechercher
Il est temps de faire quelque chose d'intéressant ! Notez que find.c appelle search , une fonction déclarée dans helpers.h . Malheureusement, nous avons oublié d'implémenter complètement cette fonction dans helpers.c ! (Il est à noter qu'on pourrait mettre le contenu de helpers.h et helpers.c dans un seul find.c . Mais parfois il est préférable de séparer les programmes en plusieurs fichiers. Surtout si certaines fonctions, ou plutôt fonctions utilitaires, peuvent être utiles pour d'autres programmes. Comme les fonctions de la bibliothèque CS50 par exemple. Jetez un oeil à helpers.c et vous verrez que la recherche renvoie toujours false, que la valeur donnée soit ou non dans les valeurs. Réécrivez la recherche pour qu'elle utilise la recherche linéaire, renvoyant vrai , si la valeur est en valeurs et false si la valeur n'est pas en valeurs. Prenez soin de renvoyer false immédiatement si n n'est pas positif. Lorsque vous êtes prêt à vérifier la validité, essayez d'appeler la commande suivante : Puisque l'un des nombres ./generate 1000 50 | ./find 127 imprimés avec generate lorsque 50 a été généré est 127, votre code devrait trouver l'aiguille ! Par contraste, essayez cette commande : ./generate 1000 50 | ./find 128 Puisque 128 ne fait pas partie de l'ensemble des nombres générés par generate lorsque 50 a été généré, votre code n'a pas besoin de trouver "l'aiguille". . Exécutez d'autres tests en exécutant generate avec des graines, en analysant le résultat et en recherchant l'aiguille qui devrait être dans la botte de foin. Notez que main dans find.c est écrit de telle manière que find renvoie 0 si "l'aiguille" est trouvée, sinon il renvoie 1. Vous pouvez vérifier le soi-disant "code de sortie" que main renvoie lorsqu'il est exécuté après avoir exécuté un autre commandes echo $? . Par exemple, si votre implémentation de recherche est correcte, si vous exécutez, ./generate 1000 50 | ./find 127 echo $? vous verrez 0, tandis que 127 fait partie des 1 000 nombres générés par la génération avec une valeur de départ de 50, donc la recherche que vous avez écrite devrait renvoyer vrai. Dans ce cas, main (écrit par nos soins) devrait renvoyer 0 (c'est-à-dire exit). Si vous donnez l'entrée suivante ./generate 1000 50 | ./find 128 echo $? , vous verrez 1 car 128 ne fait pas partie des 1000 nombres générés par generate avec une graine de 50. Dans ce cas, la recherche (écrite par vous) renverra false et main (écrite par nous ) renverra 1 (puis terminera le travail). Comprenez-vous la logique ? Lorsque tout est prêt à être vérifié à l'aide de check50, exécutez la commande suivante : check50 2015.fall.pset3.find helpers.c À propos, vous ne devriez pas vous habituer à tester votre code à l’aide de check50 avant de le tester vous-même. Après tout, check50 n'existe pas vraiment, donc exécuter le code avec vos propres échantillons d'entrée, en comparant la sortie réelle à la sortie attendue, est la meilleure habitude que vous puissiez prendre à ce stade. C'est vrai, ne devenez pas accro ! Si vous souhaitez jouer avec l'implémentation de find par les assistants cs50, exécutez cette commande : ~cs50/pset3/find
Tri
La recherche linéaire n'est pas quelque chose de vraiment impressionnant, mais dès les premières leçons (et dans la septième, nous avons répété cette astuce !), vous vous souvenez qu'on peut trouver une aiguille dans une botte de foin beaucoup plus rapidement. Mais nous devons d’abord trier notre botte de foin. Notez que find.c appelle sort , une fonction déclarée dans helpers.h . Malheureusement, nous avons « oublié » d’implémenter pleinement cette fonctionnalité dans helpers.c ! Regardez dans helpers.c et vous verrez que le tri revient instantanément, même si la fonction principale de find lui transmet le tableau réel. Rappelez-vous maintenant la syntaxe de déclaration du tableau. Non seulement vous spécifiez le type d’élément de ce tableau, mais vous spécifiez également sa taille entre crochets. C'est ce que nous faisons pour la botte de foin dans find.c : int haystack [MAX]; Mais lorsque vous parcourez un tableau, vous spécifiez uniquement son nom. Et nous procédons exactement de la même manière lorsque nous parcourons une botte de foin pour effectuer un tri dans find.c : sort (haystack, size); (Devinez pourquoi nous transmettons la taille de ce tableau séparément ?) Lorsque nous déclarons une fonction qui prend un tableau unidimensionnel comme argument, nous n'avons pas besoin de spécifier la taille du tableau. De même, nous ne l'avons pas fait lorsque nous avons déclaré sort dans helpers.h (et helpers.c) : void sort (int values [] int n); implémentez sort pour que la fonction trie réellement le tableau de nombres du plus petit au plus grand. Il doit avoir un temps d'exécution égal à O(n 2 ), où n est la taille du tableau. Vous souhaiterez probablement implémenter le tri à bulles, le tri par sélection ou le tri par insertion, comme nous l'avons appris au cours de la troisième semaine. Cependant, il est important de noter qu’il n’existe pas de manière « correcte » d’implémenter ces algorithmes. Il existe un grand nombre de variantes. En fait, vous pouvez toujours les améliorer si bon vous semble, à condition que votre implémentation converge vers O(n2 ) . Cependant, laissez l'expérimentation au corps de la fonction et, afin de simplifier les tests, ne modifiez pas notre déclaration de tri. Cela devrait ressembler à ceci : void sort (int values [] int n); Puisque la fonction renvoie une valeur vide, elle ne doit pas renvoyer de tableau trié. Au lieu de cela, il doit trier de manière « destructive » le tableau qu’il « parcourt », en déplaçant ses éléments. Au cours de la quatrième semaine, nous verrons que les tableaux sont transmis par référence plutôt que par valeur. Autrement dit, sort ne recevra pas de copies du tableau, mais le tableau d'origine lui-même. Bien que vous ne puissiez pas modifier notre déclaration de tri, vous pouvez toujours définir votre propre fonction dans helpers.c, qui peut ensuite être appelée depuis le tri. Décidez vous-même de la meilleure façon de tester votre implémentation de tri. N'oubliez pas que printf et GDB vous aideront ! Et n'oubliez pas que vous pouvez créer encore et encore la même séquence de nombres pseudo-aléatoires en spécifiant explicitement les valeurs de départ pour la génération.
Recherche binaire, conseils
La première chose que vous devez comprendre à propos de la fonction find est que nous avons déjà du code écrit (distribution). Nous comblons simplement quelques lacunes du code existant. Le programme find.c demande la saisie de nombres (c'est-à-dire pour remplir une "pile"), puis y recherche une "aiguille" à la demande de l'utilisateur, en utilisant les fonctions de tri et de recherche définies dans helpers.c . Donc, find est déjà écrit, nous devons écrire des helpers . Voici donc ce que nous devons faire :
Mettre en œuvre la recherche. Cette fonction doit renvoyer true si la valeur est trouvée dans la pile et false si elle n'y est pas.
Implémentez le tri, une fonction qui trie un tableau de valeurs.
Initialement, la recherche était implémentée de manière linéaire. Mais vous pouvez faire mieux. L'algorithme de recherche linéaire s'exécute en O(n) time . Votre tâche consiste à écrire un algorithme de recherche binaire. Son temps d'exécution est O(log n) . Cependant, son problème est qu’il a besoin de données triées en entrée, sinon cela ne fonctionnera pas. Vous vous souvenez de l’exemple du livre déchiré et vous savez probablement pourquoi. Si vous avez effectué une recherche binaire parmi les éléments et qu'il n'en reste plus (c'est-à-dire qu'il n'y a tout simplement pas d'« aiguille » dans cette « pile »), vous avez besoin que la fonction renvoie false. La recherche binaire peut être implémentée de manière itérative ou récursive (David Malan a parlé de récursion dans la huitième conférence).
Après cela, exécutez la commande 
GO TO FULL VERSION