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