[Powered by Google Translate] [Section 3] [Moins confortable] [Nate Hardison] [Université de Harvard] [C'est CS50.] [CS50.TV] Très bien, nous allons commencer. Bienvenue à la Semaine 4 de CS50. Si vous les gars ouvrez un navigateur Web et d'ouvrir pset 3, Scramble avec CS50, nous allons commencer à aller à travers la section de questions. Tout comme la semaine dernière, nous allons travailler dans les espaces CS50, si vous aussi tirer jusqu'à ce que ainsi, et si vous allez de l'avant et visitez ce lien que j'ai ici en haut. Il est temps de commencer. Nous avons notre programme de salut peu ici. Rien de fou. Une des premières choses que je veux faire avec vous aujourd'hui est d'aller sur quelques solutions à 1 Set problème, le type de solutions, par exemple, pour que vous puissiez avoir une idée de ce genre de code personnel est écrit, quels types d'étudiants d'autres codes sont l'écriture, et avez-vous jeter un coup d'oeil parce que je sais que c'est bizarre lorsque vous soumettez une solution à un problème posé et obtenir des commentaires sur votre propre version, mais il est parfois utile de voir comment d'autres personnes l'ont fait, en particulier ceux qui sont agréable à regarder. Pour la plupart, j'ai été vraiment impressionné par les solutions que vous les gars produites. Je n'ai pas encore commencé à regarder vos 2s problème posé, mais si elles sont quelque chose comme le premier, cela veut dire que de bonnes choses. Si vous regardez mes révisions, nous allons commencer tout en bas à la Révision 1, et nous allons prendre un coup d'œil à une solution Mario. Si vous tirez cette place, ces programmes que nous allons présenter sont corrects. Il n'y avait pas de problèmes avec exactitude ces problèmes, mais plutôt, nous voulons parler un peu plus sur les différents problèmes de conception qui ont été utilisées ici. Une des choses qui était intéressant au sujet de la solution c'est qu'il a utilisé ce nouveau concept appelé livre définir, parfois aussi appelé un hachage définir. Permettez-moi de faire un zoom avant sur le sujet ici. A # define permet de donner des noms à ces numéros dans votre programme. Dans ce cas, la hauteur maximale d'une pyramide de Mario a 23 et plutôt que de mettre 23 dans mon code- Nous renvoyons à ce que le codage en dur 23 - ce qui donne la place MAX_HEIGHT nom à ce nombre, de sorte que, ici dans ma boucle do-while vous pouvez réellement se référer à MAX_HEIGHT au lieu de mettre le numéro 23 po [Étudiants] Quel est l'avantage de faire cela? C'est une très bonne question. La première est la lisibilité. L'avantage d'utiliser ce # define est la lisibilité. Quand je lis ce code, je peux voir ce qui se passe. Je peux voir dans cet état là que nous testons pour la hauteur étant <0, ce qui nous aurait aussi défini à une hauteur minimale ou une hauteur min. L'autre avantage est que je peux alors lire le reste de la ligne pour voir que nous sommes également vérifier pour s'assurer que la hauteur ne dépasse pas la hauteur maximale, parce que nous allons continuer alors que la hauteur est supérieure à la hauteur max. L'autre avantage est, si je effectuer un zoom arrière un peu ici- si je lance ce programme et je le lance, disons, de 23 en ce moment, il affichera tous les 23 rangs juste comme ça. Mais disons que je voulais changer la hauteur maximale, et maintenant je veux limiter la hauteur maximale des pyramides d'être seulement dire-man, qui était géniale. # Include, # define MAX_HEIGHT, et disons que nous avons voulu mettre l'égal à 10. Or, à ce moment-là, tout ce que j'avais à faire était de changer à cet endroit-ci. Je ne peux recompiler le code, et maintenant, si je tente de taper 12, il demandera à moi. Dans ce cas, nous n'utilisons que MAX_HEIGHT fois. Ce n'est pas que les grandes d'une corvée d'aller dans et le changer dans la boucle while si vous avez besoin d'. Mais dans les programmes où vous référençant le nombre magique même encore et encore, ce mécanisme de # define est vraiment très utile parce que vous venez de changer une fois au début du fichier, c'est généralement là où vous les mettez- et le changement percole à travers le reste du fichier. D'autres choses que je voulais souligner dans cette mission que je pensais avait l'air vraiment sympa, l'un était l'appellation des variables. Vous voyez ici que nous avons appelées variables entières ligne et appelle hauteur. Les espaces, les tables de hachage, il contribue à rendre le code un peu plus lisible, rend un peu plus facile à comprendre ce qui se passe réellement. Ceci est en contraste à l'aide, par exemple, des lettres aléatoires ou juste un charabia tout à fait. Une dernière chose que je vais dire, c'est que dans les boucles for, souvent, ces variables d'itération, ces compteurs que vous utilisez dans votre pour les boucles, il est standard et conventionnel pour les commencer avec soit i et j, puis puis k et va à partir de là si vous avez besoin d'autres variables, et ce n'est qu'une convention. Il ya beaucoup de conventions. Cela dépend du langage de programmation que vous utilisez. Mais dans C, nous commencent généralement avec i. Il n'a pas de sens d'utiliser, par exemple, a ou b en fonction de la situation. C'est tout pour cette fois. Si maintenant vous tirer vers le haut Révision 2, vous verrez un autre Mario, et celui-ci est semblable à l'autre ce que nous venons de voir, mais il ne sorte quelque chose de cool. Si l'on regarde cette section ici à l'intérieur de l'intérieur de la boucle, ils utilisent une syntaxe de regard fou ici à droite de cette ligne. C'est ce qu'on appelle un opérateur ternaire. Il s'agit d'une déclaration if else condensées en une seule ligne. La condition est cette partie entre parenthèses. Il est équivalent à dire que si j > Sam. Sam. Comme l'a dit Sam, ce processus de recherche linéaire va être très lent, et au lieu de binaire de recherche, la façon dont cela fonctionne est que chaque fois que nous passons par une itération de notre algorithme de recherche, nous allons diviser la liste en deux, pour l'essentiel, dans deux listes plus petites. Et puis sur la prochaine itération de la boucle, nous allons le diviser à nouveau dans d'autres listes plus petites. Comme vous pouvez le voir, le problème ne cesse de plus en plus petits parce que nous garder la moitié des rejets de la liste à chaque fois. Comment cela fonctionne-t rejets? Pour rappel, ce que nous allons faire si nous étions un ordinateur et nous avons été, par exemple, la recherche de la numéro 5 dans la liste est que nous aurions choisir un nombre au milieu. Au milieu de cette liste, car il n'y a 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 chiffres, nous aimerions prendre le nombre soit à la 4ème position ou à la 5ème position, et nous aimerions appeler cela au milieu de notre liste. Choisissez nombre au milieu. Puis, comme l'a dit Sam, nous allons tester pour voir si ce nombre est égal au nombre que nous voulons obtenir ou notre numéro souhaité. Si c'est égal, nous l'avons trouvé. Nous gagnons. Si ce n'est pas égal, alors il ya un ou deux cas. Les deux cas sont soit le nombre doit être supérieur au nombre que nous étudions, ou c'est moins. Si elle est supérieure, nous nous dirigeons vers la droite. Et si c'est moins, nous nous déplaçons vers la gauche. Et puis on répète tout le processus soit sur la moitié droite ou la partie gauche de la liste. Le premier problème dans la section d'aujourd'hui est de savoir comment nous pouvons réellement commencer à exprimer cela dans le code C. Nous avons ici le pseudo-code. Ce que nous allons commencer à faire c'est que je vais remonter un tout nouvel espace, enregistrer cette révision afin que nous ayons ces notes pour plus tard, nous allons supprimer tout cela, et puis copiez et collez le problème posé cette information dans nos espaces, et j'espère que cela ne se brise pas. Parfait. Si vous les gars tout cela, copiez et collez ce code dans votre nouvel espace, dans une carte vierge. Essayons de Daniel. Si vous compilez et exécutez ce programme, ça marche? Non >> Qu'est-ce qu'il dit? Il affirme que le contrôle atteint la fin de non-fonction void. Ouais, donc je vais essayer de l'exécuter. Avez-vous les gars déjà vu ça? Savez-vous ce que cela signifie? Ok, nous allons disséquer cela un peu petite. C'est dire à fichier.c sur la ligne 9, colonne 1, nous avons une erreur, tout comme vous l'avez dit, et il dit qu'il est issu de l'avertissement et l'avertissement d'erreur type de retour. Il ressemble à quelque chose qui se passe avec le type de retour, ce qui est logique. Nous avons une fonction non nulle, ce qui signifie que nous avons une fonction qui ne retourne pas void. Une fonction nulle est celle qui ressemble à ceci: void foo (), et il est nul parce que le type de retour est void, ce qui signifie que si nous avions quelque chose ici comme retour 1, nous obtiendrions une erreur du compilateur pour cela. Cependant, nous avons une fonction non nulle. Notre non void de la fonction dans ce cas est la fonction de recherche parce qu'il a un type de retour bool. Quand il est dit que le contrôle atteint la fin d'une fonction non nulle, c'est parce que la recherche n'a pas d'instruction return. Ce n'est pas quelque chose de retour de type bool. Nous pouvons résoudre ce problème, et ce que vous en pensez recherche devrait revenir par défaut? Quelle devrait être la valeur de retour par défaut de la recherche? Parce que c'est ce que nous pouvons mettre à la fin. Charlotte, avez-vous un-? Vrai ou faux? >> Vrai ou faux. Lequel? Faux. Je ne sais pas. Faux? Essayons. Pourquoi dis-tu fausse déclaration? C'est une grande intuition. [Charlotte] Je ne sais pas. Nous allons retourner faux dans ce cas, car ce sera notre défaut si pour une raison quelconque, la liste est vide ou l'aiguille que nous cherchons n'existe pas. Puis, à la fin, si nous ne revenons pas réalisé plus tôt dans cette fonction, nous savons toujours que cette fonction va dire nope, ce n'est pas dans le tableau. Ce n'est pas dans la botte de foin. Maintenant, si nous compilons et exécutons il, laissez-moi sauver ce que nous puissions le tirer vers le haut. Maintenant, si nous compilons et exécutons notre programme, il construit. Nous obtenons notre petit prompt. Si je frappe 4-uh-oh. Il n'a pas d'imprimer quoi que ce soit. On dirait que tout finit bien. Nous devons combler ce po Nous avons parlé de l'algorithme en pseudo-code un peu plus tôt. Laissez-moi voir, enregistrer ce, et je vais te tirer de cet algorithme remonter. Frappons ce type. Nope. Il est là. Comment pouvons-nous faire cela? Que serait une stratégie bien pour un début ce code? Vous devez choisir un numéro dans le milieu. Comment pouvons-nous choisir un nombre au milieu d'un tableau? Des suggestions? [Étudiants] strlen divisé par 2. Strlen divisé par 2. C'est un grand. Strlen travaille avec des types particuliers de tableaux. Quels types de tableaux? Tableaux de chaînes, des tableaux de caractères. C'est ce même type de concept que nous voulons appliquer, mais nous ne pouvons pas utiliser strlen parce que nous n'avons pas un tableau de caractères. Nous avons un tableau d'entiers. Mais qu'est-ce que strlen obtenir pour nous? Savez-vous ce que cela devient pour nous? [Étudiants] strlen nous procure la longueur. Exactement, il nous procure la longueur. Strlen obtient la longueur du tableau pour nous. Comment pouvons-nous obtenir cela dans notre programme de recherche binaire? Comment pourriez-vous obtenir la longueur d'un tableau? [Étudiants] strlen? Vous pouvez obtenir la longueur d'un tableau de chaînes C correctement formaté avec strlen. Le problème, cependant, c'est que nous n'avons pas un tableau de chaînes. Si nous regardons en arrière à ce code, nous avons ce tableau d'entiers. Comment savons-nous combien de temps est-il? [Étudiants] Y at-il un équivalent pour un point de terminaison, comme l int ou quelque chose? Il s'avère qu'il ya effectivement pas, et donc, en un sens, ce n'est l'une de ces choses qui sont juste bon de savoir sur C, qu'il n'y a pas moyen d'obtenir la longueur d'un tableau si tout ce que je vous donne est le tableau. La raison pour laquelle cela fonctionne avec des cordes, la raison strlen travaux, En effet, si une chaîne est correctement formaté, il faudra que spécial caractère \ 0 à la fin. Vous pouvez aussi imaginer si vous avez une chaîne formatée incorrectement et il n'y a aucun caractère \ 0 là, alors tout ne fonctionne pas. [Étudiants] Pouvez-vous ajouter le \ 0? On pourrait dans ce cas. Nous pourrions ajouter une sorte de \ 0 ou une sorte de signifiant caractère et ensuite l'utiliser. Mais ce n'est pas tout à fait d'aller travailler parce que le 0 \ est un type char, et ici nous avons ints. L'autre chose est de savoir si nous devions utiliser une valeur spéciale comme -1 pour marquer la fin d'un tableau alors nous ne pourrions jamais stocker un -1 dans nos tableaux d'entiers. Nous serions coincés. Il s'avère que la seule façon d'obtenir la longueur d'un tableau en C est en fait de s'en souvenir lorsque vous le configurer et de le passer autour de la baie de sorte que chaque fois que j'ai une fonction qui va faire un peu de travail sur un tableau d'entiers ou flottants ou en double ou je ne sais quoi, J'ai aussi besoin de donner à la fonction la longueur du tableau, et c'est exactement ce que nous avons fait ici, à la fonction de recherche. Si vous regardez, ce que nous avons fait quand nous passons dans notre tableau ici, nous avons également passer dans la longueur, la taille. Il se trouve que nous avons appelé cette variable ici, ce paramètre ou argument. C'est ce qu'on appelle la liste des arguments d'une fonction ou d'une liste de paramètres, et ceux-ci sont également appelés arguments ou paramètres. Les gens utilisent des termes différents à des moments différents. J'ai parfois échanger moi-même. Il se trouve que cette variable est ici nommés de la même à ce # define ici. Mais ils ne sont pas la même chose. La capitalisation est importante. Si vous regardez ce qui se passe ici, nous déclarons notre tableau int, que nous avons appelés nombres. Nous lui avons donné notre taille, ce qui correspond à notre # define au sommet. Il va y avoir 8. Et puis, quand nous appelons ensuite la fonction de recherche en bas, nous passons dans le nombre que nous voulons chercher, que nous avons invité, obtenu auprès de l'utilisateur. Nous passons dans le tableau, ces numéros, et puis il faut aussi passer à la taille de la matrice, puis la valeur de taille 8 est stockée ou transmis à cette taille entière appelée variable. Nous avons la taille du tableau. Maintenant, si nous revenons à ce dont nous parlions tout à l'heure, Je pense que Missy élevé au point que ce que nous avions besoin de faire est d'obtenir la longueur du tableau et le diviser par 2, et qui nous donnera le point médian. Voyons voir. Puis-je avoir quelqu'un écrire ceci et l'enregistrer dans son espace? Que diriez-vous Leila? Puis-je écrire ce que vous avez en? Écrire la première ligne où vous prenez la longueur du tableau et obtenir le point médian et le stocker dans une variable. Je vais vous donner quelques secondes. Êtes-vous prêt? [Étudiant inaudible] Bien sûr, ai-je pu vous calculez le milieu du tableau botte de foin à l'intérieur de la fonction de recherche en utilisant la longueur de la matrice de meule, qui est la variable de taille? Rien de compliqué ici. [Leila] Juste taille / 2 et tout- Et l'enregistrer, et appuyez sur le bouton Enregistrer ici au sommet, et nous allons le tirer vers le haut. Parfait. Nous y voilà. Awesome. En l'état, ce sera compiler? [Leila] Non, ce doit être plus élevé. [Nate] Ouais, alors que devons-nous faire? [Leila] Comme milieu int ou quelque chose. Awesome. Oui, allons-y, int taille = milieu. Est-ce que cette compilation? Nous allons supprimer ce commentaire et de le sortir de la voie. Quelle ne sera pas compilé à ce sujet? Nous ne faisons pas n'importe quoi avec entier, nous avons donc besoin d'imprimer ou quelque chose comme ça. Oui, exactement. Nous aurons une variable utilisé. Quoi d'autre ne va pas travailler à ce sujet? Je pense que vous avez dit quelque chose, Sam. Des points-virgules. Ouais, il me manque ces points-virgules. Il va y avoir une chose constante pendant toute la durée du terme. La dernière chose que je vais faire c'est que je vais mettre un peu d'espace blanc de chaque côté de cet opérateur ici, puisque c'est généralement la façon dont nous le faisons selon notre guide de style. Nous avons au milieu de notre tableau. Maintenant, si nous nous rappelons à notre algorithme, ce qui était la deuxième étape que nous avions à faire une fois que nous avons le milieu? [Étudiants] Si elle est supérieure [inaudible]. Oui, nous devons donc faire une sorte de comparaison, et qu'est-ce qu'on compare ici? Vous avez dit, si elle est supérieure. Qu'y at-il dans cette phrase allusion? Le numéro qui va sortir, si ce n'est supérieure à la médiane, puis remonter au tableau? Exactement, donc le nombre qui vient quand nous- L'aiguille, donc nous comparer à l'aiguille, et ce que nous comparant à l'aiguille? Parce que l'aiguille est ce que nous recherchons. Nous sommes le comparant à se rendre à la mi-parcours. Mais est-il sensé de vérifier si l'aiguille = milieu? Est-ce logique? Quelqu'un at-il pas d'accord? Nous allons faire un essai, si (== aiguille milieu). [Étudiants] Ne printf vous l'avez trouvé. [Nate] printf ("Nous l'avons trouvé \ n"); Sinon,-je vais commencer à faire quelque chose de différent ici. Je vais commencer à mettre des accolades autour if tout le temps simplement parce que si nous ajouter plus de choses, alors nous n'obtenons pas les compilateurs. Ouais, Sam. Vous avez un point. Le problème, c'est que point central représente une position dans le tableau, mais vous pouvez l'obtenir pour représenter la valeur dans cette position du tableau. C'est un excellent point. Tout le monde a entendu ce que Sam a dit? Il a dit que milieu est aussi ne représente qu'une position dans le tableau, mais ce n'est pas le véritable élément dans le tableau. Si vous pensez que le code écrit en ce moment, si l'on regarde ce tableau ici-bas, qui dispose de 8 éléments en elle, quelle est la valeur du milieu va être dans cette fonction? [Étudiants] 4. [Nate] 4. Si l'on regarde le nombre 4 - et nous pouvons exécuter ce code et mettez un petit visage triste ici parce que nous n'avons pas trouvé, si nous exécuter ce code comme c'est en ce moment, de le télécharger, bâtiment, permettez-moi de faire défiler vers le bas, et si l'on regarde le nombre 4, nous l'avons trouvé, mais nous n'avons pas obtenu ce à printf oui. Une des raisons est que nous n'avons pas retourner vrai, mais avons-nous vraiment trouver le numéro 4? Et Sam dit non. Qu'avons-nous trouvé? Nous avons vraiment trouvé le point médian, qui, si on regarde le tableau ici-bas, ça va être l'élément à l'index 4 que nous étudions, qui est 23. Comment pouvons-nous réellement obtenir cet élément au milieu et pas seulement le milieu lui-même? [Étudiants] Nous aimerions entrer char ou quelque chose? Qu'est-ce que cela ferait, juste par curiosité? Pouvez-vous nous en dire un peu plus? Vous avez pour transformer la position dans le nombre, de sorte que vous avez à faire un lien, je pense que c'est char, mais il pourrait ne pas l'être. Ouais, c'est un bon point. Nous avons fait beaucoup de ces postes de conversion en caractères, ces caractères, dans les deux premières séries de problèmes. Il se trouve que là, ce qui est presque semblable à l'accès au ième caractère dans une chaîne, si cela fait sens. Ici, nous voulons accéder à l'élément médian. Comment faisons-nous cela? Kevin, avez-vous des suggestions comment nous pourrions le faire? Vous pourriez faire botte de foin, ouvre la parenthèse, mi, fermé support. Pouvez-vous écrire cela pour nous? Enregistrez-le ici, et nous allons tirer que vers le haut. Nous nous penchons sur cette ligne 9, et nous sommes conscients que nous ne voulons pas comparer l'aiguille au milieu, mais au contraire, nous voulons comparer l'aiguille à l'élément au milieu poste au sein de notre gamme botte de foin. Cool. Nous y voilà. Ouais, ça semble assez bon, si (== aiguille botte de foin [milieu]). Nous l'avons trouvé. Maintenant, si nous courons le dos de code we'll un peu peu- il compile, il fonctionne, et maintenant, si nous recherchons 4, nous n'avons pas à le trouver, parce que maintenant nous sommes en train d'obtenir le nombre 23. Nous obtenons la valeur 23, et c'est ce que nous comparons à notre aiguille. Mais c'est une bonne chose. C'est un pas dans la bonne direction. C'est ce que nous essayons de faire. Nous n'essayons pas de comparer l'aiguille contre les positions dans le tableau mais contre les éléments réels du réseau. Si nous regardons en arrière à nouveau maintenant à la prochaine étape de notre algorithme, quelle est la prochaine étape? Leila déjà parlé brièvement. [Étudiants] Vérifiez pour voir si elle est supérieure ou inférieure, puis décider de quel côté aller. [Nate] Ouais, alors comment pourrions-nous le faire? Pouvez-vous mettre dans un certain je-enregistrer cette révision, et puis si vous mettez en quelques lignes qui vont le faire. Oui, Charlotte. >> J'ai une question. Devrait-il pas mi-parcours - 1 parce que la première chose est c'est 0 indexées, ainsi si nous mettions 4, ce n'est pas réellement le caractère que nous recherchons? Oui, et l'autre problème avec cela, c'est- c'est une belle prise, parce que ce qui va se terminer par se produire éventuellement si nous continuons à avancer et nous ne jamais régler d'abord? Je suppose que ce que nous pourrions finir par faire est d'essayer d'accéder à l'élément à la position 8 du tableau, qui dans ce cas n'existe pas. Nous voulons faire une sorte de tenir compte du fait que nous avons une indexation zéro. [Charlotte] Désolé, je voulais dire mi-parcours - 1 dans les crochets. Nous pouvons le faire. Nous reviendrons sur cette question dans un peu. Une fois que nous commençons à arriver à la boucle réelle, c'est là que nous allons vraiment voir cette entrent en jeu. Pour le moment, nous pouvons le faire, mais vous êtes tout à fait raison. Que l'indexation zéro aura un effet que nous devons rendre compte. Voyons voir. Comment est la plus grande et de moins-? [Étudiants] je reçois comment faire le plus long et moins de part. Je n'étais pas sûr de ce que d'imprimer si vous trouvez qu'il est inférieur au point médian botte de foin ou supérieur. Ici, je peux sauver ce qui j'ai- [Nate] Oui, si vous enregistrez ce que vous avez, et nous allons le tirer vers le haut. Nous y voilà. [Étudiants] Et je mets des points d'interrogation pour ce que je ne savais pas. [Nate] Cela ressemble beaucoup. Ici nous avons des points d'interrogation parce que nous ne savons toujours pas ce que nous allons tout faire pour le moment. Qu'est-ce que nous voulons faire, oups, nous avons quelques accolades tous géniaux sur nous. Nous allons corriger ces accolades. Nous y voilà. Et alors qu'est-ce que nous voulons faire, selon notre algorithme, si nous ne trouvons pas l'aiguille? Dire dans le cas où l'aiguille est inférieure à ce que nous nous penchons. Kevin. Regardez seulement la moitié gauche. Bon, alors on va mettre un commentaire ici qui dit "regarde moins la moitié gauche." Et si l'aiguille est supérieure à la botte de foin au milieu, que voulons-nous faire? [Étudiants] Et puis tu regardes la moitié droite. Regardez la moitié droite, "regarder à moitié raison." Pas trop mal. Bon, alors, à ce moment-là, les choses s'annoncent plutôt bien. Le problème avec le code tel qu'il est écrit, c'est quoi? [Étudiants] Vous n'avez pas terminaisons pour les deux moitiés. A droite, nous n'avons pas terminaisons pour les deux moitiés. Nous avons aussi allez seulement à passer par là. Nous allons seulement regarder un point médian. Soit l'élément est là, ou il n'est pas. Pour compléter cela, nous aurons besoin de faire une sorte de répétition. Nous devons continuer à répéter jusqu'à ce que nous constatons que soit l'élément est là parce que nous avons réduit et finalement trouvé, ou il est pas là parce que nous avons regardé à travers toutes les choses dans les moitiés appropriées de la matrice et constaté que rien n'est là. Chaque fois que nous avons obtenu cette répétition se passe, qu'est-ce qu'on va utiliser? [Étudiants] Une boucle. Une sorte de boucle. Oui. [Étudiants] Peut-on faire une boucle do-while et faites-le faire et puis, tout en l'aiguille n'est pas égale-je ne sais pas où je vais avec cela. Mais un peu comme faire tant qu'il n'est pas égale à la valeur que l'entrée de l'utilisateur. Oui, nous allons donc voir, comment cela pourrait-il lui-même écrire? Vous avez dit, nous allons utiliser une boucle do-while. D'où vient le faire début? [Étudiants] Juste après la taille / 2. [Nate] Bon, et qu'est-ce qu'on va faire? Nous allons remplir le temps plus tard. Qu'allons-nous faire? [Étudiants] N'avons-nous pas envie de faire toutes les choses que nous avons dans la partie, si? [Nate] Faites tout ce genre de choses, tant mieux. Copier et coller. Oh, mec. Voyons voir si cela fonctionne, si nous le pouvons onglet présent terminée. Belle. D'accord, et nous avons donc enregistrer ce que vous les gars l'ont. Très bien, et nous allons le faire en- ce qui était la condition alors que vous étiez après? [Étudiants] Alors que l'aiguille n'est pas égal, donc comme le point d'exclamation. Mais je ne sais pas exactement ce que c'est le moment. [Nate] Oui, c'est une façon de le faire. Sam, avez-vous un commentaire? [Sam] Je me suis souvenu quand j'ai regardé les vidéos, J'ai pris une capture d'écran d'un des-comme lorsque nous avons fait le pseudo-code pour elle, il y avait une certaine relation entre max et min. Je pense que c'était quelque chose comme si max est toujours inférieur à min. Got it. [Sam] Ou comme si max n'est pas inférieur à min ou quelque chose comme ça, parce que cela signifierait que vous avez cherché tout. Ouais, et alors qu'est-ce que ça sonne comme max et min parliez? [Sam] Sélection-ce que les nombres entiers qui vont changer par rapport à où nous avons mis au point médian. Exactement. [Sam] À ce moment-là, ça va [inaudible] calculer le max et min. Milieu cette idée max et min. Est-ce logique pour les gens? Si nous devions commencer à regarder comment nous allons faire cette itération, vous êtes tout à fait raison que nous voulons utiliser une sorte de boucle do-while. Mais je suppose que si nous nous souvenons de ce qui se passe à l'endroit de ce tableau et ce qui se passe réellement-je vais écrire ici- à l'itération toute première binaire de recherche, nous avons- Je vais utiliser b et e pour indiquer le début. Et puis la fin de notre tableau. Nous savons que le début est à 4 par ici, et nous savons que la fin est à 108. Dites nous recherchons pour le numéro 15. La première fois que nous faisons cela, comme nous l'avons vu précédemment, le milieu est soit va être 16 ou 23 selon la façon dont nous calculons les choses. Depuis uniformément divisant dans le milieu nous donnerait cet espace entre 16 et 23, on ne peut le diviser uniformément ou la diviser et obtenir à un point médian vrai. Nous allons examiner 16. Nous vous rendrez compte "Hé, 16> 15 que nous recherchons." Pour ensuite examiner la moitié gauche du tableau ce que nous allons finir par faire est le rejet toute cette partie supérieure et en disant: «Bon, maintenant notre point de terminaison va être ici." La prochaine itération de notre boucle, nous cherchons maintenant à ce tableau, effectivement avoir écarté cette partie parce que maintenant si nous prenons le point médian de la différence entre le début et la fin, nous trouvons notre milieu à 8, que nous pourrons tester 8 pour voir où il est en relation avec le nombre que nous recherchons, 15, trouve que 15 est plus grande, nous devons donc passer à la partie droite de la liste, que nous connaissons parce que nous sommes des êtres humains, et nous pouvons le voir. Nous savons que la partie droite va être là où nous le trouvons, mais l'ordinateur ne sait pas que, si ce que nous allons faire, c'est nous allons effectivement ont cette montent, et maintenant le début et la fin sont au même endroit, de sorte que le milieu devient le seul numéro dans la liste à ce moment-là, qui est de 15, et nous l'avons trouvé. Est-ce que faire la lumière sur toute max où cette notation et va min, garder la trace des points de terminaison du réseau dans le but de comprendre la manière de réduire les choses? Que se passerait-il si ce n'était pas égal à 15 maintenant? Et si nous étions à la recherche de 15 et, au contraire, ce nombre avait aussi 16? Nous dirions: «Oh, elle est supérieure. Nous voulons aller vers la gauche. " Et nous passerions notre e vers la droite, à quel point nous avons un point de terminaison qui serait contradictoire. Il ne serait pas en mesure de rechercher des éléments, pas plus parce que maintenant nous avons notre point de terminaison et de notre point de départ, notre max et min notre, sont maintenant inversés. Nous recherchons à travers l'ensemble du réseau. Nous ne pouvons pas trouver quoi que ce soit. C'est le moment où nous avions envie de dire: «Bon, nous allons nous arrêter cet algorithme. Nous n'avons pas trouvé quoi que ce soit. Nous savons que ce n'est pas ici. " Comment est-ce que ça va? [Étudiants] Comment fonctionne exactement l'ordinateur passer la fin? Comment ça la fin finissent avant le début? L'extrémité se termine avant le début en raison de la mathématique que nous allons faire à chaque fois que nous faisons cela. La façon dont nous échangeons, c'est que si vous regardez la toute première fois que nous faisons ce swap où nous avons le début à 4 et à la fin tout en bas à 108 et notre milieu, disons, à 16 - Je vais remettre ce retour à 15 si l'on envisage pour les 15, nous savions que ce que nous faisions quand nous sommes arrivés le 16 et vit que cela était plus et je voulais jeter toute la partie droite de la liste, nous avons vu que ce que nous voulions faire est de déplacer cet e ici. En effet, l'e me suis déplacé à une avant le milieu. De même, lorsque nous avons fait cette itération de l'algorithme et le point milieu est à 8, nous avons constaté que 8 <15, nous avons donc voulu déplacer le b une passé le point médian. Or, le début et la fin sont tous les deux en même temps à ce 15. Si nous avions été se passe à chercher une autre valeur, et non pas 15, ou, si cela 15 avait été à la place de 16, nous avons constaté que le courrier que nous voulons déplacer un avant le milieu. Maintenant, l'e serait là retournée inférieure à la b. Passons en revue la façon dont nous finissons par cet algorithme de codage. Nous savons que nous voulons avoir ce calcul milieu. Nous savons aussi que nous voulons suivre le début et la fin du tableau de notre gamme actuelle afin que nous puissions comprendre où cette moitié gauche de la liste et où la moitié droite de la liste est. Nous faisons cela avec soit commencer et finir, ou nous pouvons les appeler min et max. Je vais utiliser commencer et finir cette fois. Quand nous commençons, si nous regardons en arrière à notre exemple ici-bas, notre début a été fixé au tout début du tableau, aussi naturel. Quel indice était-ce? Quelle devrait être notre être commencer? Daniel. [Daniel] Haystack [0]. [Nate] Ouais, pour que nous puissions égal à botte de foin [0]. Le problème, cependant, c'est que cela nous donne pas la position du premier élément. Il nous donne l'indice du premier élément ou la valeur réelle à cette première position. [Étudiants] Cela se convertir à 0,20? [Nate] Qu'est-ce que cela va faire est, eh bien, il ne fera pas de conversion. Qu'est-ce qu'il va faire, c'est qu'il va stocker un 4 en commencer, puis il sera difficile de faire des comparaisons à l'encontre commencer parce begin tiendra la valeur de 4, qui est le début de notre tableau, mais nous voulons suivre les indices dans le tableau par opposition aux valeurs. Nous allons utiliser effectivement un 0, comme ça. Pour la fin du tableau-Charlotte a soulevé cette question un peu plus tôt. C'est là que nous allons tenir compte de l'indexation zéro. Charlotte, quelle est la fin du tableau? Quel est l'indice de la fin? [Charlotte] Taille - 1. Ouais, et dont la taille doit-on utiliser? Faut-il utiliser la taille du capital ou de la taille minuscule? La taille de la capitale. Dans ce cas, nous pourrions utiliser la taille du capital. Si nous voulions que cette fonction soit portable et utilisez cette fonction à d'autres programmes, nous pouvons utiliser la taille minuscule. C'est très bien aussi. Mais Charlotte est totalement juste que nous voulons avoir la taille - 1. A ce point de [Étudiants] Comment se fait-il que vous pouvez utiliser la taille majuscules? Comment est-ce que nous pourrions utiliser la taille majuscules? Il s'avère que ceux-ci définit # sont vraiment, sous le capot, un texte comme rechercher et remplacer, si cela fait sens. Lorsque vous compilez votre code, la phase de prétraitement du compilateur passe par le fichier, et il cherche partout que vous avez écrit la taille du capital, et il remplace ce texte littéralement avec un 8, juste comme ça. En ce sens, ce qui est très différent d'une variable. Il ne prend pas de place dans la mémoire. C'est un truc simple texte de remplacement. Dans ce cas, nous allons utiliser la taille. De là, nous voulons faire une sorte de répétition, et nous sommes sur la bonne voie avec notre boucle do-while. Nous voulons faire quelque chose jusqu'à ce qu'une condition ne tient plus, et comme nous l'avons vu plus haut, nous avons vu que cette condition était en effet que nous ne voulons pas la fin à moins que le début. C'est notre condition d'arrêt. Si cela se produit, nous voulons arrêter et déclarer comme «Hé, nous n'avons pas trouvé quoi que ce soit." Pour exprimer cela, nous voulons utiliser une sorte de boucle. Dans ce cas, serait-il une boucle do-while, une boucle for, une boucle while? Nous avons une boucle do-while ici. Avez-vous les gars comme cette approche? Pensez-vous que nous devrions essayer une approche différente? Kevin, des idées? Nous pourrions avoir une boucle while parce que nous savons maximale serait plus grand que min au début de toute façon. Oui, il n'y a donc pas d'initialisation qui doit se produire. Ces boucles do-while sont grands quand vous avez quelque chose à initialiser avant de tester ensuite, alors qu'ici, nous savons que nous n'allons pas garder réinitialisation commencer et finir chaque tour de la boucle. Nous savons que nous voulons pour les initialiser, puis vérifier notre état. Dans ce cas, je vais effectivement aller avec une boucle while simple. Il s'avère que boucles do-while sont utilisés très souvent. A beaucoup d'endroits ne sont même pas enseigner ne les boucles while. Ils sont bons pour la manipulation de l'utilisateur, de sorte que nous avons vu beaucoup d'entre eux à ce jour. Mais la normale et les boucles while sont beaucoup plus fréquents. Il s'avère que cette condition écrite ne sera pas vraiment nous faire beaucoup de bien, et pourquoi est-ce? Je suis désolé, je ne connais pas votre nom. Je suis Jerry. >> Désolé? C'est B-O-R-U-je. Oh, d'accord. Je ne vois-tu pas sur ma liste. Oh, c'est parce que, oh, c'est logique. Avez-vous une idée de pourquoi cette boucle while peut ne pas fonctionner comme prévu, tel qu'il est rédigé avec la condition? [Jerry] Tu veux dire comme vous voulez tous les trucs après dans le-? Ouais, donc c'est un. Nous pourrions avoir à faire toutes ces choses dans la boucle while, ce qui est totalement vrai. L'autre chose qui est un peu plus problématique, cependant, est que cette condition ne fonctionne pas. [Étudiants] Vous devez le retourner. Bon, alors cette condition ne sera jamais vrai d'abord la façon dont nous avons parlé. Nous voulons faire quelque chose jusqu'à ce que > Plus commencer? [Étudiants] A la fin. Parce que c'est seulement la moitié de la longueur calculée. Vous devez ajouter le commencer. [Nate] Qu'est-ce que cela calculer pour nous? Si nous pensons à la fin de cette première itération de la boucle, fin va être dans 7 à la position index. Commencez est en position 0. Rappelez-vous, nous recherchons soit la position 3 ou la position 4. Si nous regardons ce calcul, juste pour le rendre un peu plus concret, mettre des chiffres ici, nous avons 7, 0, donc 7 - 0, puis / 2 est 3 dans la division entière, ce qui est. Alors devons-nous alors rajouter notre commencer? Nous ne sommes pas dans ce cas. Sur la première itération, il fera beau, car de début est 0. Mais alors que nous progressons, nous faisons vraiment tout juste besoin d' fin - début / 2. Il ya un autre truc ici, et qui est notamment l'une des priorité. [Étudiants] Avons-nous besoin de parenthèses? [Nate] Exactement, et c'est parce que si nous ne mettons pas ces parenthèses, alors cette ligne sera interprétée au lieu que (fin) - (début / 2), que nous ne voulons certainement pas. Attention à ces règles de priorité. [Étudiants] Pourquoi n'est-il pas fin à + commencer? Pourquoi n'est-il pas fin à + commencer? [Étudiants] Pourquoi n'est-il pas cela? Pourquoi serait-il +? Je pense que vous avez raison. [Étudiants] Parce que c'est la moyenne? [Nate] + Fin de commencer, vous êtes tout à fait raison. Wow, je suis totalement raté son coup. Vous avez raison. Si nous faisions le moins, nous voudrions ajouter le retour commencent po Dans ce cas, vous avez raison que nous voulons prendre la moyenne des deux, si nous voulons les ajouter, au lieu de les soustraire. [Étudiants] Il serait aussi si vous ne finissent - begin / 2 + commencer. Il serait si nous le faisons, je crois que oui. Par exemple, si nous cherchions à commencer, et nous l'avons déplacé ici au 15. Maintenant commencer est en position 2. End est à la position 7. Si on les soustrait, on obtient 5. Diviser par 2, nous obtenons 2. Et puis on ajoute 2 à l'arrière dans, et qui nous arrive à la 4ème position, qui est ici, qui est le point central. [Étudiants] Avons-nous besoin de prendre soin de l'emballage? Dans quel sens faut-il prendre soin d'envelopper? Si la somme ou la différence entre selon la façon dont nous le faisons n'est pas un nombre pair. Ensuite, l'ordinateur devient confus si quand il est 2,5; déplacez-vous vers la gauche ou vers la droite pour déterminer qui est le milieu? Got it. Il s'avère que la division entière, nous ne jamais obtenir ces nombres à virgule flottante. Nous n'avons jamais obtenir la décimale. Il est totalement écarté. Si vous avez un ordinateur diviser deux variables int, et une est 7, et l'autre est 2, vous n'obtiendrez pas 3.5 en tant que résultat. Il obtiendra 3. Le reste sera rejeté, donc c'est effectivement arrondissement pas un rond, mais plutôt un plancher, si vous les gars sont familiers avec ce que les mathématiques, où vous rejeter complètement la virgule, et si vous êtes essentiellement le tronquer inférieur le plus proche de la position de l'ensemble, à l'entier le plus proche. [Étudiants] Mais alors c'est problématique parce que si vous avez un tableau de 7 éléments puis qui prend automatiquement le 3ème élément de la médiane au lieu de la 4ème. Comment pouvons-nous résoudre ce problème? C'est problématique parce que si nous avons eu une série de 7, il serait prendre la 3e place du 4. Pourriez-vous expliquer un peu plus? [Étudiants] Parce que si vous disposez de 7 éléments, puis le 4ème élément serait le point central, non? N'oubliez pas vos commentaires sur zéro étant indexé, cependant. [Étudiants] Ouais, donc en position 3. Ce serait le point central. Ouais. Oh, d'accord. Je vois ce que tu veux dire. C'est un peu bizarre, comme on s'habitue à cette notion de se débarrasser des nombres décimaux. C'est un excellent point. Finissons-en. Nous avons calculé notre milieu. Nous testons pour voir si notre aiguille est égale à la valeur moyenne. Nous l'impression que nous l'avons trouvé, mais vraiment, qu'est-ce que nous voulons faire dans cette situation? Nous l'avons trouvé, nous voulons que l'appelant que nous l'avons trouvé. Nous avons une fonction qui est une fonction booléenne typée. La façon dont nous signaler à l'appelant de notre fonction que nous sommes prêts à aller est-on dire, "Hé, c'est vrai." Comment ferions-nous cela, Kevin? Vous êtes en hochant la tête. >> [Kevin] Ajouter vrai retour. [Nate] Exactement, retournez true. Maintenant, si ce n'est pas égal, comment pourrions-nous examiner la moitié gauche? Des idées? Stella, des idées? Vous devez définir une nouvelle position pour la fin. Ouais. Donc, nous devons faire la position du milieu - fin. Grande. Nous avons besoin de définir une nouvelle position pour la fin à regarder la moitié gauche. C'est ce que nous avons parlé auparavant, où J'ai toujours revenir à cet exemple. J'ai le commencer ici, et puis j'ai la fin, tout en venant ici. Encore une fois, si nous sommes à la recherche de 15 ans, et notre milieu est à 16, et nous nous rendons compte, "Oops, 16 est plus grande. Nous voulons aller à la moitié gauche. " Nous serions alors déplacer l'extrémité de la 15, et nous le faisons par l'un emportant à partir du milieu et la mise que notre nouvelle fin. De même, si nous voulons regarder la moitié droite, comment ferions-nous cela? Avez-vous une idée? [Étudiants] Vous venez de définir commencer au point milieu + 1. [Nate] Grande. Et maintenant, dans le cas où nous ne trouvons rien, est-ce que vous pris soin de nous? Daniel, est-ce que vous prendre soin de nous? [Daniel] No. [Nate] Si nous le faire à travers l'ensemble du réseau et nous n'avons rien trouvé, où cela serait-il pris en charge, ou devrions-nous prendre soin de lui? [Daniel] La condition du while. [Nate] Ouais, la condition du while, exactement. Il prendra soin de passer par l'ensemble du réseau si l'on ne trouve rien. Cette boucle while se termine. Nous ne pourrons jamais avoir rencontré cette condition, et nous pouvons renvoyer false. On peut aussi laisser ce si ici comme ça parce que si cette affirmation est vraie si, et notre fonction sera de retour, et nous allons donc essentiellement annuler cette fonction à ce stade quand nous reviendrons vrai. Mais qu'est-ce qui se passe avec cette structure ici? Est-ce que cela fonctionne tout à fait, ou est-il une faille logique là-dedans? Il ya une certaine faille logique là-dedans, avec la façon dont il est mis en place. Que pourrait-il être? [Étudiants] Pourquoi avez-vous besoin - et + 1s? Qui définit notre gamme pour être notre nouvelle moitié gauche et la moitié droite. [Étudiants] Mais pourquoi ne pas le faire sans - 1s 1s et +? [Nate] Nous pourrions égale à la médiane? Ce qui pourrait être problématique à ce sujet? [Étudiants] Je suppose que c'est inefficace parce que vous vérifiez une valeur qui a déjà été vérifié. [Nate] Exactement, Sam est tout à fait raison. Si vous réglez la fin et le début égale à la médiane au lieu de - 1 et + 1 réflexive, à un certain moment dans l'avenir, nous allons finir par contrôler le milieu nouveau. [Étudiants] J'ai commencé le pset, et puis j'ai eu quelque chose comme ça où j'ai oublié le 1 +, et il est resté coincé dans une boucle infinie. Oui, parce que à un moment donné, vous ne réussirez jamais à faire commencer et terminer à fait se chevaucher. Cool. Il ya encore une faille logique, et c'est ce qui devrait certainement être un autre si. Pourquoi cela pourrait-il être? La raison en est que ce n'est pas une autre si-avez-vous vu cela, Kevin? [Kevin] Oui, parce que vous décidez de changer le point de fin. [Nate] Exactement. Nous changeons le point final, et si c'est écrit comme ça we'll-faire des espaces entre- il vérifiera ce cas. Cette affaire, si elle réussit, annulerait sortir de la fonction. Ensuite, il vérifie cette affaire suivante, et si cela réussit, il ajustera le point final, et puis il va continuer et vérifier ce cas. Mais à ce stade, nous ne voulons pas de poursuivre la vérification. Heureusement, nous n'avons pas réinitialiser le milieu ici, et nous savons que cette affaire ne réussira pas. Mais nous voulons vraiment mettre l'autre si il y en même si cela pourrait, dans ce cas puisque nous ne sommes pas régler le point milieu, cela ferait-il une différence? Non, parce que ces cas sont tous exclusifs. Encore une fois, mon mauvais. Nous n'avons pas, je crois, besoin de cette else if. Nous pouvons faire un essai et exécutez-le et voyez ce qui se passe. Bâtiment, une erreur s'est produite. C'est probablement parce que je suis parti de ces b et e en ici. Dois-je plus de ceux au sommet? Il ne ressemble pas à ça. Nous zoom arrière, construire, là, il va, maintenant si nous cherchons 15, Oui. Permettez-moi de zoom avant 15, oui. On peut l'exécuter à nouveau. Téléchargement du code source, construction, au fonctionnement. Nous pouvons chercher pour quelque chose comme 13, et nous n'obtenons rien imprimer, il n'est donc pas conclure que pour nous. C'est très bien, car ce n'est pas dans notre liste. Nous sommes maintenant hors du temps. Ça va être tout pour cette semaine. Merci de vous joindre, et vous verrez plus tard. [CS50.TV]