JASON HIRSCHHORN: Bienvenue à trois semaines, tout le monde. Nous avons un occupé, mais passionnante section avant de nous. Alors d'abord, parce que nous avons fait des progrès avec le cours, mais nous avons encore ont beaucoup d'apprentissage à faire, je suis vais vous montrer les gars des ressources qui devrait se révéler incroyablement utile lorsque vous approchez pas seulement votre problème fixe, mais aussi digérer tous le matériel que nous vous donnons gars des conférences et des shorts et section. Ensuite, nous allons passer les 20 premiers à 25 minutes de l'article va plus GDB, que vous pouvez ou ne pouvez pas avoir utilisé à ce point, mais il s'agit d'un outil incroyablement utile qui sera vous aider à déboguer vos programmes. Beaucoup d'entre vous ont utilisé printf dans le milieu de votre programme de comprendre ce qui équivalait à une variable. GDB est encore mieux que printf et ne vis pas votre code, car vous exécuter sur un fichier exécutable. Donc, nous allons passer en revue les 10 plus utiles les commandes dont vous avez besoin pour GDB, et nous sommes va aller sur un exercice ensemble afin dans le problème de définir trois et au-delà, vous peut utiliser GDB pour aider debug vos programmes. Et enfin, nous allons passer en revue certains tri et de recherche des algorithmes que vous avez vu en cours, et nous sommes va effectivement code, pas seulement pseudo, mais le code binaire de recherche, tri à bulles, et la sélection sorte. Alors d'abord, je veux aller sur les ressources. Il s'agit d'une longue liste, et c'est une police plus petite parce que j'ai eu beaucoup de s'adapter ici. Mais ce ne sera pas seulement vous aider, nouveau, avec les ensembles de problèmes et informations à digérer que vous avez appris, mais certainement, viendra le temps de test, ceux-ci être incroyablement utile. Alors d'abord, la conférence prend note. Si vous allez à cs50.net/lectures et faites défiler jusqu'à la semaine et le jour précis, vous verrez qu'il ya des notes pour chaque conférences, qui n'est pas simplement une transcription, mais une version modifiée de ce qui a été couverte en conférence avec le code extraits et autres friandises utiles. Je recommande vivement d'aller sur ceux-ci. Et puis aussi, il ya le code source disponible à partir de chaque conférence. Et encore, ces diapositives seront également disponible en ligne à cs50.net/sections ce soir. Donc, deuxième sont les courts métrages chaque semaine couvrent des sujets, généralement de 5 à 15 minutes. Et ceux espérons vous donnera un grande amorce sur différents sujets. Troisième - et c'est nouveau cette an - est study.cs50.net. Si vous n'avez pas vérifié, je recommandons fortement que vous le faites. Vous pouvez donc choisir un sujet. Nous avons des dizaines de sujets là-bas. Ainsi, par exemple, vous choisissez Fonctions. Il vous donne quelques diapositives et note sur les fonctions. Ce sont effectivement les diapositives que FO sont encouragés à utiliser au cours de notre présentations de la section. Il ya aussi des trucs et astuces pour faire face avec des fonctions, et il ya problèmes pratiques qui aident vous travaillez avec des fonctions. Nous vous donnons également des liens à court sur fonctions et les temps que les fonctions ont mis en lecture. Donc study.cs50.net, nouveau cette année, une ressource fantastique. Ensuite, je dois l'homme, qui est le manuel commande que vous pouvez exécuter à l' ligne de commande. Donc, si vous avez des questions au sujet d'un commande, par exemple, rand, qui nous rencontré la semaine dernière lors de la section et vous avez probablement rencontré dans votre problème réglé en passant dans le générer du code, mais si vous tapez l'homme rand, vous obtenez la page qui vous dit tout sur rand. Il vous donne ce qu'il faut, le paramètres qu'il faut, ainsi que le retour type et une brève description de cette fonction. Afin de vérifier rand. Il peut être un peu verbeux et confus, donc parfois je trouve que simplement googler ce que je veux savoir est la meilleure façon de trouver la réponse. Donc pratiquer avec Google. Obtenir de bons à Google. Il va devenir votre meilleur ami. Ainsi que Google, si vous ne pouvez pas le trouver sur Google, cs50.net/discuss, c'est le forum de discussion. Il ya des chances si vous avez une question, un de vos 700 + pairs a également question et peut-être demandé déjà dans la discuter forums et ont répondu il. Donc si vous avez une question commune ou Vous avez une question que vous pensez peut-être d'autres personnes auraient pu courir dans, consultez cs50.net/discuss. Enfin, les deux derniers, si vous voulez parler à un être humain réel, bureau heures du lundi au vendredi. Il ya aussi en ligne les heures de bureau pour les étudiants de vulgarisation. Et le dernier mais non le moindre, moi, le point d'exclamation. Vous avez tous mes coordonnées. Si vous besoin de quelque chose, s'il vous plaît jamais N'hésitez pas à me contacter. Toujours se sentir libre de le faire. Très peu d'entre vous m'ont ajoutée sur Gchat, de sorte que a été décevante, mais j'espère que ça va changer entre ce et la section suivante. Des questions jusqu'ici sur les ressources? Grand. Enfin, une autre fiche pour rétroaction, sayat.me/cs50. Vous pouvez me donner des commentaires anonymes sur la façon dont je le fais. C'était vraiment utile semaine dernière. J'ai eu quelques commentaires de vous les gars droit, après l'article, plus de d'autres étudiants qui ont regardé ce au cours de la semaine, et était incroyablement utile. Je vais essayer de limiter ma consommation de le mot «doux», mais je vais vous montrer mon enthousiasme et l'excitation d'autres moyens. Mais il y avait d'autres supplémentaires évaluations de fond, deux avantages et delta. Alors s'il vous plaît, je vous donne les gars commentaires sur vos ensembles de problèmes. N'hésitez pas à me donner des commentaires sur mon enseignement. Je suis ici pour vous les gars. Grand. C'est tout ce que j'ai pour la première section. Est-ce que quelqu'un a une des questions à ce jour? Et j'ai une note pour le centre de contrôle. étudiants d'extension m'ont envoyé des messages dire qu'ils ne reçoivent pas toute audio, mais ce n'est pas en mon pouvoir de fixer. Donc, j'espère, qui obtient résolu sous peu. Si vous regardez en ligne, salut, mais vous ne pouvez pas m'entendre. Alors d'abord, nous allons passer par GDB. GDB, comme je l'ai fait allusion au plus tôt, est un outil de débogage beaucoup mieux que printf. Donc, pour commencer avec GDB, les gars, si vous voulez ouvrir votre appareil et prendre le fichier que j'ai envoyé à vous plus tôt - ce fichier sera également disponible en ligne en un peu - et exécuter GDB. / le nom du fichier. Tout d'abord, bien sûr, vous devez compiler déposer parce GDB ne fonctionne que sur fichiers exécutables. Mais si jamais vous voulez commencer GDB, la première chose que vous faites, vous avez GDB. / César. Donc, c'est le nom du programme que nous sommes aller avec elle en ce moment. Donc, je vais écrire rendre à César, ce qui me donnera un fichier exécutable ici en vert. Et puis je vais courir GDB. / Cesar. Et là vous allez. Vous voyez, nous avons un texte me disant sur la version de GDB, me donner des informations de garantie, et nous avoir l'invite du PIB, qui ressemble un peu de comme notre invite de ligne de commande, mais vous voyez qu'il est ouvert paren, GDB, paren proches. Avant de continuer et déboguer ce fichier que je vous ai envoyée, permettez-nous sur quelques commandes utiles si nous avons un sens de ce que nous allons couvrir. Ces commandes sont répertoriées ici dans le ordre dans lequel j'utilise généralement eux. Donc, je commence mon programme en exécutant GBD. / Nom du programme, dans ce cas, César. Et puis la première chose que je fais de 99,9% du temps est de type break signifie. Cela définit un point d'arrêt au principal. Essentiellement, ce que vous faites là est le programme va s'arrêter à principal de sorte que vous pouvez commencer à l'examiner ligne par ligne, plutôt que de courir tous le chemin à travers. Vous pouvez interrompre à différents points dans votre code, mais principale est généralement un bon endroit pour commencer. La prochaine commande je cours est géré. Cela commence le programme en cours, et si vous avez besoin d'entrer en ligne de commande arguments, vous l'exécutez cette commande. Exécuter avec les arguments. Donc, puisque nous allons sur une version de C, qui est le programme que vous les gars écrit pour pset deux - celui-ci, bien sûr, a quelques bugs dans ce que nous espérons que nous trouverons - nous allons lancer l'exécution de certaines commandes arguments de ligne parce que César, comme vous les gars savent par le problème mis spec, prend un certain arguments de ligne de commande. Le prochain couple de commandes, la prochaine on est effectivement appelée prochaine. Que l'on vous prend ligne par ligne dans votre programme. Alors frapper n puis Entrée vous amène à la ligne suivante, l'exécution d' la ligne précédente. Étape vous amène non seulement à la ligne suivante, mais il vous emmène fonctions à l'intérieur. Donc, si vous avez écrit une fonction dans votre code ou si vous voulez découvrir un i, par exemple, vous pouvez frapper s, et plutôt que d'aller à la prochaine ligne de le fichier que vous allez par le droit maintenant, vous allez vraiment vous entrez dans cette fonction et voir son code. Liste montre, en très convivial format, les 10 ou si les lignes autour de où vous êtes actuellement dans votre code de sorte que vous pouvez réellement voir le fichier plutôt que d'avoir à permuter en arrière et vient entre différents points de vue. L'impression est comme printf, comme son nom l'indique. Cela vous montre ce qu'est une variable égale. Information habitants est vraiment utile. Il s'agit d'une version spéciale de l'impression. Information habitants vous montre tous les locaux des variables, tous imprime pour vous qui sont disponibles actuellement. J'ai donc généralement, plutôt que d'avoir à imprimer les quatre variables que je suis curieux de savoir si je suis dans une boucle, pour exemple, je viens d'écrire des informations habitants, et ça me ce que mon compteur i montrer égaux, ainsi que le tableau que je suis travail égal. Enfin, continuer. Taper pause vous arrête au point de rupture. Vous pouvez vous promener à travers la ligne de Conformément à la prochaine étape et. Continuer exécute le programme pour votre prochain point de rupture ou jusqu'à la fin si il n'y a plus de points de rupture. Désactiver supprime les points de rupture si vous a décidé la pause principale était inapproprié, vous voulez le mettre ailleurs. Et enfin q, stoppé, sort de GDB. Donc ce programme. / César, nous allons de regarder à travers ce moment et nous vont utiliser GDB pour trouver les bugs dans ce programme. J'ai couru ce programme plus tôt avec Vérifiez 50, et j'ai eu un froncement de sourcils. Tout ce qu'il existait, elle a établi, il passé beaucoup de tests, mais pour une raison quelconque, il n'a pas passé le cinquième test, tournant BARFOO, tous les bouchons, en E-D-U-I-R-R, tous les bouchons, en utilisant trois comme une clé. Je suis assez proche. Je suis descendu par une lettre. Donc, il ya une petite erreur ici. J'ai regardé dans mon code. Je ne pouvais pas comprendre. Heureusement, vous avez peut m'aider comprendre ce que ce bug est. Donc, c'est l'erreur que nous sommes chercher. Passons en GDB. Encore une fois, je n'ai plus GDB. / César, alors maintenant nous sommes dans GDB. Et ce qui est le premier chose que je dois faire? Je viens entré GDB. Quelqu'un me donner une bonne commande à entrer. ÉTUDIANT: Casser principale. JASON HIRSCHHORN: Pause principale. Fantastique. Tapons que po Les gars, vous pouvez regarder ici ou suivez long sur vos ordinateurs. Cassez principale, et vous verrez une point de rupture a été fixé à - il me donne une adresse de mémoire étrange, et il me donne aussi le numéro de la ligne. Si je devais revenir sur ce dossier, Je voudrais réaliser que le principal arrivé sur la ligne 21. Que dois-je exécuter prochaine? Est mon programme en cours d'exécution? Non. Alors, que dois-je exécuter prochaine? ETUDIANT: Exécuter. JASON HIRSCHHORN: Exécuter. Dois-je exécuter juste terme, ou devrais- J'ajoute quelques autres choses? ETUDIANT: Exécuter avec l'argument. JASON HIRSCHHORN: Exécuter avec les arguments de la commande. Et puisque je suis le débogage d'un très spécifique cas, je dois entrer dans cette commande argument de ligne. Je vais donc ne cours de trois, ce qui est, encore une fois, la sortie que j'ai obtenu à partir de Check 50. Démarrage du programme. Nous passons par quelques lignes. Vous allez maintenant voir que nous sommes sur la ligne 21. Comment puis-je savoir que nous sommes sur la ligne 21? Parce que si vous regardez à gauche de ma fenêtre de terminal, il il dit à la ligne 21. Et cela me donne, en fait, le code qui est à la ligne 21. Donc, je me suis mal exprimé plus tôt. Principale n'est pas vraiment à la ligne 21. Principale est un couple de lignes ci-dessus 21. Mais à la ligne 21, c'est où nous cassons. Cette ligne de code a non encore exécutée. C'est important. La ligne que vous voyez n'a pas encore été exécuté. C'est la ligne de code suivante vous êtes sur le point d'exécuter. Donc, la ligne suivante, comme vous les gars sont probablement familier avec, est-ce état de la vérification pour voir si j'ai conclu un argument de ligne de commande. Et un i, ce qui est la deuxième partie de ce faire? Qu'est-ce qu'un i? ETUDIANT: Modification à un nombre entier. JASON HIRSCHHORN: Désolé? ETUDIANT: Ça change la argument un entier. JASON HIRSCHHORN: Donc un i changements arg v1 d'une chaîne en entier. Et puis qu'est-ce qu'il contrôle? ETUDIANT: Si il ya une deuxième argument de ligne de commande, côté de l'exécution du programme. JASON HIRSCHHORN: Et ce qui est la seconde moitié de cette Expression booléenne contrôle? Cette partie ici, un i? ETUDIANT: Si elle est négative. JASON HIRSCHHORN: Faire en sorte que? ÉTUDIANTS: Faire en sorte qu'il est, en effet, positif. JASON HIRSCHHORN: Exactement. Ceci est vérifié pour voir si elle est négatif, et si elle est négative, je avoir un sentiment de puissance de la prochaine ligne être me crier à l'utilisateur. Donc, nous allons frapper fin d'exécuter cette ligne. Nous ne voyons pas cette ligne que vous les gars peut-être s'attendre à voir crier à l' utilisateur, puis revenir, parce cette ligne ne s'est pas exécuté. Je suis entré 3. Donc, je n'ai, en fait, entrer deux commande arguments de la ligne, et 3 est supérieur à zéro. Donc, nous avons vu que la ligne, nous avons exécuté, mais nous n'avons pas intervenons l'intérieur de la condition if. Alors maintenant, à côté, je vois que je suis la mise en clé int équivaut à une i arg v1. Donc c'est moi créer une clé variable. Donc, si j'imprime touche en ce moment, parce que qui vous permet de voir la valeur dans la variable, clé est égale à 47. C'est bizarre, mais bien sûr, c'est parce que je n'ai pas encore exécuté cette ligne. Alors maintenant, si je frappe n, exécutez cette ligne, et faire touche d'impression, clé sera égale à 3, c'est ce que nous nous attendons à égal. Encore une fois, dans GDB, la ligne que vous voyez vous n'avez pas encore exécuté. Vous devez frapper n ou s ou un nombre d'autres commandes à fait exécuter cette ligne. Imprimer touche. De clés à 3. Jusqu'ici, tout va bien. String est le texte brut. Disons exécuter cette ligne. Je reçois une chaîne de l'utilisateur. Voyons dans mon chèque de 50, je entrer BARFOO tous les bouchons, donc c'est ce que je vais entrer. Si j'imprime maintenant texte brut. Vous verrez qu'il est égal à une chaîne. Il me donne une autre hexadécimal bizarre nombre, mais il le fait dans fait dire que ma chaîne est BARFOO. Si je voulais voir ce que touche égale à ce point, comment pourrais-je vérifier touche? ETUDIANT: Imprimer touche. JASON HIRSCHHORN: Imprimer touche, exactement. Et effectivement, il ya un raccourci. Si vous êtes fatigué de taper impression, vous pouvez simplement taper p. Donc touche p fait exactement la même chose. Et encore, je vois est égal à 3. Si je voulais savoir ce que les deux clé et BARFOO égalé à la fois mais j'étais fatigué de taper chaque un individuellement, je pourrait Infos habitants. Cela me donne égaux clés 3. Texte brut est égal BARFOO. Il me donne aussi ces deux choses bizarres au sommet, cette variable i et cette variable n. Ceux-ci sont réellement existant dans mon programme principal. Nous ne les avons pas encore rencontré, mais comme un aperçu, les ma pour exister dans la boucle. Alors maintenant, ils égalent quelque étrange nombre parce qu'ils n'ont pas été encore initialisés, mais ils existent encore dans la mémoire, de sorte qu'ils sont tout simplement mis à une valeur d'ordures. Mais nous ne voyons clé dans la plaine texte là. Donc, je vais exécuter cette ligne, ligne 34, la boucle pour. Nous allons sauter dans le pour la boucle en frappant n. Et nous sommes à l'intérieur de la boucle for. Nous sommes à notre première vérification. Et encore, ceux-ci devraient sorte de regarder familier pour vous, parce que c'était un César programme qui a été écrit, mais encore une fois, a une sorte de bug. Et maintenant, si je le fais d'info habitants, parce que je suis l'intérieur de cette boucle, vous verrez que i est égal à zéro, comme nous le prévoyons. C'est ce que nous avons à et initialisé il dans la boucle. n est égal à 6. Cela fait également sens parce que nous avons mis en à la strlen de texte brut. Donc, je tiens à faire d'info locaux ou impression à la variable souvent pour s'assurer que tout est toujours ce Je m'attends à ce qu'il égale. Dans ce cas, tout est ce que je m'attends à ce qu'il égale. Commençons donc par le déplacement cette boucle. La ligne que je suis sur la ligne 36 est, si simple texte i est supérieur à un et plaine moins i est inférieur ou égal à z. Je sais que mon problème n'est pas de ma première lettre, c'est la deuxième lettre. Si nous regardons en arrière à l'arrivée 50, B va à E amende. Je prends le A et le laisser tel un A, pas changer de D. Alors quelque chose ne va pas avec la deuxième lettre. Donc, je vais passer il en une seconde. Mais si je ne veux vérifier ce que plaine texte que j'ai égalé dans ce cas particulier cas, je pense qu'il devrait être quoi? Que dois-je le texte brut égal dans ce premier tour par la boucle? ÉTUDIANT: Zero? JASON HIRSCHHORN: Texte brut de I? Il devrait donc être capitale B. J'ai, bien sûr, est égal à zéro, mais le texte brut support zéro support fermé est égal à B parce que les chaînes, comme nous l'avons vu la semaine dernière, sommes ensemble, nous obtenons l' premier caractère à partir de cela. Encore une fois, si j'ai imprimé le texte brut de Moi, je fais, en fait, obtenir le caractère B. Et c'est propre, non? Je n'ai pas vraiment le texte brut I. Ce n'est pas l'une des variables j'ai mis ou initialisé, mais vous pouvez imprimer toute une foule de choses si vous le souhaitez. Mais passons à travers. Si le texte brut I est supérieur à A et le texte brut I est inférieur ou égal à Z, qui est clairement le cas parce que nous avons un B. du capital Je vais courir une certaine maîtrise sur elle. Nous avons vu que les mathématiques la semaine dernière, donc nous allons tenir pour acquis que cela fonctionne droit selon Vérifiez 50. Ces accolades, le premier montré que je sortais le si condition, la seconde a montré une que je suis sortie de la boucle. Et maintenant quand je frappe suivante, nous verrons nous sommes de retour à la boucle de nouveau. Nous allons à travers la pour boucle de nouveau. Revenons en fait dans la deuxième itération de la boucle et le type Info habitants. Donc, nous sommes dans la deuxième itération de notre boucle pour. I est égale à 1, dont nous attendons. N est égal à 6, dont nous attendons. Est égal à la touche 3, dont nous attendons. Et texte brut, vous verrez, égal EARFOO maintenant, pas plus parce BARFOO dans notre itération précédente, le B était changé de capital E. Alors que nous sommes sur de rencontrer le problème, si ce C'est là que nous allons plonger dans le débogage. Mais quelqu'un at-il des questions sur ce que nous avons fait jusqu'à présent? Fantastique. Donc, nous sommes sur le point d'exécuter ce si état, plaine support de texte Je fermai support supérieure à A et texte brut I inférieur ou égal à Z. Mais avant de Je vais dans les détails, car c'est là que Je sais que mon erreur, je tiens à souligner hors texte brut de I. Alors Mettons impression. Il ne égaler le caractère A, de sorte que semble jusqu'ici, tout va bien et bon. Donc, je m'attends à ce que la ligne par ma logique, cette ligne doit être vrai. C'est une lettre majuscule. Mais si je frappe n, nous ne réalisons que ce ligne, en fait, ne s'est pas exécuté. Je sautai à l'autre si. Pourquoi est-ce arrivé? ETUDIANT: Parce que vous avez votre état de texte brut est supérieur que A, non égal ou supérieur à. JASON HIRSCHHORN: Donc, j'ai eu mon texte brut I est supérieur à A, qui n'est pas supérieure supérieure ou égale à. Donc clairement, la capitale A n'a pas déclencher cette si la condition, et nous l'avons fait pas entrer dedans, et nous avons fait pas faire le changement nécessaire. Alors, c'est ça, en fait. J'ai pensé que mon bug. Je pourrais retourner dans mon fichier source, changer, et le mettre à jour et Vérifiez exécuter 50 fois. Mais nous allons voir, juste pour la pédagogie de même, si je continue. Else if n'exécute pas non plus, mais ce qui équivaut à la place est la commande cela ne change pas. Donc ce n'est pas du tout changé, et si je imprimer le texte brut ici, nous verrons aller à travers cette boucle n'a pas, en fait, changer cette deuxième caractère du tout. C'est toujours un grand A. Encore une fois, nous débogué notre erreur. Nous avons réalisé qu'il y avait une certaine logique manquant. Et nous débogué il avance avant exécuter effectivement cette ligne, mais vous auriez remarqué si nous avions juste Suivant frapper et sauter à cette autre si, ce qui signifie que que si la condition n'était pas vrai. Nous n'avons pas, en effet, obtenir le résultat que nous attendions. Alors nous aurions pu être invité, avions nous pas été aussi astucieux, à regarder que si l'état et de vérifier si, en fait, notre condition devrait évaluer à vrai dans le contexte actuel. C'est tout pour le débogage de ce programme. Quelqu'un at-il des questions? Quelle est la commande que je pourrais frapper à quitter GDB? Q. Et puis je vais être amené, quitter de toute façon? Oui ou non. Je vais frapper oui, et je l'ai quitter GDB. C'était donc une amorce rapide de GDB. En fait, dans un scénario réel, Je l'ai fait pendant les heures de bureau. Je GDBed ce programme exact heures de bureau avec un étudiant. Et si nous revenons aux commandes, nous avons vu avant, nous avons utilisé la rupture principale, première chose que nous avons fait. Nous avons utilisé terme avec des arguments de ligne de commande, deuxième chose que nous avons fait. Nous avons utilisé la prochaine beaucoup à se déplacer nous à travers les lignes. Et encore, la version courte de est à côté n. C'est dans les parenthèses en gris sur la diapositive. Nous n'avons pas utilisé l'étape, mais nous n'avons pas nécessairement besoin de ce cas. Mais nous pourrions utiliser dans un peu plus tard aujourd'hui si nous sommes le débogage, pour exemple, la recherche binaire lorsque binaire recherche est appelé dans un document distinct fonction, mais il ya une erreur avec elle. Nous allons vouloir entrer dans l'appel à la recherche binaire et effectivement déboguer. Liste, nous n'avons pas utiliser parce que nous avions un bon sens de notre code, mais si je ne voulait se faire une idée de ce que je Code était là, je ne pouvais tout simplement utiliser la liste. Imprimons, nous avons utilisé, nous avons utilisé les habitants d'info. Continuons, nous n'avons pas besoin d'utiliser dans ce cas, ni ne nous besoin d'utiliser désactivons, mais nous avons fait usage quitter. Encore une fois, ces 10 commandes, pratiquer. Si vous comprenez ces 10 commandes, vous devriez être pour le débogage tout délivrer GDB. Donc, nous sommes sur le point d'aller plus loin, de nouveau, à la cœur de l'article d'aujourd'hui, aller plus ces tri et de recherche algorithmes. Avant de le faire, à nouveau, des questions, commentaires, préoccupations pour GDB? Donc tout le monde est va utiliser GDB plutôt que printf? Donc tout le monde, à cause de la perpétuité, tout le monde hoche la tête de leur droit de la tête maintenant, je vais vous voir à des heures de bureau et tous les FO vous et voir ils diront, montre-moi comment utiliser GDB, et vous serez en mesure pour leur montrer, non? Sorte de? Peut-être que je l'espère. Cool. Nous allons donc passer à tri et de recherche. Vous voyez, j'ai une liste déjà triée pour nous, mais cela ne va pas d'être toujours le cas. Ainsi, dans le problème posé cahier des charges problème réglé trois, vous avez short que vous pouvez regarder, et il fait vous demande de regarder ces courts métrages. Toujours en conférence la semaine dernière, nous sommes allés beaucoup de ces algorithmes, donc je suis ne va pas passer du temps dans la classe va au cours de ces algorithmes à nouveau ou dessin photos pour la façon dont ces algorithmes fonctionnent. Encore une fois, cette information, vous pouvez ré-montre conférence, ou que l'information est capturé exceptionnellement sur le short pour ces recherches, tous qui sont disponibles à cs50.net. Ainsi, au lieu, ce que nous allons faire est d'écrire ces programmes. Nous avons un sens, un modèle mental, de la façon dont ils travaillent, et si ce que nous allons à faire est de coder pour de vrai. Nous allons transformer ce modèle mental, cette image, si vous voulez, dans le code réel. Et si vous étiez un peu confus ou flou sur le modèle mental, je suis totalement d' comprendre. Nous ne sommes pas réellement aller sauter sur le code d'emblée. Ainsi, alors que cette invite dans cette diapositive demande de coder recherche binaire, et en fait, une version itérative d' recherche binaire, la première chose que je voulez vraiment que vous faites est écrire du pseudo. Donc, vous avez ce modèle mental de la façon dont les travaux de recherche binaire. Prenez une feuille de papier si vous avez un facilement disponibles, ou ouvrir un éditeur de texte, et je voudrais tout le monde à écrire. Prendre quatre minutes pour écrire le pseudocode pour la recherche binaire. Encore une fois, pensez à ce modèle mental. Je vais venir autour si vous avez des questions et nous pouvons dessiner l'image sur. Mais d'abord, avant de commencer la programmation, Je voudrais écrire la pseudocode pour la recherche binaire quand nous plonger, nous avons une certaine direction que là où nous devrions tête. ETUDIANT: Pouvons-nous supposer le tableau de valeurs que nous obtenons est déjà triés? JASON HIRSCHHORN: Donc, pour la recherche binaire de travailler - excellente question - vous prendre dans un tri tableau de valeurs. Supposons donc que cela fonctionnera. Nous allons revenir à cette diapositive. Vous verrez dans le pourpre de la fonction déclaration est bool binary_search int valeur, les valeurs int, int n. Cela devrait vous être familier si vous avez déjà approché ou obtenu votre mains sales avec le jeu de problème. Mais c'est votre déclaration de fonction. Encore une fois, ne devrait pas besoin de s'inquiéter que beaucoup en ce moment. Ce que je veux vraiment que vous faites est de prendre quatre minutes pour binaire pseudo- recherche, puis nous irons plus que comme un groupe. Et je ferai un tour. Si vous avez des questions, n'hésitez pas sans lever la main. Pourquoi ne prenez-vous pas deux minutes pour finir le pseudo? Je sais que cela peut sembler ridicule nous passons beaucoup de temps sur quelque chose qui n'est même pas en fait dans C, mais surtout pour les plus algorithmes et problème difficile ensembles que nous devons comprendre, à partir de pseudo ne pas se soucier sur la syntaxe, juste se soucier la logique, est incroyablement utile. Et de cette façon, vous n'êtes pas résoudre deux problèmes extrêmement difficiles à la fois. Vous êtes juste en se concentrant sur la logique, et alors vous vous déplacez dans la syntaxe. OK. Commençons en passant par le pseudo-code. J'ai écrit ici, binaire Recherche pseudo. Nous écrirons ce sur la monter ensemble. Ou je vais l'écrire et vous donnerai moi les invites dont j'ai besoin. Alors quelqu'un peut-il me donner la première ligne de la pseudo-vous écrit pour la recherche binaire? Oui, Annie? Étudiant: Alors que la longueur de la la liste est supérieur à zéro. JASON HIRSCHHORN: Bien que la longueur de la liste supérieur à zéro. Et encore une fois, nous voyons un certain C-consultant choses syntaxiques sur ici. Mais la grande majorité est en anglais. Quelqu'un at-il une ligne qu'ils mettent avant cela dans leur pseudo-code? ETUDIANT: Récupère un tableau de nombres triés. JASON HIRSCHHORN: Vous avez écrit "obtenir un tableau de nombres triés. "par la déclaration de fonction, nous passerons un tableau de nombres triés. ETUDIANT: [inaudible]. JASON HIRSCHHORN: Donc, nous allons avoir. Mais oui, si nous n'avions pas, nous aurait besoin de trier notre tableau de chiffres, parce que la recherche binaire ne fonctionne que sur les tableaux triés. Ainsi, alors que la longueur de la liste est égal à zéro, je suis allez mettre dans des accolades pour le faire paraître un peu plus comme C. Mais alors, semble à la carte sur un tout en boucle, donc à l'intérieur de ce tout boucle qu'est-ce que nous devons faire de la recherche binaire? Quelqu'un d'autre qui ne m'a pas donné une répondre encore mais qui a écrit cela? ETUDIANT: Allez au milieu de la liste. JASON HIRSCHHORN: Tom. Allez au milieu de la liste. Et la question de suivi, ce qui faisons-nous une fois que nous sommes à la milieu de la liste? ETUDIANT: Faites une vérification si c'est le numéro que vous cherchez. JASON HIRSCHHORN: Excellent. Allez au milieu de la liste et de vérifier si notre valeur est là - fantastique. Quelqu'un at-il quelque chose d'autre qui était différent que cela? C'est exactement ça. La première chose que nous faisons à la recherche binaire est d'aller au milieu de la liste et vérifier pour voir si notre valeur est là. Donc, je suppose que si notre valeur est là, que faisons-nous? ETUDIANT: Nous revenons zéro [inaudible]. JASON HIRSCHHORN: Ouais, si notre valeur est là, nous l'avons trouvé. Donc, nous pouvons dire d'une certaine façon, mais ce fonction est définie, nous disons l'utilisateur nous l'avons trouvé. Si elle n'est pas là, cependant, c'est où cela devient difficile. Donc, si elle n'est pas là, quelqu'un d'autre qui a été de travailler sur la recherche binaire ou a une idée maintenant, que faisons-nous? ETUDIANT: question. JASON HIRSCHHORN: Oui? ETUDIANT: Est ce que le tableau déjà trié? JASON HIRSCHHORN: Oui, nous supposons le tableau est déjà trié. ETUDIANT: Ainsi donc, vous devez vérifier si la valeur que vous voyez est supérieure à la valeur que vous voulez, vous pouvez vous déplacer au milieu de l'autre moitié. JASON HIRSCHHORN: Donc, si le milieu de la liste est supérieur à ce que nous sommes cherchez, alors nous n'avons quoi? Nous nous déplaçons où? ETUDIANT: Vous voulez passer à la moitié de la liste avec chiffres inférieurs à celui. JASON HIRSCHHORN: Donc, nous allons appeler que la gauche. Donc, si du milieu est plus grande, nous pouvons rechercher la moitié gauche de la liste. Et puis par la recherche, ce qui je veux dire par la recherche? ETUDIANT: [inaudible]. JASON HIRSCHHORN: Nous allons au milieu. Nous répétons fait cette chose. Nous revenons sur notre boucle while. Je vais vous donner le dernier - d'autre, si, du milieu est inférieure à ce que nous faisons, que faisons-nous ici? ETUDIANT: Allez vers la droite. JASON HIRSCHHORN: Rechercher la droite. Ce qui semble bon, mais quelqu'un at-il tout ce que nous risquons de rater ou tout ce que vous mettez dans votre pseudo-code? Donc, c'est ce que nous avons fait jusqu'ici. Bien que la longueur de la liste est supérieur à zéro, nous allons aller au milieu de la liste et vérifier si notre valeur est là. Si le milieu est plus grande, nous allons recherche à gauche, sinon si le milieu est moins, nous allons chercher la droite. Donc, nous avons tous eu une certaine familiarité avec les termes que nous utilisons en informatique et les outils que nous avons. Mais vous déjà remarqué que nous étions parler en anglais, mais nous avons trouvé un beaucoup de choses qui semblaient à la carte à outils dont nous disposons dans notre trousse d'outils de codage. Donc, dès le départ, nous ne sommes pas va effectivement coder encore. Que voyons-nous ici en anglais que les cartes à des choses que nous pouvons écrire en C? ETUDIANT: Bien. JASON HIRSCHHORN: Bien. Donc tout ici cartes sur à quoi? ETUDIANT: Une boucle while. JASON HIRSCHHORN: Une boucle while? Ou peut-être, de façon plus générale, une boucle. Nous voulons faire quelque chose encore et encore. Donc, nous allons coder une boucle. Et nous savons déjà, parce que nous avons fait cette une couple de fois et nous avoir beaucoup d'exemples là-bas, comment fait d'écrire cet indice pour une boucle. Ce qui devrait être assez facile. Nous devrions être en mesure d'obtenir que commencé assez rapidement. Que voyons-nous ici? Quels sont les autres structures syntaxes, les choses que nous connaissons en C,-nous ont déjà un sens basé hors des mots que nous utilisions? Oui, Anna? [Inaudible] je plaisante. Anna, aller de l'avant. ETUDIANT: Si et d'autre. JASON HIRSCHHORN: Si et d'autre - ici. Alors qu'est-ce que ceux qui ressemblent? ETUDIANT: Une instruction if autre. JASON HIRSCHHORN: Ouais, conditions, non? Donc, nous aurons probablement besoin de écrire quelques conditions. Et encore une fois, mais peut-être déroutant au d'abord, nous avons généralement un sens maintenant de la façon d'écrire les conditions et la syntaxe de la condition. Et si nous ne le faisons pas, nous venons de voir les syntaxe de la condition, couper et coller que, parce que nous savons que nous besoin d'un état ici. Toutes les autres choses que nous voyons que la carte sur choses que nous pourrions avoir besoin de le faire en C? Ouais, Aleha? ETUDIANT: C'est peut-être évident, simplement en vérifiant si un valeur est égale à quelque chose. JASON HIRSCHHORN: Alors, comment pouvons nous vérifions et - il faut aller dans le milieu de la liste et de vérifier si notre valeur est là? Comment faisons-nous cela en C? Quelle est la syntaxe pour cela? ETUDIANT: Equals, égaux. JASON HIRSCHHORN: Equals, égaux. Donc ce contrôle va probablement être un signe égal, égaux. Donc, nous allons savons que nous devons que quelque part. Et en fait, juste à l'écrire, nous voyons ces autres choses. Nous allons avoir à faire quelques opérateurs de comparaison là - fantastique. Donc, il ressemble réellement, par et un grand, nous n'avons pas écrit mot de code C encore. Mais nous avons le modèle mental bas via des conférences et les shorts. Nous avons écrit pseudo-code en tant que groupe. Et déjà, nous avons 80% si elle n'est pas 90% de ce que nous devons faire. Maintenant, nous avons juste besoin de coder , ce qui de plus, est un problème non-trivial à résoudre. Mais au moins, nous sommes coincés sur la logique. Au moins maintenant, quand nous allons à des heures de bureau, Je peux dire que je sais ce que je dois à faire, mais pouvez-vous rappeler me de la syntaxe? Ou même si les heures de bureau sont entassés, vous Google peut pour la syntaxe, plutôt que d'être coincé sur la logique. Et encore une fois, plutôt que d'essayer de résoudre la logique et les problèmes de syntaxe tous à la fois, il est souvent préférable d' briser ces deux problèmes difficiles loin dans deux les plus faciles à gérer et faire le pseudo-code en premier et ensuite le code en C. Voyons donc ce que j'ai fait pour le pseudo-code à l'avance. Bien que la longueur de la liste est supérieur à zéro, regarder le milieu de la liste. Si nombre trouvé retourné vrai, d'autre si plus grand nombre, la recherche gauche. Sinon, si faible nombre, la recherche droite, retourner false. Alors que l'air presque identique sinon presque identique à ce que nous écrivions. En fait, Tom, que vous avez dit la première, briser le milieu de la liste et si nombre trouvé dans deux états est en fait ce que j'ai fait. Je les y combiné. Je devrais avoir écouté vous la première fois. Donc, c'est le pseudo-code que nous avons. Si vous voulez maintenant, désolé, aller revenir à notre problème initial. Laissez-nous le code binary.c. Ainsi, mettre en oeuvre une version itérative d' recherche binaire en utilisant ce qui suit déclaration de fonction. Et vous n'avez pas besoin de copier vers le bas pour l'instant. Je vais en fait d'ouvrir vous ici binary.c. Donc, il ya la déclaration de fonction dans le milieu de l'écran. Et vous verrez j'ai pris le pseudo-code de sur mes côtés, mais presque identique à ce que nous écrivions, et mettre que pour vous. Alors maintenant, nous allons prendre cinq minutes pour coder cette fonction. Et encore une fois, si vous avez des questions, levez la main, laissez-moi savoir, je vais venir autour. ETUDIANT: [inaudible]. JASON HIRSCHHORN: Donc j'ai pris le binaire définition de recherche en haut, sur la ligne 12. C'est ce que j'ai pour ma diapositive. Et puis tout ce pseudo-code que je viens de copier et coller à partir de la diapositive, pseudo-code diapositive. Je ne suis toujours pas entendre [inaudible]. Donc, si vous avez terminé votre mise en œuvre, je tiens à le vérifier. Je vous ai envoyé le fichier Helpers.h précédemment dans cette classe. Et il sera disponible en ligne ainsi pour le téléchargement pour regarder les gens cette fois de l'article retardée. Et je viens d'utiliser la distribution générique Code de pset3. J'ai donc pris find.C, utiliser mon fichier Helpers.h plutôt que le fichier Helpers.h qui est donnée dans le code de distribution. Et je devais faire un autre changement dans find.C plutôt que d'appeler tout simplement recherche, appeler binary_search. Donc, si vous voulez tester votre code, savent que c'est la façon de le faire. En fait, lorsque nous allons exécuter ce code en ce moment, je viens de faire une copie de mon répertoire pset3, encore une fois, échangé les fichiers Aides et puis faites que changer dans find.C appeler binary_search plutôt que de simplement chercher. JASON HIRSCHHORN: Oui. Vous avez une question? ETUDIANT: Passons. JASON HIRSCHHORN: Pas de soucis. Eh bien, nous allons commencer. Nous allons coder cela comme un groupe. Une autre note. Encore une fois, ce n'est, peut facilement être échangé dans de problème Set Trois. J'ai mon fichier Helpers.h qui, plutôt que la Helpers.h on nous donne, déclare recherche binaire, bulle tri et la sélection sorte. Et dans find.c vous remarquerez sur la ligne, quel est ce, ligne 68, nous appelons binaire recherche plutôt que la recherche. Encore une fois, le code est disponible en ligne ou le code qui vous êtes la création en ce moment peut être facilement échangé en p pour la série 3 pour le vérifier. Mais d'abord, nous allons Recherche de code binaire. Notre déclaration de fonction, nous revenons un bool. Nous prenons un nombre entier appelé valeur. Nous prenons un tableau d'entiers appelé valeurs, et nous prenons n être la taille de la matrice. Sur la ligne 10, ici, j'ai forte comprennent stdbool.h. Est-ce que quelqu'un sait pourquoi c'est là? Alors qu'est-ce que cette ligne de code fait? ETUDIANT: Il vous permet de utiliser un type de retour bool. JASON HIRSCHHORN: Exactement. ETUDIANT: Ou c'est une bibliothèque qui permet d'utiliser un type de retour bool. JASON HIRSCHHORN: Donc, la forte comprennent ligne stdbool.h me donne une certaine les définitions et les déclarations pour des choses que je suis autorisé à utiliser dans cette bibliothèque. Donc parmi ceux se disant qu'il ya ce type bool appelé, et il peut être vrai ou faux. C'est ce que cette ligne fait. Et si je n'ai pas eu cette ligne, je voudrais avoir des ennuis pour la rédaction de ce mot ici, bool, juste là. Exactement. J'ai donc besoin que dans ce code. OK. Donc, encore une fois, est un processus itératif la version, pas un récursive. Alors laissez-nous commencer. Commençons par cette première ligne de code pseudo. Et nous espérons, nous le ferons - ou pas d'espoir. Nous allons faire le tour de la salle. Nous allons ligne par ligne, et je vais vous aider vous avez compris la ligne que nous avons besoin d'écrire en premier. Ainsi, alors que la longueur de la liste est supérieur à zéro. Commençons à l'avant. Quelle ligne devrais-je écrire ici, dans le code? ETUDIANT: Bien parenthèses n est supérieur à 0. JASON HIRSCHHORN: Bien n est grand que 0. Donc n est la taille de la liste, et nous vérifions si - [VOIX interposition] JASON HIRSCHHORN: - Pardon? Étudiant: Comment savons-nous que n est la taille de la liste? JASON HIRSCHHORN: Désolé. Par la spécification pset, la recherche et des fonctions de tri, vous devez écrire, n est la taille de la liste. J'ai oublié d'expliquer ici. Mais oui. n est la taille de l' la liste, dans ce cas. Ainsi, alors que n est supérieur à 0. OK. Cela peut se révéler un peu problématique cependant, si les choses se passent. Parce que nous allons continuer à connaître la taille de la liste tout au long de cette fonction, mais dire que nous partons avec un tableau de 5 entiers. Et nous allons à travers et nous avons maintenant rétréci vers le bas un tableau de 2 entiers. Dont 2 entiers est-ce? La taille est 2 maintenant que nous voulons Regardons, mais qui 2 est-ce? Cela fait-il sens, cette question? OK. Je vais demander à nouveau. Donc, nous commençons avec cet ensemble de 5 entiers, et n est égal à 5, non? Nous courons à travers ici. nous allons probablement changer la taille, droit, comme les choses se passent. Qui est ce que nous disons que nous voulons faire. Nous ne voulons pas chercher la chose complète à nouveau. Donc disons que nous changeons à 2. Nous prenons la moitié de la liste qui est étrange. Il suffit donc de choisir 2. Alors maintenant, est égal à n 2. Je m'excuse pour les pauvres marqueurs effaçables à sec. Droite? Et nous sommes à la recherche dans la liste à nouveau avec une liste de taille 2. Eh bien, notre tableau est encore de taille 5. Nous disons que nous ne voulons recherche 2 places en elle. Alors que deux spots sont ceux-là? Cela fait-il sens? Sont-ils les laissés 2 points? Sont-ils les bonnes 2 places? Sont-ils les moyens 2 places? Nous avons brisé le problème vers le bas, mais nous ne savons pas réellement quelle partie de le problème que nous cherchons toujours à, tout en ayant ces 2 variables. Nous avons donc besoin d'un peu plus de, tandis que n est supérieur à 0. Nous devons savoir où que n est dans notre tableau réelle. Donc, quelqu'un at-il une changer cette ligne? La plupart de cette ligne est parfaitement correct. Y at-il un autre ajout? Pouvons-nous échanger quelque chose que n faire de cette ligne un peu mieux? Mm-hm? ETUDIANT: Pouvez-vous initialiser une variable comme la longueur de n qui va ensuite être utilisé plus tard dans la fonction? JASON HIRSCHHORN: Donc initialiser une longueur variable de n, et nous utilisons plus tard? Mais alors que nous venons de mettre à jour la longueur et nous encore rencontrer ce problème lorsque nous réduire la durée de notre problème, mais on ne sait jamais où, en fait, que la longueur des cartes sur. ETUDIANT: N'est-ce pas va se passer plus tard, quand vous dites, recherche à gauche, chercher à droite? Vous allez aller à un autre zone de votre - JASON HIRSCHHORN: Nous allons aller à une zone, mais comment savons-nous qui sont aller? Si nous n'avons que le tableau et ce n, comment savons-nous où aller au tableau. Dans le dos, oui? ÉTUDIANT: Avez-vous, comme, une plus faible lié et une variable limite supérieure ou quelque chose comme ça? JASON HIRSCHHORN: OK. C'est donc une autre idée. Plutôt que de simplement garder une trace de l' taille, nous gardons la trace de la plus faible et variable liée supérieure. Alors, comment pouvons-nous calculons la taille de une borne inférieure et la borne supérieure? [VOIX interposition] JASON HIRSCHHORN: soustraction. Et aussi garder la trace de la moindre lié et limite supérieure pour nous faire savoir, cherchons-nous ces deux? Sommes-nous à la recherche de ces deux ici? Cherchons-nous les deux du milieu? Probablement pas les deux du milieu, car cela, en fait, est la recherche binaire. Mais maintenant, nous serons en mesure d'obtenir la taille, mais aussi les limites de la matrice. En substance, si nous avons notre géant annuaire, nous déchirer en deux. Nous savons maintenant où que les petits répertoire est. Mais nous ne sommes pas réellement déchirant l'annuaire de moitié. Nous avons encore besoin de savoir où l' nouvelles limites de notre problème est. Quelqu'un at-il des questions à ce sujet? Oui? ÉTUDIANT: Serait-il travailler en créant un variable i, alors que vous décale juste la position de i par rapport à son la position actuelle, et de la longueur, n? JASON HIRSCHHORN: Et quelle est i? ETUDIANT: Comme je être comme sorte de - Comme vous le feriez d'initialiser i à la position moyenne de la matrice. Et puis, si la valeur à la position i dans au milieu de la matrice pour en trouvé être inférieure à la valeur que vous avez besoin, je maintenant devient la longueur du tableau, plus la valeur de i divisée par deux. Comme, voir, vous passez i - JASON HIRSCHHORN: Droit. ETUDIANT: - à la - JASON HIRSCHHORN: Je suis presque positif qui va travailler. Mais le point de l'être, vous avez besoin de deux éléments d'information ici. Vous pouvez le faire avec début et à la fin, ou vous pouvez le faire avec la taille, puis certains marqueur. Mais vous n'avez pas besoin de deux pièces d'informations ici. Vous ne pouvez pas vous en tirer avec un seul. Est-ce que c'est logique? Donc, nous allons passer, et nous allons faire [inaudible] et créer des marqueurs. Alors t'as écrivez dans votre code? Etudiant: Je viens de dire int lié l'un est égal à 0. JASON HIRSCHHORN: Appelons que int, en commençant. ETUDIANT: OK. JASON HIRSCHHORN: Cela fait plus de sens pour moi. Et? ETUDIANT: je l'ai dit, je suppose, int fin. JASON HIRSCHHORN: int fin. Étudiant: Je suppose, n moins 1, ou quelque chose comme ça. Comme, le dernier élément. JASON HIRSCHHORN: Donc vous avez écrit, int début égale à 0, point-virgule, et int fin égale n moins 1, point-virgule. Donc, essentiellement, ce que nous faisons ici, la première position 0. Et comme nous le savons dans des tableaux, ils ne vont pas jusqu'à n, elles montent à n moins 1. Nous avons donc des limites de notre tableau. Et ces premières bornes se trouvent les limites initiales de notre problème. OK. Donc, ça sonne bien. Ensuite, si nous revenons à cette ligne, tout en la longueur de la liste est supérieur à 0, ce que, au lieu de n, devrait nous mettons ici? ETUDIANT: Donnez fin moins début. JASON HIRSCHHORN: Bien se terminant moins début est supérieur à 0? OK. Et nous pourrions, si nous voulions faire un peu mieux que, ce pouvions-nous faire? Si nous voulions nettoyer ce code un peu? Comment pouvons-nous nous débarrasser de la 0? C'est juste une question de style. Il est exact en ce moment. ETUDIANT: Ending ne égal début? JASON HIRSCHHORN: Nous pouvons faire quoi? [VOIX interposition] ETUDIANT: Ending est supérieure? JASON HIRSCHHORN: Ouais. Nous pouvons juste faire tout en mettant fin est supérieure à début. Droite. Nous avons ajouté à partir de l'autre côté de cela, et nous nous sommes débarrassés de l'0. Ainsi, elle a simplement un peu plus propre. OK. Ainsi, alors que la longueur de la liste est 0, nous avons écrit que, tout en mettant fin est plus que de commencer. Nous allons mettre dans notre nécessaire accolades, et puis la première chose nous voulons faire est de regarder eux dans une petite liste. Vous? Pouvez-vous me donner le - ETUDIANT: Si parenthèses support carré de valeur - JASON HIRSCHHORN: Si parenthèses support carré de valeur. ETUDIANT: Ending divisé par 2. JASON HIRSCHHORN: Fin? Étudiant: Je vois un problème avec votre - JASON HIRSCHHORN: OK. Eh bien, regardez au milieu. Comment savons-nous ce que le milieu est? Ouais. Permettez-moi de supprimer ce code. Comment savons-nous ce que le milieu est? En tout, quand vous avez le début et la fin, comment trouvez-vous le milieu? ETUDIANT: Vous faites la moyenne. ETUDIANT: Vous ajoutez ensemble et ensuite - JASON HIRSCHHORN: Ajouter les ensemble et alors? Étudiant: Et vous faites la moyenne. Diviser par 2. JASON HIRSCHHORN: Ajouter les et diviser par 2. Donc milieu int égale? Tom, vous pouvez me le donner? Étudiante: Début en plus fin - JASON HIRSCHHORN: Début en plus fin. ETUDIANT: Tout, support, divisé par 2. JASON HIRSCHHORN: Tout, entre parenthèses, divisée par deux. Ce qui me donne le milieu de quoi que ce soit, corriger? ETUDIANT: Vous avez également besoin d'arrondir vers le haut. JASON HIRSCHHORN: Ce que vous faites dire, j'ai besoin d'arrondir vers le haut? [VOIX interposition] ETUDIANT: Parce que si c'est une étrange nombre, alors c'est comme - JASON HIRSCHHORN: Eh bien, OK. Ainsi, j'ai pu arrondir vers le haut. Mais si c'est un nombre impair, un 5, je peux prendre une distance à partir du milieu. Ou si c'est un nombre pair, plutôt, c'est une meilleure affaire. Si c'est 4, nous avons seulement 4, je peux prendre la première «milieu», entre guillemets ou le second «milieu». Soit serait travailler pour une recherche binaire, donc je n'ai pas vraiment besoin de l'arrondir. Mais il ya une autre chose que je besoin de regarder cette ligne. Nous pourrions ne pas le réaliser encore, mais nous allons y revenir. Parce que cette ligne fait encore besoin une autre chose. Mais jusqu'à présent, nous avons écrit quatre lignes de code. Nous avons notre début et se terminant marqueurs. Nous avons notre boucle while, qui mappe sur directement à notre pseudo. Nous cherchons au milieu qui mappe directement sur notre pseudo. Je dirais cela va au milieu de la liste, cette ligne de code. Et puis, une fois que nous allons à la moyenne de la liste, la prochaine chose que nous devons faire est de vérifier si notre valeur est là pour le pseudo-code, nous avons écrit plus tôt. Alors, comment pouvons nous vérifions si notre valeur est au milieu de la liste? Vous. Pourquoi ne pas vous faire cela? ETUDIANT: Si notre valeur de est au milieu est égal à tout ce que nous mettons le - Je veux dire égal à égal - JASON HIRSCHHORN: Il - OK. Étudiant: Je ne suis pas sûr de ce que l' variable, nous sommes à la recherche pour que, parce que - [VOIX interposition] ETUDIANT: [inaudible]. JASON HIRSCHHORN: Exactement. Par la déclaration de fonction, nous sommes à la recherche d'une valeur. Nous allons donc chercher une valeur dans un tableau de valeurs. Donc, vous avez parfaitement raison. Vous ferez, si le support de la valeur de parenthèse ouverte milieu fermé égaux de support est égale à la valeur et à l'intérieur il que devons-nous faire? Si notre valeur est là, ce devons-nous faire? [VOIX interposition] ETUDIANT: Retour zéro. JASON HIRSCHHORN: Retour vrai. ETUDIANT: Retour vrai. JASON HIRSCHHORN: Michael, qu'est-ce que cette ligne fait? ETUDIANT: [inaudible] l'exécution du programme sa course, et qui est au-dessus, et vous avez ce que vous devez faire? JASON HIRSCHHORN: Le programme ou quoi? Dans ce cas? ÉTUDIANTS: La fonction. JASON HIRSCHHORN: La fonction. Et donc, pour revenir à ce que appelé et lui donner la valeur, c'est vrai. Exactement. Main. Quel est le type de retour de principal, Michael? ETUDIANT: int, entier? JASON HIRSCHHORN: int, exactement. Un entier. C'était juste une question de s'assurer vous les gars ont été au-dessus de celui-ci. Que faut-il revenir souvent, si toutes les choses fonctionnent bien? ETUDIANT: Zéro. JASON HIRSCHHORN: zéro. Exactement. ETUDIANT: Si cela renvoie simplement vrai, il n'y a pas d'informations étant donné sur ce que le - Oh, c'est juste dire que ce valeur est à l'intérieur du tableau. JASON HIRSCHHORN: Exactement. Ce programme ne donne pas d'informations où exactement la valeur est. C'est seulement en disant, oui, nous avons trouvé il, ou non, nous n'avons pas trouvé. Donc, si le nombre trouvé, retourne vrai. Eh bien, en fait nous avons juste fait ce vraiment rapidement que une ligne de code. Je propose donc que la ligne de pseudo. ETUDIANT: N'avons-nous pas besoin pour changer le tableau? Il devrait être des valeurs, pas de valeur, non? JASON HIRSCHHORN: Désolé. Merci. ÉTUDIANT: Oui. JASON HIRSCHHORN: Cette ligne devraient être des valeurs. Exactement. OK. Donc, nous avons examiné la liste du milieu. Si nombre trouvé return true. Continuant sur notre pseudo, si milieu est supérieur, la recherche gauche. J'ai donc eu ici, si le nombre supérieur, la recherche gauche. Constantine, peut vous donner moi cette ligne de code? ÉTUDIANT: Si la valeur moyenne - JASON HIRSCHHORN: Donc, si la valeur - si parenthèse ouverte valeurs support support à proximité du milieu - ETUDIANT: Est inférieure à la valeur? JASON HIRSCHHORN: Est moins. ETUDIANT: Moins de valeur. JASON HIRSCHHORN Valeur. Eh bien, en fait, vous voulez vérifier si le nombre - Désolé. C'est un peu déroutant. Mais d'autre si le nombre dans la milieu de la liste est plus grande. ETUDIANT: Oh, OK. JASON HIRSCHHORN: Je vais changer cela. Sinon, si milieu est plus élevé, nous vouloir chercher gauche, OK? Et que faisons-nous à l'intérieur ce si l'état? ETUDIANT: Puis-je faire un petit changement à l'état, changer à autre si? JASON HIRSCHHORN: Sinon, si? OK. Donc, ce code s'exécute environ la même. Mais la bonne chose sur l'utilisation de if, else si, d'autre ou si, si, d'autre si, d'autre signifie que seulement l'un de ceux va vérifier, pas tous les trois d'entre eux, potentiellement. Et qui le rend un peu plus agréable sur l'ordinateur qui est l'exécution de votre programme. Donc, [? Constantine,?] nous sommes à l'intérieur de cette ligne, d'autre si les valeurs, tranche moyenne près support est supérieure à la valeur. Que devons-nous faire? Nous devons rechercher la gauche. Comment faisons-nous cela? Je vais vous donner un bon départ. Nous avons ces deux choses appelées début et de fin. Donc, ce qu'il faut faire au début? Si vous souhaitez rechercher la gauche de la liste, nous obtenons notre début courant. Que devons-nous faire? ETUDIANT: Nous fixons le début à mi plus 1. JASON HIRSCHHORN: Donc, si nous sommes recherche de la gauche? ETUDIANT: Désolé, moins milieu - de sorte que la fin serait milieu moins 1 et au début - JASON HIRSCHHORN: Et qu'est-ce qui se passe au début? ETUDIANT: Il reste le même. JASON HIRSCHHORN: Donc, le sens reste le même. Si nous sommes à la recherche de la gauche, nous sommes en utilisant le même début - tout à fait exact. Et la fin? Désolé, ce que fait le se terminant égal à nouveau? ETUDIANT: moins Moyen 1. JASON HIRSCHHORN: moins Moyen 1. Maintenant, pourquoi moins 1, et pas seulement du milieu? ÉTUDIANTS: Le milieu est de la imaginez déjà, parce que nous avions vérifier que c'est sur? JASON HIRSCHHORN: C'est tout à fait exact. Le milieu est hors de l'image. Nous avons déjà vérifié le milieu. Donc, nous ne voulons pas "au milieu", citation Ils ont dit, de continuer à être dans la tableau que nous cherchons. Donc, c'est fantastique. Sinon, si les valeurs tranche intermédiaire est supérieure que la valeur se terminant égaux moins milieu 1. Jeff, que dire de cette dernière ligne? ÉTUDIANT: Else. Valeurs du milieu est inférieure à la valeur? JASON HIRSCHHORN: Nous allons vous me donner d'autre. Donc, si vous ne me donnez pas - Étudiant: Alors commencer serait ainsi milieu 1. JASON Hirschhorn: Début égaux , plus une moyenne, de plus, pour la même raison que Constantine nous a donné plus tôt. Et à la fin, qui n'a pas donné moi une ligne de code encore? Return false, Aleha, ce écrivons-nous ici? ETUDIANT: Retour faux. JASON HIRSCHHORN: Retour faux. Et nous devons le faire, parce que si nous ne trouvent pas, nous devons nous dire ne pas le trouver. Et nous avons dit que nous allons revenir un bool, de sorte que nous avons d'y retourner une part de bool. Donc, nous allons exécuter ce code. Je vais en fait - Nous sommes donc dans le terminal. Nous dégageons notre fenêtre. Faisons tout. Nous avons trouvé il ya une erreur. Il ya une erreur à la ligne 15, qui devrait virgule à la fin de la déclaration. Alors qu'est-ce que j'ai oublié? ÉTUDIANT: point-virgule. JASON HIRSCHHORN: point-virgule droit ici. Je pense que c'est le code de Tom. Alors Tom, [inaudible]. Je plaisante. Faisons Marque Toutes nouveau. ÉTUDIANT: Qu'est-ce répertoire Dropbox devrions-nous être pour cela? JASON HIRSCHHORN: Ainsi, vous pouvez juste regarder de ce bit. Mais encore une fois, si vous voulez faire avancer ce coder dans votre répertoire pset3 pour essayer dehors, c'est ce que j'ai fait. Si vous remarquez ici - désolé, bonne question. [? LS,?] J'ai ici le code de find.c à partir du code de distribution de cette semaine. J'ai Helpers.h. J'ai un fichier de Marque que j'ai effectivement édité un peu pour inclure ces nouveaux fichiers que nous écrivons. Tout ce code sera disponible, pas le code de distribution, mais le nouveau Créer un fichier, le nouveau fichier sera Helpers.h disponible en ligne pour téléchargement. Encore une fois, si ce sont les codes supplémentaires nous ont. Donc, assurez-tout, par cette ligne, qui fait trouver, binaire, la sélection de la bulle - marques tous trois d'entre eux et compile en ce code exécutable trouvaille. Donc, en général, nous ne voulons pas à droite à check50. Nous voulons faire quelques tests sur notre propre. Mais afin que nous puissions accélérer le un peu, check50 2013 pset3.find passera dans helpers.c-- mon mauvais. Je n'ai pas tout de suite. Donc, nous allons en fait exécuter le code pour de vrai. Usage.find /, vous savez ce que cela signifie? ETUDIANT: Vous avez besoin d'un deuxième ligne de commande sur elle. JASON HIRSCHHORN: J'ai besoin d' une seconde ligne de commande. Et par la spécification, j'ai besoin pour entrer dans ce que nous recherchons. Examinons donc de 42. Nous allons continuer dans triés, parce que nous n'ont pas encore écrit une fonction de tri - 42, 43, 44. Et de contrôle D n'a pas trouvé l' l'aiguille dans la botte de foin. C'est mauvais. C'est certainement là. Essayons autre chose. C'est peut-être parce que j'ai mis au début. Faisons 41, 42, 43. Nous y voilà. Il l'a trouvé. Disons-le à la fin maintenant, juste afin que nous puissions être approfondie - 40, 41, 42. Vous n'avez pas trouvé l'aiguille. Donc je l'ai mentionné plus tôt. Malheureusement, je savais que ce qui allait se passer. Mais à des fins pédagogiques, il est bon d'explorer. Il ne fonctionne pas. Pour une raison quelconque, il ne peut pas le trouver. Nous savons ce qu'il ya dedans, mais nous ne sommes pas à le trouver. Donc, une chose que nous pourrions faire est de passer par GDB pour le trouver, mais le fait que ce soit, sans passer par GDB, avoir un sens où nous foiré? [? Madu? ?] Étudiant: Je pense qu'il pourrait être quand s'achève est égal au début, et c'est juste une liste à un élément. Ensuite, il ignore simplement la place en fait de vérifier. JASON HIRSCHHORN: C'est tout à fait exact. Lorsque fin égale début, nous faisons ont encore un élément dans notre liste? ÉTUDIANT: Oui. JASON HIRSCHHORN: Oui, en fait, nous avoir un et un seul élément. Et ce sera le plus susceptible de se produire lorsque, par le code que nous avons testé, nous sommes à la avant de la botte de foin ou à la fin de la botte de foin. C'est là que début et fin va à l'égalité un, à la recherche binaire. Donc, dans ces deux cas, il ne fonctionne pas, parce fin était égale à début. Mais si fin est égal à début, cela boucle while exécuter? Il ne fait pas. Et nous aurions pu vérifier que de nouveau par GDB. Alors, comment pouvons-nous résoudre ce code, car quand tout se terminant est égal à commencer, nous voulons aussi ce tout en boucle à exécuter. Alors, que pouvons-nous faire fixer à la ligne 18? ETUDIANT: [inaudible] est supérieure supérieure ou égale à. JASON HIRSCHHORN: Exactement. Alors que fin est supérieure à ou égale à début. Alors maintenant, nous nous assurons d'obtenir que cas de coin à la fin. Et nous allons voir. Lançons ce une fois de plus. Faisons tous. Encore une fois, vous avez juste à suivre ici. Trouver 41 cette fois. Juste garder cohérente. Trouver 42. Mettons au début - 42, 43, 44. Nous l'avons trouvé. Donc, c'était bien le changement nous devions faire. C'était beaucoup de nous codage vient de faire, la recherche binaire. Quelqu'un at-il des questions avant Je passe dans les lignes que nous avons écrit dans recherche binaire ou comment nous avons pensé ce que nous n'avons comprendre? Avant de poursuivre, je tiens également à souligner que dans l'ensemble, nous avons cartographié notre pseudo-code pour un un sur notre code. Nous avons eu cette chose délicate de comprendre la début et de fin. Mais si vous n'aviez pas compris cela, vous aurait écrit à peu près la code identique, sauf pour les deux premières lignes. Et puis, vous auriez compris quand vous l'avez fait dans les contrôles et les cas qui vous avez besoin d'autre chose. Donc, même si vous aviez suivi notre ligne pseudo-code à la ligne, vous avez obtenu tous, mais deux lignes de codez vous avez besoin d'écrire. Et je serais prêt à parier que vous les gars aurait tout compris cela assez rapidement, que vous avez besoin de mettre une sorte de marqueur là pour comprendre où vous étiez. C'est nouveau, c'est le pouvoir de faire pseudo-code à l'avance. Donc, nous pouvons faire la logique du premier, puis nous pouvons vous soucier de la syntaxe. Si nous avions été confondu sur la logique tout en essayant d'écrire ce code en C, nous avons obtenu tout foiré. Et puis nous serions poser des questions sur logique et la syntaxe et le maillage tous ensemble. Et nous aurions obtenu perdu dans ce qui peut rapidement devenir un problème très difficile. Passons donc maintenant sur à la sélection sorte. Nous avons 20 minutes. Donc, j'ai un sentiment que nous ne serons pas en mesure de obtenir par tous de la sélection sorte et tri à bulles. Mais laissez-nous au moins essayer pour terminer la sélection sorte. Donc, mettre en œuvre la sélection Trier par le suivant la déclaration de fonction. Encore une fois, ceci est pris à partir de la problème réglé spécification. Valeurs int est entre parenthèses, est un tableau d'entiers. Et int.n est la taille de ce tableau. Sélection tri va pour trier ce tableau. Donc, selon notre modèle mental de la sélection sorte, nous nous retirons le - d'abord, nous allons dans la liste de la première temps, trouver le plus petit nombre, mettre au début, trouver le deuxième plus petit nombre, le mettre dans le deuxième position, si nous voulons tri dans l'ordre croissant. Je ne vous force pas à écrire pseudo-code en ce moment. Mais avant de faire le code en tant que classe dans cinq minutes, nous allons écrire pseudo-code pour que nous ayons une idée de l'endroit où nous allons. Donc, essayer d'écrire le pseudo-code sur votre propre. Et puis essayer de transformer cette pseudo-code en code. Nous allons le faire en tant que groupe en cinq minutes. Et bien sûr, laissez-moi savoir si vous avez des questions. ETUDIANT: C'est tout? JASON HIRSCHHORN: Voir dans quelle mesure vous peut obtenir en deux minutes. Je comprends que vous ne sera pas être en mesure de terminer. Mais nous allons passer en revue ce que un groupe. Vous êtes tous de codage si [inaudible], donc je suis désolé pour interrompre ce que vous faites. Mais nous allons passer par cela comme un groupe. Et encore une fois, la recherche binaire, vous donne tout moi un si pas plus de lignes de code. Merci pour cela. Nous allons faire la même chose ici, le code en tant que groupe. Donc, la sélection sorte - Écrivons certains pseudo-code rapide. Par modèle mental, quelqu'un peut-il me donner la première ligne de pseudo-code, s'il vous plaît? Qu'est-ce que je veux faire? ETUDIANT: Bien que la liste est irrecevable. JASON HIRSCHHORN: OK, tout la liste est irrecevable. Et que voulez-vous dire "en panne?" Étudiant: Alors que [inaudible] n'a pas été triés. JASON HIRSCHHORN: Bien que la liste est en panne, que faisons-nous? Donnez-moi la deuxième ligne, s'il vous plaît, Marcus. Étudiant: Donc, trouver la prochaine le plus petit nombre. Ce sera en retrait. JASON HIRSCHHORN: Donc, trouver la prochain plus petit nombre. Et puis quelqu'un d'autre? Une fois que nous trouvons la plus petite suivante nombre, que faisons-nous? Je vais dire trouver le plus petit nombre. C'est ce que nous voulons faire. Donc, trouver le plus petit nombre. Alors que faisons-nous? ETUDIANT: [inaudible] à début. JASON HIRSCHHORN: Désolé? ETUDIANT: Placez-le dans le au début de la liste. JASON HIRSCHHORN: Donc, le placer dans le début de la liste. Et que faisons-nous de la chose qui était au commencement de la liste, non? Nous écraser quelque chose. Alors, où allons-nous mettre cela? Ouais, Anna? ETUDIANT: Lorsque le plus petit nombre était? JASON HIRSHHORN: Donc, mettez le début de la liste où la plus petit nombre était. Ainsi, alors que la liste est en panne, trouver le plus petit nombre, placez-le dans le début de la liste, mettez la à partir de la liste où la plus petit nombre était. Marcus, pouvez-vous reformuler cette ligne alors que la liste est en panne? ETUDIANT: Bien que les chiffres n'ont pas été triés? JASON HIRSHHORN: OK, afin de savent que les chiffres n'ont pas été triés, que devons-nous faire? Combien devons-nous passer par cette liste? Étudiant: Donc je suppose que pour une boucle, ou tandis que, tandis que le nombre contrôlés est moins à la longueur de la liste? JASON HIRSHHORN: OK, c'est bon. Je pense que je misphrased ma question mal. Je voulais juste obtenir à nous allons devoir aller toute la liste. Ainsi, alors que la liste est en panne, pour moi, c'est dur à la carte sur. Mais fondamentalement, c'est la façon dont Je pense à ce sujet. Passez par la liste entière, trouver la plus petit nombre, le placer dans le début - en fait, vous avez raison. Mettons les deux. Ainsi, alors que la liste est en panne, nous besoin de passer par la liste complète une fois, trouver le plus petit nombre, le lieu dans le début de la liste, mettre le début de la liste où l' était plus petit nombre, et ensuite, si l' liste est encore en panne, nous avons eu à passer par cette processus nouveau, non? C'est pourquoi la sélection sorte, Big-O exécution de la sélection sorte, n'importe qui? ETUDIANT: n carré. JASON HIRSHHORN: n carré. Parce que, comme Marcus et je viens de réaliser ici, nous allons avoir à parcourir la liste de liste nombre de fois. Donc passer par quelque chose de longueur n n nombre de fois est, en fait, n carré. Voici donc notre pseudo. Cela semble très bon. Quelqu'un at-il des questions sur le pseudocode? Parce qu'en fait la sélection sorte devrait probablement venir un à un, le code de pseudo. Donc, des questions sur le la logique de pseudocode? S'il vous plaît demander maintenant. Sélection sorte - alors que la liste est hors de l'ordre, nous allons passer par là et de trouver le plus petit à chaque fois et le mettre à l'avant. Ainsi, alors que la liste est en panne, peut quelqu'un me donne cette ligne de code qui ne m'a pas donné une ligne code encore, s'il vous plaît? Cela ressemble à quoi? ÉTUDIANT: C'est une boucle. JASON HIRSHHORN: Il semble certainement une boucle for. OK, pouvez-vous me donner la boucle? Pour - ETUDIANT: i est égal à 0. JASON HIRSHHORN: i ou - ce qui nous manque? Ce qui se passe ici? ETUDIANT: Int. JASON HIRSHHORN: Exactement. (Int i = 0; - ETUDIANT: i