1 00:00:00,000 --> 00:00:06,370 2 00:00:06,370 --> 00:00:08,150 >> JASON HIRSCHHORN: Bienvenue à trois semaines, tout le monde. 3 00:00:08,150 --> 00:00:11,650 Nous avons un occupé, mais passionnante section avant de nous. 4 00:00:11,650 --> 00:00:17,010 Alors d'abord, parce que nous avons fait des progrès avec le cours, mais nous avons encore 5 00:00:17,010 --> 00:00:20,570 ont beaucoup d'apprentissage à faire, je suis vais vous montrer les gars des ressources 6 00:00:20,570 --> 00:00:24,160 qui devrait se révéler incroyablement utile lorsque vous approchez pas seulement votre 7 00:00:24,160 --> 00:00:28,130 problème fixe, mais aussi digérer tous le matériel que nous vous donnons gars 8 00:00:28,130 --> 00:00:30,800 des conférences et des shorts et section. 9 00:00:30,800 --> 00:00:34,790 >> Ensuite, nous allons passer les 20 premiers à 25 minutes de l'article va plus 10 00:00:34,790 --> 00:00:38,630 GDB, que vous pouvez ou ne pouvez pas avoir utilisé à ce point, mais il s'agit d'un 11 00:00:38,630 --> 00:00:42,570 outil incroyablement utile qui sera vous aider à déboguer vos programmes. 12 00:00:42,570 --> 00:00:46,060 Beaucoup d'entre vous ont utilisé printf dans le milieu de votre programme de comprendre 13 00:00:46,060 --> 00:00:47,430 ce qui équivalait à une variable. 14 00:00:47,430 --> 00:00:52,060 GDB est encore mieux que printf et ne vis pas votre code, car vous 15 00:00:52,060 --> 00:00:53,320 exécuter sur un fichier exécutable. 16 00:00:53,320 --> 00:00:56,500 Donc, nous allons passer en revue les 10 plus utiles les commandes dont vous avez besoin pour GDB, et nous sommes 17 00:00:56,500 --> 00:01:00,540 va aller sur un exercice ensemble afin dans le problème de définir trois et au-delà, vous 18 00:01:00,540 --> 00:01:03,320 peut utiliser GDB pour aider debug vos programmes. 19 00:01:03,320 --> 00:01:06,420 Et enfin, nous allons passer en revue certains tri et de recherche des algorithmes 20 00:01:06,420 --> 00:01:10,590 que vous avez vu en cours, et nous sommes va effectivement code, pas seulement 21 00:01:10,590 --> 00:01:17,360 pseudo, mais le code binaire de recherche, tri à bulles, et la sélection sorte. 22 00:01:17,360 --> 00:01:20,090 >> Alors d'abord, je veux aller sur les ressources. 23 00:01:20,090 --> 00:01:23,530 Il s'agit d'une longue liste, et c'est une police plus petite parce que j'ai eu beaucoup de 24 00:01:23,530 --> 00:01:24,390 s'adapter ici. 25 00:01:24,390 --> 00:01:26,950 Mais ce ne sera pas seulement vous aider, nouveau, avec les ensembles de problèmes et 26 00:01:26,950 --> 00:01:30,760 informations à digérer que vous avez appris, mais certainement, viendra le temps de test, ceux-ci 27 00:01:30,760 --> 00:01:32,130 être incroyablement utile. 28 00:01:32,130 --> 00:01:34,700 Alors d'abord, la conférence prend note. 29 00:01:34,700 --> 00:01:39,480 Si vous allez à cs50.net/lectures et faites défiler jusqu'à la semaine et le jour précis, 30 00:01:39,480 --> 00:01:43,120 vous verrez qu'il ya des notes pour chaque conférences, qui n'est pas simplement une 31 00:01:43,120 --> 00:01:47,250 transcription, mais une version modifiée de ce qui a été couverte en conférence avec le code 32 00:01:47,250 --> 00:01:49,610 extraits et autres friandises utiles. 33 00:01:49,610 --> 00:01:52,220 Je recommande vivement d'aller sur ceux-ci. 34 00:01:52,220 --> 00:01:55,340 Et puis aussi, il ya le code source disponible à partir de chaque conférence. 35 00:01:55,340 --> 00:02:00,050 Et encore, ces diapositives seront également disponible en ligne à cs50.net/sections 36 00:02:00,050 --> 00:02:01,480 ce soir. 37 00:02:01,480 --> 00:02:06,860 >> Donc, deuxième sont les courts métrages chaque semaine couvrent des sujets, généralement de 5 à 15 38 00:02:06,860 --> 00:02:08,090 minutes. 39 00:02:08,090 --> 00:02:12,310 Et ceux espérons vous donnera un grande amorce sur différents sujets. 40 00:02:12,310 --> 00:02:12,870 Troisième - 41 00:02:12,870 --> 00:02:16,370 et c'est nouveau cette an - est study.cs50.net. 42 00:02:16,370 --> 00:02:20,110 Si vous n'avez pas vérifié, je recommandons fortement que vous le faites. 43 00:02:20,110 --> 00:02:21,100 Vous pouvez donc choisir un sujet. 44 00:02:21,100 --> 00:02:23,040 Nous avons des dizaines de sujets là-bas. 45 00:02:23,040 --> 00:02:24,770 Ainsi, par exemple, vous choisissez Fonctions. 46 00:02:24,770 --> 00:02:27,270 Il vous donne quelques diapositives et note sur les fonctions. 47 00:02:27,270 --> 00:02:31,190 Ce sont effectivement les diapositives que FO sont encouragés à utiliser au cours de notre 48 00:02:31,190 --> 00:02:32,710 présentations de la section. 49 00:02:32,710 --> 00:02:35,040 Il ya aussi des trucs et astuces pour faire face avec des fonctions, et il ya 50 00:02:35,040 --> 00:02:37,290 problèmes pratiques qui aident vous travaillez avec des fonctions. 51 00:02:37,290 --> 00:02:41,500 Nous vous donnons également des liens à court sur fonctions et les temps que les fonctions 52 00:02:41,500 --> 00:02:42,750 ont mis en lecture. 53 00:02:42,750 --> 00:02:46,550 Donc study.cs50.net, nouveau cette année, une ressource fantastique. 54 00:02:46,550 --> 00:02:52,180 >> Ensuite, je dois l'homme, qui est le manuel commande que vous pouvez exécuter à l' 55 00:02:52,180 --> 00:02:52,770 ligne de commande. 56 00:02:52,770 --> 00:02:57,880 Donc, si vous avez des questions au sujet d'un commande, par exemple, rand, qui nous 57 00:02:57,880 --> 00:03:00,900 rencontré la semaine dernière lors de la section et vous avez probablement rencontré dans 58 00:03:00,900 --> 00:03:05,380 votre problème réglé en passant dans le générer du code, mais si vous tapez l'homme 59 00:03:05,380 --> 00:03:09,980 rand, vous obtenez la page qui vous dit tout sur rand. 60 00:03:09,980 --> 00:03:14,040 Il vous donne ce qu'il faut, le paramètres qu'il faut, ainsi que le retour 61 00:03:14,040 --> 00:03:16,530 type et une brève description de cette fonction. 62 00:03:16,530 --> 00:03:17,500 >> Afin de vérifier rand. 63 00:03:17,500 --> 00:03:22,270 Il peut être un peu verbeux et confus, donc parfois je trouve que 64 00:03:22,270 --> 00:03:26,150 simplement googler ce que je veux savoir est la meilleure façon de trouver la réponse. 65 00:03:26,150 --> 00:03:27,940 Donc pratiquer avec Google. 66 00:03:27,940 --> 00:03:28,600 Obtenir de bons à Google. 67 00:03:28,600 --> 00:03:30,600 Il va devenir votre meilleur ami. 68 00:03:30,600 --> 00:03:34,300 >> Ainsi que Google, si vous ne pouvez pas le trouver sur Google, cs50.net/discuss, c'est 69 00:03:34,300 --> 00:03:35,550 le forum de discussion. 70 00:03:35,550 --> 00:03:39,390 Il ya des chances si vous avez une question, un de vos 700 + pairs a également 71 00:03:39,390 --> 00:03:42,110 question et peut-être demandé déjà dans la discuter 72 00:03:42,110 --> 00:03:43,540 forums et ont répondu il. 73 00:03:43,540 --> 00:03:48,130 Donc si vous avez une question commune ou Vous avez une question que vous pensez 74 00:03:48,130 --> 00:03:52,300 peut-être d'autres personnes auraient pu courir dans, consultez cs50.net/discuss. 75 00:03:52,300 --> 00:03:55,450 >> Enfin, les deux derniers, si vous voulez parler à un être humain réel, bureau 76 00:03:55,450 --> 00:03:57,770 heures du lundi au vendredi. 77 00:03:57,770 --> 00:04:00,850 Il ya aussi en ligne les heures de bureau pour les étudiants de vulgarisation. 78 00:04:00,850 --> 00:04:04,370 Et le dernier mais non le moindre, moi, le point d'exclamation. 79 00:04:04,370 --> 00:04:05,960 Vous avez tous mes coordonnées. 80 00:04:05,960 --> 00:04:11,940 Si vous besoin de quelque chose, s'il vous plaît jamais N'hésitez pas à me contacter. 81 00:04:11,940 --> 00:04:14,020 Toujours se sentir libre de le faire. 82 00:04:14,020 --> 00:04:17,490 Très peu d'entre vous m'ont ajoutée sur Gchat, de sorte que a été décevante, 83 00:04:17,490 --> 00:04:20,410 mais j'espère que ça va changer entre ce et la section suivante. 84 00:04:20,410 --> 00:04:22,105 Des questions jusqu'ici sur les ressources? 85 00:04:22,105 --> 00:04:25,670 86 00:04:25,670 --> 00:04:27,450 Grand. 87 00:04:27,450 --> 00:04:34,280 >> Enfin, une autre fiche pour rétroaction, sayat.me/cs50. 88 00:04:34,280 --> 00:04:37,050 Vous pouvez me donner des commentaires anonymes sur la façon dont je le fais. 89 00:04:37,050 --> 00:04:38,320 C'était vraiment utile semaine dernière. 90 00:04:38,320 --> 00:04:41,890 J'ai eu quelques commentaires de vous les gars droit, après l'article, plus de 91 00:04:41,890 --> 00:04:44,750 d'autres étudiants qui ont regardé ce au cours de la semaine, et 92 00:04:44,750 --> 00:04:46,830 était incroyablement utile. 93 00:04:46,830 --> 00:04:50,250 Je vais essayer de limiter ma consommation de le mot «doux», mais je vais vous montrer mon 94 00:04:50,250 --> 00:04:52,410 enthousiasme et l'excitation d'autres moyens. 95 00:04:52,410 --> 00:04:56,550 Mais il y avait d'autres supplémentaires évaluations de fond, 96 00:04:56,550 --> 00:04:57,600 deux avantages et delta. 97 00:04:57,600 --> 00:05:00,480 Alors s'il vous plaît, je vous donne les gars commentaires sur vos ensembles de problèmes. 98 00:05:00,480 --> 00:05:01,790 N'hésitez pas à me donner des commentaires sur mon enseignement. 99 00:05:01,790 --> 00:05:04,010 Je suis ici pour vous les gars. 100 00:05:04,010 --> 00:05:05,270 >> Grand. 101 00:05:05,270 --> 00:05:07,020 C'est tout ce que j'ai pour la première section. 102 00:05:07,020 --> 00:05:08,565 Est-ce que quelqu'un a une des questions à ce jour? 103 00:05:08,565 --> 00:05:12,370 104 00:05:12,370 --> 00:05:14,640 Et j'ai une note pour le centre de contrôle. 105 00:05:14,640 --> 00:05:21,200 étudiants d'extension m'ont envoyé des messages dire qu'ils ne reçoivent pas toute audio, 106 00:05:21,200 --> 00:05:23,870 mais ce n'est pas en mon pouvoir de fixer. 107 00:05:23,870 --> 00:05:25,280 Donc, j'espère, qui obtient résolu sous peu. 108 00:05:25,280 --> 00:05:28,850 Si vous regardez en ligne, salut, mais vous ne pouvez pas m'entendre. 109 00:05:28,850 --> 00:05:33,860 >> Alors d'abord, nous allons passer par GDB. 110 00:05:33,860 --> 00:05:37,100 GDB, comme je l'ai fait allusion au plus tôt, est un outil de débogage 111 00:05:37,100 --> 00:05:39,040 beaucoup mieux que printf. 112 00:05:39,040 --> 00:05:44,700 Donc, pour commencer avec GDB, les gars, si vous voulez ouvrir votre appareil 113 00:05:44,700 --> 00:05:49,070 et prendre le fichier que j'ai envoyé à vous plus tôt - ce fichier sera également 114 00:05:49,070 --> 00:05:51,940 disponible en ligne en un peu - 115 00:05:51,940 --> 00:05:55,700 et exécuter GDB. / le nom du fichier. 116 00:05:55,700 --> 00:05:58,580 Tout d'abord, bien sûr, vous devez compiler déposer parce GDB ne fonctionne que sur 117 00:05:58,580 --> 00:05:59,890 fichiers exécutables. 118 00:05:59,890 --> 00:06:02,300 >> Mais si jamais vous voulez commencer GDB, la première chose que vous faites, 119 00:06:02,300 --> 00:06:04,550 vous avez GDB. / César. 120 00:06:04,550 --> 00:06:08,340 Donc, c'est le nom du programme que nous sommes aller avec elle en ce moment. 121 00:06:08,340 --> 00:06:12,810 Donc, je vais écrire rendre à César, ce qui me donnera un fichier exécutable 122 00:06:12,810 --> 00:06:14,100 ici en vert. 123 00:06:14,100 --> 00:06:19,250 Et puis je vais courir GDB. / Cesar. 124 00:06:19,250 --> 00:06:19,810 >> Et là vous allez. 125 00:06:19,810 --> 00:06:24,540 Vous voyez, nous avons un texte me disant sur la version de GDB, me donner 126 00:06:24,540 --> 00:06:27,570 des informations de garantie, et nous avoir l'invite du PIB, qui ressemble un peu 127 00:06:27,570 --> 00:06:29,350 de comme notre invite de ligne de commande, mais vous voyez qu'il est ouvert 128 00:06:29,350 --> 00:06:32,510 paren, GDB, paren proches. 129 00:06:32,510 --> 00:06:36,520 Avant de continuer et déboguer ce fichier que je vous ai envoyée, permettez-nous sur 130 00:06:36,520 --> 00:06:40,220 quelques commandes utiles si nous avons un sens de ce que nous allons couvrir. 131 00:06:40,220 --> 00:06:45,060 >> Ces commandes sont répertoriées ici dans le ordre dans lequel j'utilise généralement eux. 132 00:06:45,060 --> 00:06:50,230 Donc, je commence mon programme en exécutant GBD. / Nom du programme, 133 00:06:50,230 --> 00:06:51,360 dans ce cas, César. 134 00:06:51,360 --> 00:06:57,430 Et puis la première chose que je fais de 99,9% du temps est de type break signifie. 135 00:06:57,430 --> 00:06:59,070 Cela définit un point d'arrêt au principal. 136 00:06:59,070 --> 00:07:03,260 Essentiellement, ce que vous faites là est le programme va s'arrêter à 137 00:07:03,260 --> 00:07:06,100 principal de sorte que vous pouvez commencer à l'examiner ligne par ligne, plutôt que de courir tous 138 00:07:06,100 --> 00:07:07,040 le chemin à travers. 139 00:07:07,040 --> 00:07:09,730 Vous pouvez interrompre à différents points dans votre code, mais principale est généralement un 140 00:07:09,730 --> 00:07:11,870 bon endroit pour commencer. 141 00:07:11,870 --> 00:07:14,840 >> La prochaine commande je cours est géré. 142 00:07:14,840 --> 00:07:17,400 Cela commence le programme en cours, et si vous avez besoin d'entrer en ligne de commande 143 00:07:17,400 --> 00:07:19,090 arguments, vous l'exécutez cette commande. 144 00:07:19,090 --> 00:07:20,500 Exécuter avec les arguments. 145 00:07:20,500 --> 00:07:25,000 Donc, puisque nous allons sur une version de C, qui est le programme que vous les gars 146 00:07:25,000 --> 00:07:26,160 écrit pour pset deux - 147 00:07:26,160 --> 00:07:29,880 celui-ci, bien sûr, a quelques bugs dans ce que nous espérons que nous trouverons - 148 00:07:29,880 --> 00:07:32,810 nous allons lancer l'exécution de certaines commandes arguments de ligne parce que César, 149 00:07:32,810 --> 00:07:34,860 comme vous les gars savent par le problème mis spec, prend un certain 150 00:07:34,860 --> 00:07:36,380 arguments de ligne de commande. 151 00:07:36,380 --> 00:07:40,000 >> Le prochain couple de commandes, la prochaine on est effectivement appelée prochaine. 152 00:07:40,000 --> 00:07:42,470 Que l'on vous prend ligne par ligne dans votre programme. 153 00:07:42,470 --> 00:07:45,800 Alors frapper n puis Entrée vous amène à la ligne suivante, l'exécution d' 154 00:07:45,800 --> 00:07:46,880 la ligne précédente. 155 00:07:46,880 --> 00:07:49,440 Étape vous amène non seulement à la ligne suivante, mais il 156 00:07:49,440 --> 00:07:51,070 vous emmène fonctions à l'intérieur. 157 00:07:51,070 --> 00:07:54,310 Donc, si vous avez écrit une fonction dans votre code ou si vous voulez découvrir un 158 00:07:54,310 --> 00:07:57,820 i, par exemple, vous pouvez frapper s, et plutôt que d'aller à la prochaine ligne de 159 00:07:57,820 --> 00:08:02,390 le fichier que vous allez par le droit maintenant, vous allez vraiment vous entrez dans 160 00:08:02,390 --> 00:08:04,670 cette fonction et voir son code. 161 00:08:04,670 --> 00:08:12,300 >> Liste montre, en très convivial format, les 10 ou si les lignes autour de 162 00:08:12,300 --> 00:08:14,940 où vous êtes actuellement dans votre code de sorte que vous pouvez réellement voir le fichier 163 00:08:14,940 --> 00:08:17,810 plutôt que d'avoir à permuter en arrière et vient entre différents points de vue. 164 00:08:17,810 --> 00:08:21,890 L'impression est comme printf, comme son nom l'indique. 165 00:08:21,890 --> 00:08:24,020 Cela vous montre ce qu'est une variable égale. 166 00:08:24,020 --> 00:08:25,870 >> Information habitants est vraiment utile. 167 00:08:25,870 --> 00:08:27,740 Il s'agit d'une version spéciale de l'impression. 168 00:08:27,740 --> 00:08:31,770 Information habitants vous montre tous les locaux des variables, tous imprime pour vous 169 00:08:31,770 --> 00:08:33,380 qui sont disponibles actuellement. 170 00:08:33,380 --> 00:08:36,360 J'ai donc généralement, plutôt que d'avoir à imprimer les quatre variables que je suis 171 00:08:36,360 --> 00:08:39,929 curieux de savoir si je suis dans une boucle, pour exemple, je viens d'écrire des informations habitants, 172 00:08:39,929 --> 00:08:43,470 et ça me ce que mon compteur i montrer égaux, ainsi que le tableau que je suis 173 00:08:43,470 --> 00:08:45,130 travail égal. 174 00:08:45,130 --> 00:08:47,530 >> Enfin, continuer. 175 00:08:47,530 --> 00:08:49,300 Taper pause vous arrête au point de rupture. 176 00:08:49,300 --> 00:08:51,380 Vous pouvez vous promener à travers la ligne de Conformément à la prochaine étape et. 177 00:08:51,380 --> 00:08:55,640 Continuer exécute le programme pour votre prochain point de rupture ou jusqu'à la fin si 178 00:08:55,640 --> 00:08:57,180 il n'y a plus de points de rupture. 179 00:08:57,180 --> 00:09:00,060 Désactiver supprime les points de rupture si vous a décidé la pause principale était 180 00:09:00,060 --> 00:09:01,890 inapproprié, vous voulez le mettre ailleurs. 181 00:09:01,890 --> 00:09:05,090 Et enfin q, stoppé, sort de GDB. 182 00:09:05,090 --> 00:09:10,784 >> Donc ce programme. / César, nous allons de regarder à travers ce moment et nous 183 00:09:10,784 --> 00:09:13,490 vont utiliser GDB pour trouver les bugs dans ce programme. 184 00:09:13,490 --> 00:09:18,110 J'ai couru ce programme plus tôt avec Vérifiez 50, et j'ai eu un froncement de sourcils. 185 00:09:18,110 --> 00:09:22,310 Tout ce qu'il existait, elle a établi, il passé beaucoup de tests, mais pour 186 00:09:22,310 --> 00:09:27,950 une raison quelconque, il n'a pas passé le cinquième test, tournant BARFOO, tous les bouchons, en 187 00:09:27,950 --> 00:09:33,350 E-D-U-I-R-R, tous les bouchons, en utilisant trois comme une clé. 188 00:09:33,350 --> 00:09:34,090 Je suis assez proche. 189 00:09:34,090 --> 00:09:35,410 Je suis descendu par une lettre. 190 00:09:35,410 --> 00:09:37,340 Donc, il ya une petite erreur ici. 191 00:09:37,340 --> 00:09:38,070 J'ai regardé dans mon code. 192 00:09:38,070 --> 00:09:38,850 Je ne pouvais pas comprendre. 193 00:09:38,850 --> 00:09:41,740 Heureusement, vous avez peut m'aider comprendre ce que ce bug est. 194 00:09:41,740 --> 00:09:44,610 >> Donc, c'est l'erreur que nous sommes chercher. 195 00:09:44,610 --> 00:09:46,090 Passons en GDB. 196 00:09:46,090 --> 00:09:51,100 Encore une fois, je n'ai plus GDB. / César, alors maintenant nous sommes dans GDB. 197 00:09:51,100 --> 00:09:54,290 Et ce qui est le premier chose que je dois faire? 198 00:09:54,290 --> 00:09:56,680 Je viens entré GDB. 199 00:09:56,680 --> 00:10:00,316 Quelqu'un me donner une bonne commande à entrer. 200 00:10:00,316 --> 00:10:01,140 >> ÉTUDIANT: Casser principale. 201 00:10:01,140 --> 00:10:01,800 >> JASON HIRSCHHORN: Pause principale. 202 00:10:01,800 --> 00:10:02,900 Fantastique. 203 00:10:02,900 --> 00:10:03,560 Tapons que po 204 00:10:03,560 --> 00:10:06,390 Les gars, vous pouvez regarder ici ou suivez long sur vos ordinateurs. 205 00:10:06,390 --> 00:10:09,410 Cassez principale, et vous verrez une point de rupture a été fixé à - 206 00:10:09,410 --> 00:10:12,340 il me donne une adresse de mémoire étrange, et il me donne aussi le numéro de la ligne. 207 00:10:12,340 --> 00:10:15,310 Si je devais revenir sur ce dossier, Je voudrais réaliser que le principal 208 00:10:15,310 --> 00:10:17,700 arrivé sur la ligne 21. 209 00:10:17,700 --> 00:10:18,950 Que dois-je exécuter prochaine? 210 00:10:18,950 --> 00:10:22,970 211 00:10:22,970 --> 00:10:25,060 Est mon programme en cours d'exécution? 212 00:10:25,060 --> 00:10:25,650 Non. 213 00:10:25,650 --> 00:10:27,175 Alors, que dois-je exécuter prochaine? 214 00:10:27,175 --> 00:10:27,520 >> ETUDIANT: Exécuter. 215 00:10:27,520 --> 00:10:28,050 >> JASON HIRSCHHORN: Exécuter. 216 00:10:28,050 --> 00:10:30,760 Dois-je exécuter juste terme, ou devrais- J'ajoute quelques autres choses? 217 00:10:30,760 --> 00:10:31,960 >> ETUDIANT: Exécuter avec l'argument. 218 00:10:31,960 --> 00:10:33,320 >> JASON HIRSCHHORN: Exécuter avec les arguments de la commande. 219 00:10:33,320 --> 00:10:36,420 Et puisque je suis le débogage d'un très spécifique cas, je dois entrer dans cette 220 00:10:36,420 --> 00:10:37,120 commande argument de ligne. 221 00:10:37,120 --> 00:10:42,290 Je vais donc ne cours de trois, ce qui est, encore une fois, la sortie que j'ai obtenu à partir de Check 50. 222 00:10:42,290 --> 00:10:44,240 Démarrage du programme. 223 00:10:44,240 --> 00:10:45,420 Nous passons par quelques lignes. 224 00:10:45,420 --> 00:10:47,700 Vous allez maintenant voir que nous sommes sur la ligne 21. 225 00:10:47,700 --> 00:10:49,200 Comment puis-je savoir que nous sommes sur la ligne 21? 226 00:10:49,200 --> 00:10:52,170 Parce que si vous regardez à gauche de ma fenêtre de terminal, il 227 00:10:52,170 --> 00:10:53,120 il dit à la ligne 21. 228 00:10:53,120 --> 00:10:57,010 Et cela me donne, en fait, le code qui est à la ligne 21. 229 00:10:57,010 --> 00:10:58,440 Donc, je me suis mal exprimé plus tôt. 230 00:10:58,440 --> 00:10:59,770 Principale n'est pas vraiment à la ligne 21. 231 00:10:59,770 --> 00:11:02,000 Principale est un couple de lignes ci-dessus 21. 232 00:11:02,000 --> 00:11:04,300 Mais à la ligne 21, c'est où nous cassons. 233 00:11:04,300 --> 00:11:06,280 Cette ligne de code a non encore exécutée. 234 00:11:06,280 --> 00:11:06,890 C'est important. 235 00:11:06,890 --> 00:11:09,120 La ligne que vous voyez n'a pas encore été exécuté. 236 00:11:09,120 --> 00:11:12,650 C'est la ligne de code suivante vous êtes sur le point d'exécuter. 237 00:11:12,650 --> 00:11:15,860 >> Donc, la ligne suivante, comme vous les gars sont probablement familier avec, est-ce 238 00:11:15,860 --> 00:11:20,070 état de la vérification pour voir si j'ai conclu un argument de ligne de commande. 239 00:11:20,070 --> 00:11:22,140 Et un i, ce qui est la deuxième partie de ce faire? 240 00:11:22,140 --> 00:11:23,457 Qu'est-ce qu'un i? 241 00:11:23,457 --> 00:11:24,950 >> ETUDIANT: Modification à un nombre entier. 242 00:11:24,950 --> 00:11:25,450 >> JASON HIRSCHHORN: Désolé? 243 00:11:25,450 --> 00:11:27,400 >> ETUDIANT: Ça change la argument un entier. 244 00:11:27,400 --> 00:11:30,890 >> JASON HIRSCHHORN: Donc un i changements arg v1 d'une chaîne en entier. 245 00:11:30,890 --> 00:11:32,140 Et puis qu'est-ce qu'il contrôle? 246 00:11:32,140 --> 00:11:35,414 247 00:11:35,414 --> 00:11:37,112 >> ETUDIANT: Si il ya une deuxième argument de ligne de commande, côté 248 00:11:37,112 --> 00:11:38,100 de l'exécution du programme. 249 00:11:38,100 --> 00:11:39,460 >> JASON HIRSCHHORN: Et ce qui est la seconde moitié de cette 250 00:11:39,460 --> 00:11:41,220 Expression booléenne contrôle? 251 00:11:41,220 --> 00:11:42,540 Cette partie ici, un i? 252 00:11:42,540 --> 00:11:44,080 >> ETUDIANT: Si elle est négative. 253 00:11:44,080 --> 00:11:45,380 >> JASON HIRSCHHORN: Faire en sorte que? 254 00:11:45,380 --> 00:11:47,120 >> ÉTUDIANTS: Faire en sorte qu'il est, en effet, positif. 255 00:11:47,120 --> 00:11:47,650 >> JASON HIRSCHHORN: Exactement. 256 00:11:47,650 --> 00:11:50,600 Ceci est vérifié pour voir si elle est négatif, et si elle est négative, je 257 00:11:50,600 --> 00:11:53,220 avoir un sentiment de puissance de la prochaine ligne être me crier à l'utilisateur. 258 00:11:53,220 --> 00:11:55,930 Donc, nous allons frapper fin d'exécuter cette ligne. 259 00:11:55,930 --> 00:11:59,925 Nous ne voyons pas cette ligne que vous les gars peut-être s'attendre à voir crier à l' 260 00:11:59,925 --> 00:12:03,030 utilisateur, puis revenir, parce cette ligne ne s'est pas exécuté. 261 00:12:03,030 --> 00:12:03,840 Je suis entré 3. 262 00:12:03,840 --> 00:12:06,860 Donc, je n'ai, en fait, entrer deux commande arguments de la ligne, et 3 est 263 00:12:06,860 --> 00:12:07,610 supérieur à zéro. 264 00:12:07,610 --> 00:12:09,950 Donc, nous avons vu que la ligne, nous avons exécuté, mais nous n'avons pas intervenons 265 00:12:09,950 --> 00:12:11,300 l'intérieur de la condition if. 266 00:12:11,300 --> 00:12:17,060 >> Alors maintenant, à côté, je vois que je suis la mise en clé int équivaut à une i arg v1. 267 00:12:17,060 --> 00:12:18,840 Donc c'est moi créer une clé variable. 268 00:12:18,840 --> 00:12:22,450 Donc, si j'imprime touche en ce moment, parce que qui vous permet de voir la 269 00:12:22,450 --> 00:12:26,040 valeur dans la variable, clé est égale à 47. 270 00:12:26,040 --> 00:12:28,810 C'est bizarre, mais bien sûr, c'est parce que je n'ai pas 271 00:12:28,810 --> 00:12:30,490 encore exécuté cette ligne. 272 00:12:30,490 --> 00:12:35,880 Alors maintenant, si je frappe n, exécutez cette ligne, et faire touche d'impression, clé sera égale à 3, 273 00:12:35,880 --> 00:12:37,740 c'est ce que nous nous attendons à égal. 274 00:12:37,740 --> 00:12:41,170 >> Encore une fois, dans GDB, la ligne que vous voyez vous n'avez pas encore exécuté. 275 00:12:41,170 --> 00:12:44,850 Vous devez frapper n ou s ou un nombre d'autres commandes à fait 276 00:12:44,850 --> 00:12:46,610 exécuter cette ligne. 277 00:12:46,610 --> 00:12:47,380 Imprimer touche. 278 00:12:47,380 --> 00:12:48,280 De clés à 3. 279 00:12:48,280 --> 00:12:49,750 Jusqu'ici, tout va bien. 280 00:12:49,750 --> 00:12:51,000 String est le texte brut. 281 00:12:51,000 --> 00:12:52,270 Disons exécuter cette ligne. 282 00:12:52,270 --> 00:12:53,970 Je reçois une chaîne de l'utilisateur. 283 00:12:53,970 --> 00:12:58,690 >> Voyons dans mon chèque de 50, je entrer BARFOO tous les bouchons, donc 284 00:12:58,690 --> 00:13:01,330 c'est ce que je vais entrer. 285 00:13:01,330 --> 00:13:07,300 Si j'imprime maintenant texte brut. 286 00:13:07,300 --> 00:13:08,610 Vous verrez qu'il est égal à une chaîne. 287 00:13:08,610 --> 00:13:11,100 Il me donne une autre hexadécimal bizarre nombre, mais il le fait dans 288 00:13:11,100 --> 00:13:13,620 fait dire que ma chaîne est BARFOO. 289 00:13:13,620 --> 00:13:19,308 Si je voulais voir ce que touche égale à ce point, comment pourrais-je vérifier touche? 290 00:13:19,308 --> 00:13:20,710 >> ETUDIANT: Imprimer touche. 291 00:13:20,710 --> 00:13:22,010 >> JASON HIRSCHHORN: Imprimer touche, exactement. 292 00:13:22,010 --> 00:13:23,260 Et effectivement, il ya un raccourci. 293 00:13:23,260 --> 00:13:25,910 Si vous êtes fatigué de taper impression, vous pouvez simplement taper p. 294 00:13:25,910 --> 00:13:28,340 Donc touche p fait exactement la même chose. 295 00:13:28,340 --> 00:13:29,730 Et encore, je vois est égal à 3. 296 00:13:29,730 --> 00:13:34,760 >> Si je voulais savoir ce que les deux clé et BARFOO égalé à la fois 297 00:13:34,760 --> 00:13:37,215 mais j'étais fatigué de taper chaque un individuellement, je 298 00:13:37,215 --> 00:13:38,590 pourrait Infos habitants. 299 00:13:38,590 --> 00:13:41,170 Cela me donne égaux clés 3. 300 00:13:41,170 --> 00:13:42,500 Texte brut est égal BARFOO. 301 00:13:42,500 --> 00:13:45,265 Il me donne aussi ces deux choses bizarres au sommet, cette variable i et 302 00:13:45,265 --> 00:13:46,590 cette variable n. 303 00:13:46,590 --> 00:13:48,460 >> Ceux-ci sont réellement existant dans mon programme principal. 304 00:13:48,460 --> 00:13:51,280 Nous ne les avons pas encore rencontré, mais comme un aperçu, les 305 00:13:51,280 --> 00:13:52,880 ma pour exister dans la boucle. 306 00:13:52,880 --> 00:13:55,360 Alors maintenant, ils égalent quelque étrange nombre parce qu'ils n'ont pas été 307 00:13:55,360 --> 00:13:58,300 encore initialisés, mais ils existent encore dans la mémoire, de sorte qu'ils sont tout simplement mis 308 00:13:58,300 --> 00:14:00,220 à une valeur d'ordures. 309 00:14:00,220 --> 00:14:02,890 Mais nous ne voyons clé dans la plaine texte là. 310 00:14:02,890 --> 00:14:06,390 >> Donc, je vais exécuter cette ligne, ligne 34, la boucle pour. 311 00:14:06,390 --> 00:14:08,220 Nous allons sauter dans le pour la boucle en frappant n. 312 00:14:08,220 --> 00:14:10,050 Et nous sommes à l'intérieur de la boucle for. 313 00:14:10,050 --> 00:14:11,360 Nous sommes à notre première vérification. 314 00:14:11,360 --> 00:14:14,300 Et encore, ceux-ci devraient sorte de regarder familier pour vous, parce que c'était un 315 00:14:14,300 --> 00:14:18,080 César programme qui a été écrit, mais encore une fois, a une sorte de bug. 316 00:14:18,080 --> 00:14:21,940 >> Et maintenant, si je le fais d'info habitants, parce que je suis l'intérieur de cette boucle, vous verrez 317 00:14:21,940 --> 00:14:23,900 que i est égal à zéro, comme nous le prévoyons. 318 00:14:23,900 --> 00:14:26,820 C'est ce que nous avons à et initialisé il dans la boucle. 319 00:14:26,820 --> 00:14:27,560 n est égal à 6. 320 00:14:27,560 --> 00:14:30,700 Cela fait également sens parce que nous avons mis en à la strlen de texte brut. 321 00:14:30,700 --> 00:14:34,270 Donc, je tiens à faire d'info locaux ou impression à la variable souvent pour s'assurer que 322 00:14:34,270 --> 00:14:36,370 tout est toujours ce Je m'attends à ce qu'il égale. 323 00:14:36,370 --> 00:14:39,800 Dans ce cas, tout est ce que je m'attends à ce qu'il égale. 324 00:14:39,800 --> 00:14:41,850 >> Commençons donc par le déplacement cette boucle. 325 00:14:41,850 --> 00:14:45,715 La ligne que je suis sur la ligne 36 est, si simple texte i est supérieur à un et plaine 326 00:14:45,715 --> 00:14:48,540 moins i est inférieur ou égal à z. 327 00:14:48,540 --> 00:14:51,880 Je sais que mon problème n'est pas de ma première lettre, c'est la deuxième lettre. 328 00:14:51,880 --> 00:14:56,290 Si nous regardons en arrière à l'arrivée 50, B va à E amende. 329 00:14:56,290 --> 00:14:59,010 Je prends le A et le laisser tel un A, pas changer de D. Alors 330 00:14:59,010 --> 00:15:00,200 quelque chose ne va pas avec la deuxième lettre. 331 00:15:00,200 --> 00:15:01,640 Donc, je vais passer il en une seconde. 332 00:15:01,640 --> 00:15:06,030 >> Mais si je ne veux vérifier ce que plaine texte que j'ai égalé dans ce cas particulier 333 00:15:06,030 --> 00:15:07,760 cas, je pense qu'il devrait être quoi? 334 00:15:07,760 --> 00:15:10,980 Que dois-je le texte brut égal dans ce premier tour par la boucle? 335 00:15:10,980 --> 00:15:14,046 336 00:15:14,046 --> 00:15:15,110 >> ÉTUDIANT: Zero? 337 00:15:15,110 --> 00:15:16,510 >> JASON HIRSCHHORN: Texte brut de I? 338 00:15:16,510 --> 00:15:21,180 Il devrait donc être capitale B. J'ai, bien sûr, est égal à zéro, mais le texte brut 339 00:15:21,180 --> 00:15:25,600 support zéro support fermé est égal à B parce que les chaînes, comme nous l'avons vu la semaine dernière, 340 00:15:25,600 --> 00:15:28,650 sommes ensemble, nous obtenons l' premier caractère à partir de cela. 341 00:15:28,650 --> 00:15:34,960 Encore une fois, si j'ai imprimé le texte brut de Moi, je fais, en fait, obtenir le caractère 342 00:15:34,960 --> 00:15:36,560 B. Et c'est propre, non? 343 00:15:36,560 --> 00:15:40,380 Je n'ai pas vraiment le texte brut I. Ce n'est pas l'une des variables j'ai mis 344 00:15:40,380 --> 00:15:42,950 ou initialisé, mais vous pouvez imprimer toute une foule de choses 345 00:15:42,950 --> 00:15:45,640 si vous le souhaitez. 346 00:15:45,640 --> 00:15:47,340 >> Mais passons à travers. 347 00:15:47,340 --> 00:15:50,050 Si le texte brut I est supérieur à A et le texte brut I est inférieur ou égal à 348 00:15:50,050 --> 00:15:53,290 Z, qui est clairement le cas parce que nous avons un B. du capital Je vais courir 349 00:15:53,290 --> 00:15:54,230 une certaine maîtrise sur elle. 350 00:15:54,230 --> 00:15:58,530 Nous avons vu que les mathématiques la semaine dernière, donc nous allons tenir pour acquis que cela fonctionne 351 00:15:58,530 --> 00:16:00,900 droit selon Vérifiez 50. 352 00:16:00,900 --> 00:16:03,720 >> Ces accolades, le premier montré que je sortais le si 353 00:16:03,720 --> 00:16:07,030 condition, la seconde a montré une que je suis sortie de la boucle. 354 00:16:07,030 --> 00:16:10,400 Et maintenant quand je frappe suivante, nous verrons nous sommes de retour à la boucle de nouveau. 355 00:16:10,400 --> 00:16:11,970 Nous allons à travers la pour boucle de nouveau. 356 00:16:11,970 --> 00:16:18,110 Revenons en fait dans la deuxième itération de la boucle et le type 357 00:16:18,110 --> 00:16:20,520 Info habitants. 358 00:16:20,520 --> 00:16:22,190 >> Donc, nous sommes dans la deuxième itération de notre boucle pour. 359 00:16:22,190 --> 00:16:24,530 I est égale à 1, dont nous attendons. 360 00:16:24,530 --> 00:16:26,650 N est égal à 6, dont nous attendons. 361 00:16:26,650 --> 00:16:28,810 Est égal à la touche 3, dont nous attendons. 362 00:16:28,810 --> 00:16:32,625 Et texte brut, vous verrez, égal EARFOO maintenant, pas plus parce BARFOO 363 00:16:32,625 --> 00:16:37,930 dans notre itération précédente, le B était changé de capital E. Alors que nous sommes sur 364 00:16:37,930 --> 00:16:40,040 de rencontrer le problème, si ce C'est là que nous allons 365 00:16:40,040 --> 00:16:41,130 plonger dans le débogage. 366 00:16:41,130 --> 00:16:43,365 Mais quelqu'un at-il des questions sur ce que nous avons fait jusqu'à présent? 367 00:16:43,365 --> 00:16:46,770 368 00:16:46,770 --> 00:16:47,910 Fantastique. 369 00:16:47,910 --> 00:16:52,710 >> Donc, nous sommes sur le point d'exécuter ce si état, plaine support de texte Je fermai 370 00:16:52,710 --> 00:16:57,500 support supérieure à A et texte brut I inférieur ou égal à Z. Mais avant de 371 00:16:57,500 --> 00:17:00,450 Je vais dans les détails, car c'est là que Je sais que mon erreur, je tiens à souligner 372 00:17:00,450 --> 00:17:06,859 hors texte brut de I. Alors Mettons impression. 373 00:17:06,859 --> 00:17:12,020 Il ne égaler le caractère A, de sorte que semble jusqu'ici, tout va bien et bon. 374 00:17:12,020 --> 00:17:14,740 >> Donc, je m'attends à ce que la ligne par ma logique, cette ligne doit être vrai. 375 00:17:14,740 --> 00:17:16,099 C'est une lettre majuscule. 376 00:17:16,099 --> 00:17:20,599 Mais si je frappe n, nous ne réalisons que ce ligne, en fait, ne s'est pas exécuté. 377 00:17:20,599 --> 00:17:22,609 Je sautai à l'autre si. 378 00:17:22,609 --> 00:17:25,460 Pourquoi est-ce arrivé? 379 00:17:25,460 --> 00:17:27,480 >> ETUDIANT: Parce que vous avez votre état de texte brut est supérieur 380 00:17:27,480 --> 00:17:29,130 que A, non égal ou supérieur à. 381 00:17:29,130 --> 00:17:32,260 >> JASON HIRSCHHORN: Donc, j'ai eu mon texte brut I est supérieur à A, qui n'est pas supérieure 382 00:17:32,260 --> 00:17:32,850 supérieure ou égale à. 383 00:17:32,850 --> 00:17:38,130 Donc clairement, la capitale A n'a pas déclencher cette si la condition, et nous l'avons fait 384 00:17:38,130 --> 00:17:40,520 pas entrer dedans, et nous avons fait pas faire le changement nécessaire. 385 00:17:40,520 --> 00:17:41,360 Alors, c'est ça, en fait. 386 00:17:41,360 --> 00:17:42,920 J'ai pensé que mon bug. 387 00:17:42,920 --> 00:17:46,775 Je pourrais retourner dans mon fichier source, changer, et le mettre à jour et 388 00:17:46,775 --> 00:17:47,855 Vérifiez exécuter 50 fois. 389 00:17:47,855 --> 00:17:52,590 >> Mais nous allons voir, juste pour la pédagogie de même, si je continue. 390 00:17:52,590 --> 00:17:59,580 Else if n'exécute pas non plus, mais ce qui équivaut à la place est la commande 391 00:17:59,580 --> 00:18:00,500 cela ne change pas. 392 00:18:00,500 --> 00:18:04,840 Donc ce n'est pas du tout changé, et si je imprimer le texte brut ici, nous verrons aller 393 00:18:04,840 --> 00:18:08,250 à travers cette boucle n'a pas, en fait, changer cette deuxième caractère du tout. 394 00:18:08,250 --> 00:18:09,600 C'est toujours un grand A. 395 00:18:09,600 --> 00:18:12,690 >> Encore une fois, nous débogué notre erreur. 396 00:18:12,690 --> 00:18:17,380 Nous avons réalisé qu'il y avait une certaine logique manquant. 397 00:18:17,380 --> 00:18:20,590 Et nous débogué il avance avant exécuter effectivement cette ligne, 398 00:18:20,590 --> 00:18:24,320 mais vous auriez remarqué si nous avions juste Suivant frapper et sauter à cette autre si, 399 00:18:24,320 --> 00:18:26,710 ce qui signifie que que si la condition n'était pas vrai. 400 00:18:26,710 --> 00:18:29,550 Nous n'avons pas, en effet, obtenir le résultat que nous attendions. 401 00:18:29,550 --> 00:18:33,240 Alors nous aurions pu être invité, avions nous pas été aussi astucieux, à regarder 402 00:18:33,240 --> 00:18:38,510 que si l'état et de vérifier si, en fait, notre condition devrait évaluer à 403 00:18:38,510 --> 00:18:41,150 vrai dans le contexte actuel. 404 00:18:41,150 --> 00:18:42,880 >> C'est tout pour le débogage de ce programme. 405 00:18:42,880 --> 00:18:45,340 Quelqu'un at-il des questions? 406 00:18:45,340 --> 00:18:50,486 Quelle est la commande que je pourrais frapper à quitter GDB? 407 00:18:50,486 --> 00:18:53,900 Q. Et puis je vais être amené, quitter de toute façon? 408 00:18:53,900 --> 00:18:54,390 Oui ou non. 409 00:18:54,390 --> 00:18:58,440 Je vais frapper oui, et je l'ai quitter GDB. 410 00:18:58,440 --> 00:19:00,860 >> C'était donc une amorce rapide de GDB. 411 00:19:00,860 --> 00:19:03,430 En fait, dans un scénario réel, Je l'ai fait pendant les heures de bureau. 412 00:19:03,430 --> 00:19:06,710 Je GDBed ce programme exact heures de bureau avec un étudiant. 413 00:19:06,710 --> 00:19:12,410 Et si nous revenons aux commandes, nous avons vu avant, nous avons utilisé la rupture principale, première 414 00:19:12,410 --> 00:19:13,190 chose que nous avons fait. 415 00:19:13,190 --> 00:19:16,060 Nous avons utilisé terme avec des arguments de ligne de commande, deuxième chose que nous avons fait. 416 00:19:16,060 --> 00:19:18,520 Nous avons utilisé la prochaine beaucoup à se déplacer nous à travers les lignes. 417 00:19:18,520 --> 00:19:20,310 Et encore, la version courte de est à côté n. 418 00:19:20,310 --> 00:19:22,920 C'est dans les parenthèses en gris sur la diapositive. 419 00:19:22,920 --> 00:19:28,590 >> Nous n'avons pas utilisé l'étape, mais nous n'avons pas nécessairement besoin de ce cas. 420 00:19:28,590 --> 00:19:32,150 Mais nous pourrions utiliser dans un peu plus tard aujourd'hui si nous sommes le débogage, pour 421 00:19:32,150 --> 00:19:36,500 exemple, la recherche binaire lorsque binaire recherche est appelé dans un document distinct 422 00:19:36,500 --> 00:19:38,200 fonction, mais il ya une erreur avec elle. 423 00:19:38,200 --> 00:19:40,440 Nous allons vouloir entrer dans l'appel à la recherche binaire et 424 00:19:40,440 --> 00:19:41,840 effectivement déboguer. 425 00:19:41,840 --> 00:19:45,130 Liste, nous n'avons pas utiliser parce que nous avions un bon sens de notre code, mais si je 426 00:19:45,130 --> 00:19:48,420 ne voulait se faire une idée de ce que je Code était là, je ne pouvais tout simplement utiliser la liste. 427 00:19:48,420 --> 00:19:50,310 >> Imprimons, nous avons utilisé, nous avons utilisé les habitants d'info. 428 00:19:50,310 --> 00:19:53,260 Continuons, nous n'avons pas besoin d'utiliser dans ce cas, ni ne nous besoin d'utiliser 429 00:19:53,260 --> 00:19:55,060 désactivons, mais nous avons fait usage quitter. 430 00:19:55,060 --> 00:19:57,850 Encore une fois, ces 10 commandes, pratiquer. 431 00:19:57,850 --> 00:20:00,770 Si vous comprenez ces 10 commandes, vous devriez être pour le débogage tout 432 00:20:00,770 --> 00:20:02,525 délivrer GDB. 433 00:20:02,525 --> 00:20:05,230 434 00:20:05,230 --> 00:20:08,420 >> Donc, nous sommes sur le point d'aller plus loin, de nouveau, à la cœur de l'article d'aujourd'hui, aller plus 435 00:20:08,420 --> 00:20:09,720 ces tri et de recherche algorithmes. 436 00:20:09,720 --> 00:20:14,075 Avant de le faire, à nouveau, des questions, commentaires, préoccupations pour GDB? 437 00:20:14,075 --> 00:20:16,750 438 00:20:16,750 --> 00:20:20,960 Donc tout le monde est va utiliser GDB plutôt que printf? 439 00:20:20,960 --> 00:20:24,550 Donc tout le monde, à cause de la perpétuité, tout le monde hoche la tête de leur droit de la tête 440 00:20:24,550 --> 00:20:27,400 maintenant, je vais vous voir à des heures de bureau et tous les FO vous et voir 441 00:20:27,400 --> 00:20:29,460 ils diront, montre-moi comment utiliser GDB, et vous serez en mesure 442 00:20:29,460 --> 00:20:31,240 pour leur montrer, non? 443 00:20:31,240 --> 00:20:31,760 Sorte de? 444 00:20:31,760 --> 00:20:32,640 Peut-être que je l'espère. 445 00:20:32,640 --> 00:20:33,670 Cool. 446 00:20:33,670 --> 00:20:35,790 >> Nous allons donc passer à tri et de recherche. 447 00:20:35,790 --> 00:20:40,710 Vous voyez, j'ai une liste déjà triée pour nous, mais cela ne va pas 448 00:20:40,710 --> 00:20:42,220 d'être toujours le cas. 449 00:20:42,220 --> 00:20:49,170 Ainsi, dans le problème posé cahier des charges problème réglé trois, vous avez short 450 00:20:49,170 --> 00:20:51,410 que vous pouvez regarder, et il fait vous demande de regarder ces courts métrages. 451 00:20:51,410 --> 00:20:55,090 Toujours en conférence la semaine dernière, nous sommes allés beaucoup de ces algorithmes, donc je suis 452 00:20:55,090 --> 00:20:59,150 ne va pas passer du temps dans la classe va au cours de ces algorithmes à nouveau ou dessin 453 00:20:59,150 --> 00:21:01,130 photos pour la façon dont ces algorithmes fonctionnent. 454 00:21:01,130 --> 00:21:04,030 Encore une fois, cette information, vous pouvez ré-montre conférence, ou que l'information 455 00:21:04,030 --> 00:21:08,570 est capturé exceptionnellement sur le short pour ces recherches, tous 456 00:21:08,570 --> 00:21:10,920 qui sont disponibles à cs50.net. 457 00:21:10,920 --> 00:21:14,200 >> Ainsi, au lieu, ce que nous allons faire est d'écrire ces programmes. 458 00:21:14,200 --> 00:21:18,190 Nous avons un sens, un modèle mental, de la façon dont ils travaillent, et si ce que nous allons 459 00:21:18,190 --> 00:21:20,210 à faire est de coder pour de vrai. 460 00:21:20,210 --> 00:21:23,430 Nous allons transformer ce modèle mental, cette image, si vous voulez, dans le 461 00:21:23,430 --> 00:21:24,960 code réel. 462 00:21:24,960 --> 00:21:28,460 Et si vous étiez un peu confus ou flou sur le modèle mental, je suis totalement d' 463 00:21:28,460 --> 00:21:28,770 comprendre. 464 00:21:28,770 --> 00:21:30,540 >> Nous ne sommes pas réellement aller sauter sur le code d'emblée. 465 00:21:30,540 --> 00:21:36,030 Ainsi, alors que cette invite dans cette diapositive demande de coder recherche binaire, et 466 00:21:36,030 --> 00:21:39,470 en fait, une version itérative d' recherche binaire, la première chose que je 467 00:21:39,470 --> 00:21:42,370 voulez vraiment que vous faites est écrire du pseudo. 468 00:21:42,370 --> 00:21:47,020 Donc, vous avez ce modèle mental de la façon dont les travaux de recherche binaire. 469 00:21:47,020 --> 00:21:50,060 Prenez une feuille de papier si vous avez un facilement disponibles, ou ouvrir un 470 00:21:50,060 --> 00:21:52,520 éditeur de texte, et je voudrais tout le monde à écrire. 471 00:21:52,520 --> 00:21:57,470 Prendre quatre minutes pour écrire le pseudocode pour la recherche binaire. 472 00:21:57,470 --> 00:21:58,990 >> Encore une fois, pensez à ce modèle mental. 473 00:21:58,990 --> 00:22:01,980 Je vais venir autour si vous avez des questions et nous pouvons dessiner l'image sur. 474 00:22:01,980 --> 00:22:06,220 Mais d'abord, avant de commencer la programmation, Je voudrais écrire la 475 00:22:06,220 --> 00:22:09,920 pseudocode pour la recherche binaire quand nous plonger, nous avons une certaine direction que 476 00:22:09,920 --> 00:22:12,110 là où nous devrions tête. 477 00:22:12,110 --> 00:22:15,330 >> ETUDIANT: Pouvons-nous supposer le tableau de valeurs que nous obtenons est déjà triés? 478 00:22:15,330 --> 00:22:17,960 >> JASON HIRSCHHORN: Donc, pour la recherche binaire de travailler - excellente question - vous 479 00:22:17,960 --> 00:22:20,970 prendre dans un tri tableau de valeurs. 480 00:22:20,970 --> 00:22:22,290 Supposons donc que cela fonctionnera. 481 00:22:22,290 --> 00:22:23,480 Nous allons revenir à cette diapositive. 482 00:22:23,480 --> 00:22:27,220 Vous verrez dans le pourpre de la fonction déclaration est bool binary_search int 483 00:22:27,220 --> 00:22:29,230 valeur, les valeurs int, int n. 484 00:22:29,230 --> 00:22:32,910 Cela devrait vous être familier si vous avez déjà approché ou obtenu votre 485 00:22:32,910 --> 00:22:34,580 mains sales avec le jeu de problème. 486 00:22:34,580 --> 00:22:35,910 >> Mais c'est votre déclaration de fonction. 487 00:22:35,910 --> 00:22:39,080 Encore une fois, ne devrait pas besoin de s'inquiéter que beaucoup en ce moment. 488 00:22:39,080 --> 00:22:43,660 Ce que je veux vraiment que vous faites est de prendre quatre minutes pour binaire pseudo- 489 00:22:43,660 --> 00:22:46,380 recherche, puis nous irons plus que comme un groupe. 490 00:22:46,380 --> 00:22:47,500 Et je ferai un tour. 491 00:22:47,500 --> 00:22:49,590 Si vous avez des questions, n'hésitez pas sans lever la main. 492 00:22:49,590 --> 00:25:07,110 493 00:25:07,110 --> 00:25:09,680 >> Pourquoi ne prenez-vous pas deux minutes pour finir le pseudo? 494 00:25:09,680 --> 00:25:13,690 495 00:25:13,690 --> 00:25:15,820 Je sais que cela peut sembler ridicule nous passons beaucoup de temps sur 496 00:25:15,820 --> 00:25:20,350 quelque chose qui n'est même pas en fait dans C, mais surtout pour les plus 497 00:25:20,350 --> 00:25:24,030 algorithmes et problème difficile ensembles que nous devons comprendre, 498 00:25:24,030 --> 00:25:27,210 à partir de pseudo ne pas se soucier sur la syntaxe, juste se soucier 499 00:25:27,210 --> 00:25:29,150 la logique, est incroyablement utile. 500 00:25:29,150 --> 00:25:32,720 Et de cette façon, vous n'êtes pas résoudre deux problèmes extrêmement difficiles à la fois. 501 00:25:32,720 --> 00:25:35,390 Vous êtes juste en se concentrant sur la logique, et alors vous vous déplacez dans la syntaxe. 502 00:25:35,390 --> 00:25:59,960 503 00:25:59,960 --> 00:26:01,385 >> OK. 504 00:26:01,385 --> 00:26:03,680 Commençons en passant par le pseudo-code. 505 00:26:03,680 --> 00:26:05,380 J'ai écrit ici, binaire Recherche pseudo. 506 00:26:05,380 --> 00:26:07,360 Nous écrirons ce sur la monter ensemble. 507 00:26:07,360 --> 00:26:10,040 Ou je vais l'écrire et vous donnerai moi les invites dont j'ai besoin. 508 00:26:10,040 --> 00:26:15,010 Alors quelqu'un peut-il me donner la première ligne de la pseudo-vous 509 00:26:15,010 --> 00:26:18,350 écrit pour la recherche binaire? 510 00:26:18,350 --> 00:26:20,258 Oui, Annie? 511 00:26:20,258 --> 00:26:22,698 >> Étudiant: Alors que la longueur de la la liste est supérieur à zéro. 512 00:26:22,698 --> 00:26:26,114 513 00:26:26,114 --> 00:26:34,880 >> JASON HIRSCHHORN: Bien que la longueur de la liste supérieur à zéro. 514 00:26:34,880 --> 00:26:38,810 Et encore une fois, nous voyons un certain C-consultant choses syntaxiques sur ici. 515 00:26:38,810 --> 00:26:41,550 Mais la grande majorité est en anglais. 516 00:26:41,550 --> 00:26:43,980 Quelqu'un at-il une ligne qu'ils mettent avant cela dans leur pseudo-code? 517 00:26:43,980 --> 00:26:47,280 518 00:26:47,280 --> 00:26:50,210 >> ETUDIANT: Récupère un tableau de nombres triés. 519 00:26:50,210 --> 00:26:53,600 >> JASON HIRSCHHORN: Vous avez écrit "obtenir un tableau de nombres triés. "par la 520 00:26:53,600 --> 00:26:56,140 déclaration de fonction, nous passerons un tableau de nombres triés. 521 00:26:56,140 --> 00:26:57,280 >> ETUDIANT: [inaudible]. 522 00:26:57,280 --> 00:26:59,030 >> JASON HIRSCHHORN: Donc, nous allons avoir. 523 00:26:59,030 --> 00:27:01,820 Mais oui, si nous n'avions pas, nous aurait besoin de trier notre tableau de 524 00:27:01,820 --> 00:27:04,850 chiffres, parce que la recherche binaire ne fonctionne que sur les tableaux triés. 525 00:27:04,850 --> 00:27:11,300 Ainsi, alors que la longueur de la liste est égal à zéro, je suis allez mettre dans des accolades 526 00:27:11,300 --> 00:27:15,420 pour le faire paraître un peu plus comme C. Mais alors, semble à la carte sur un 527 00:27:15,420 --> 00:27:19,550 tout en boucle, donc à l'intérieur de ce tout boucle qu'est-ce que nous devons 528 00:27:19,550 --> 00:27:22,000 faire de la recherche binaire? 529 00:27:22,000 --> 00:27:25,530 >> Quelqu'un d'autre qui ne m'a pas donné une répondre encore mais qui a écrit cela? 530 00:27:25,530 --> 00:27:31,750 531 00:27:31,750 --> 00:27:33,320 >> ETUDIANT: Allez au milieu de la liste. 532 00:27:33,320 --> 00:27:33,980 >> JASON HIRSCHHORN: Tom. 533 00:27:33,980 --> 00:27:35,230 Allez au milieu de la liste. 534 00:27:35,230 --> 00:27:43,290 535 00:27:43,290 --> 00:27:45,530 Et la question de suivi, ce qui faisons-nous une fois que nous sommes à la 536 00:27:45,530 --> 00:27:46,870 milieu de la liste? 537 00:27:46,870 --> 00:27:49,310 >> ETUDIANT: Faites une vérification si c'est le numéro que vous cherchez. 538 00:27:49,310 --> 00:27:50,120 >> JASON HIRSCHHORN: Excellent. 539 00:27:50,120 --> 00:28:05,500 Allez au milieu de la liste et de vérifier si notre valeur est là - 540 00:28:05,500 --> 00:28:06,515 fantastique. 541 00:28:06,515 --> 00:28:10,460 Quelqu'un at-il quelque chose d'autre qui était différent que cela? 542 00:28:10,460 --> 00:28:11,210 C'est exactement ça. 543 00:28:11,210 --> 00:28:13,800 >> La première chose que nous faisons à la recherche binaire est d'aller au milieu de la liste et 544 00:28:13,800 --> 00:28:15,870 vérifier pour voir si notre valeur est là. 545 00:28:15,870 --> 00:28:19,682 Donc, je suppose que si notre valeur est là, que faisons-nous? 546 00:28:19,682 --> 00:28:21,610 >> ETUDIANT: Nous revenons zéro [inaudible]. 547 00:28:21,610 --> 00:28:23,400 >> JASON HIRSCHHORN: Ouais, si notre valeur est là, nous l'avons trouvé. 548 00:28:23,400 --> 00:28:27,950 Donc, nous pouvons dire d'une certaine façon, mais ce fonction est définie, nous disons l'utilisateur 549 00:28:27,950 --> 00:28:28,520 nous l'avons trouvé. 550 00:28:28,520 --> 00:28:30,950 Si elle n'est pas là, cependant, c'est où cela devient difficile. 551 00:28:30,950 --> 00:28:35,120 Donc, si elle n'est pas là, quelqu'un d'autre qui a été de travailler sur la recherche binaire ou 552 00:28:35,120 --> 00:28:36,830 a une idée maintenant, que faisons-nous? 553 00:28:36,830 --> 00:28:37,830 >> ETUDIANT: question. 554 00:28:37,830 --> 00:28:38,100 >> JASON HIRSCHHORN: Oui? 555 00:28:38,100 --> 00:28:39,920 >> ETUDIANT: Est ce que le tableau déjà trié? 556 00:28:39,920 --> 00:28:42,200 >> JASON HIRSCHHORN: Oui, nous supposons le tableau est déjà trié. 557 00:28:42,200 --> 00:28:46,480 >> ETUDIANT: Ainsi donc, vous devez vérifier si la valeur que vous voyez est supérieure à 558 00:28:46,480 --> 00:28:51,745 la valeur que vous voulez, vous pouvez vous déplacer au milieu de l'autre moitié. 559 00:28:51,745 --> 00:28:54,110 >> JASON HIRSCHHORN: Donc, si le milieu de la liste est supérieur à ce que nous sommes 560 00:28:54,110 --> 00:28:57,440 cherchez, alors nous n'avons quoi? 561 00:28:57,440 --> 00:28:58,320 Nous nous déplaçons où? 562 00:28:58,320 --> 00:29:01,400 >> ETUDIANT: Vous voulez passer à la moitié de la liste avec 563 00:29:01,400 --> 00:29:02,780 chiffres inférieurs à celui. 564 00:29:02,780 --> 00:29:04,460 >> JASON HIRSCHHORN: Donc, nous allons appeler que la gauche. 565 00:29:04,460 --> 00:29:15,435 Donc, si du milieu est plus grande, nous pouvons rechercher la moitié gauche de la liste. 566 00:29:15,435 --> 00:29:20,620 567 00:29:20,620 --> 00:29:22,980 Et puis par la recherche, ce qui je veux dire par la recherche? 568 00:29:22,980 --> 00:29:24,010 >> ETUDIANT: [inaudible]. 569 00:29:24,010 --> 00:29:24,410 >> JASON HIRSCHHORN: Nous allons au milieu. 570 00:29:24,410 --> 00:29:25,740 Nous répétons fait cette chose. 571 00:29:25,740 --> 00:29:29,210 Nous revenons sur notre boucle while. 572 00:29:29,210 --> 00:29:31,480 Je vais vous donner le dernier - 573 00:29:31,480 --> 00:29:39,047 d'autre, si, du milieu est inférieure à ce que nous faisons, que faisons-nous ici? 574 00:29:39,047 --> 00:29:40,360 >> ETUDIANT: Allez vers la droite. 575 00:29:40,360 --> 00:29:41,610 >> JASON HIRSCHHORN: Rechercher la droite. 576 00:29:41,610 --> 00:29:47,440 577 00:29:47,440 --> 00:29:51,710 Ce qui semble bon, mais quelqu'un at-il tout ce que nous risquons de rater ou 578 00:29:51,710 --> 00:29:53,200 tout ce que vous mettez dans votre pseudo-code? 579 00:29:53,200 --> 00:29:57,080 580 00:29:57,080 --> 00:29:58,410 Donc, c'est ce que nous avons fait jusqu'ici. 581 00:29:58,410 --> 00:30:00,960 Bien que la longueur de la liste est supérieur à zéro, nous allons aller 582 00:30:00,960 --> 00:30:03,220 au milieu de la liste et vérifier si notre valeur est là. 583 00:30:03,220 --> 00:30:06,970 >> Si le milieu est plus grande, nous allons recherche à gauche, sinon si le milieu est 584 00:30:06,970 --> 00:30:09,230 moins, nous allons chercher la droite. 585 00:30:09,230 --> 00:30:14,430 Donc, nous avons tous eu une certaine familiarité avec les termes que nous utilisons en informatique 586 00:30:14,430 --> 00:30:15,550 et les outils que nous avons. 587 00:30:15,550 --> 00:30:18,300 Mais vous déjà remarqué que nous étions parler en anglais, mais nous avons trouvé un 588 00:30:18,300 --> 00:30:24,790 beaucoup de choses qui semblaient à la carte à outils dont nous disposons dans notre trousse d'outils de codage. 589 00:30:24,790 --> 00:30:27,210 Donc, dès le départ, nous ne sommes pas va effectivement coder encore. 590 00:30:27,210 --> 00:30:33,300 >> Que voyons-nous ici en anglais que les cartes à des choses que nous pouvons écrire en C? 591 00:30:33,300 --> 00:30:34,560 >> ETUDIANT: Bien. 592 00:30:34,560 --> 00:30:35,320 >> JASON HIRSCHHORN: Bien. 593 00:30:35,320 --> 00:30:40,610 Donc tout ici cartes sur à quoi? 594 00:30:40,610 --> 00:30:42,630 >> ETUDIANT: Une boucle while. 595 00:30:42,630 --> 00:30:43,200 >> JASON HIRSCHHORN: Une boucle while? 596 00:30:43,200 --> 00:30:44,540 Ou peut-être, de façon plus générale, une boucle. 597 00:30:44,540 --> 00:30:46,260 Nous voulons faire quelque chose encore et encore. 598 00:30:46,260 --> 00:30:49,050 Donc, nous allons coder une boucle. 599 00:30:49,050 --> 00:30:51,640 Et nous savons déjà, parce que nous avons fait cette une couple de fois et nous 600 00:30:51,640 --> 00:30:54,180 avoir beaucoup d'exemples là-bas, comment fait d'écrire 601 00:30:54,180 --> 00:30:55,310 cet indice pour une boucle. 602 00:30:55,310 --> 00:30:56,160 Ce qui devrait être assez facile. 603 00:30:56,160 --> 00:30:58,070 Nous devrions être en mesure d'obtenir que commencé assez rapidement. 604 00:30:58,070 --> 00:31:01,830 >> Que voyons-nous ici? 605 00:31:01,830 --> 00:31:06,820 Quels sont les autres structures syntaxes, les choses que nous connaissons en C,-nous 606 00:31:06,820 --> 00:31:09,790 ont déjà un sens basé hors des mots que nous utilisions? 607 00:31:09,790 --> 00:31:10,830 Oui, Anna? 608 00:31:10,830 --> 00:31:11,360 [Inaudible] 609 00:31:11,360 --> 00:31:12,990 je plaisante. 610 00:31:12,990 --> 00:31:13,540 Anna, aller de l'avant. 611 00:31:13,540 --> 00:31:14,530 >> ETUDIANT: Si et d'autre. 612 00:31:14,530 --> 00:31:16,260 >> JASON HIRSCHHORN: Si et d'autre - ici. 613 00:31:16,260 --> 00:31:18,840 Alors qu'est-ce que ceux qui ressemblent? 614 00:31:18,840 --> 00:31:20,420 >> ETUDIANT: Une instruction if autre. 615 00:31:20,420 --> 00:31:21,560 >> JASON HIRSCHHORN: Ouais, conditions, non? 616 00:31:21,560 --> 00:31:24,650 Donc, nous aurons probablement besoin de écrire quelques conditions. 617 00:31:24,650 --> 00:31:31,185 Et encore une fois, mais peut-être déroutant au d'abord, nous avons généralement un sens maintenant 618 00:31:31,185 --> 00:31:34,010 de la façon d'écrire les conditions et la syntaxe de la condition. 619 00:31:34,010 --> 00:31:36,850 Et si nous ne le faisons pas, nous venons de voir les syntaxe de la condition, couper et coller 620 00:31:36,850 --> 00:31:39,950 que, parce que nous savons que nous besoin d'un état ici. 621 00:31:39,950 --> 00:31:44,910 Toutes les autres choses que nous voyons que la carte sur choses que nous pourrions avoir besoin de le faire en C? 622 00:31:44,910 --> 00:31:48,312 623 00:31:48,312 --> 00:31:48,960 Ouais, Aleha? 624 00:31:48,960 --> 00:31:50,370 >> ETUDIANT: C'est peut-être évident, simplement en vérifiant si un 625 00:31:50,370 --> 00:31:51,990 valeur est égale à quelque chose. 626 00:31:51,990 --> 00:31:54,578 >> JASON HIRSCHHORN: Alors, comment pouvons nous vérifions et - il faut aller dans le milieu de la liste 627 00:31:54,578 --> 00:31:55,610 et de vérifier si notre valeur est là? 628 00:31:55,610 --> 00:31:56,570 Comment faisons-nous cela en C? 629 00:31:56,570 --> 00:31:58,450 Quelle est la syntaxe pour cela? 630 00:31:58,450 --> 00:31:59,235 >> ETUDIANT: Equals, égaux. 631 00:31:59,235 --> 00:32:00,650 >> JASON HIRSCHHORN: Equals, égaux. 632 00:32:00,650 --> 00:32:03,540 Donc ce contrôle va probablement être un signe égal, égaux. 633 00:32:03,540 --> 00:32:04,510 Donc, nous allons savons que nous devons que quelque part. 634 00:32:04,510 --> 00:32:07,510 Et en fait, juste à l'écrire, nous voyons ces autres choses. 635 00:32:07,510 --> 00:32:11,400 Nous allons avoir à faire quelques opérateurs de comparaison là - 636 00:32:11,400 --> 00:32:12,010 fantastique. 637 00:32:12,010 --> 00:32:14,980 Donc, il ressemble réellement, par et un grand, nous n'avons pas écrit 638 00:32:14,980 --> 00:32:16,390 mot de code C encore. 639 00:32:16,390 --> 00:32:20,610 Mais nous avons le modèle mental bas via des conférences et les shorts. 640 00:32:20,610 --> 00:32:22,350 >> Nous avons écrit pseudo-code en tant que groupe. 641 00:32:22,350 --> 00:32:27,110 Et déjà, nous avons 80% si elle n'est pas 90% de ce que nous devons faire. 642 00:32:27,110 --> 00:32:28,550 Maintenant, nous avons juste besoin de coder , ce qui de plus, est un 643 00:32:28,550 --> 00:32:30,110 problème non-trivial à résoudre. 644 00:32:30,110 --> 00:32:31,890 Mais au moins, nous sommes coincés sur la logique. 645 00:32:31,890 --> 00:32:38,040 Au moins maintenant, quand nous allons à des heures de bureau, Je peux dire que je sais ce que je dois 646 00:32:38,040 --> 00:32:40,160 à faire, mais pouvez-vous rappeler me de la syntaxe? 647 00:32:40,160 --> 00:32:42,940 Ou même si les heures de bureau sont entassés, vous Google peut pour la syntaxe, plutôt 648 00:32:42,940 --> 00:32:45,040 que d'être coincé sur la logique. 649 00:32:45,040 --> 00:32:48,570 >> Et encore une fois, plutôt que d'essayer de résoudre la logique et les problèmes de syntaxe tous 650 00:32:48,570 --> 00:32:51,900 à la fois, il est souvent préférable d' briser ces deux problèmes difficiles loin dans 651 00:32:51,900 --> 00:32:58,280 deux les plus faciles à gérer et faire le pseudo-code en premier et ensuite le code en C. 652 00:32:58,280 --> 00:33:00,620 Voyons donc ce que j'ai fait pour le pseudo-code à l'avance. 653 00:33:00,620 --> 00:33:04,060 >> Bien que la longueur de la liste est supérieur à zéro, regarder le milieu 654 00:33:04,060 --> 00:33:05,090 de la liste. 655 00:33:05,090 --> 00:33:09,610 Si nombre trouvé retourné vrai, d'autre si plus grand nombre, la recherche gauche. 656 00:33:09,610 --> 00:33:13,200 Sinon, si faible nombre, la recherche droite, retourner false. 657 00:33:13,200 --> 00:33:18,710 Alors que l'air presque identique sinon presque identique à ce que nous écrivions. 658 00:33:18,710 --> 00:33:23,030 En fait, Tom, que vous avez dit la première, briser le milieu de la liste et si 659 00:33:23,030 --> 00:33:24,880 nombre trouvé dans deux états est en fait ce que j'ai fait. 660 00:33:24,880 --> 00:33:25,507 >> Je les y combiné. 661 00:33:25,507 --> 00:33:27,100 Je devrais avoir écouté vous la première fois. 662 00:33:27,100 --> 00:33:30,640 Donc, c'est le pseudo-code que nous avons. 663 00:33:30,640 --> 00:33:35,060 Si vous voulez maintenant, désolé, aller revenir à notre problème initial. 664 00:33:35,060 --> 00:33:37,780 Laissez-nous le code binary.c. 665 00:33:37,780 --> 00:33:40,870 Ainsi, mettre en oeuvre une version itérative d' recherche binaire en utilisant ce qui suit 666 00:33:40,870 --> 00:33:42,420 déclaration de fonction. 667 00:33:42,420 --> 00:33:44,550 >> Et vous n'avez pas besoin de copier vers le bas pour l'instant. 668 00:33:44,550 --> 00:33:49,470 Je vais en fait d'ouvrir vous ici binary.c. 669 00:33:49,470 --> 00:33:52,880 Donc, il ya la déclaration de fonction dans le milieu de l'écran. 670 00:33:52,880 --> 00:33:57,570 Et vous verrez j'ai pris le pseudo-code de sur mes côtés, mais presque identique 671 00:33:57,570 --> 00:33:59,740 à ce que nous écrivions, et mettre que pour vous. 672 00:33:59,740 --> 00:34:06,010 Alors maintenant, nous allons prendre cinq minutes pour coder cette fonction. 673 00:34:06,010 --> 00:34:08,199 >> Et encore une fois, si vous avez des questions, levez la main, laissez-moi savoir, je vais 674 00:34:08,199 --> 00:34:08,710 venir autour. 675 00:34:08,710 --> 00:34:09,800 >> ETUDIANT: [inaudible]. 676 00:34:09,800 --> 00:34:12,380 >> JASON HIRSCHHORN: Donc j'ai pris le binaire définition de recherche en 677 00:34:12,380 --> 00:34:14,429 haut, sur la ligne 12. 678 00:34:14,429 --> 00:34:16,429 C'est ce que j'ai pour ma diapositive. 679 00:34:16,429 --> 00:34:20,940 Et puis tout ce pseudo-code que je viens de copier et coller à partir de la diapositive, 680 00:34:20,940 --> 00:34:22,190 pseudo-code diapositive. 681 00:34:22,190 --> 00:35:22,830 682 00:35:22,830 --> 00:35:26,786 Je ne suis toujours pas entendre [inaudible]. 683 00:35:26,786 --> 00:37:13,010 684 00:37:13,010 --> 00:37:15,820 >> Donc, si vous avez terminé votre mise en œuvre, je tiens à le vérifier. 685 00:37:15,820 --> 00:37:19,410 Je vous ai envoyé le fichier Helpers.h précédemment dans cette classe. 686 00:37:19,410 --> 00:37:22,360 Et il sera disponible en ligne ainsi pour le téléchargement pour regarder les gens 687 00:37:22,360 --> 00:37:24,750 cette fois de l'article retardée. 688 00:37:24,750 --> 00:37:29,350 Et je viens d'utiliser la distribution générique Code de pset3. 689 00:37:29,350 --> 00:37:34,590 J'ai donc pris find.C, utiliser mon fichier Helpers.h plutôt que le fichier Helpers.h 690 00:37:34,590 --> 00:37:36,280 qui est donnée dans le code de distribution. 691 00:37:36,280 --> 00:37:39,310 >> Et je devais faire un autre changement dans find.C plutôt que d'appeler tout simplement 692 00:37:39,310 --> 00:37:42,770 recherche, appeler binary_search. 693 00:37:42,770 --> 00:37:49,080 Donc, si vous voulez tester votre code, savent que c'est la façon de le faire. 694 00:37:49,080 --> 00:37:52,530 En fait, lorsque nous allons exécuter ce code en ce moment, je viens de faire une copie de 695 00:37:52,530 --> 00:37:59,820 mon répertoire pset3, encore une fois, échangé les fichiers Aides et puis faites que 696 00:37:59,820 --> 00:38:04,695 changer dans find.C appeler binary_search plutôt que de simplement chercher. 697 00:38:04,695 --> 00:40:08,620 698 00:40:08,620 --> 00:40:09,120 >> JASON HIRSCHHORN: Oui. 699 00:40:09,120 --> 00:40:11,258 Vous avez une question? 700 00:40:11,258 --> 00:40:12,150 >> ETUDIANT: Passons. 701 00:40:12,150 --> 00:40:12,600 >> JASON HIRSCHHORN: Pas de soucis. 702 00:40:12,600 --> 00:40:13,370 Eh bien, nous allons commencer. 703 00:40:13,370 --> 00:40:15,090 Nous allons coder cela comme un groupe. 704 00:40:15,090 --> 00:40:16,050 Une autre note. 705 00:40:16,050 --> 00:40:20,600 Encore une fois, ce n'est, peut facilement être échangé dans de problème Set Trois. 706 00:40:20,600 --> 00:40:25,530 J'ai mon fichier Helpers.h qui, plutôt que la Helpers.h on nous donne, 707 00:40:25,530 --> 00:40:28,560 déclare recherche binaire, bulle tri et la sélection sorte. 708 00:40:28,560 --> 00:40:37,400 Et dans find.c vous remarquerez sur la ligne, quel est ce, ligne 68, nous appelons binaire 709 00:40:37,400 --> 00:40:39,160 recherche plutôt que la recherche. 710 00:40:39,160 --> 00:40:42,930 Encore une fois, le code est disponible en ligne ou le code qui vous êtes 711 00:40:42,930 --> 00:40:46,590 la création en ce moment peut être facilement échangé en p pour la série 3 pour le vérifier. 712 00:40:46,590 --> 00:40:50,620 >> Mais d'abord, nous allons Recherche de code binaire. 713 00:40:50,620 --> 00:40:53,690 Notre déclaration de fonction, nous revenons un bool. 714 00:40:53,690 --> 00:40:55,810 Nous prenons un nombre entier appelé valeur. 715 00:40:55,810 --> 00:40:59,285 Nous prenons un tableau d'entiers appelé valeurs, et nous prenons n être 716 00:40:59,285 --> 00:41:00,850 la taille de la matrice. 717 00:41:00,850 --> 00:41:05,640 Sur la ligne 10, ici, j'ai forte comprennent stdbool.h. 718 00:41:05,640 --> 00:41:07,360 Est-ce que quelqu'un sait pourquoi c'est là? 719 00:41:07,360 --> 00:41:12,180 720 00:41:12,180 --> 00:41:16,600 Alors qu'est-ce que cette ligne de code fait? 721 00:41:16,600 --> 00:41:19,880 >> ETUDIANT: Il vous permet de utiliser un type de retour bool. 722 00:41:19,880 --> 00:41:20,350 >> JASON HIRSCHHORN: Exactement. 723 00:41:20,350 --> 00:41:22,300 >> ETUDIANT: Ou c'est une bibliothèque qui permet d'utiliser un type de retour bool. 724 00:41:22,300 --> 00:41:27,590 >> JASON HIRSCHHORN: Donc, la forte comprennent ligne stdbool.h me donne une certaine 725 00:41:27,590 --> 00:41:31,340 les définitions et les déclarations pour des choses que je suis autorisé à utiliser dans 726 00:41:31,340 --> 00:41:32,400 cette bibliothèque. 727 00:41:32,400 --> 00:41:36,570 Donc parmi ceux se disant qu'il ya ce type bool appelé, et il peut être 728 00:41:36,570 --> 00:41:37,750 vrai ou faux. 729 00:41:37,750 --> 00:41:39,010 C'est ce que cette ligne fait. 730 00:41:39,010 --> 00:41:41,680 Et si je n'ai pas eu cette ligne, je voudrais avoir des ennuis pour la rédaction de ce 731 00:41:41,680 --> 00:41:43,520 mot ici, bool, juste là. 732 00:41:43,520 --> 00:41:44,140 Exactement. 733 00:41:44,140 --> 00:41:46,430 J'ai donc besoin que dans ce code. 734 00:41:46,430 --> 00:41:47,690 OK. 735 00:41:47,690 --> 00:41:51,860 Donc, encore une fois, est un processus itératif la version, pas un récursive. 736 00:41:51,860 --> 00:41:53,820 Alors laissez-nous commencer. 737 00:41:53,820 --> 00:41:56,200 >> Commençons par cette première ligne de code pseudo. 738 00:41:56,200 --> 00:41:58,770 Et nous espérons, nous le ferons - ou pas d'espoir. 739 00:41:58,770 --> 00:42:00,530 Nous allons faire le tour de la salle. 740 00:42:00,530 --> 00:42:05,110 Nous allons ligne par ligne, et je vais vous aider vous avez compris la ligne que nous avons besoin 741 00:42:05,110 --> 00:42:06,310 d'écrire en premier. 742 00:42:06,310 --> 00:42:10,550 Ainsi, alors que la longueur de la liste est supérieur à zéro. 743 00:42:10,550 --> 00:42:12,680 Commençons à l'avant. 744 00:42:12,680 --> 00:42:15,190 Quelle ligne devrais-je écrire ici, dans le code? 745 00:42:15,190 --> 00:42:19,470 >> ETUDIANT: Bien parenthèses n est supérieur à 0. 746 00:42:19,470 --> 00:42:21,900 >> JASON HIRSCHHORN: Bien n est grand que 0. 747 00:42:21,900 --> 00:42:26,550 Donc n est la taille de la liste, et nous vérifions si - 748 00:42:26,550 --> 00:42:26,800 >> [VOIX interposition] 749 00:42:26,800 --> 00:42:27,660 >> JASON HIRSCHHORN: - Pardon? 750 00:42:27,660 --> 00:42:29,360 >> Étudiant: Comment savons-nous que n est la taille de la liste? 751 00:42:29,360 --> 00:42:29,690 >> JASON HIRSCHHORN: Désolé. 752 00:42:29,690 --> 00:42:34,690 Par la spécification pset, la recherche et des fonctions de tri, vous devez écrire, 753 00:42:34,690 --> 00:42:36,230 n est la taille de la liste. 754 00:42:36,230 --> 00:42:37,710 J'ai oublié d'expliquer ici. 755 00:42:37,710 --> 00:42:41,310 Mais oui. n est la taille de l' la liste, dans ce cas. 756 00:42:41,310 --> 00:42:44,740 Ainsi, alors que n est supérieur à 0. 757 00:42:44,740 --> 00:42:45,580 OK. 758 00:42:45,580 --> 00:42:50,090 Cela peut se révéler un peu problématique cependant, si les choses se passent. 759 00:42:50,090 --> 00:42:54,510 Parce que nous allons continuer à connaître la taille de la liste tout au long de cette 760 00:42:54,510 --> 00:43:06,640 fonction, mais dire que nous partons avec un tableau de 5 entiers. 761 00:43:06,640 --> 00:43:08,950 Et nous allons à travers et nous avons maintenant rétréci vers le bas 762 00:43:08,950 --> 00:43:10,310 un tableau de 2 entiers. 763 00:43:10,310 --> 00:43:12,160 Dont 2 entiers est-ce? 764 00:43:12,160 --> 00:43:15,895 La taille est 2 maintenant que nous voulons Regardons, mais qui 2 est-ce? 765 00:43:15,895 --> 00:43:17,720 Cela fait-il sens, cette question? 766 00:43:17,720 --> 00:43:18,020 >> OK. 767 00:43:18,020 --> 00:43:19,120 Je vais demander à nouveau. 768 00:43:19,120 --> 00:43:26,640 Donc, nous commençons avec cet ensemble de 5 entiers, et n est égal à 5, non? 769 00:43:26,640 --> 00:43:28,050 Nous courons à travers ici. 770 00:43:28,050 --> 00:43:31,560 nous allons probablement changer la taille, droit, comme les choses se passent. 771 00:43:31,560 --> 00:43:32,700 Qui est ce que nous disons que nous voulons faire. 772 00:43:32,700 --> 00:43:34,150 Nous ne voulons pas chercher la chose complète à nouveau. 773 00:43:34,150 --> 00:43:35,480 Donc disons que nous changeons à 2. 774 00:43:35,480 --> 00:43:36,970 Nous prenons la moitié de la liste qui est étrange. 775 00:43:36,970 --> 00:43:38,800 Il suffit donc de choisir 2. 776 00:43:38,800 --> 00:43:40,590 Alors maintenant, est égal à n 2. 777 00:43:40,590 --> 00:43:42,780 Je m'excuse pour les pauvres marqueurs effaçables à sec. 778 00:43:42,780 --> 00:43:43,080 Droite? 779 00:43:43,080 --> 00:43:45,670 Et nous sommes à la recherche dans la liste à nouveau avec une liste de taille 2. 780 00:43:45,670 --> 00:43:48,580 Eh bien, notre tableau est encore de taille 5. 781 00:43:48,580 --> 00:43:51,920 Nous disons que nous ne voulons recherche 2 places en elle. 782 00:43:51,920 --> 00:43:53,590 Alors que deux spots sont ceux-là? 783 00:43:53,590 --> 00:43:57,640 784 00:43:57,640 --> 00:43:58,815 >> Cela fait-il sens? 785 00:43:58,815 --> 00:44:00,290 Sont-ils les laissés 2 points? 786 00:44:00,290 --> 00:44:01,940 Sont-ils les bonnes 2 places? 787 00:44:01,940 --> 00:44:03,540 Sont-ils les moyens 2 places? 788 00:44:03,540 --> 00:44:06,350 Nous avons brisé le problème vers le bas, mais nous ne savons pas réellement quelle partie de 789 00:44:06,350 --> 00:44:11,600 le problème que nous cherchons toujours à, tout en ayant ces 2 variables. 790 00:44:11,600 --> 00:44:16,450 Nous avons donc besoin d'un peu plus de, tandis que n est supérieur à 0. 791 00:44:16,450 --> 00:44:21,410 Nous devons savoir où que n est dans notre tableau réelle. 792 00:44:21,410 --> 00:44:26,660 >> Donc, quelqu'un at-il une changer cette ligne? 793 00:44:26,660 --> 00:44:27,970 La plupart de cette ligne est parfaitement correct. 794 00:44:27,970 --> 00:44:29,170 Y at-il un autre ajout? 795 00:44:29,170 --> 00:44:32,510 Pouvons-nous échanger quelque chose que n faire de cette ligne un peu mieux? 796 00:44:32,510 --> 00:44:32,865 Mm-hm? 797 00:44:32,865 --> 00:44:38,040 >> ETUDIANT: Pouvez-vous initialiser une variable comme la longueur de n qui va ensuite être utilisé 798 00:44:38,040 --> 00:44:39,600 plus tard dans la fonction? 799 00:44:39,600 --> 00:44:42,060 >> JASON HIRSCHHORN: Donc initialiser une longueur variable de n, 800 00:44:42,060 --> 00:44:42,900 et nous utilisons plus tard? 801 00:44:42,900 --> 00:44:47,070 Mais alors que nous venons de mettre à jour la longueur et nous encore rencontrer ce problème lorsque nous 802 00:44:47,070 --> 00:44:51,180 réduire la durée de notre problème, mais on ne sait jamais où, en fait, 803 00:44:51,180 --> 00:44:52,510 que la longueur des cartes sur. 804 00:44:52,510 --> 00:44:54,790 >> ETUDIANT: N'est-ce pas va se passer plus tard, quand vous dites, recherche à gauche, 805 00:44:54,790 --> 00:44:55,746 chercher à droite? 806 00:44:55,746 --> 00:44:57,640 Vous allez aller à un autre zone de votre - 807 00:44:57,640 --> 00:44:59,110 >> JASON HIRSCHHORN: Nous allons aller à une zone, mais comment savons-nous 808 00:44:59,110 --> 00:45:01,150 qui sont aller? 809 00:45:01,150 --> 00:45:03,800 Si nous n'avons que le tableau et ce n, comment savons-nous où 810 00:45:03,800 --> 00:45:05,050 aller au tableau. 811 00:45:05,050 --> 00:45:05,900 Dans le dos, oui? 812 00:45:05,900 --> 00:45:07,507 >> ÉTUDIANT: Avez-vous, comme, une plus faible lié et une variable limite supérieure ou 813 00:45:07,507 --> 00:45:08,586 quelque chose comme ça? 814 00:45:08,586 --> 00:45:09,060 >> JASON HIRSCHHORN: OK. 815 00:45:09,060 --> 00:45:10,780 C'est donc une autre idée. 816 00:45:10,780 --> 00:45:13,490 Plutôt que de simplement garder une trace de l' taille, nous gardons la trace de la plus faible et 817 00:45:13,490 --> 00:45:14,770 variable liée supérieure. 818 00:45:14,770 --> 00:45:17,840 Alors, comment pouvons-nous calculons la taille de une borne inférieure et la borne supérieure? 819 00:45:17,840 --> 00:45:18,520 >> [VOIX interposition] 820 00:45:18,520 --> 00:45:19,710 >> JASON HIRSCHHORN: soustraction. 821 00:45:19,710 --> 00:45:23,650 Et aussi garder la trace de la moindre lié et limite supérieure pour nous faire savoir, 822 00:45:23,650 --> 00:45:26,215 cherchons-nous ces deux? 823 00:45:26,215 --> 00:45:28,220 Sommes-nous à la recherche de ces deux ici? 824 00:45:28,220 --> 00:45:29,540 Cherchons-nous les deux du milieu? 825 00:45:29,540 --> 00:45:32,810 Probablement pas les deux du milieu, car cela, en fait, est la recherche binaire. 826 00:45:32,810 --> 00:45:37,320 Mais maintenant, nous serons en mesure d'obtenir la taille, mais aussi les limites de la matrice. 827 00:45:37,320 --> 00:45:40,020 En substance, si nous avons notre géant annuaire, nous déchirer en deux. 828 00:45:40,020 --> 00:45:42,990 Nous savons maintenant où que les petits répertoire est. 829 00:45:42,990 --> 00:45:45,260 Mais nous ne sommes pas réellement déchirant l'annuaire de moitié. 830 00:45:45,260 --> 00:45:48,570 Nous avons encore besoin de savoir où l' nouvelles limites de notre problème est. 831 00:45:48,570 --> 00:45:51,645 Quelqu'un at-il des questions à ce sujet? 832 00:45:51,645 --> 00:45:52,440 Oui? 833 00:45:52,440 --> 00:45:56,020 >> ÉTUDIANT: Serait-il travailler en créant un variable i, alors que vous décale juste 834 00:45:56,020 --> 00:46:00,770 la position de i par rapport à son la position actuelle, et de la longueur, n? 835 00:46:00,770 --> 00:46:01,710 >> JASON HIRSCHHORN: Et quelle est i? 836 00:46:01,710 --> 00:46:04,110 >> ETUDIANT: Comme je être comme sorte de - 837 00:46:04,110 --> 00:46:08,040 Comme vous le feriez d'initialiser i à la position moyenne de la matrice. 838 00:46:08,040 --> 00:46:12,540 Et puis, si la valeur à la position i dans au milieu de la matrice pour en trouvé 839 00:46:12,540 --> 00:46:17,870 être inférieure à la valeur que vous avez besoin, je maintenant devient la longueur du tableau, plus 840 00:46:17,870 --> 00:46:19,215 la valeur de i divisée par deux. 841 00:46:19,215 --> 00:46:20,270 Comme, voir, vous passez i - 842 00:46:20,270 --> 00:46:20,770 >> JASON HIRSCHHORN: Droit. 843 00:46:20,770 --> 00:46:21,165 >> ETUDIANT: - à la - 844 00:46:21,165 --> 00:46:24,010 >> JASON HIRSCHHORN: Je suis presque positif qui va travailler. 845 00:46:24,010 --> 00:46:26,800 Mais le point de l'être, vous avez besoin de deux éléments d'information ici. 846 00:46:26,800 --> 00:46:30,050 Vous pouvez le faire avec début et à la fin, ou vous pouvez le faire avec la taille, puis 847 00:46:30,050 --> 00:46:31,060 certains marqueur. 848 00:46:31,060 --> 00:46:32,630 Mais vous n'avez pas besoin de deux pièces d'informations ici. 849 00:46:32,630 --> 00:46:34,160 Vous ne pouvez pas vous en tirer avec un seul. 850 00:46:34,160 --> 00:46:35,830 Est-ce que c'est logique? 851 00:46:35,830 --> 00:46:39,560 >> Donc, nous allons passer, et nous allons faire [inaudible] 852 00:46:39,560 --> 00:46:41,330 et créer des marqueurs. 853 00:46:41,330 --> 00:46:42,690 Alors t'as écrivez dans votre code? 854 00:46:42,690 --> 00:46:46,190 >> Etudiant: Je viens de dire int lié l'un est égal à 0. 855 00:46:46,190 --> 00:46:47,790 >> JASON HIRSCHHORN: Appelons que int, en commençant. 856 00:46:47,790 --> 00:46:49,140 >> ETUDIANT: OK. 857 00:46:49,140 --> 00:46:50,590 >> JASON HIRSCHHORN: Cela fait plus de sens pour moi. 858 00:46:50,590 --> 00:46:51,670 Et? 859 00:46:51,670 --> 00:46:54,340 >> ETUDIANT: je l'ai dit, je suppose, int fin. 860 00:46:54,340 --> 00:46:55,870 >> JASON HIRSCHHORN: int fin. 861 00:46:55,870 --> 00:46:57,640 >> Étudiant: Je suppose, n moins 1, ou quelque chose comme ça. 862 00:46:57,640 --> 00:46:59,100 Comme, le dernier élément. 863 00:46:59,100 --> 00:47:02,310 >> JASON HIRSCHHORN: Donc vous avez écrit, int début égale à 0, point-virgule, et int 864 00:47:02,310 --> 00:47:04,320 fin égale n moins 1, point-virgule. 865 00:47:04,320 --> 00:47:06,850 Donc, essentiellement, ce que nous faisons ici, la première position 0. 866 00:47:06,850 --> 00:47:09,570 Et comme nous le savons dans des tableaux, ils ne vont pas jusqu'à n, elles montent à n moins 1. 867 00:47:09,570 --> 00:47:11,110 Nous avons donc des limites de notre tableau. 868 00:47:11,110 --> 00:47:15,730 Et ces premières bornes se trouvent les limites initiales de notre problème. 869 00:47:15,730 --> 00:47:16,640 OK. 870 00:47:16,640 --> 00:47:19,200 Donc, ça sonne bien. 871 00:47:19,200 --> 00:47:22,380 Ensuite, si nous revenons à cette ligne, tout en la longueur de la liste est supérieur à 0, 872 00:47:22,380 --> 00:47:24,752 ce que, au lieu de n, devrait nous mettons ici? 873 00:47:24,752 --> 00:47:28,820 >> ETUDIANT: Donnez fin moins début. 874 00:47:28,820 --> 00:47:34,780 >> JASON HIRSCHHORN: Bien se terminant moins début est supérieur à 0? 875 00:47:34,780 --> 00:47:35,480 OK. 876 00:47:35,480 --> 00:47:37,730 Et nous pourrions, si nous voulions faire un peu mieux que, ce 877 00:47:37,730 --> 00:47:38,980 pouvions-nous faire? 878 00:47:38,980 --> 00:47:41,650 879 00:47:41,650 --> 00:47:43,412 Si nous voulions nettoyer ce code un peu? 880 00:47:43,412 --> 00:47:46,716 881 00:47:46,716 --> 00:47:48,180 Comment pouvons-nous nous débarrasser de la 0? 882 00:47:48,180 --> 00:47:51,560 883 00:47:51,560 --> 00:47:52,690 C'est juste une question de style. 884 00:47:52,690 --> 00:47:53,690 Il est exact en ce moment. 885 00:47:53,690 --> 00:47:54,870 >> ETUDIANT: Ending ne égal début? 886 00:47:54,870 --> 00:47:55,740 >> JASON HIRSCHHORN: Nous pouvons faire quoi? 887 00:47:55,740 --> 00:47:56,730 >> [VOIX interposition] 888 00:47:56,730 --> 00:47:57,330 >> ETUDIANT: Ending est supérieure? 889 00:47:57,330 --> 00:47:57,720 >> JASON HIRSCHHORN: Ouais. 890 00:47:57,720 --> 00:48:01,110 Nous pouvons juste faire tout en mettant fin est supérieure à début. 891 00:48:01,110 --> 00:48:03,580 Droite. 892 00:48:03,580 --> 00:48:06,240 Nous avons ajouté à partir de l'autre côté de cela, et nous nous sommes débarrassés de l'0. 893 00:48:06,240 --> 00:48:08,000 Ainsi, elle a simplement un peu plus propre. 894 00:48:08,000 --> 00:48:08,990 OK. 895 00:48:08,990 --> 00:48:11,460 Ainsi, alors que la longueur de la liste est 0, nous avons écrit que, tout en mettant fin est plus 896 00:48:11,460 --> 00:48:12,240 que de commencer. 897 00:48:12,240 --> 00:48:19,840 Nous allons mettre dans notre nécessaire accolades, et puis la première chose 898 00:48:19,840 --> 00:48:22,090 nous voulons faire est de regarder eux dans une petite liste. 899 00:48:22,090 --> 00:48:22,510 Vous? 900 00:48:22,510 --> 00:48:23,320 Pouvez-vous me donner le - 901 00:48:23,320 --> 00:48:26,460 >> ETUDIANT: Si parenthèses support carré de valeur - 902 00:48:26,460 --> 00:48:30,450 >> JASON HIRSCHHORN: Si parenthèses support carré de valeur. 903 00:48:30,450 --> 00:48:33,210 >> ETUDIANT: Ending divisé par 2. 904 00:48:33,210 --> 00:48:33,952 >> JASON HIRSCHHORN: Fin? 905 00:48:33,952 --> 00:48:35,280 >> Étudiant: Je vois un problème avec votre - 906 00:48:35,280 --> 00:48:35,750 >> JASON HIRSCHHORN: OK. 907 00:48:35,750 --> 00:48:39,150 Eh bien, regardez au milieu. 908 00:48:39,150 --> 00:48:41,226 Comment savons-nous ce que le milieu est? 909 00:48:41,226 --> 00:48:42,450 Ouais. 910 00:48:42,450 --> 00:48:43,070 Permettez-moi de supprimer ce code. 911 00:48:43,070 --> 00:48:46,360 Comment savons-nous ce que le milieu est? 912 00:48:46,360 --> 00:48:48,003 En tout, quand vous avez le début et la fin, comment trouvez-vous 913 00:48:48,003 --> 00:48:48,876 le milieu? 914 00:48:48,876 --> 00:48:49,590 >> ETUDIANT: Vous faites la moyenne. 915 00:48:49,590 --> 00:48:51,820 >> ETUDIANT: Vous ajoutez ensemble et ensuite - 916 00:48:51,820 --> 00:48:53,150 >> JASON HIRSCHHORN: Ajouter les ensemble et alors? 917 00:48:53,150 --> 00:48:54,090 >> Étudiant: Et vous faites la moyenne. 918 00:48:54,090 --> 00:48:55,050 Diviser par 2. 919 00:48:55,050 --> 00:48:56,500 >> JASON HIRSCHHORN: Ajouter les et diviser par 2. 920 00:48:56,500 --> 00:48:59,400 Donc milieu int égale? 921 00:48:59,400 --> 00:49:01,120 Tom, vous pouvez me le donner? 922 00:49:01,120 --> 00:49:03,550 >> Étudiante: Début en plus fin - 923 00:49:03,550 --> 00:49:04,950 >> JASON HIRSCHHORN: Début en plus fin. 924 00:49:04,950 --> 00:49:06,880 >> ETUDIANT: Tout, support, divisé par 2. 925 00:49:06,880 --> 00:49:10,940 >> JASON HIRSCHHORN: Tout, entre parenthèses, divisée par deux. 926 00:49:10,940 --> 00:49:16,300 Ce qui me donne le milieu de quoi que ce soit, corriger? 927 00:49:16,300 --> 00:49:18,980 >> ETUDIANT: Vous avez également besoin d'arrondir vers le haut. 928 00:49:18,980 --> 00:49:19,990 >> JASON HIRSCHHORN: Ce que vous faites dire, j'ai besoin d'arrondir vers le haut? 929 00:49:19,990 --> 00:49:20,400 >> [VOIX interposition] 930 00:49:20,400 --> 00:49:24,520 >> ETUDIANT: Parce que si c'est une étrange nombre, alors c'est comme - 931 00:49:24,520 --> 00:49:25,440 >> JASON HIRSCHHORN: Eh bien, OK. 932 00:49:25,440 --> 00:49:26,360 Ainsi, j'ai pu arrondir vers le haut. 933 00:49:26,360 --> 00:49:33,350 Mais si c'est un nombre impair, un 5, je peux prendre une distance à partir du milieu. 934 00:49:33,350 --> 00:49:35,665 Ou si c'est un nombre pair, plutôt, c'est une meilleure affaire. 935 00:49:35,665 --> 00:49:39,600 Si c'est 4, nous avons seulement 4, je peux prendre la première «milieu», entre guillemets ou 936 00:49:39,600 --> 00:49:41,760 le second «milieu». 937 00:49:41,760 --> 00:49:46,390 Soit serait travailler pour une recherche binaire, donc je n'ai pas vraiment besoin de l'arrondir. 938 00:49:46,390 --> 00:49:48,640 Mais il ya une autre chose que je besoin de regarder cette ligne. 939 00:49:48,640 --> 00:49:50,530 Nous pourrions ne pas le réaliser encore, mais nous allons y revenir. 940 00:49:50,530 --> 00:49:53,200 Parce que cette ligne fait encore besoin une autre chose. 941 00:49:53,200 --> 00:49:55,990 >> Mais jusqu'à présent, nous avons écrit quatre lignes de code. 942 00:49:55,990 --> 00:49:58,120 Nous avons notre début et se terminant marqueurs. 943 00:49:58,120 --> 00:50:01,320 Nous avons notre boucle while, qui mappe sur directement à notre pseudo. 944 00:50:01,320 --> 00:50:05,790 Nous cherchons au milieu qui mappe directement sur notre pseudo. 945 00:50:05,790 --> 00:50:09,070 Je dirais cela va au milieu de la liste, cette ligne de code. 946 00:50:09,070 --> 00:50:11,560 Et puis, une fois que nous allons à la moyenne de la liste, la prochaine chose que nous devons faire 947 00:50:11,560 --> 00:50:14,880 est de vérifier si notre valeur est là pour le pseudo-code, nous avons écrit plus tôt. 948 00:50:14,880 --> 00:50:17,100 >> Alors, comment pouvons nous vérifions si notre valeur est au milieu de la liste? 949 00:50:17,100 --> 00:50:17,300 Vous. 950 00:50:17,300 --> 00:50:18,511 Pourquoi ne pas vous faire cela? 951 00:50:18,511 --> 00:50:23,070 >> ETUDIANT: Si notre valeur de est au milieu est égal à 952 00:50:23,070 --> 00:50:24,592 tout ce que nous mettons le - 953 00:50:24,592 --> 00:50:26,190 Je veux dire égal à égal - 954 00:50:26,190 --> 00:50:26,690 >> JASON HIRSCHHORN: Il - 955 00:50:26,690 --> 00:50:27,940 OK. 956 00:50:27,940 --> 00:50:30,080 957 00:50:30,080 --> 00:50:32,170 >> Étudiant: Je ne suis pas sûr de ce que l' variable, nous sommes à la recherche 958 00:50:32,170 --> 00:50:32,850 pour que, parce que - 959 00:50:32,850 --> 00:50:33,330 >> [VOIX interposition] 960 00:50:33,330 --> 00:50:34,520 >> ETUDIANT: [inaudible]. 961 00:50:34,520 --> 00:50:35,060 >> JASON HIRSCHHORN: Exactement. 962 00:50:35,060 --> 00:50:37,260 Par la déclaration de fonction, nous sommes à la recherche d'une valeur. 963 00:50:37,260 --> 00:50:39,760 Nous allons donc chercher une valeur dans un tableau de valeurs. 964 00:50:39,760 --> 00:50:41,080 Donc, vous avez parfaitement raison. 965 00:50:41,080 --> 00:50:45,040 Vous ferez, si le support de la valeur de parenthèse ouverte milieu fermé égaux de support 966 00:50:45,040 --> 00:50:49,930 est égale à la valeur et à l'intérieur il que devons-nous faire? 967 00:50:49,930 --> 00:50:51,230 Si notre valeur est là, ce devons-nous faire? 968 00:50:51,230 --> 00:50:51,420 >> [VOIX interposition] 969 00:50:51,420 --> 00:50:52,160 >> ETUDIANT: Retour zéro. 970 00:50:52,160 --> 00:50:53,070 >> JASON HIRSCHHORN: Retour vrai. 971 00:50:53,070 --> 00:50:54,790 >> ETUDIANT: Retour vrai. 972 00:50:54,790 --> 00:50:57,856 >> JASON HIRSCHHORN: Michael, qu'est-ce que cette ligne fait? 973 00:50:57,856 --> 00:51:01,105 >> ETUDIANT: [inaudible] l'exécution du programme sa course, et qui est au-dessus, et 974 00:51:01,105 --> 00:51:01,920 vous avez ce que vous devez faire? 975 00:51:01,920 --> 00:51:03,030 >> JASON HIRSCHHORN: Le programme ou quoi? 976 00:51:03,030 --> 00:51:03,700 Dans ce cas? 977 00:51:03,700 --> 00:51:04,210 >> ÉTUDIANTS: La fonction. 978 00:51:04,210 --> 00:51:05,170 >> JASON HIRSCHHORN: La fonction. 979 00:51:05,170 --> 00:51:08,420 Et donc, pour revenir à ce que appelé et lui donner la valeur, c'est vrai. 980 00:51:08,420 --> 00:51:09,890 Exactement. 981 00:51:09,890 --> 00:51:10,170 Main. 982 00:51:10,170 --> 00:51:12,035 Quel est le type de retour de principal, Michael? 983 00:51:12,035 --> 00:51:16,480 984 00:51:16,480 --> 00:51:17,150 >> ETUDIANT: int, entier? 985 00:51:17,150 --> 00:51:18,080 >> JASON HIRSCHHORN: int, exactement. 986 00:51:18,080 --> 00:51:18,680 Un entier. 987 00:51:18,680 --> 00:51:20,980 C'était juste une question de s'assurer vous les gars ont été au-dessus de celui-ci. 988 00:51:20,980 --> 00:51:24,250 Que faut-il revenir souvent, si toutes les choses fonctionnent bien? 989 00:51:24,250 --> 00:51:24,520 >> ETUDIANT: Zéro. 990 00:51:24,520 --> 00:51:24,820 >> JASON HIRSCHHORN: zéro. 991 00:51:24,820 --> 00:51:25,430 Exactement. 992 00:51:25,430 --> 00:51:28,790 >> ETUDIANT: Si cela renvoie simplement vrai, il n'y a pas d'informations étant donné 993 00:51:28,790 --> 00:51:30,675 sur ce que le - 994 00:51:30,675 --> 00:51:34,040 Oh, c'est juste dire que ce valeur est à l'intérieur du tableau. 995 00:51:34,040 --> 00:51:35,350 >> JASON HIRSCHHORN: Exactement. 996 00:51:35,350 --> 00:51:38,080 Ce programme ne donne pas d'informations où exactement la valeur est. 997 00:51:38,080 --> 00:51:41,850 C'est seulement en disant, oui, nous avons trouvé il, ou non, nous n'avons pas trouvé. 998 00:51:41,850 --> 00:51:42,990 Donc, si le nombre trouvé, retourne vrai. 999 00:51:42,990 --> 00:51:45,500 Eh bien, en fait nous avons juste fait ce vraiment rapidement que une ligne de code. 1000 00:51:45,500 --> 00:51:47,500 Je propose donc que la ligne de pseudo. 1001 00:51:47,500 --> 00:51:50,045 >> ETUDIANT: N'avons-nous pas besoin pour changer le tableau? 1002 00:51:50,045 --> 00:51:52,830 Il devrait être des valeurs, pas de valeur, non? 1003 00:51:52,830 --> 00:51:53,430 >> JASON HIRSCHHORN: Désolé. 1004 00:51:53,430 --> 00:51:54,010 Merci. 1005 00:51:54,010 --> 00:51:54,800 >> ÉTUDIANT: Oui. 1006 00:51:54,800 --> 00:51:55,850 >> JASON HIRSCHHORN: Cette ligne devraient être des valeurs. 1007 00:51:55,850 --> 00:51:57,150 Exactement. 1008 00:51:57,150 --> 00:51:57,920 OK. 1009 00:51:57,920 --> 00:51:59,170 Donc, nous avons examiné la liste du milieu. 1010 00:51:59,170 --> 00:52:00,790 Si nombre trouvé return true. 1011 00:52:00,790 --> 00:52:04,470 Continuant sur notre pseudo, si milieu est supérieur, la recherche gauche. 1012 00:52:04,470 --> 00:52:09,640 J'ai donc eu ici, si le nombre supérieur, la recherche gauche. 1013 00:52:09,640 --> 00:52:12,700 1014 00:52:12,700 --> 00:52:14,462 Constantine, peut vous donner moi cette ligne de code? 1015 00:52:14,462 --> 00:52:17,240 1016 00:52:17,240 --> 00:52:23,520 >> ÉTUDIANT: Si la valeur moyenne - 1017 00:52:23,520 --> 00:52:24,890 >> JASON HIRSCHHORN: Donc, si la valeur - 1018 00:52:24,890 --> 00:52:28,890 si parenthèse ouverte valeurs support support à proximité du milieu - 1019 00:52:28,890 --> 00:52:31,500 >> ETUDIANT: Est inférieure à la valeur? 1020 00:52:31,500 --> 00:52:32,760 >> JASON HIRSCHHORN: Est moins. 1021 00:52:32,760 --> 00:52:33,800 >> ETUDIANT: Moins de valeur. 1022 00:52:33,800 --> 00:52:34,060 >> JASON HIRSCHHORN Valeur. 1023 00:52:34,060 --> 00:52:35,310 Eh bien, en fait, vous voulez vérifier si le nombre - 1024 00:52:35,310 --> 00:52:38,310 1025 00:52:38,310 --> 00:52:38,490 Désolé. 1026 00:52:38,490 --> 00:52:39,140 C'est un peu déroutant. 1027 00:52:39,140 --> 00:52:43,920 Mais d'autre si le nombre dans la milieu de la liste est plus grande. 1028 00:52:43,920 --> 00:52:45,170 >> ETUDIANT: Oh, OK. 1029 00:52:45,170 --> 00:52:49,800 1030 00:52:49,800 --> 00:52:50,410 >> JASON HIRSCHHORN: Je vais changer cela. 1031 00:52:50,410 --> 00:52:55,060 Sinon, si milieu est plus élevé, nous vouloir chercher gauche, OK? 1032 00:52:55,060 --> 00:52:57,310 Et que faisons-nous à l'intérieur ce si l'état? 1033 00:52:57,310 --> 00:53:03,660 1034 00:53:03,660 --> 00:53:07,510 >> ETUDIANT: Puis-je faire un petit changement à l'état, changer à autre si? 1035 00:53:07,510 --> 00:53:08,380 >> JASON HIRSCHHORN: Sinon, si? 1036 00:53:08,380 --> 00:53:09,270 OK. 1037 00:53:09,270 --> 00:53:12,840 Donc, ce code s'exécute environ la même. 1038 00:53:12,840 --> 00:53:18,620 Mais la bonne chose sur l'utilisation de if, else si, d'autre ou si, si, d'autre si, d'autre 1039 00:53:18,620 --> 00:53:22,320 signifie que seulement l'un de ceux va vérifier, pas tous les trois d'entre eux, 1040 00:53:22,320 --> 00:53:23,290 potentiellement. 1041 00:53:23,290 --> 00:53:25,530 Et qui le rend un peu plus agréable sur l'ordinateur qui est 1042 00:53:25,530 --> 00:53:26,670 l'exécution de votre programme. 1043 00:53:26,670 --> 00:53:27,620 >> Donc, [? Constantine,?] 1044 00:53:27,620 --> 00:53:31,330 nous sommes à l'intérieur de cette ligne, d'autre si les valeurs, tranche moyenne près support 1045 00:53:31,330 --> 00:53:32,260 est supérieure à la valeur. 1046 00:53:32,260 --> 00:53:33,150 Que devons-nous faire? 1047 00:53:33,150 --> 00:53:33,970 Nous devons rechercher la gauche. 1048 00:53:33,970 --> 00:53:35,220 Comment faisons-nous cela? 1049 00:53:35,220 --> 00:53:46,960 1050 00:53:46,960 --> 00:53:48,720 Je vais vous donner un bon départ. 1051 00:53:48,720 --> 00:53:52,210 >> Nous avons ces deux choses appelées début et de fin. 1052 00:53:52,210 --> 00:53:57,340 Donc, ce qu'il faut faire au début? 1053 00:53:57,340 --> 00:53:59,640 Si vous souhaitez rechercher la gauche de la liste, nous obtenons notre début courant. 1054 00:53:59,640 --> 00:54:01,080 Que devons-nous faire? 1055 00:54:01,080 --> 00:54:04,220 >> ETUDIANT: Nous fixons le début à mi plus 1. 1056 00:54:04,220 --> 00:54:05,120 >> JASON HIRSCHHORN: Donc, si nous sommes recherche de la gauche? 1057 00:54:05,120 --> 00:54:06,250 >> ETUDIANT: Désolé, moins milieu - 1058 00:54:06,250 --> 00:54:11,310 de sorte que la fin serait milieu moins 1 et au début - 1059 00:54:11,310 --> 00:54:12,450 >> JASON HIRSCHHORN: Et qu'est-ce qui se passe au début? 1060 00:54:12,450 --> 00:54:13,210 >> ETUDIANT: Il reste le même. 1061 00:54:13,210 --> 00:54:14,120 >> JASON HIRSCHHORN: Donc, le sens reste le même. 1062 00:54:14,120 --> 00:54:16,040 Si nous sommes à la recherche de la gauche, nous sommes en utilisant le même début - 1063 00:54:16,040 --> 00:54:16,860 tout à fait exact. 1064 00:54:16,860 --> 00:54:17,870 Et la fin? 1065 00:54:17,870 --> 00:54:19,390 Désolé, ce que fait le se terminant égal à nouveau? 1066 00:54:19,390 --> 00:54:20,750 >> ETUDIANT: moins Moyen 1. 1067 00:54:20,750 --> 00:54:21,620 >> JASON HIRSCHHORN: moins Moyen 1. 1068 00:54:21,620 --> 00:54:23,470 Maintenant, pourquoi moins 1, et pas seulement du milieu? 1069 00:54:23,470 --> 00:54:32,870 1070 00:54:32,870 --> 00:54:35,570 >> ÉTUDIANTS: Le milieu est de la imaginez déjà, parce que nous avions 1071 00:54:35,570 --> 00:54:36,700 vérifier que c'est sur? 1072 00:54:36,700 --> 00:54:37,630 >> JASON HIRSCHHORN: C'est tout à fait exact. 1073 00:54:37,630 --> 00:54:38,580 Le milieu est hors de l'image. 1074 00:54:38,580 --> 00:54:39,800 Nous avons déjà vérifié le milieu. 1075 00:54:39,800 --> 00:54:44,730 Donc, nous ne voulons pas "au milieu", citation Ils ont dit, de continuer à être dans la 1076 00:54:44,730 --> 00:54:46,110 tableau que nous cherchons. 1077 00:54:46,110 --> 00:54:47,670 Donc, c'est fantastique. 1078 00:54:47,670 --> 00:54:50,670 >> Sinon, si les valeurs tranche intermédiaire est supérieure que la valeur se terminant égaux 1079 00:54:50,670 --> 00:54:51,920 moins milieu 1. 1080 00:54:51,920 --> 00:54:55,060 1081 00:54:55,060 --> 00:54:57,340 Jeff, que dire de cette dernière ligne? 1082 00:54:57,340 --> 00:54:58,590 >> ÉTUDIANT: Else. 1083 00:54:58,590 --> 00:55:02,486 1084 00:55:02,486 --> 00:55:06,000 Valeurs du milieu est inférieure à la valeur? 1085 00:55:06,000 --> 00:55:07,570 >> JASON HIRSCHHORN: Nous allons vous me donner d'autre. 1086 00:55:07,570 --> 00:55:09,310 Donc, si vous ne me donnez pas - 1087 00:55:09,310 --> 00:55:12,270 >> Étudiant: Alors commencer serait ainsi milieu 1. 1088 00:55:12,270 --> 00:55:16,100 1089 00:55:16,100 --> 00:55:19,070 >> JASON Hirschhorn: Début égaux , plus une moyenne, de plus, pour la même 1090 00:55:19,070 --> 00:55:20,820 raison que Constantine nous a donné plus tôt. 1091 00:55:20,820 --> 00:55:24,280 Et à la fin, qui n'a pas donné moi une ligne de code encore? 1092 00:55:24,280 --> 00:55:26,600 Return false, Aleha, ce écrivons-nous ici? 1093 00:55:26,600 --> 00:55:28,590 >> ETUDIANT: Retour faux. 1094 00:55:28,590 --> 00:55:29,320 >> JASON HIRSCHHORN: Retour faux. 1095 00:55:29,320 --> 00:55:33,340 Et nous devons le faire, parce que si nous ne trouvent pas, nous devons nous dire 1096 00:55:33,340 --> 00:55:34,080 ne pas le trouver. 1097 00:55:34,080 --> 00:55:36,270 Et nous avons dit que nous allons revenir un bool, de sorte que nous avons d'y retourner 1098 00:55:36,270 --> 00:55:38,150 une part de bool. 1099 00:55:38,150 --> 00:55:42,590 >> Donc, nous allons exécuter ce code. 1100 00:55:42,590 --> 00:55:44,520 Je vais en fait - 1101 00:55:44,520 --> 00:55:45,930 Nous sommes donc dans le terminal. 1102 00:55:45,930 --> 00:55:47,230 Nous dégageons notre fenêtre. 1103 00:55:47,230 --> 00:55:49,270 Faisons tout. 1104 00:55:49,270 --> 00:55:50,340 Nous avons trouvé il ya une erreur. 1105 00:55:50,340 --> 00:55:54,280 Il ya une erreur à la ligne 15, qui devrait virgule à la fin de la 1106 00:55:54,280 --> 00:55:54,890 déclaration. 1107 00:55:54,890 --> 00:55:56,454 Alors qu'est-ce que j'ai oublié? 1108 00:55:56,454 --> 00:55:57,230 >> ÉTUDIANT: point-virgule. 1109 00:55:57,230 --> 00:56:00,200 >> JASON HIRSCHHORN: point-virgule droit ici. 1110 00:56:00,200 --> 00:56:00,950 Je pense que c'est le code de Tom. 1111 00:56:00,950 --> 00:56:01,870 Alors Tom, [inaudible]. 1112 00:56:01,870 --> 00:56:03,120 Je plaisante. 1113 00:56:03,120 --> 00:56:05,010 1114 00:56:05,010 --> 00:56:07,310 Faisons Marque Toutes nouveau. 1115 00:56:07,310 --> 00:56:10,180 >> ÉTUDIANT: Qu'est-ce répertoire Dropbox devrions-nous être pour cela? 1116 00:56:10,180 --> 00:56:11,345 >> JASON HIRSCHHORN: Ainsi, vous pouvez juste regarder de ce bit. 1117 00:56:11,345 --> 00:56:16,380 Mais encore une fois, si vous voulez faire avancer ce coder dans votre répertoire pset3 pour essayer 1118 00:56:16,380 --> 00:56:17,050 dehors, c'est ce que j'ai fait. 1119 00:56:17,050 --> 00:56:18,600 Si vous remarquez ici - désolé, bonne question. 1120 00:56:18,600 --> 00:56:19,460 >> [? LS,?] 1121 00:56:19,460 --> 00:56:24,700 J'ai ici le code de find.c à partir du code de distribution de cette semaine. 1122 00:56:24,700 --> 00:56:26,300 J'ai Helpers.h. 1123 00:56:26,300 --> 00:56:30,010 J'ai un fichier de Marque que j'ai effectivement édité un peu pour inclure ces nouveaux 1124 00:56:30,010 --> 00:56:30,710 fichiers que nous écrivons. 1125 00:56:30,710 --> 00:56:34,120 Tout ce code sera disponible, pas le code de distribution, mais le nouveau 1126 00:56:34,120 --> 00:56:39,510 Créer un fichier, le nouveau fichier sera Helpers.h disponible en ligne pour téléchargement. 1127 00:56:39,510 --> 00:56:41,800 Encore une fois, si ce sont les codes supplémentaires nous ont. 1128 00:56:41,800 --> 00:56:46,130 >> Donc, assurez-tout, par cette ligne, qui fait trouver, binaire, la sélection de la bulle - marques 1129 00:56:46,130 --> 00:56:50,930 tous trois d'entre eux et compile en ce code exécutable trouvaille. 1130 00:56:50,930 --> 00:56:54,090 Donc, en général, nous ne voulons pas à droite à check50. 1131 00:56:54,090 --> 00:56:57,580 Nous voulons faire quelques tests sur notre propre. 1132 00:56:57,580 --> 00:57:11,750 Mais afin que nous puissions accélérer le un peu, check50 2013 pset3.find passera 1133 00:57:11,750 --> 00:57:14,630 dans helpers.c-- mon mauvais. 1134 00:57:14,630 --> 00:57:16,050 >> Je n'ai pas tout de suite. 1135 00:57:16,050 --> 00:57:20,670 Donc, nous allons en fait exécuter le code pour de vrai. 1136 00:57:20,670 --> 00:57:23,570 Usage.find /, vous savez ce que cela signifie? 1137 00:57:23,570 --> 00:57:25,970 >> ETUDIANT: Vous avez besoin d'un deuxième ligne de commande sur elle. 1138 00:57:25,970 --> 00:57:26,980 >> JASON HIRSCHHORN: J'ai besoin d' une seconde ligne de commande. 1139 00:57:26,980 --> 00:57:30,640 Et par la spécification, j'ai besoin pour entrer dans ce que nous recherchons. 1140 00:57:30,640 --> 00:57:33,750 Examinons donc de 42. 1141 00:57:33,750 --> 00:57:37,030 Nous allons continuer dans triés, parce que nous n'ont pas encore écrit une fonction de tri - 1142 00:57:37,030 --> 00:57:41,830 42, 43, 44. 1143 00:57:41,830 --> 00:57:46,240 >> Et de contrôle D n'a pas trouvé l' l'aiguille dans la botte de foin. 1144 00:57:46,240 --> 00:57:46,505 C'est mauvais. 1145 00:57:46,505 --> 00:57:47,200 C'est certainement là. 1146 00:57:47,200 --> 00:57:48,090 Essayons autre chose. 1147 00:57:48,090 --> 00:57:49,860 C'est peut-être parce que j'ai mis au début. 1148 00:57:49,860 --> 00:57:54,490 >> Faisons 41, 42, 43. 1149 00:57:54,490 --> 00:57:55,012 Nous y voilà. 1150 00:57:55,012 --> 00:57:56,400 Il l'a trouvé. 1151 00:57:56,400 --> 00:58:00,040 Disons-le à la fin maintenant, juste afin que nous puissions être approfondie - 1152 00:58:00,040 --> 00:58:03,580 40, 41, 42. 1153 00:58:03,580 --> 00:58:05,760 Vous n'avez pas trouvé l'aiguille. 1154 00:58:05,760 --> 00:58:07,550 Donc je l'ai mentionné plus tôt. 1155 00:58:07,550 --> 00:58:08,980 Malheureusement, je savais que ce qui allait se passer. 1156 00:58:08,980 --> 00:58:11,490 >> Mais à des fins pédagogiques, il est bon d'explorer. 1157 00:58:11,490 --> 00:58:12,990 Il ne fonctionne pas. 1158 00:58:12,990 --> 00:58:16,020 Pour une raison quelconque, il ne peut pas le trouver. 1159 00:58:16,020 --> 00:58:18,970 Nous savons ce qu'il ya dedans, mais nous ne sommes pas à le trouver. 1160 00:58:18,970 --> 00:58:24,140 Donc, une chose que nous pourrions faire est de passer par GDB pour le trouver, mais le fait que ce soit, 1161 00:58:24,140 --> 00:58:27,850 sans passer par GDB, avoir un sens où nous foiré? 1162 00:58:27,850 --> 00:58:28,480 [? Madu? ?] 1163 00:58:28,480 --> 00:58:30,960 >> Étudiant: Je pense qu'il pourrait être quand s'achève est égal au début, et c'est 1164 00:58:30,960 --> 00:58:33,090 juste une liste à un élément. 1165 00:58:33,090 --> 00:58:35,560 Ensuite, il ignore simplement la place en fait de vérifier. 1166 00:58:35,560 --> 00:58:36,940 >> JASON HIRSCHHORN: C'est tout à fait exact. 1167 00:58:36,940 --> 00:58:41,110 Lorsque fin égale début, nous faisons ont encore un élément dans notre liste? 1168 00:58:41,110 --> 00:58:42,480 >> ÉTUDIANT: Oui. 1169 00:58:42,480 --> 00:58:45,450 >> JASON HIRSCHHORN: Oui, en fait, nous avoir un et un seul élément. 1170 00:58:45,450 --> 00:58:50,500 Et ce sera le plus susceptible de se produire lorsque, par le code que nous avons testé, nous sommes à la 1171 00:58:50,500 --> 00:58:54,640 avant de la botte de foin ou à la fin de la botte de foin. 1172 00:58:54,640 --> 00:58:56,000 C'est là que début et fin va à l'égalité 1173 00:58:56,000 --> 00:58:57,820 un, à la recherche binaire. 1174 00:58:57,820 --> 00:59:01,440 Donc, dans ces deux cas, il ne fonctionne pas, parce fin était égale à début. 1175 00:59:01,440 --> 00:59:06,030 >> Mais si fin est égal à début, cela boucle while exécuter? 1176 00:59:06,030 --> 00:59:06,390 Il ne fait pas. 1177 00:59:06,390 --> 00:59:08,660 Et nous aurions pu vérifier que de nouveau par GDB. 1178 00:59:08,660 --> 00:59:14,000 Alors, comment pouvons-nous résoudre ce code, car quand tout se terminant est égal à 1179 00:59:14,000 --> 00:59:16,070 commencer, nous voulons aussi ce tout en boucle à exécuter. 1180 00:59:16,070 --> 00:59:18,620 >> Alors, que pouvons-nous faire fixer à la ligne 18? 1181 00:59:18,620 --> 00:59:21,060 >> ETUDIANT: [inaudible] est supérieure supérieure ou égale à. 1182 00:59:21,060 --> 00:59:21,700 >> JASON HIRSCHHORN: Exactement. 1183 00:59:21,700 --> 00:59:24,600 Alors que fin est supérieure à ou égale à début. 1184 00:59:24,600 --> 00:59:27,300 Alors maintenant, nous nous assurons d'obtenir que cas de coin à la fin. 1185 00:59:27,300 --> 00:59:27,870 Et nous allons voir. 1186 00:59:27,870 --> 00:59:29,560 Lançons ce une fois de plus. 1187 00:59:29,560 --> 00:59:31,266 >> Faisons tous. 1188 00:59:31,266 --> 00:59:33,910 Encore une fois, vous avez juste à suivre ici. 1189 00:59:33,910 --> 00:59:36,280 Trouver 41 cette fois. 1190 00:59:36,280 --> 00:59:37,360 Juste garder cohérente. 1191 00:59:37,360 --> 00:59:38,210 >> Trouver 42. 1192 00:59:38,210 --> 00:59:38,930 Mettons au début - 1193 00:59:38,930 --> 00:59:41,630 42, 43, 44. 1194 00:59:41,630 --> 00:59:42,860 Nous l'avons trouvé. 1195 00:59:42,860 --> 00:59:47,710 Donc, c'était bien le changement nous devions faire. 1196 00:59:47,710 --> 00:59:51,090 >> C'était beaucoup de nous codage vient de faire, la recherche binaire. 1197 00:59:51,090 --> 00:59:55,760 Quelqu'un at-il des questions avant Je passe dans les lignes que nous avons écrit dans 1198 00:59:55,760 --> 00:59:58,750 recherche binaire ou comment nous avons pensé ce que nous n'avons comprendre? 1199 00:59:58,750 --> 01:00:01,900 1200 01:00:01,900 --> 01:00:06,270 Avant de poursuivre, je tiens également à souligner que dans l'ensemble, nous avons cartographié 1201 01:00:06,270 --> 01:00:09,300 notre pseudo-code pour un un sur notre code. 1202 01:00:09,300 --> 01:00:11,550 >> Nous avons eu cette chose délicate de comprendre la 1203 01:00:11,550 --> 01:00:12,890 début et de fin. 1204 01:00:12,890 --> 01:00:17,380 Mais si vous n'aviez pas compris cela, vous aurait écrit à peu près la 1205 01:00:17,380 --> 01:00:20,740 code identique, sauf pour les deux premières lignes. 1206 01:00:20,740 --> 01:00:23,380 Et puis, vous auriez compris quand vous l'avez fait dans les contrôles et les cas qui 1207 01:00:23,380 --> 01:00:24,840 vous avez besoin d'autre chose. 1208 01:00:24,840 --> 01:00:28,510 Donc, même si vous aviez suivi notre ligne pseudo-code à la ligne, vous avez 1209 01:00:28,510 --> 01:00:31,130 obtenu tous, mais deux lignes de codez vous avez besoin d'écrire. 1210 01:00:31,130 --> 01:00:33,900 >> Et je serais prêt à parier que vous les gars aurait tout compris cela 1211 01:00:33,900 --> 01:00:37,940 assez rapidement, que vous avez besoin de mettre une sorte de marqueur là pour comprendre 1212 01:00:37,940 --> 01:00:39,190 où vous étiez. 1213 01:00:39,190 --> 01:00:41,540 1214 01:00:41,540 --> 01:00:44,550 C'est nouveau, c'est le pouvoir de faire pseudo-code à l'avance. 1215 01:00:44,550 --> 01:00:47,310 Donc, nous pouvons faire la logique du premier, puis nous pouvons vous soucier de la syntaxe. 1216 01:00:47,310 --> 01:00:51,470 >> Si nous avions été confondu sur la logique tout en essayant d'écrire ce code en C, 1217 01:00:51,470 --> 01:00:53,110 nous avons obtenu tout foiré. 1218 01:00:53,110 --> 01:00:56,340 Et puis nous serions poser des questions sur logique et la syntaxe et le maillage 1219 01:00:56,340 --> 01:00:57,320 tous ensemble. 1220 01:00:57,320 --> 01:01:02,170 Et nous aurions obtenu perdu dans ce qui peut rapidement devenir un 1221 01:01:02,170 --> 01:01:04,000 problème très difficile. 1222 01:01:04,000 --> 01:01:08,680 Passons donc maintenant sur à la sélection sorte. 1223 01:01:08,680 --> 01:01:10,760 >> Nous avons 20 minutes. 1224 01:01:10,760 --> 01:01:14,130 Donc, j'ai un sentiment que nous ne serons pas en mesure de obtenir par tous de la sélection sorte 1225 01:01:14,130 --> 01:01:15,940 et tri à bulles. 1226 01:01:15,940 --> 01:01:20,670 Mais laissez-nous au moins essayer pour terminer la sélection sorte. 1227 01:01:20,670 --> 01:01:23,540 Donc, mettre en œuvre la sélection Trier par le suivant la déclaration de fonction. 1228 01:01:23,540 --> 01:01:27,530 >> Encore une fois, ceci est pris à partir de la problème réglé spécification. 1229 01:01:27,530 --> 01:01:31,560 Valeurs int est entre parenthèses, est un tableau d'entiers. 1230 01:01:31,560 --> 01:01:33,490 Et int.n est la taille de ce tableau. 1231 01:01:33,490 --> 01:01:36,840 Sélection tri va pour trier ce tableau. 1232 01:01:36,840 --> 01:01:43,580 >> Donc, selon notre modèle mental de la sélection sorte, nous nous retirons le - 1233 01:01:43,580 --> 01:01:47,720 d'abord, nous allons dans la liste de la première temps, trouver le plus petit nombre, 1234 01:01:47,720 --> 01:01:52,860 mettre au début, trouver le deuxième plus petit nombre, le mettre dans le 1235 01:01:52,860 --> 01:01:56,380 deuxième position, si nous voulons tri dans l'ordre croissant. 1236 01:01:56,380 --> 01:01:58,440 Je ne vous force pas à écrire pseudo-code en ce moment. 1237 01:01:58,440 --> 01:02:01,350 >> Mais avant de faire le code en tant que classe dans cinq minutes, nous allons écrire 1238 01:02:01,350 --> 01:02:03,550 pseudo-code pour que nous ayons une idée de l'endroit où nous allons. 1239 01:02:03,550 --> 01:02:05,630 Donc, essayer d'écrire le pseudo-code sur votre propre. 1240 01:02:05,630 --> 01:02:08,610 Et puis essayer de transformer cette pseudo-code en code. 1241 01:02:08,610 --> 01:02:10,740 Nous allons le faire en tant que groupe en cinq minutes. 1242 01:02:10,740 --> 01:02:32,560 1243 01:02:32,560 --> 01:02:33,895 >> Et bien sûr, laissez-moi savoir si vous avez des questions. 1244 01:02:33,895 --> 01:03:56,738 1245 01:03:56,738 --> 01:03:58,230 >> ETUDIANT: C'est tout? 1246 01:03:58,230 --> 01:04:00,280 >> JASON HIRSCHHORN: Voir dans quelle mesure vous peut obtenir en deux minutes. 1247 01:04:00,280 --> 01:04:01,790 Je comprends que vous ne sera pas être en mesure de terminer. 1248 01:04:01,790 --> 01:04:03,050 Mais nous allons passer en revue ce que un groupe. 1249 01:04:03,050 --> 01:04:57,830 1250 01:04:57,830 --> 01:05:00,630 >> Vous êtes tous de codage si [inaudible], donc je suis désolé pour interrompre ce que vous faites. 1251 01:05:00,630 --> 01:05:02,530 Mais nous allons passer par cela comme un groupe. 1252 01:05:02,530 --> 01:05:07,590 Et encore une fois, la recherche binaire, vous donne tout moi un si pas plus de lignes de code. 1253 01:05:07,590 --> 01:05:08,530 Merci pour cela. 1254 01:05:08,530 --> 01:05:11,730 Nous allons faire la même chose ici, le code en tant que groupe. 1255 01:05:11,730 --> 01:05:15,170 >> Donc, la sélection sorte - Écrivons certains pseudo-code rapide. 1256 01:05:15,170 --> 01:05:20,380 Par modèle mental, quelqu'un peut-il me donner la première ligne de pseudo-code, s'il vous plaît? 1257 01:05:20,380 --> 01:05:23,000 1258 01:05:23,000 --> 01:05:24,270 Qu'est-ce que je veux faire? 1259 01:05:24,270 --> 01:05:27,070 >> ETUDIANT: Bien que la liste est irrecevable. 1260 01:05:27,070 --> 01:05:30,630 >> JASON HIRSCHHORN: OK, tout la liste est irrecevable. 1261 01:05:30,630 --> 01:05:33,540 Et que voulez-vous dire "en panne?" 1262 01:05:33,540 --> 01:05:34,960 >> Étudiant: Alors que [inaudible] 1263 01:05:34,960 --> 01:05:36,210 n'a pas été triés. 1264 01:05:36,210 --> 01:05:38,460 1265 01:05:38,460 --> 01:05:40,290 >> JASON HIRSCHHORN: Bien que la liste est en panne, que faisons-nous? 1266 01:05:40,290 --> 01:05:44,200 Donnez-moi la deuxième ligne, s'il vous plaît, Marcus. 1267 01:05:44,200 --> 01:05:47,186 >> Étudiant: Donc, trouver la prochaine le plus petit nombre. 1268 01:05:47,186 --> 01:05:49,000 Ce sera en retrait. 1269 01:05:49,000 --> 01:05:55,140 >> JASON HIRSCHHORN: Donc, trouver la prochain plus petit nombre. 1270 01:05:55,140 --> 01:05:56,460 Et puis quelqu'un d'autre? 1271 01:05:56,460 --> 01:06:01,030 Une fois que nous trouvons la plus petite suivante nombre, que faisons-nous? 1272 01:06:01,030 --> 01:06:03,010 Je vais dire trouver le plus petit nombre. 1273 01:06:03,010 --> 01:06:04,820 C'est ce que nous voulons faire. 1274 01:06:04,820 --> 01:06:06,210 >> Donc, trouver le plus petit nombre. 1275 01:06:06,210 --> 01:06:08,061 Alors que faisons-nous? 1276 01:06:08,061 --> 01:06:09,480 >> ETUDIANT: [inaudible] à début. 1277 01:06:09,480 --> 01:06:10,680 >> JASON HIRSCHHORN: Désolé? 1278 01:06:10,680 --> 01:06:12,700 >> ETUDIANT: Placez-le dans le au début de la liste. 1279 01:06:12,700 --> 01:06:18,540 >> JASON HIRSCHHORN: Donc, le placer dans le début de la liste. 1280 01:06:18,540 --> 01:06:20,140 Et que faisons-nous de la chose qui était au commencement 1281 01:06:20,140 --> 01:06:20,830 de la liste, non? 1282 01:06:20,830 --> 01:06:21,910 Nous écraser quelque chose. 1283 01:06:21,910 --> 01:06:23,130 Alors, où allons-nous mettre cela? 1284 01:06:23,130 --> 01:06:24,120 Ouais, Anna? 1285 01:06:24,120 --> 01:06:25,520 >> ETUDIANT: Lorsque le plus petit nombre était? 1286 01:06:25,520 --> 01:06:32,530 >> JASON HIRSHHORN: Donc, mettez le début de la liste où la 1287 01:06:32,530 --> 01:06:35,180 plus petit nombre était. 1288 01:06:35,180 --> 01:06:38,510 Ainsi, alors que la liste est en panne, trouver le plus petit nombre, placez-le dans 1289 01:06:38,510 --> 01:06:40,630 le début de la liste, mettez la à partir de la liste où la 1290 01:06:40,630 --> 01:06:42,900 plus petit nombre était. 1291 01:06:42,900 --> 01:06:45,780 Marcus, pouvez-vous reformuler cette ligne alors que la liste est en panne? 1292 01:06:45,780 --> 01:06:51,160 1293 01:06:51,160 --> 01:06:53,900 >> ETUDIANT: Bien que les chiffres n'ont pas été triés? 1294 01:06:53,900 --> 01:06:55,920 >> JASON HIRSHHORN: OK, afin de savent que les chiffres n'ont pas été 1295 01:06:55,920 --> 01:06:58,670 triés, que devons-nous faire? 1296 01:06:58,670 --> 01:07:00,640 Combien devons-nous passer par cette liste? 1297 01:07:00,640 --> 01:07:09,650 >> Étudiant: Donc je suppose que pour une boucle, ou tandis que, tandis que le nombre contrôlés est moins 1298 01:07:09,650 --> 01:07:11,900 à la longueur de la liste? 1299 01:07:11,900 --> 01:07:13,160 >> JASON HIRSHHORN: OK, c'est bon. 1300 01:07:13,160 --> 01:07:15,000 Je pense que je misphrased ma question mal. 1301 01:07:15,000 --> 01:07:15,990 Je voulais juste obtenir à nous allons devoir aller 1302 01:07:15,990 --> 01:07:17,580 toute la liste. 1303 01:07:17,580 --> 01:07:20,490 Ainsi, alors que la liste est en panne, pour moi, c'est dur à la carte sur. 1304 01:07:20,490 --> 01:07:24,940 Mais fondamentalement, c'est la façon dont Je pense à ce sujet. 1305 01:07:24,940 --> 01:07:28,880 Passez par la liste entière, trouver la plus petit nombre, le placer dans le 1306 01:07:28,880 --> 01:07:30,130 début - en fait, vous avez raison. 1307 01:07:30,130 --> 01:07:31,380 Mettons les deux. 1308 01:07:31,380 --> 01:07:33,470 1309 01:07:33,470 --> 01:07:39,050 >> Ainsi, alors que la liste est en panne, nous besoin de passer par la liste complète 1310 01:07:39,050 --> 01:07:42,250 une fois, trouver le plus petit nombre, le lieu dans le début de la liste, mettre 1311 01:07:42,250 --> 01:07:45,430 le début de la liste où l' était plus petit nombre, et ensuite, si l' 1312 01:07:45,430 --> 01:07:47,460 liste est encore en panne, nous avons eu à passer par cette 1313 01:07:47,460 --> 01:07:48,620 processus nouveau, non? 1314 01:07:48,620 --> 01:07:51,610 C'est pourquoi la sélection sorte, Big-O exécution de la sélection sorte, n'importe qui? 1315 01:07:51,610 --> 01:07:52,830 >> ETUDIANT: n carré. 1316 01:07:52,830 --> 01:07:53,590 >> JASON HIRSHHORN: n carré. 1317 01:07:53,590 --> 01:07:57,040 Parce que, comme Marcus et je viens de réaliser ici, nous allons avoir à 1318 01:07:57,040 --> 01:08:00,310 parcourir la liste de liste nombre de fois. 1319 01:08:00,310 --> 01:08:03,420 Donc passer par quelque chose de longueur n n nombre de fois 1320 01:08:03,420 --> 01:08:04,990 est, en fait, n carré. 1321 01:08:04,990 --> 01:08:08,100 >> Voici donc notre pseudo. 1322 01:08:08,100 --> 01:08:09,360 Cela semble très bon. 1323 01:08:09,360 --> 01:08:11,870 Quelqu'un at-il des questions sur le pseudocode? 1324 01:08:11,870 --> 01:08:14,440 Parce qu'en fait la sélection sorte devrait probablement venir un à un, le code de 1325 01:08:14,440 --> 01:08:14,980 pseudo. 1326 01:08:14,980 --> 01:08:17,569 Donc, des questions sur le la logique de pseudocode? 1327 01:08:17,569 --> 01:08:18,819 S'il vous plaît demander maintenant. 1328 01:08:18,819 --> 01:08:22,609 1329 01:08:22,609 --> 01:08:25,379 >> Sélection sorte - alors que la liste est hors de l'ordre, nous allons passer par là 1330 01:08:25,379 --> 01:08:27,529 et de trouver le plus petit à chaque fois et le mettre à l'avant. 1331 01:08:27,529 --> 01:08:33,470 Ainsi, alors que la liste est en panne, peut quelqu'un me donne cette ligne de code qui 1332 01:08:33,470 --> 01:08:39,689 ne m'a pas donné une ligne code encore, s'il vous plaît? 1333 01:08:39,689 --> 01:08:40,939 Cela ressemble à quoi? 1334 01:08:40,939 --> 01:08:43,669 1335 01:08:43,669 --> 01:08:44,649 >> ÉTUDIANT: C'est une boucle. 1336 01:08:44,649 --> 01:08:45,830 >> JASON HIRSHHORN: Il semble certainement une boucle for. 1337 01:08:45,830 --> 01:08:47,653 OK, pouvez-vous me donner la boucle? 1338 01:08:47,653 --> 01:08:48,925 Pour - 1339 01:08:48,925 --> 01:08:50,219 >> ETUDIANT: i est égal à 0. 1340 01:08:50,219 --> 01:08:52,705 >> JASON HIRSHHORN: i ou - 1341 01:08:52,705 --> 01:08:55,111 ce qui nous manque? 1342 01:08:55,111 --> 01:08:56,819 Ce qui se passe ici? 1343 01:08:56,819 --> 01:08:57,550 >> ETUDIANT: Int. 1344 01:08:57,550 --> 01:08:59,270 >> JASON HIRSHHORN: Exactement. 1345 01:08:59,270 --> 01:09:02,590 (Int i = 0; - 1346 01:09:02,590 --> 01:09:07,843 >> ETUDIANT: i 01:09:09,319 >> JASON HIRSHHORN: Cloué il, Jeff. 1348 01:09:09,319 --> 01:09:10,660 Nous allons dans la liste, non? 1349 01:09:10,660 --> 01:09:11,880 Nous avons vu que le code avant. 1350 01:09:11,880 --> 01:09:12,850 Parfait. 1351 01:09:12,850 --> 01:09:14,790 Mettons donc nos accolades ici. 1352 01:09:14,790 --> 01:09:17,859 Je vais mettre un peu accolades ici. 1353 01:09:17,859 --> 01:09:21,660 >> Ainsi, alors que c'est 0, nous devons aller à travers l'ensemble de la liste. 1354 01:09:21,660 --> 01:09:26,612 Donc, chaque fois que nous entrons dans la liste, Que voulons-nous de suivre? 1355 01:09:26,612 --> 01:09:28,260 >> ÉTUDIANT: Si des swaps sont faites. 1356 01:09:28,260 --> 01:09:29,069 >> JASON HIRSHHORN: Trouver le plus petit nombre. 1357 01:09:29,069 --> 01:09:31,479 Donc, nous devrions probablement garder une trace de le plus petit nombre à chaque fois. 1358 01:09:31,479 --> 01:09:34,590 Donc, la ligne que je peux faire pour garder une trace du plus petit nombre? 1359 01:09:34,590 --> 01:09:37,720 Aleha, comment puis-je garder piste de quelque chose? 1360 01:09:37,720 --> 01:09:38,460 >> ETUDIANT: Lancer une nouvelle variable. 1361 01:09:38,460 --> 01:09:39,390 >> JASON HIRSHHORN: Lancer une nouvelle variable. 1362 01:09:39,390 --> 01:09:40,069 Créons donc une variable. 1363 01:09:40,069 --> 01:09:41,830 Quel type? 1364 01:09:41,830 --> 01:09:42,930 >> ETUDIANT: Int. 1365 01:09:42,930 --> 01:09:43,710 >> JASON HIRSHHORN: Int. 1366 01:09:43,710 --> 01:09:44,939 Appelons-le le plus petit. 1367 01:09:44,939 --> 01:09:47,600 Et ce qu'il fait quand même nous ne faisons que commencer? 1368 01:09:47,600 --> 01:09:48,910 Nous n'avons pas encore épuisé la liste. 1369 01:09:48,910 --> 01:09:50,540 Nous sommes à la première partie de la figurer notre première fois. 1370 01:09:50,540 --> 01:09:51,930 Qu'est-ce que c'est égal, le plus petit nombre? 1371 01:09:51,930 --> 01:09:54,140 >> ETUDIANT: Valeurs i. 1372 01:09:54,140 --> 01:09:54,900 >> JASON HIRSHHORN: Valeurs i. 1373 01:09:54,900 --> 01:09:56,980 Cela semble tout à fait raison, non? 1374 01:09:56,980 --> 01:09:59,590 Le plus petit nombre au début C'est là que nous sommes. 1375 01:09:59,590 --> 01:10:01,960 Alors maintenant, nous avons notre petit, et nous avons besoin de de passer par la liste entière et 1376 01:10:01,960 --> 01:10:05,080 comparer plus petit pour tout le reste. 1377 01:10:05,080 --> 01:10:08,150 Alors allons-nous la liste de nouveau? 1378 01:10:08,150 --> 01:10:08,630 Michael? 1379 01:10:08,630 --> 01:10:10,000 >> ETUDIANT: Vous devez vous une autre boucle. 1380 01:10:10,000 --> 01:10:10,383 >> JASON HIRSHHORN: Une autre boucle. 1381 01:10:10,383 --> 01:10:11,276 Faisons-le. 1382 01:10:11,276 --> 01:10:12,540 Donnez-moi un peu de code. 1383 01:10:12,540 --> 01:10:13,790 >> ETUDIANT: Pour boucle - 1384 01:10:13,790 --> 01:10:16,750 1385 01:10:16,750 --> 01:10:19,470 pour les plus petits - 1386 01:10:19,470 --> 01:10:23,040 1387 01:10:23,040 --> 01:10:25,770 juste int j, pourriez-vous dire? 1388 01:10:25,770 --> 01:10:31,150 = 0, de telle sorte que - 1389 01:10:31,150 --> 01:10:34,014 1390 01:10:34,014 --> 01:10:35,710 >> JASON HIRSHHORN: Eh bien, si nous voulons de passer par la liste complète - 1391 01:10:35,710 --> 01:10:37,847 >> ETUDIANT: j 01:10:42,140 1393 01:10:42,140 --> 01:10:42,405 >> JASON HIRSHHORN: Fantastique. 1394 01:10:42,405 --> 01:10:46,100 Nous allons passer par la boucle une fois de plus. 1395 01:10:46,100 --> 01:10:51,380 Et comment pouvons-nous trouver l' plus petit nombre? 1396 01:10:51,380 --> 01:10:52,630 Tom? 1397 01:10:52,630 --> 01:10:54,570 1398 01:10:54,570 --> 01:11:00,520 Nous avons le plus petit nombre actuel, alors comment pouvons-nous trouver le nouveau petit? 1399 01:11:00,520 --> 01:11:07,200 >> ETUDIANT: Nous pouvons vérifier si la plus petite nombre que nous avons est supérieure à 1400 01:11:07,200 --> 01:11:09,040 valeurs support j. 1401 01:11:09,040 --> 01:11:14,740 >> JASON HIRSHHORN: Donc, si petit est plus grand que les valeurs j support. 1402 01:11:14,740 --> 01:11:19,350 Donc, si notre petit courant est plus grand que - 1403 01:11:19,350 --> 01:11:21,770 Je vais passer ces deux lignes Code de là-bas pour une seconde. 1404 01:11:21,770 --> 01:11:26,010 Parce que nous faisons avant tout échange, nous besoin de passer par la liste entière. 1405 01:11:26,010 --> 01:11:28,880 Donc ce pseudo doit effectivement être à l'extérieur de la boucle intérieure qui. 1406 01:11:28,880 --> 01:11:30,390 Donc passer par la liste entière. 1407 01:11:30,390 --> 01:11:34,520 Si la plus petite est plus grande que valeurs j alors quoi? 1408 01:11:34,520 --> 01:11:37,830 >> Etudiant: Alors petit égaux valeurs j. 1409 01:11:37,830 --> 01:11:41,190 1410 01:11:41,190 --> 01:11:42,600 >> JASON HIRSHHORN: Fantastique. 1411 01:11:42,600 --> 01:11:44,580 Une question rapide - 1412 01:11:44,580 --> 01:11:47,236 la première fois que nous allons à travers cette boucle, i va être égal à 0, j va 1413 01:11:47,236 --> 01:11:50,710 égale à 0 une fois que nous recevons ici. 1414 01:11:50,710 --> 01:11:52,410 Donc, nous allons être en comparant un certain nombre de lui-même. 1415 01:11:52,410 --> 01:11:53,660 Est-ce efficace? 1416 01:11:53,660 --> 01:11:57,260 1417 01:11:57,260 --> 01:11:58,390 Non, ce n'est pas vraiment efficace. 1418 01:11:58,390 --> 01:12:02,915 Ne nous j besoin donc d'aller de 0 à n à chaque fois? 1419 01:12:02,915 --> 01:12:06,310 Avons-nous besoin de toujours vérifier toute la liste? 1420 01:12:06,310 --> 01:12:06,520 [Inaudible]? 1421 01:12:06,520 --> 01:12:07,564 >> ETUDIANT: Commencez par i à la place. 1422 01:12:07,564 --> 01:12:09,405 >> JASON HIRSHHORN: J Can commencer par quoi? 1423 01:12:09,405 --> 01:12:09,990 >> ETUDIANT: i. 1424 01:12:09,990 --> 01:12:13,040 >> JASON HIRSHHORN: j peut commencer par i. 1425 01:12:13,040 --> 01:12:18,840 Alors maintenant, nous comparons à partir avec celui que nous sommes sur. 1426 01:12:18,840 --> 01:12:21,020 Mais même alors, c'est que efficace que possible? 1427 01:12:21,020 --> 01:12:22,320 >> ETUDIANT: i + 1. 1428 01:12:22,320 --> 01:12:25,420 >> JASON HIRSHHORN: i + 1 semble être le plus efficace, parce que nous 1429 01:12:25,420 --> 01:12:26,120 déjà i. 1430 01:12:26,120 --> 01:12:28,100 Nous indiquant que la plus petite à la ligne 15. 1431 01:12:28,100 --> 01:12:29,350 Nous allons commencer avec le une prochaine automatiquement. 1432 01:12:29,350 --> 01:12:34,470 1433 01:12:34,470 --> 01:12:38,540 Donc, nous passons par la boucle. 1434 01:12:38,540 --> 01:12:39,620 Nous allons passer en revue chaque fois. 1435 01:12:39,620 --> 01:12:40,860 Nous allons passer par un certain nombre de fois. 1436 01:12:40,860 --> 01:12:42,860 Maintenant que nous avons obtenu par ce intérieure de boucle. 1437 01:12:42,860 --> 01:12:44,350 Nous avons la plus petite valeur sauve. 1438 01:12:44,350 --> 01:12:46,045 Nous avons besoin de le mettre à la au début de la liste. 1439 01:12:46,045 --> 01:12:48,390 Alors, comment puis-je le place à la à partir de la liste? 1440 01:12:48,390 --> 01:12:51,290 1441 01:12:51,290 --> 01:12:55,926 Quelle est la variable qui fait référence au début de la liste? 1442 01:12:55,926 --> 01:13:00,500 Nous sommes dans ce dehors de la boucle, si ce se réfère à la 1443 01:13:00,500 --> 01:13:01,280 à partir de la liste? 1444 01:13:01,280 --> 01:13:02,880 >> ETUDIANT: Valeurs i. 1445 01:13:02,880 --> 01:13:03,510 >> JASON HIRSHHORN: Exactement. 1446 01:13:03,510 --> 01:13:04,650 Valeurs i est le début de la - 1447 01:13:04,650 --> 01:13:06,320 ou désolé, pas le début. 1448 01:13:06,320 --> 01:13:07,090 C'était déroutant. 1449 01:13:07,090 --> 01:13:11,620 C'est là que nous sommes au début de la partie non triés de la liste. 1450 01:13:11,620 --> 01:13:12,800 Ainsi, les valeurs i. 1451 01:13:12,800 --> 01:13:14,050 Et qu'est-ce que l'égalité? 1452 01:13:14,050 --> 01:13:15,925 1453 01:13:15,925 --> 01:13:17,326 >> ÉTUDIANTS: La plus petite. 1454 01:13:17,326 --> 01:13:18,862 >> JASON HIRSHHORN: Valeurs i est égal à quoi? 1455 01:13:18,862 --> 01:13:19,310 >> ÉTUDIANTS: La plus petite. 1456 01:13:19,310 --> 01:13:20,030 >> JASON HIRSHHORN: plus petit. 1457 01:13:20,030 --> 01:13:20,980 Exactement. 1458 01:13:20,980 --> 01:13:23,510 Donc, nous plaçant au début de la liste, et maintenant nous devons mettre 1459 01:13:23,510 --> 01:13:25,710 le début de la liste où le plus petit nombre était. 1460 01:13:25,710 --> 01:13:29,700 Alors, comment puis-je écrire où l' plus petit nombre était? 1461 01:13:29,700 --> 01:13:31,670 Valeurs de quoi? 1462 01:13:31,670 --> 01:13:33,170 >> ETUDIANT: 0. 1463 01:13:33,170 --> 01:13:34,090 >> JASON HIRSHHORN: Le petit nombre est à 0? 1464 01:13:34,090 --> 01:13:35,340 >> ÉTUDIANT: Oui. 1465 01:13:35,340 --> 01:13:38,680 1466 01:13:38,680 --> 01:13:39,910 >> JASON HIRSHHORN: si le plus petit nombre était à la fin de 1467 01:13:39,910 --> 01:13:40,860 cette liste non triés? 1468 01:13:40,860 --> 01:13:42,460 >> ETUDIANT: Désolé, quelle était la question? 1469 01:13:42,460 --> 01:13:44,020 >> JASON HIRSHHORN: Où est le plus petit nombre? 1470 01:13:44,020 --> 01:13:46,940 Nous avons pris le plus petit et le mettre à la début, avec cette ligne ici. 1471 01:13:46,940 --> 01:13:48,987 >> ETUDIANT: Il doit avoir été enregistrée dans un - 1472 01:13:48,987 --> 01:13:50,510 >> ETUDIANT: Valeurs j. 1473 01:13:50,510 --> 01:13:51,520 >> JASON HIRSHHORN: Eh bien, c'est valeurs pas nécessairement j. 1474 01:13:51,520 --> 01:13:54,100 Il n'existe même pas à ce point. 1475 01:13:54,100 --> 01:13:55,960 >> ETUDIANT: Vous devez déclarer une variable précédemment et 1476 01:13:55,960 --> 01:13:58,230 puis l'affecter à - 1477 01:13:58,230 --> 01:14:01,150 quand vous trouvez le plus petit nombre, affecter l'indice de ce nombre à 1478 01:14:01,150 --> 01:14:02,480 une variable ou quelque chose comme ça. 1479 01:14:02,480 --> 01:14:04,790 >> JASON HIRSHHORN: Alors, peut vous dites que nouveau? 1480 01:14:04,790 --> 01:14:08,390 >> Étudiant: Alors, où vous avez déclaré int plus petite, vous devez également déclarer int 1481 01:14:08,390 --> 01:14:10,750 petit indice = i, ou quelque chose comme ça. 1482 01:14:10,750 --> 01:14:13,280 >> JASON HIRSHHORN: Alors, où je ne int plus petit, je dois non seulement garder une trace 1483 01:14:13,280 --> 01:14:16,150 de la valeur, mais l'emplacement. 1484 01:14:16,150 --> 01:14:20,850 int = smallest_location dans ce cas, nous allons juste faire i. 1485 01:14:20,850 --> 01:14:22,390 Nous avons besoin de savoir où il est. 1486 01:14:22,390 --> 01:14:26,820 Nous sommes arrivés à la fin du code, et nous réalisé que nous ne savions pas où il était. 1487 01:14:26,820 --> 01:14:29,810 Et là encore, nous sommes cartographie ceci sur un pour un. 1488 01:14:29,810 --> 01:14:32,890 Vous les gars de codage sur votre propre volonté probablement arriver au même problème. 1489 01:14:32,890 --> 01:14:34,130 Comment diable puis-je le trouver? 1490 01:14:34,130 --> 01:14:36,720 Et puis vous vous rendez compte, attendez, je besoin de garder une trace de cela. 1491 01:14:36,720 --> 01:14:38,500 >> Donc, si la plus petite est plus grande Les valeurs de j. 1492 01:14:38,500 --> 01:14:39,740 Nous avons mis plus petit est égal aux valeurs j. 1493 01:14:39,740 --> 01:14:42,090 Que devons-nous changer? 1494 01:14:42,090 --> 01:14:43,710 Constantin, quoi d'autre nous devons changer? 1495 01:14:43,710 --> 01:14:44,560 >> ÉTUDIANTS: L'emplacement. 1496 01:14:44,560 --> 01:14:45,270 >> JASON HIRSHHORN: Exactement. 1497 01:14:45,270 --> 01:14:46,925 Donnez-moi donc cette ligne dans le code. 1498 01:14:46,925 --> 01:14:53,310 >> ETUDIANT: smallest_location = j. 1499 01:14:53,310 --> 01:14:54,790 >> JASON HIRSHHORN: Exactement. 1500 01:14:54,790 --> 01:14:58,210 Et puis vers le bas à la fin, si nous voulons mettre le début de la liste où 1501 01:14:58,210 --> 01:15:00,790 le plus petit nombre était, comment ne nous référons à l'endroit où la 1502 01:15:00,790 --> 01:15:02,200 plus petit nombre était? 1503 01:15:02,200 --> 01:15:03,580 Marcus? 1504 01:15:03,580 --> 01:15:08,530 >> ÉTUDIANTS: Le plus petit nombre était situé au plus petit emplacement. 1505 01:15:08,530 --> 01:15:12,230 >> JASON HIRSHHORN: Donc, à des valeurs smallest_location. 1506 01:15:12,230 --> 01:15:14,700 Et qu'est-ce que nous avons mis là-bas? 1507 01:15:14,700 --> 01:15:17,600 Le début de l' liste, c'est quoi? 1508 01:15:17,600 --> 01:15:19,710 >> ETUDIANT: Eh bien, nous ne savons pas vraiment plus parce que nous écrasait. 1509 01:15:19,710 --> 01:15:23,250 Donc, c'est un des endroits échangés de ces deux lignes? 1510 01:15:23,250 --> 01:15:26,110 Si vous passez ces deux lignes autour. 1511 01:15:26,110 --> 01:15:30,740 >> JASON HIRSHHORN: OK, si nous ne faisons pas plus, parce que nous avons réinitialisé la ligne 1512 01:15:30,740 --> 01:15:31,960 avant les valeurs i à petit. 1513 01:15:31,960 --> 01:15:33,810 Donc, nous avons perdu cette valeur initiale. 1514 01:15:33,810 --> 01:15:37,350 Donc, vous avez dit échange de ces deux lignes. 1515 01:15:37,350 --> 01:15:41,780 Alors maintenant mettre le début de la liste où le plus petit nombre était. 1516 01:15:41,780 --> 01:15:47,060 Donc smallest_location égal valeurs i. 1517 01:15:47,060 --> 01:15:51,310 Cela déplacer le début de cette partie non triés de la liste à l' 1518 01:15:51,310 --> 01:15:52,090 petit emplacement. 1519 01:15:52,090 --> 01:15:54,860 Et puis en valeurs i Nous nous déplaçons que le plus petit nombre. 1520 01:15:54,860 --> 01:15:57,450 >> Est-ce logique pourquoi nous eu à faire que de swap? 1521 01:15:57,450 --> 01:15:59,650 Nous aurions écrasé cette valeur - une autre chose que vous auriez probablement 1522 01:15:59,650 --> 01:16:02,740 compris et trouvé dans le PIB. 1523 01:16:02,740 --> 01:16:05,310 Nous avons donc pris soin de tout le pseudo-code. 1524 01:16:05,310 --> 01:16:10,935 Y at-il autre chose que nous besoin d'écrire ici? 1525 01:16:10,935 --> 01:16:14,911 Quelqu'un peut-il penser à quelque chose? 1526 01:16:14,911 --> 01:16:16,180 >> Étudiant: Comment savez-vous lorsque vous avez terminé? 1527 01:16:16,180 --> 01:16:17,680 >> JASON HIRSHHORN: Comment pouvons-nous savoir quand nous aurons terminé? 1528 01:16:17,680 --> 01:16:18,890 Grande question. 1529 01:16:18,890 --> 01:16:21,684 Alors, comment savons-nous quand nous aurons fini. 1530 01:16:21,684 --> 01:16:24,720 >> ETUDIANT: Créer une variable pour tenir le compte de si il ya un swap fait ou pas 1531 01:16:24,720 --> 01:16:27,810 et passer par un passage. 1532 01:16:27,810 --> 01:16:30,180 >> JASON HIRSHHORN: OK. 1533 01:16:30,180 --> 01:16:31,800 Ce serait travailler dans la bulle de tri. 1534 01:16:31,800 --> 01:16:35,210 Mais pour la sélection sorte, si nous ne faisons pas faire un échange, qui pourrait bien être 1535 01:16:35,210 --> 01:16:38,670 parce que la plus petite valeur est en raison de leur position droite. 1536 01:16:38,670 --> 01:16:41,240 Nous pourrions avoir une liste 1, 2, 4, 3. 1537 01:16:41,240 --> 01:16:42,830 La seconde fois, nous ne fera pas des swaps. 1538 01:16:42,830 --> 01:16:47,260 Nous serons sur le numéro 2, mais nous encore besoin de continuer. 1539 01:16:47,260 --> 01:16:49,390 Ainsi avons-nous besoin de garder une trace du moment nous aurons terminé, ou voulons-nous juste aller 1540 01:16:49,390 --> 01:16:50,640 jusqu'à ce que ce soit fini? 1541 01:16:50,640 --> 01:16:54,098 1542 01:16:54,098 --> 01:16:56,740 >> ETUDIANT: Nous pouvons seulement aller jusqu'à ce qu'il soit terminé. 1543 01:16:56,740 --> 01:16:58,090 >> JASON HIRSHHORN: Nous pouvons seulement aller jusqu'à que ce soit fini. 1544 01:16:58,090 --> 01:17:01,720 En tri à bulles, vous avez parfaitement raison, Jeff et Aleha, avec votre solution - 1545 01:17:01,720 --> 01:17:04,990 il est bon de garder une trace du nombre de swaps que vous avez fait, parce que dans la bulle 1546 01:17:04,990 --> 01:17:07,920 sorte, si vous n'avez en fait pas faire des swaps, vous avez terminé et vous pouvez peut-être réduire votre 1547 01:17:07,920 --> 01:17:09,000 problème un peu. 1548 01:17:09,000 --> 01:17:11,440 Mais pour la sélection sorte, vous avez vraiment obtenu d'aller jusqu'à la fin de la 1549 01:17:11,440 --> 01:17:14,940 la liste chaque fois. 1550 01:17:14,940 --> 01:17:16,200 >> Donc, c'est cela. 1551 01:17:16,200 --> 01:17:18,530 Nous avons deux minutes. 1552 01:17:18,530 --> 01:17:21,560 Faisons tous. 1553 01:17:21,560 --> 01:17:24,340 Permettez-moi juste ouvert trouverez ici et fais que je suis en fait appeler - 1554 01:17:24,340 --> 01:17:25,610 Je ne demande pas tri à bulles. 1555 01:17:25,610 --> 01:17:29,230 Nous allons changer cela à la sélection sorte. 1556 01:17:29,230 --> 01:17:31,060 faire toute. / trouver. 1557 01:17:31,060 --> 01:17:32,360 Voyons 42. 1558 01:17:32,360 --> 01:17:38,110 Cette fois, nous allons passer un liste non triés, car il doit trier 1559 01:17:38,110 --> 01:17:43,790 en premier lieu, par le Code de recherche - devrait trier d'abord en utilisant notre fonction de tri, puis 1560 01:17:43,790 --> 01:17:44,995 chercher quelque chose. 1561 01:17:44,995 --> 01:17:46,245 Croisons les doigts tout le monde. 1562 01:17:46,245 --> 01:17:48,530 1563 01:17:48,530 --> 01:17:49,370 >> Oh mon Dieu. 1564 01:17:49,370 --> 01:17:50,800 Whoa, mon cœur battait. 1565 01:17:50,800 --> 01:17:52,320 Donc, c'est exact. 1566 01:17:52,320 --> 01:17:57,270 En fait, si nous avons manqué ce plus largement, le code, autant que je peux 1567 01:17:57,270 --> 01:17:59,280 dire, est tout à fait correct. 1568 01:17:59,280 --> 01:18:02,150 Il ya quelques suggestions Je voudrais avoir pour vous. 1569 01:18:02,150 --> 01:18:06,215 Par exemple, 15 et 16 semblent un peu redondant. 1570 01:18:06,215 --> 01:18:09,450 Il semble que vous n'avez pas nécessairement besoin d'économiser à la fois ceux. 1571 01:18:09,450 --> 01:18:12,790 Si vous avez le moindre emplacement, vous peut facilement trouver la plus petite valeur par 1572 01:18:12,790 --> 01:18:14,750 juste en tapant les valeurs de i. 1573 01:18:14,750 --> 01:18:18,100 >> Donc, si je devais être le classement de votre code, que je vais en fait, je voudrais 1574 01:18:18,100 --> 01:18:21,160 probablement enlever un point si vous inclus les deux, parce que vous 1575 01:18:21,160 --> 01:18:22,670 n'ont pas besoin à la fois de ceux-ci. 1576 01:18:22,670 --> 01:18:25,400 Si vous avez l'emplacement, vous pouvez très facilement obtenir la valeur. 1577 01:18:25,400 --> 01:18:27,520 Et il semble un peu bizarre pour stocker tous les deux. 1578 01:18:27,520 --> 01:18:31,070 Peut-être même pas prendre un point, mais certainement commenter que c'est peut-être 1579 01:18:31,070 --> 01:18:32,670 pas un choix stylistique vous devez faire. 1580 01:18:32,670 --> 01:18:35,290 Bien sûr, le code encore fonctionne parfaitement. 1581 01:18:35,290 --> 01:18:36,860 >> Donc, malheureusement, nous n'avons pas obtenir de tri à bulles. 1582 01:18:36,860 --> 01:18:37,940 Je suis désolé. 1583 01:18:37,940 --> 01:18:39,135 Nous avons fait la sélection finale sorte. 1584 01:18:39,135 --> 01:18:41,450 Est-ce que quelqu'un a des questions finales sur la sélection sorte? 1585 01:18:41,450 --> 01:18:44,320 1586 01:18:44,320 --> 01:18:47,690 >> OK, avant, nous nous dirigeons, je veux que vous d'ouvrir votre navigateur Chrome. 1587 01:18:47,690 --> 01:18:54,340 Désolé, c'était juste une prise flagrante pour un type de navigateur Internet. 1588 01:18:54,340 --> 01:18:57,770 Vous pouvez ouvrir n'importe quel type de navigateur, mais il sera probablement Chrome. 1589 01:18:57,770 --> 01:19:01,250 Et aller à ce site Web suivant - 1590 01:19:01,250 --> 01:19:06,410 sayat.me/cs50. 1591 01:19:06,410 --> 01:19:07,685 Si vous n'êtes pas à taper dans votre ordinateur en ce moment, vous êtes clairement 1592 01:19:07,685 --> 01:19:10,210 ne pas le faire, Tom. 1593 01:19:10,210 --> 01:19:12,870 >> Et s'il vous plaît le faire soit à droite maintenant ou dans l'heure - 1594 01:19:12,870 --> 01:19:14,260 donnez-moi part de vos remarques. 1595 01:19:14,260 --> 01:19:15,660 Ce n'est que la deuxième section. 1596 01:19:15,660 --> 01:19:18,060 Nous avons beaucoup plus ensemble, donc je avoir beaucoup de place à l'amélioration. 1597 01:19:18,060 --> 01:19:19,620 Je espérons aussi fait des choses bien. 1598 01:19:19,620 --> 01:19:22,160 Ainsi, vous pouvez me faire sentir mal du tout, mais si vous aussi vous voulez me donner un smiley 1599 01:19:22,160 --> 01:19:24,250 visage, j'apprécierais aussi. 1600 01:19:24,250 --> 01:19:25,330 Remplissez que po 1601 01:19:25,330 --> 01:19:28,210 >> Et avec une minute, C'était trois semaines. 1602 01:19:28,210 --> 01:19:30,750 Je vais rester à l'extérieur pour un peu si vous avez des questions. 1603 01:19:30,750 --> 01:19:32,220 Je vais voir les gars dans la leçon de demain. 1604 01:19:32,220 --> 01:19:34,742