DAVID J. Malan: Ceci est CS50 et ceci est le début de la quatrième semaine. Et, garçon, est dans Volkswagen difficulté à cause de logiciels. Prenons un coup d'oeil. [LECTURE VIDÉO] -Cars, Les personnages les plus intelligents dans les films Fast and Furious. Cette semaine constructeur automobile allemand Volkswagen se trouvait au milieu d'un scandale de proportions potentiellement criminelles. 

-Volkswagen Se prépare à des milliards des amendes, des possibles accusations criminelles pour ses cadres, comme la société présente ses excuses pour truquer 11 millions de voitures à l'aider à battre les essais d'émissions. 

Modèles diesel sont -Certains conçu avec des logiciels sophistiqués que l'information utilisée y compris le position de la direction et véhicule accélérer pour déterminer la voiture était subir des tests d'émissions. En vertu de cette circonstance, le moteur permettrait de réduire les émissions toxiques. Mais la voiture a été truqué à la dérivation que quand il a été entraînée. Les émissions ont augmenté de 10 à 40 fois au-dessus des niveaux APE acceptables. 

[FIN LECTURE] 

DAVID J. Malan: Alors disons regarde ça et de voir exactement comment cette pourraient être mis en oeuvre et comment cela pourrait affecter autant de voitures de ce genre. Donc, dans ma main voici la presse presse qui a été publié par le EPA-- l'environnement Agence de protection qui est l'organisme de réglementation des États-Unis que gère les préoccupations environnementales, puis le réel Avis juridique qui était envoyer à Volkswagen il ya quelques jours. 

Donc, l'EPA écrit, et divulgue maintenant publiquement, un logiciel sophistiqué sur certain algorithme Véhicules Volkswagen détecte lorsque la voiture est en cours tests sur les émissions officielles et tourne émissions complètes contrôle sur seulement pendant l'essai. L'efficacité de Ces véhicules pollution dispositifs de contrôle des émissions est grandement réduit au cours de la conduite normale tout situations. Il en résulte des voitures qui répondent à la normes dans le laboratoire ou des tests la station, mais, en fonctionnement normal émettre oxides-- d'azote ou NOx-- à jusqu'à 40 fois la norme. Le logiciel produit par Volkswagen est un dispositif entre guillemets, la défaite, tel que défini par la Clean Air Act aux États-Unis. 

Ils poursuivent en disant que l'EPA et un autre organisme découvert le dispositif de la défaite logiciel après analyse indépendante par des chercheurs de l'Ouest Université de Virginie. NOx contribue à la pollution le dioxyde d'azote, l'ozone au niveau du sol, et les particules fines. L'exposition à ces a été liée polluants avec une large gamme de effets graves pour la santé, y compris l'asthme accru attaques et autres respiratoires maladies qui peuvent être assez graves d'envoyer des gens à l'hôpital. L'exposition à l'ozone et la matière particulaire a également été associée à prématuré les décès dus aux respiratoires ou des effets cardiovasculaires liées. Les enfants, les personnes âgées, les personnes maladie respiratoire préexistante sont particulièrement à risque de effets sur la santé de ces polluants. 

Qu'il suffise de dire est, il est tout à fait sérieux. Et Passons à lire juste un de plus extrait et ensuite, nous allons jeter un oeil à les implications sous-jacentes de ce dans le cadre d'une voiture. Plus précisément, Volkswagen fabriqué et installé logiciel dans le soi-disant commande électronique module-- ou de ECM-- que ces véhicules détectés lorsque le véhicule a été mis à l'essai pour conformité avec les normes d'émissions EPA. Basé sur divers intrants, y compris la position du volant, véhicule la vitesse, la durée du moteur de fonctionnement, et la pression barométrique, ces entrées précisément suivi des paramètres de la procédure d'essai fédéral utilisé pour tests d'émission selon la certification EPA fins. 

Lors de tests d'émissions de l'EPA, le logiciel de véhicules ECM le logiciel qui a produit couru les résultats des émissions conformes. En tout autre temps, la logiciel ECM du véhicule a couru une route séparée étalonnage qui réduit l'efficacité de la système global de contrôle des émissions, spécifiquement la catalytique sélective réduction du Lean NOx trap-- que nous verrons dans un instant. En conséquence, les émissions de NOx augmenté d'un facteur de 10 à 40 fois au-dessus des niveaux conformes EPA en fonction du type de cycle de conduite. 

Donc, ce que cela signifie vraiment, et la code source pour le logiciel en cours d'exécution sur les Volkswagen n'a pas encore été divulguée publiquement, est que, effectivement, ce équivalent il ya quelque part à l'intérieur du code de Volkswagen. Si vous êtes en cours de test, et si la voiture détecte certains facteurs environnementaux comme le volant la position ou le mouvement de celui-ci ou de la voiture ou manquer un certain nombre d'autres facteurs qui sont actuellement émis l'hypothèse de faire partie de cette formule, ils se tournent tout simplement sur émissions plein contrôle. En d'autres termes, ils commencent émettant moins de polluants. 

Sinon, dans toutes les autres situations quand il est pas détecté comme étant dans le laboratoire, ils le font tout simplement pas. Et si vous pouvez simplifier cela en plus pseudo béton avec quelque chose comme ça. Si les roues tournent, mais le volant est pas, suggestive que la voiture est sur certains sorte de cylindre rotatif mais dans une sorte de entrepôt testé, alors se comporter comme le APE vous aimer. Ne pas autrement. Donc, nous allons jeter un coup d'oeil à une courte vidéo qui jette un regard sur ce que les implications sont de ce fait mécaniquement. 

[LECTURE VIDÉO] 

-Last Vendredi EPA a annoncé que certains Voitures Volkswagen Audi faites entre 2009 et cette année ont été en utilisant un dispositif que l'on appelle la défaite à contourner les lois sur les émissions conçu pour garder l'air pur. Mais qu'est-ce que cela signifie exactement? 

Eh bien, les voitures modernes ont des dizaines des ordinateurs à l'intérieur. Et certains de ces ordinateurs aider à coordonner les fonctions du moteur pour optimale performances tout en veillant qu'il n'y a pas trop d'ordures sortant du tuyau d'échappement. Ils ont effectivement travaillé de cette façon depuis plusieurs décennies. Fondamentalement, chaque partie du moteur d'une voiture moderne présente un capteur ou dispositif de commande sur elle, et ces ordinateurs en train de lire dans les données des milliers de fois par seconde ajustements de courtoisie comme le rapport du combustible à l'air cela va dans les cylindres. 

Ces Volkswagen tricherie et les modèles Audi sont des diesels, et diesels ont un plus ordinateur vraiment important paramètres contrôlés, ce qui est la quantité de carburant non brûlé passe dans l'échappement. Maintenant que sonne mal. Ne sonne pas comme vous voudriez carburant imbrûlé entrer dans l'échappement. Mais dans le cas d'un diesel, vous avez quelque chose appelé un piège à NOx qui est un dispositif qui absorbe et pièges pour les oxydes d'azote qui sont des polluants qui serait sinon, passez dans l'atmosphère. Et l'effet de ce piège à NOx est renforcée avec du carburant non brûlé. Ainsi, un dispositif d'invalidation est un programme spécial l'intérieur de ces ordinateurs qui peuvent rendre ressembler à la voiture répond émission normes, même quand il ne le fait pas. Volkswagen avait un problème sur ses mains. Ses moteurs diesel ont été connus pour obtenir une grande économie de carburant, mais le piège à NOx ne fonctionne bien lorsque plus de carburant est utilisé. Donc, la voiture serait de détecter, en utilisant ce dispositif de défaite, quand il se faisait un émissions test, ce serait utiliser plus de carburant, bien faire le travail de piège à NOx, émissions serait bien. Mais alors que vous obtenez sur la route, le dispositif éteint, vous brûlez moins de carburant mais vous mettez autant que 40 fois plus de polluants dans l'atmosphère. Mais comment diable fait la voiture sait qu'il était pour vérifier la conformité des émissions? L'EPA dit qu'il était un système sophistiqué système qui vérifie les choses comme la position du volant, vitesse, combien de temps le moteur était allumé, et la même pression atmosphérique. En d'autres termes, il y avait aucune façon cela était accidentelle parce que le logiciel était conçu très soigneusement pour détecter un test d'émissions officielle. Voilà quelques-unes assez grave la tromperie et qui est pourquoi Volkswagen est en tels ennuis sérieux. En fait, leur PDG, Martin Winterkorn, juste démissionné. 

Alors qu'est-ce qui se passe ensuite? Eh bien, si vous êtes l'un des demi-million Jetta diesel, Beatles, Golfs, Passat, ou Audi A3s effectuée, les bonnes nouvelles est est que votre voiture est toujours sûr de conduire. Vous n'êtes pas obligé de le ranger jusqu'à ce que Volkswagen émet un rappel. Mais à un certain point ils sont probablement devoir de mettre à jour le logiciel à l'intérieur de votre voiture. Lorsque cela arrive, vous pourriez obtenir moins de miles par réservoir. Avocats se préparent déjà pour les procès d'action de classe afin que les propriétaires pourraient obtenir une indemnisation à un certain moment dans l'avenir. Mais cela ne va pas à arriver de si tôt. 

[FIN LECTURE] DAVID J. Malan: Donc, cela soulève effectivement une grande question d'image intéressante à la confiance. Droit? Nous avons tous des iPhones ou androïdes ou quelque chose dans nos poches plus probable ces jours-ci, ou des ordinateurs portables sur les tours qui sont logiciel fonctionnant fait par Apple et Microsoft et de grappes d'autres sociétés. Mais comment savons-nous que ce que ces produits logiciels font est en fait ce que ceux-ci entreprises disent qu'ils font? 

Par exemple, qui est à dire que chaque fois que vous faire un appel téléphonique sur votre iPhone ou téléphone Android ou analogue, que le numéro de téléphone qui est également non étant téléchargé vers le serveur un peu de compagnie à cause de quelque programme que vous avez écrit, que ce soit l'exploitation système lui-même comme iOS ou Android, ou parce que vous avez téléchargé certains app tiers qui en quelque sorte est à l'écoute à tout ce que vous tapez ou tout ce que vous êtes en train de dire. Comment savez-vous que, lorsque vous les gars exécutent Clang Ou Faire de compiler votre propre logiciel dans CS50, comment vous ne possédez que le personnel du CS50, par l'intermédiaire de la bibliothèque CS50, n'a pas été connectant tous les chaîne que vous avez jamais obtenu ou chaque pouce que vous avez jamais eu? Eh bien, vous pourriez certainement chercher au code source pour quelque chose comme la bibliothèque CS50, vous pourrait regarder le code source pour système d'exploitation Linux courir sur CS50 IDE. Mais une présentation étonnante a été donné en 1984 à la réception du prix Turing par un très célèbre informaticien connu as-- nommé Ken Thompson, qui a reçu le prix Turing qui est en quelque sorte de la science informatique de Prix ​​Nobel, si vous voulez, pour son travail sur une système d'exploitation appelé Unix, ce qui est très similaire à l'esprit de ce que nous utilisons qui est Linux. Et la question qu'il a posée dans son discours d'acceptation, essentiellement fixant le cadre pour la années et des années de discussion à propos de la confiance et de la sécurité, était présent. Dans quelle mesure doit-on la confiance d'un déclaration selon laquelle un program-- un morceau est de software-- libre de chevaux de Troie? Peut-être qu'il est plus important de faire confiance les gens qui ont écrit le logiciel. 

Et en fait, nous avons relié à l'entretien qu'il a donné en acceptant ce prix dans les années 80 sur le site de CS50 en vertu de la page Conférences pour aujourd'hui. Parce que ce que vous verrez est qu'il donne effectivement assez simple exemple de la façon même un compilateur comme Clang ou quoi compilateurs d'autres ont utilisé dans le passé, si intégré dans le compilateur nous nous utilisent est un peu si condition que dit essentiellement, si vous remarquez que ce code utilise la fonction de GetString ou getint fonction, aller de l'avant et insérez une porte arrière ou un cheval de Troie de telle sorte que ce programme a maintenant quelques zéros et ceux qui font quelque chose malveillants. Logging tout votre frappes, le téléchargement de ces données à un serveur, ou vraiment rien. 

Et ce que Ken Thompson passe à faire dans son discours est de démontrer que même si vous avez accès à la source code d'un compilateur qui malveillance pourrait faire cela, il n'a pas d'importance parce que il ya cette poule et l'oeuf la réalité des nombreux passé ans moyennant quoi compilateurs sont utilisés pour compiler eux-mêmes. En d'autres termes, le chemin du retour quand quelqu'un avait pour avoir écrit le premier compilateur. Et par la suite, en tout temps ils ont mis à jour un compilateur en modifiant son code source, l'ajout de fonctionnalités et recompilée pour des gens comme nous à utiliser, ainsi, ils utilisent l'ancienne version du compilateur de compiler la nouvelle version du compilateur. Et si vous jetez un oeil à la conférence qu'il a donné, vous verrez que parce que de circularité, vous pouvez effectivement avoir des bugs ou Les chevaux de Troie intégrés dans les logiciels nous utilisons. Et même si vous regardez le code source de ces programmes, il pourrait même ne pas être évidente parce que la supercherie est en fait dans une version plus ancienne d'un compilateur qui a depuis été injecter la menace dans notre logiciel. 

Qui est seulement de dire, nous vraiment ne peut pas et ne devrait pas faire confiance aux logiciels fonctionnant sur nos ordinateurs portables ou les téléphones ou tout nombre de places. Et en fait, plus tard dans ce semestre lorsque nous commençons à parler de la programmation web et effectivement commencer à construire applications Web nous-mêmes, nous allons parler de ces menaces et autres. Maintenant, vous pourriez avoir demandé et a remarqué qu'il y avait un tout petit Darth Vader dans les clips The Verge il montrait à propos de Volkswagen. Si vous ne l'avez jamais vu, je pensé que nous devrions alléger l'humeur, car tout cela est très déprimant et effrayant. Je vais regarder en arrière au Super Bowl 2,011 quand un commerce Et ce Volkswagen-- rend presque les sympathiques again-- diffusé pour la première fois à la télévision. Il est le deuxième clip 60 que je pense que vous apprécierez. [LECTURE VIDÉO] [MUSIQUE - Theme from "STAR WARS"] [Chien aboie] [Voiture commence] [FIN LECTURE] DAVID J. Malan: Ouais. Je vérifiais juste. Cette voiture est sur la liste des violations. Bien. Donc, nous examinons certains Pseudocode il ya un instant. Et voici une plus grande extrait de code de pseudo- que nous avons vu à quelques reprises jusqu'ici. Et nous allons utiliser ce est une occasion maintenant d'introduire une nouvelle programmation technique que nous avons fait voir algorithmique la semaine dernière, lorsque nous avons examiné le tri par fusion. Mais nous allons formaliser et de voir comment nous pourrions utiliser dans le code actuel, et ensuite, nous allons utiliser cette technique sur la route plus susceptibles de résoudre certains autres problèmes. 

Donc, ce fut l'un des premiers programmes que nous jamais écrit, mais dans le code de pseudo-code. Et ce que ce programme permis de faire cours était de trouver Mike Smith dans un livre de téléphone. Et remarquez en particulier les huit lignes et 11 qui avait cette déclaration Atteindre. Et en fait, certains langues, C parmi eux, faire réellement avoir un déclaration qui est littéralement aller à qui vous permet de sauter à une ligne spécifique. Il est généralement mal vu parce il peut être très facilement abusé et vous pouvez commencer à sauter votre programme partout par opposition à l'aide du genre de logique et le flux de contrôle que nous avons utilisé jusqu'à présent avec juste boucles et conditions et analogues. 

Mais nous pouvons simplifier cet algorithme dans le code de pseudo comme suit. Au lieu de cela itératif ou l'approche en boucle où nous continuons à revenir en arrière et en arrière et retour à la ligne de trois, pourquoi ne pas juste genre de Pount et plus disent globalement en ligne sept et 10, il suffit de remplacer ces deux avec des paires de lignes, d'autre si Smith est antérieure dans le livre nous allons rechercher Mike dans le la moitié gauche de l'ouvrage. Sinon, si Smith est plus tard dans la livre, chercher Mike dans la bonne la moitié du livre. Et remarquez déjà la circularité. Droit? Je cherche à Mike le livre de téléphone, puis Je finalement atteint peut-être la ligne de sept ou peut-être la ligne 10 et mon instruction pour moi est la recherche pour Mike dans la moitié de l'annuaire téléphonique. Eh bien, comment puis-je rechercher pour Mike? Je suis dans le milieu de chercher Mike, pourquoi vous me sorte de l'envoi d'un cercle? Mais cela est OK parce que ce qui est en passant à la taille du problème, comme écrit dans la ligne 7 et 10? Nous ne sommes pas simplement en disant recherche pour Mike, recherche pour Mike. Nous spécifiquement dire quoi? Rechercher pour lui dans la moitié gauche de la moitié droite qui est effectivement moitié de la taille du problème. Donc, il est OK que nous sommes en quelque sorte engager dans cette circularité, cet argument circulaire, car au moins nous sommes qui rend le problème plus en plus petits. Et finalement, nous allons atteindre que l'affaire dite de base où nous avons juste une page gauche- que notre volontaire de la semaine dernière did-- nous avions une page à gauche et puis nous ne faisons pas continuer à chercher pour Mike Smith parce qu'il est soit sur cette page ou il est pas. 

Alors, comment pouvons-nous mettre en œuvre cette idée, cette sorte de circularité dans le code réel? Eh bien, nous pouvons tirer parti d'une technique qui est généralement connu comme la récursivité. Et nous avons vu cela dans le pseudo pour le tri par fusion de la semaine dernière. Rappelons que ce fut le pseudo pour le tri par fusion. Il est sans doute encore plus simple que bulle de sélection, ou le tri par insertion seulement en termes de la simplicité avec lequel vous pouvez exprimer. 

Mais cela est parce que nous sommes en quelque sorte de révolution disant, chercher quelque chose par la recherche de nouveau. Mais nous sommes à la recherche, soit sur la moitié gauche ou la partie droite et puis finalement nous sommes la fusion dans ce cas. Mais ici aussi, avec ces deux lignes de tri, avons-nous eu à nouveau cette idée de la récursivité. Et concrètement ce que cela signifie, dans le contexte d'un algorithme, qui est un algorithme récursif est si elle utilise ou appelle lui-même. 

Ou en termes de C, une fonction est recursive-- une fonction appelée foo est récursive si foo, quelque part dans son code source, appelle la fonction foo lui-même. Et cela est mauvais si tout foo ne fait jamais est lui-même appeler encore et encore. Il est OK si foo cesse finalement, comme le fait tri par fusion, en disant, attendez une minute, si ce problème est super faible, par exemple, ou je l'ai trouvé que je suis cherchez, il suffit de retourner. Ne pas récursive, ne pas cycliquement appeler moi-même à nouveau. 

Et nous allons donc jeter un oeil à comment cela pourrait effectivement travailler. Donc, je vais aller de l'avant et ouvert jusqu'à deux exemples de code source ici. Dont l'un est appelé sigma 0. Et ce ne sont pas du tout récursif, mais prenons un oeil à ce que ce programme fait. Je l'ai dépouillé toutes commentaires, mais tout du code source sur CS50 de site des commentaires si vous envie de lire à travers elle à nouveau plus tard. Et nous allons faire un couple de la santé mentale vérifie ici. 

Alors au sommet de ce code, nous avons inclure CS50.h. Qu'est-ce que cela fait? Pourquoi est-il ici? En termes simples raisonnable. Qu'est ce que ça fait? Ouais. 

Auditoire: Alors que la fonction getint fonctionne. 

DAVID J. Malan: Alors que la fonction getint fonctionne. En raison de cet intérieur fichier, CS50.h, qui nous verrons avant longtemps dans termes de son code source, a un tas de fonctions declared-- getint, GetString, et un tas de others-- et sauf nous avons en fait que Inclure ligne, le compilateur Clang est pas va savoir qu'il existe. Et va de même pour la ligne où deux int est définie printf, qui est une fonction nous gardons à l'aide un peu. Maintenant, la quatrième ligne semble un peu excentrique parce qu'elle est juste une seule ligne. Il a un point-virgule, pas bouclés accolades, pas de code à l'intérieur de celui-ci. Mais qu'est-ce que nous appelons cette chose dans les dernières semaines? Ouais. Ainsi, un prototype. Et pourquoi avons-nous un prototype qui semble être un peu redondant généralement parce que nous avons l'habitude voir la fonction nouveau plus tard dans le fichier, à droite? Alors pourquoi ne vous êtes juste have-- gratter la tête, mais je vais le prendre. Ouais. 

AUDIENCE: [inaudible] fonction après la principale. DAVID J. Malan: Exactement. Alors que le compilateur vous connaît définir à terme ou mettre en œuvre après que la fonction principale, sans doute. Ainsi, et plus Clang compilateurs sont un peu idiot et ils ne sauront ce que vous leur dites. Et si vous souhaitez utiliser une fonction appelée sigma, mieux vous enseignez le compilateur qu'elle existe à l'avance. 

Maintenant, elle-même principale, même mais il ya un tas de lignes, est assez familier espérons maintenant. Il a une boucle Do While dont le but dans la vie ici est apparemment d'obtenir un nombre entier positif de l'utilisateur. Et juste garder le harceler ou elle jusqu'à ce qu'ils coopèrent. Puis, en ligne 16, je dois un appel intéressant. IntAnswer. Qui, sur la main gauche côté me donne un Int qui peut store-- appelé réponse-- qui va stocker, apparemment, la valeur de retour de sigma. Donc sigma est juste une nom arbitraire mais significative que je vous ai donné à une fonction dont le but dans la vie est de prendre un argument-- nous l'appellerons N dans ce case-- et juste de prendre la somme de ce nombre En outre, chaque nombre positif qui est plus petit que lui. 

Donc, si je passe dans le numéro 2 de sigma, je tiens à ajouter 2 plus 1 ainsi 0-- pas 0-- sorte que me donne 3. Si je passe à 3 sigma, je veux avoir 3 + 2 + 1, ce qui me donne 6. Et ainsi de suite. Donc, il ajoute juste tout le nombres inférieurs ou égaux à elle. 

Maintenant, ici-bas, je vais juste d'imprimer la réponse. Donc, comme un test de cohérence rapide, nous allons faire sigma 0-- dot slash sigma 0-- et laissez-moi tape 2. Et je reçois en effet 3. Permettez-moi de tape 3. Je reçois en effet 6. Et si quelqu'un peut faire le calcul rapidement, si je fais 50 que vais-je obtenir? 

AUDIENCE: [inaudible]. DAVID J. Malan: Eh bien, non. Mais 1275 qui est assez proche. Donc, cela est le résultat de faire 50 plus de 49 plus 48 plus 47, plus 46 tout le chemin vers le bas à 1. Donc, voilà tout sigma fait. Mais nous allons voir comment nous avons mis en œuvre maintenant. Donc ici est la fonction elle-même. Et cela ne semble pas avoir rien à voir avec la récursivité encore. En fait, nous utilisons un vieille technique de l'école. Je l'initialisation d'une somme variable appelée à zéro, alors je dois un foreloop ici, et je déclarer un Int appelé I, qui définit elle égale à 1-- si je pouvais le mettre égal à zéro, mais depuis que je fais plus, qui se soucie si elle est zéro ou un. Il va avoir aucun effet. 

Donc, je suis itération tant que I est inférieur ou égal à m, ce qui est l'argument qui a été adoptée en. Et puis je continue incrémentation I. Et aperçu de la boucle tout ce que je fais est de faire la somme en plus égaux I. Et voilà délibérée. Je ne veux pas faire, dans ce cas, comme somme plus plus. Je veux effectivement ajouter la valeur de courant de I qui maintient grossit et plus grand pour le décompte en cours d'exécution. 

Et puis je reviens somme. Et si la réponse obtient la somme de la valeur. Et puis je l'imprimer. Donc, il ya une opportunité ici, cependant, de sorte de simplifier ce code conceptuellement et le genre de coup-ci est l'esprit en termes de simplicité, même si elle prend un certain temps pour trier de comprendre pourquoi cette est puissant dans ces petits exemples. Voici donc le sigma One-- deuxième version de ce code. Tout là-haut est identique si que même histoire applique comme avant. Mais maintenant, regardons à la mise en oeuvre de sigma qui Je l'ai réduit à juste ces lines-- quatre lignes de code, vraiment, plus quelques accolades et espace blanc. 

Mais qu'est-ce que je fais? Si m est inférieur ou égal à zéro, je dois sorte de gérer ce cas super simple. Et si vous me remettez zéro ou rien négatif qui est juste bizarre, Je vais juste arbitrairement mais toujours revenir à zéro. Je ne veux pas que cette chose entrer dans certains infinie bizarre boucle en raison d'une valeur négative. Donc, je dis juste que si vous me donnez zéro ou moins, je suis de retour à zéro. 

Mais ce qui est bon parce que ce cette page unique de l'annuaire téléphonique ce qui reste. Je mordre un problème très spécifique et de ne pas appeler quelque chose de manière récursive. Mais dans la ligne 31, ce qui Je ne semblent faire? Les parenthèses sont juste garder les choses, je l'espère, un peu plus clair. Mais tout ce que je fais est que je suis M-- retour quel que soit vous remettez moi-- plus le valeur de M-- désolé, plus la valeur de sigma de M moins 1. Qu'est-ce que cela signifie? Si vous me donnez le numéro 3 comme entrée, la réponse que je veux obtenir en fin de compte est 6 parce 3 + 2 + 1 me donne 6. Mais comment puis-je pense comment ce code est exécuté? La première fois que je l'appelle sigma et je passe à la valeur 3, Cela revient à dire sur un morceau de papier, voici la valeur 3 et je l'ai été adoptée ce que sigma. 3 est évidemment pas moins de 0 pour SI la condition ne concerne pas. L'autre ne le fait. Alors, que dois-je faire? Je veux retourner m, qui est 3, plus sigma de M moins 1. Alors permettez-moi de garder trace de cela. Je vais mettre ce morceau de papier vers le bas. Et quelle valeur, pour être clair, vais-je passer en sigma à ce point dans l'histoire? Quel numéro? 2, non? 3 moins 1 est 2. Je viens donc besoin d'un peu bout de papier ici. Alors maintenant, est de se sigma de nouveau appelé. Et je l'ai délibérément mis cette baisse parce qu'il est un peu comme une pause cette version de l'histoire parce que maintenant je suis concentré sur le signal de M moins 1. Alors m était de 3, m moins 1 est 2. Voici donc 2 que je l'ai été adoptée. La figure 2 est évidemment égale ou supérieure à 0 pour ce cas ne se applique pas. Sinon je reviens m, ce qui est chose, plus sigma de quelle valeur? Donc, si sigma de 1-- parce m est en ce moment 2 SO 2 moins 1 est 1. Alors maintenant, je viens de la valeur 1. Je passe tout simplement le nombre Une fonction de la sigma-- ou moi-même afin ici-- 1 est évidemment pas inférieur à zéro, ne se applique toujours pas. 

Sinon retourner 1 plus sigma de quoi? 0. Alors permettez-moi de me souviens que. Je vais revenir plus tard. Maintenant, je vais aller de l'avant et jot le numéro 0 parce que ce mon argument ou paramètre. Je passai le nombre 0 et enfin ce processus de simplement me répéter ad nauseam ne cesse parce que ce Je ne fais immédiatement une fois que je vois cela 0? Je reviens à zéro. Alors maintenant, vous avez pour rembobiner l'histoire. 

Si je vais maintenant en arrière dans le temps, ce qui était la chose la plus récente Je l'ai fait si vous étiez littéralement rembobiner une vidéo? Je vais prendre le plus récent 1 et qui me donne plus de 1 0 est 1. Si je continue à le rembobinage de la histoire, cela va me donner 2 plus cette valeur en cours d'exécution, ce qui est 1. Voilà donc 3. Et puis je vais continuer à le rembobinage. Quand je mets le numéro 3-- donc 3 + 3 me donne 6. 

Et maintenant, si vous avez rembobiné la vidéo jusqu'à ce point, ce fut le très la première question que je posais. Lorsqu'il est passé de 3, ce qui est de 3 sigma? Il est en effet 6, la somme de tous ces morceaux de papier. Donc, si cela prend un peu de temps pour envelopper votre esprit autour, ça va. Mais considérez qu'il était un little-- il était très délibérée que je empilés ces nombres les uns sur les autres. Il est un peu comme avoir un memory-- un record dans le temps, comme un laveur dans une vidéo, que je peux bien rembobiner. Et nous allons revenir à cette métaphore dans un tout petit peu. 

Mais d'abord, il se trouve qu'il ya beaucoup des geeks et des drôles de gens, Je suppose que, chez Google. Serait quelqu'un qui est très bon à l'esprit googler à venir pour un instant et aidez-moi à chercher quelque chose? Très très discret,. Quelqu'un qui n'a jamais venir avant, peut-être. D'ACCORD. Ouais? Allons. Venez faire un tour. Comment t'appelles tu? 

SAM: Sam. 

DAVID J. Malan: Sam, allez vers le bas. Ceci est la même. Enchanté de faire votre connaissance. Hey. Venez ici. Donc, tout ce que je veux que vous fassiez, si vous pourriez, Sam, voici Google. Pouvez-vous chercher pour la récursivité terme? Ne gâchez pas. 

Et let's-- maintenant oui. OK Cliquez sur ce. Mieux cliquez sur cela. Ahh, l'obtenir. Non? D'ACCORD. Donc, nous allons faire une ou deux autres. Pas tellement connexes académiquement ici, mais avez-vous déjà cherché Google pour anagramme? 

SAM: Non 

DAVID J. Malan: OK. Rechercher anagramme la place de la récursion. Que diriez-vous de travers. Vous avez déjà effectué une recherche pour guingois? Maintenant, celui-ci est un peu difficile à voir, mais je l'espère everything's-- OK. Il est juste vous et moi profiter de cette. D'ACCORD. 

Donc finalement, ce one's-- il est un peu de travers. Maintenant, faire un tonneau. Formidable. Bien. Grand merci à Sam. Et voilà. Merci. 

Alors qu'est-ce qui se passe dans tous les de ces exemples stupides? Alors, vraiment, sous le capot de Les millions de Google de lignes de code est apparemment un peu idiot SI des conditions qui sont essentiellement vérifier si l'utilisateur a tapé dans cette phrase, faire quelque chose qui a probablement pris une quantité non négligeable de temps à mettre en oeuvre simplement être amusant de cette façon. Mais tout cela est qu'il revient jusqu'à sous le capot. Mais, bien sûr, la récursivité est plus du geekier exemple parmi ces trucs spéciaux. Et il ya sûrement d'autres là-bas ainsi que nous avons peut-être même pas juste encore découvert. 

Alors jetez un oeil, ou envisager maintenant le programme suivant, et certainement saisir toute de ces derniers sur votre chemin. Je vais aller de l'avant et ouvrir un programme qui est va essayer de permuter deux valeurs. Mais avant que nous y allons, nous allons le faire. Pourrions-nous en obtenir un plus bénévole, je pense? Aimeriez-vous faire du bénévolat? Non? Allez vers le haut. Allez vers le haut. Bien. Donc, votre nom est quoi? 

LAUREN: Lauren. 

DAVID J. Malan: Lauren. Allez jusqu'à, Lauren. Alors Lauren est en cours contesté ici comme suit. Enchanté de faire votre connaissance. Donc, Lauren a ici devant de ses deux tasses vides. Et nous avons un peu d'orange jus de fruits et du lait et nous allons aller de l'avant et faire ce qui suit. Nous allons juste pour remplir cette. A quelques onces de lait ici et nous allons remplir un peu de jus d'orange ici. 

Et en face de tous ces membres de l'auditoire, permuter les deux valeurs de ces tasses. Mettez le jus d'orange dans la tasse de lait et du lait dans la tasse de jus d'orange. Comment feriez-vous si vous étiez à la maison et a eu accès à d'autres fournitures? LAUREN: mettre dans une autre tasse. DAVID J. Malan: OK. Donc, nous allons jeter un temporaire variables, si l'on veut. Et aller de l'avant maintenant et mettre en œuvre cette même procédure de permutation. Si bon. Nous avons mis dans le JO temporaire variable lait dans la variable JO, et maintenant la variable temporaire dans la variable de lait. D'ACCORD. Donc, très bien fait jusqu'ici. Ainsi, il se maintenir que out-- pensé pour un instant. Ici, juste connaisseur jusqu'à un peu, ce serait le code C correspondant que nous venons de mise en œuvre. Nous avions deux entrées, a et b, deux que nous dirons juste pour la simplicité sont INT. Et remarquez ici, si je veux échanger les valeurs de deux variables a et b, nous avons en effet besoin d'un intermédiaire, un variable temporaire, une tasse temporaire, dans lequel l'écoulement l'une des valeurs de sorte que nous avons un espace réservé pour elle. Mais alors le code est exactement comme Lauren ici mis en œuvre. 

Maintenant, juste pour obtenir un peu fou, se révèle que vous pouvez le faire sans une variable temporaire. Pour ce faire correctement, cependant, nous allons d'avoir à tricher avec une certaine chimie. Nous avons des tasses supplémentaires ici. Donc, la chose la plus proche qui ressemble comme le lait et l'eau perhaps-- ou de lait et OJ-- est que nous avons une certaine l'eau, donc nous allons remplir celui-ci jusqu'à avec quelques onces d'eau claire. Voilà sans doute trop. Ouais. Voilà certainement trop. Attendez une seconde. 

Et maintenant, nous avons du pétrole, qui, si je me souviens à partir du milieu classe de chimie de l'école, il faut espérer qu'il ne se mélange pas à l'eau. Mais ce genre de genre de ressemble à du lait et JO. Alors maintenant, sans utiliser une variable temporaire, vous pouvez échanger ces deux valeurs? Donc, les huiles qui se passe dans la tasse d'eau, l'eau passe dans la tasse d'huile. LAUREN: Pas d'autres tasses? DAVID J. Malan: Pas d'autres tasses. Et je ne l'ai pas fait testé ce avant cette année donc je ne sais pas si cela va effectivement travailler chimiquement. Cela n'a pas été censé se produire. Est-ce que ça marche? Bien. Donc, la séparation? Bien. Maintenant, nous sommes arrivés à obtenir le l'eau dans l'autre tasse. Smarter concentrateurs de chimie pourrait probablement le faire mieux que moi. 

LAUREN: L'eau est sur le fond. 

J. DAVID MALAN: Le water-- qui était ce qui est la clé de la dernière fois que nous avons fait cela. Vous devez le faire dans le bon ordre. Ouais. C'est bon. Alors maintenant, nous avons deux tasses d'huile. D'ACCORD. C'est bon. Mais si cela a fonctionné chimiquement que I-- 

LAUREN: Ceci est l'eau. 

DAVID J. Malan: Voilà surtout de l'eau. Bien. Mais cela reste la même tasse comme avant. Alors versez it-- l'essayer là-bas. D'ACCORD. Ceci est une bonne utilisation du temps de classe aujourd'hui. D'ACCORD. Donc maintenant nous-- agréable. Sorte de. Bien. Donc très bon. Merci à Lauren. Très bien fait. 

Il suffit donc de faire sauter votre esprit, et cela est peut-être quelque chose de jouer avec si vous le souhaitez dans CS50 ID, vous pouvez, en fait, permuter deux variables sans l'aide d'un nombre entier temporaire. Et cela est le code C correspondant. Et si vous vous souvenez de la dernière Mercredi, nous avons introduit, bien que brièvement, certains nouveaux opérateurs en C et ne quiconque rappeler ce que le petit peu de carotte symbole est, ce petit triangulaire le symbole de flèche représente? Qu'est-ce que l'opérateur bit à bit? 

AUDIENCE: EXOR. 

DAVID J. Malan: EXOR. Ou exclusif. Donc, si vous voulez, juste pour le plaisir au la maison, pour donner a et b deux arbitraire des valeurs comme tout eight-- et je choisiraient une valeur de huit bits. Si vous faites cela avec 32 bits, vous aurez très rapidement vous ennuyer. Mais juste donner un huit bits valeur qui est quelconque, un ou deux, et de donner b une valeur similaire. Ensuite, en utilisant la définition du XOR de mercredi dernier, appliquer ce bit par bit, chacun des ces huit bits dans chacun de a et b, et ensuite faire exactement par ce code. Et il est pas faux ce que vous voyez ici à l'écran. Il revient en effet vers le bas à trois opérations XOR et comme par magie, et un b échangeront positions sans perte d'information. 

Donc, l'huile et de l'eau est l'affaire plus proche incarnation réelle du monde Je pouvais penser à imiter cela. Mais il est certainement plus facile de utiliser une variable temporaire, comme dans ce cas ici. Et cela aussi est une opportunité dire, aussi, ce genre de micro optimisation, comme un chercheur en informatique dirait, tout genre de plaisir pour se vanter de la façon dont vous l'avez fait sans comme par exemple changer avec une variable supplémentaire, il est pas tout à fait convaincante. Parce que pour sauver 32 bits, que dans le cas d'un int réelle, est pas tout à fait convaincante sur un système dans lequel vous utilisez peut-être des dizaines de mégaoctets ou encore plus cette mémoire ces jours. Et en fait, quand nous obtenons à un ensemble de problèmes plus tard et vous implémentez sort checker et vous être mis au défi de le faire avec ce que peu de RAM et aussi peu temps que possible sur la vous computer-- encore avoir une semaine pour mettre en œuvre it-- vous have-- vous serez contesté pour minimiser ces ressources. Et cela est vraiment la seule occasionner ce semestre où vous serez encouragé à se raser éteint même le meilleur rendement coûte autrement. 

Alors comment pouvons-nous what-- Voyons cela en code réel? Permettez-moi maintenant aller de l'avant et d'ouvrir un exemple que l'on appelle délibérément Pas de Swap, car il ne le fait pas en fait permuter les variables que vous pourriez réellement attendre. Donc, nous allons jeter un coup d'oeil. Voici un programme qui n'a pas de CS50 bibliothèque en cours, I / O juste standard. Maintenant, nous avons un prototype pour le swap en haut sommet qui vient signifie qu'il est arrivé à définir ultérieurement. Et voici principale. 

Je affecté arbitrairement x et y, respectivement, l'une et deux valeurs simplement parce qu'ils sont petits et facile à penser. Et puis je dois juste un tas de printfs où je dois un chèque de santé mentale. x est égal à 1 et y est égal à 2 est probablement ce que ces printfs diront. Donc, pas de magie à ce jour. 

Ensuite, je vais prétendre à imprimer def, échangeant Dot Dot Dot. Je vais appeler le swap fonction, en passant en x et y. Et supposons pour l'instant que swap est mis en œuvre exactement comme il ya un moment avec une variable temporaire. Et donc je prétends hardiment, échangé. x est maintenant présent et y est maintenant. Mais le dossier, bien sûr, est appelé Non Swap. Donc, nous allons réellement voir ce qui se passe. Si je compile pas de swap puis faire ./noswap, x vaut 1, y vaut 2. Échangeant échangé. x vaut 1, y vaut 2. Donc, il semble effectivement être viciée même si swap-- nous allons défiler maintenant-- est mis en œuvre par l'exactement Je Code proposé il ya un moment. Donc, on ne va pas à obtenir la fantaisie avec les trucs de XOR pour le moment. Cela, aussi, devrait fonctionner comme avec le lait et JO, mais il ne semble pas fonctionner. 

Donc, nous allons le faire à nouveau. Peut-être que je viens de ne fonctionnait pas comme il faut. Donc, nous allons courir à nouveau pas de swap. Peut-être I-- pas. Donc, il est tout simplement pas de travail. Alors, faisons un petit test de cohérence. Permettez-moi aller de l'avant ici au Swap et il suffit d'ajouter, attendez une minute, un est% i / n et nous allons plug-in de la valeur de a. Parce que je veux vraiment pour voir ce qui se passe. Et en effet, cela est une technique de débogage que vous utilisez peut-être en les heures de bureau ou à la maison, déjà semblable à la première moitié de Dan La vidéo de Armendariz dans PSET3 dans laquelle nous avons introduit l'impression que def une technique recommandée, au moins pour les cas simples. Laissez-moi aller de l'avant et lance make pas de swap nouveau, ./noswap. 

Intéressant. Donc remarquer ce qui semble être vrai. X est 1, y est égal à 2, mais a vaut 2 lorsque b est égal à 1. Donc, ces deux parvint à se échangé mais x et y ne se font pas échangés. Donc, pour être clair, ce qui se passe est, ici je dois x et y et ceux qui sont des variables locales dans le portée du principal, je suis de passage en x et y échanger. Maintenant, swap, comme une fonction distincte, est libre d'appeler ses arguments ou ses paramètres tout ce qu'il veut. Foo ou bar ou X ou Y ou a ou b. Juste pour faire comprendre qu'ils sont pas identique à x et y en soi, Je l'ai dit a et b. Mais nous pourrions les appeler comme on veut. 

Et il ressemble swap est passé x-- Alias ​​a-- et il est étant passé y-- Alias ​​b. D'une certaine manière ces trois lignes sont échangeant ces valeurs exactement comme Lauren a fait avec le lait et JO. Mais quand nous imprimons sur les valeurs, a et b sont en effet échanger mais x et y avoir aucun changement pour eux. Rappelons que x et y sont ici. 

Donc, nous pouvons voir ce via une autre technique ainsi. Et cela aussi est une technique intégré dans le problème ensemble de trois. Allons de l'avant et de le faire dans CS50 ID si vous avez pas déjà. Sur le nous de droite avoir cette onglet débogueur. Et si vous ouvrez cette place, il ya quelques informations arcanes qui est jeté à vous d'abord. Mais nous allons taquiner cette part très vite. 

Donc un, vous voyez les variables locales. Avère que construire en CS50 IDE, et beaucoup d'environnements de programmation plus généralement, est un débogueur. Un outil qui vous permet de voir visuellement ce qui se passe à l'intérieur de votre programme sans avoir à recourir à l'ajout printfs et compilation et l'exécution et en ajoutant de printf et la compilation et la course, qui a déjà, dans les heures de bureau ou à la maison, est probablement obtenir assez fastidieux. 

Donc, ici, dans un instant, nous sommes va voir en temps réel les valeurs de nos variables locales. Nous allons aussi être en mesure de mettre en ce qu'on appelle des points d'arrêt qui existe des possibilités dans mon programme pour mettre en pause exécution à une ligne de code spécifique que je suis curieux de savoir. Droit? Ces programmes sont exécutés en une fraction de seconde. Il est plutôt agréable pour nous les humains plus lents pour être en mesure de faire une pause, prendre un moment, voir ce qui se passe autour de une certaine ligne de code sans labour du programme à travers elle et de finition entièrement. Ainsi, un des points d'arrêt va nous permettre de casser et arrêter à un certain point. 

Pile d'appel est une façon élégante de disent quelles sont les fonctions actuellement être appelé pour le moment. Principal est toujours appelé en premier. Mais si principal appelle un fonction appelée Swap, nous allons en fait de voir ce tour de fonctions qui ont été appelé dans l'ordre chronologique inverse. Voyons cela. 

Je vais effectuer un zoom arrière. Je vais revenir à mon code. Et juste parce que je veux à être pédant ici, Je vais aller de l'avant et cliquez sur juste à gauche de la ligne de cinq. Et cela crée un point rouge. Et remarquez sur le côté droit que le débogueur sait, hey, Je viens de dire à un point d'arrêt noswap.c ligne de cinq, spécifiquement à cette ligne de code. Ainsi, le débogueur sait que je ont demandé que la prochaine fois Je lance mon programme, il pause il exécution plutôt que de simplement courir le tout super rapide. 

Alors maintenant, je vais cliquez sur le débogage bouton en haut de l'IDE et que va faire ce qui suit. Il va d'abord ouvrir un peu second terminal regardant effrayant window-- débogage à distance à partir de accueillir tel ou such-- et nous allons revenir à ce que tout ce qui signifie avant longtemps. Mais ce qui est important pour l'instant est que ce point rouge a été frappé, le débogueur a délibérément pause execution-- pas sur cette ligne en soi, mais sur la première ligne de code réelle dans cette fonction. Et voilà pourquoi la ligne est de sept maintenant surlignés en jaune. 

Et maintenant, nous allons jeter un coup d'oeil du côté de la main droite. Il ressemble, par défaut, bien assez, x a quelle valeur? 0. Et Y a quelle valeur? Zero. Et cela est à prévoir dans le sens que x et Y- que line-- jaune a pas encore exécuté. Donc x ne devraient pas avoir la valeur 1. Il pourrait avoir une autre valeur, une valeur dite ordures. Et nous avons eu de la chance en ce qu'il est zéro à ce stade, essentiellement. 

Alors maintenant, il n'y a que quelques-uns boutons que nous avons besoin de prendre soin quand le débogage de cette façon. Remarquez ici, nous avons un bouton Lecture. Et si nous jouons ou frapper curriculum vitae, qui est juste aller à courir à travers le reste du programme ou jusqu'à ce qu'il frappe un autre point d'arrêt. Mais je ne l'ai pas mis tout autre les points d'arrêt, il est donc juste va courir jusqu'à la fin. Ce genre de défaites les but de fouiner. 

Ainsi, au lieu, je me soucie ces icônes à droite. Et si je survole eux, comme vous devriez le faire aussi, vous verrez petites infobulles tips--. Celui-ci est enjamber. Maintenant, cela ne signifie pas sauter la ligne de code suivante. Cela signifie tout simplement l'exécuter et passer à la suivante, passer à la suivante, passer à la suivante. En d'autres termes, par l'intermédiaire ce bouton, puis-je marcher grâce à mon code d'une étape à la fois. Ligne par ligne, littéralement. Or, à la droite de qui, il ya une autre que nous verrons dans un instant. Ceci est la soi-disant Step Into icône qui est va me permettre plongée dans une autre fonction. Mais voyons cela dans un instant. Donc, je vais cliquez enjamber. Et maintenant remarquer, comme je clique ce bouton en haut à droite, garder vos yeux à peu près sous Local Variables et voir ce qui se passe à x. x 1 est maintenant parce que le ligne jaune a maintenant exécuté et nous sommes passés à la ligne 8. Et dans un moment y devrait, espérons devenir 2. 

Maintenant, rien de ce qui intéressant qui se passe pour un peu. Tout cela est est printf. Et remarquez, dans mon terminal secondaire fenêtre, je vois la sortie de l'impression def. Et maintenant, je dois faire un décision que le programmeur. Je peux franchir cette ligne de code, mais pas l'exécuter obtenir curieux de savoir ce qu'il ya dedans. Ou je peux réellement entrer dedans et aller à l'intérieur de lui-même Swap. Alors, faisons ce dernier. 

Permettez-moi aller de l'avant et cliquez sur Au cours mais pas l'étape Step Into. Remarquez, tout d'un coup la fenêtre change pour mettre en évidence le premier ligne de code dans Swap. Voilà la ligne 21. Et maintenant, ce qui est une sorte de génial est que, si vous regardez par ici, comme prévu, une virgule b vaut 1 et 2, respectivement. Pourquoi est-Temp 32767? Rappelant que temporaire, tout comme la tasse vide il ya un instant, est déclarée ici sur la ligne 21. Pourquoi 32,000- Je veux dire, pourquoi est- juste une valeur bizarre? Ouais? 

PUBLIC: Il est pas initialisé. 

DAVID J. Malan: Il est pas été initialisé. Donc, notre ordinateur toujours dispose d'une mémoire physique. Il a toujours RAM physique. Et il ya toujours de zéro et l'autre est là, non? Parce que nous sommes en utilisant notre ordinateur toute la journée, vous utilisez le CS50 IDE ou les serveurs toute la journée. Alors que la RAM soit a des zéros ou quelqu'un de certains ou de zéros et de uns. Peu importe si oui ou pas vous les utilisez. Vous ne pouvez pas tout simplement avoir vierge espaces où vous veulent bits. Ils sont soit des zéros et des uns. 

Donc, il se trouve que temporaire, car nous avons pas encore initialisé il, nous avons ces 32 bits mais ils ont pas initialisée à des valeurs connues. Donc, ce qu'ils étaient les plus récemment utilisé pour-- ces 32 bits-- nous sommes juste de voir les artefacts de certains l'utilisation antérieure de ceux notamment 32 morceaux. Dès que je clique Step Over si, ouf, la température va obtenir la valeur 1. Et si je le fais encore, un est va être donnée la valeur 2 puis b va être étant donné la valeur 1. 

Et donc ce qui est agréable maintenant à ce point dans l'histoire est que le débogueur est me montrant, super lentement à mon propre rythme, ce qui l'état de Swap est. Mais notez en haut ici, un avis que la pile d'appel effectivement comporte deux couches à elle. Maintenant, celui qui est mis en évidence comme Swap, si je clique sur la place principale, remarquez comment les variables locales changent parce que le développeur peut juste sauter autour et aller dans une portée différente. Ainsi, même si nous faisons tout cela travailler et échanger correctement a et b, si je reviens et-vient entre Swap où a est 2 et b est 1 et Main, a été affectée principal du tout? Non. Alors, quel est l'emporter ici? Eh bien, il se trouve que tout moment vous appelez une fonction comme Swap, et vous le transmettre arguments, ce qui vous êtes de passage à la fonction de swap dans ce cas est une copie de ces arguments. Donc, si x et y sont chacun respectivement 32 bits, ce qui est d'obtenir Swap est deux nouveaux locale variables, ou des arguments, appelé et b-- mais ceux qui sont arbitraires names-- mais le modèle de zéros et ceux à l'intérieur de a et b sont la queue pour être identique à X et Y, mais ils ne sont pas la même chose que x et y. 

Il est comme si principale a sur son morceau de papier le numéro 1 et 2 pour x et y, et puis quand il tend que morceau de papier pour swap, Swap obtient très rapidement sa propre plume, écrit vers le bas 1 et 2 sur sa propre feuille de papier, mains en arrière xy original principal et fait ensuite son propre chose avec a et b. Et cela est maintenant super important parce cela a des implications non triviaux pour réellement écrire du code correcte car il semble que nous ne pouvons pas échanger deux variables. 

Je l'ai écrit une fonction de swap correcte. Nous avons mis en place avec comme Lauren une fonction de permutation correcte dans la réalité, mais apparemment rien de cela questions si vous ne pouvez pas réellement échanger de façon permanente deux valeurs. Donc, nous avons besoin d'une autre manière pour obtenir réellement à ce, et nous devons être en mesure de effectivement résoudre ce problème. Et il se out-- et nous viendrons Retour à cette image particulière avant long-- ce qui est une façon vous pourriez en tirer la mémoire de votre ordinateur. Il est juste un rectangle. Vous pouvez dessiner tout certain nombre de façons, mais il est pratique pour dessiner comme un rectangle pour la raison suivante. 

Nous allons commencer aujourd'hui et au-delà parler de la pile dite. Et la pile est juste un morceau de RAM-- un morceau de memory-- que les fonctions ont accès quand ils sont appelés. Et il se trouve que à le fond de cette pile est où toutes les variables locales de principales org et C et V org et tout ça vont aller par défaut. Et si principal appelle une autre fonction comme Swap, ainsi, Swap va obtenir un autre couche de mémoire jusqu'à dessus. 

Et juste pour vous donner un sommaire rapide image de cela, si je dépasse ici-- et permettez-moi de miroir Cette sur le frais généraux comme well-- ce que je dois vraiment, si nous nous soucions seulement de la bas de cette image pour le moment, est que quand je lance un programme et Main est appelée, Main est donnée à un morceau de RAM dans mon ordinateur qui est au bas de cette soi-disant pile. Et je vais dessiner délibérément comme un carré. Donc, il est comme 32 bits ou quatre octets. Et si cette fonction principale a une variable appelée x avec une valeur de 1 et il a une variable appelée y à la valeur de 2, qui est comme la prise de ce ruban de mémoire Main a été donnée par l'exploitation système et en le divisant de façon à ce que la première variable locale va ici, le second va ici, et voilà. 

Lorsque principal appelle, permutez obtient sa propre tranche de mémoire que nous allons dessiner comme ça du système d'exploitation, et il va avoir son variables locales propres en fonction sur notre mise en œuvre plus tôt avec des variables locales d'un et b qu'initialement obtenir les valeurs 1 et 2. Mais alors, dès que le code de swap exécute, et Lauren swaps en fait le JO et le lait, ce qui se passe? Eh bien, ce 2 devient un 1, ce 1 devient un 2, et, en passant, il est une variable temporaire qui est en cours utilisé tout ce temps que finalement s'en va. Mais il n'a pas d'importance combien de travail que vous faites dans cette ligne de-- dans cet espace mémoire, x et y sont complètement intacte. 

Donc, nous avons besoin d'une certaine façon de donner Swap et fonctionne comme il accès secrète, si vous voulez, à like-- fonctions à la mémoire comme x et y. Donc, nous allons jeter un oeil à un exemple qui permet nous voyons exactement ce qui a été passe tout ce temps. Je vais aller de l'avant et d'ouvrir Comparer Zero. Et je vais fermer notre débogueur, je vais de fermer ce message effrayant à la recherche juste dit, attendez une minute, vous êtes dans le milieu de débogage. Je vais cacher cet onglet ici juste pour revenir à la simplicité. Donc, ne vous inquiétez pas si GDB est tué. Cela signifie simplement que le programme a été cesser de fumer, délibérément, dans ce cas, par moi. 

Et maintenant Comparer Zéro fait cela. Je suis en utilisant le CS50 bibliothèque E / S standard. Je dois une fonction principale de cette première dit, dire quelque chose, et obtient une chaîne. Ensuite, dit encore et obtient une autre chaîne. Et remarquez que ces deux chaînes sont appelés s et t, respectivement. Et maintenant ce programme, Comparer Zéro, son but dans la vie, il est censé me dire, ai-je tape la même chose? Et donc je vais revenir à la première semaine. Je suis en utilisant mon opérateur égal égalité qui est l'opérateur de la qualité. Non l'opérateur d'affectation, l'opérateur d'égalité. Je suis juste comparant s et t. 

Donc, nous allons effectivement aller de l'avant et de le faire. Et je vais aller de l'avant et de faire Comparer Zero. Je vais faire ./comparezero. Et je vais aller de l'avant et dire quelque chose comme, faisons maman en minuscules Et que diriez-maman en majuscules. Et bien sûr, je tape des choses différentes. Bien. Cela est à prévoir. 

Lançons nouveau. Les deux fois, font minuscules, minuscules. Cela semble super identique à moi. Entrez. D'ACCORD. Peut-être qu'il est juste bizarre parce que il est ne pas aimer ma grammaire. Alors, faisons un MOM de capital, capitale MOM, identiques. Choses différentes. 

Alors, pourquoi est-ce? Eh bien, qu'est-ce qui se passe réellement sur sous le capot ici? Donc, nous allons revenir sur ici pour un moment et de considérer ce GetString est en train de faire. Lorsque vous appelez GetString, qui est une fonction que nous nous a écrit et il devient en quelque sorte un séquence de caractères provenant de l'utilisateur. Et supposons que le premier fois que je appelle GetString, qui me donne un morceau de la mémoire qui ressemble à ceci. Et si je tapé en minuscules m-o-M-- et ce qui se passe après? Juste un test de cohérence rapide. 

Backslash zéro. Nous savons que. Et rappelons que nous avons joué autour avec le nom de Zamila et un tas d'autres noms quand Rob a été ici à la recherche ce qui se passe à l'intérieur de la mémoire. Donc cette histoire est exactement la même. Ceci est ce que GetString est de retour pour moi. Maintenant, mon code il ya un instant stockée la valeur de retour de GetString dans une variable appelée s. Et puis la deuxième fois je l'ai appelé, il stocké dans une variable appelée t. 

Donc, si je vais ici, je dois de tirer cette variable-- locale et je vais généralement dessiner une chaîne comme just-- nous allons appeler s-- comme une petite place ici. Et maintenant, comment fonctionne somehow-- maman aller à l'intérieur de cette variable s? Eh bien, nous devons revenir aux premiers principes ici. Quel est GetString effectivement de retour? 

Donc, il se trouve que M-O-M barre oblique inverse zéro, et un certain nombre d'autres chaînes dans la mémoire comme Zamila et Rob ou Andy ou d'autres, sont bien sûr dans notre la RAM ou mémoire de l'ordinateur. Et votre RAM a like-- vous avez un concert de RAM, deux concerts de RAM, ou un milliard ou deux milliards d'octets, ou peut-être encore plus ces jours-ci. Supposons donc, pour les besoins d'aujourd'hui, qu'il n'a pas d'importance comment on numérote eux, mais on peut numéroter chaque de ceux milliards ou deux milliards ou quatre milliards d'octets. 

Et disons simplement arbitrairement que ceci est la première piqûre, deuxième morsure, troisième, quatrième. Je délibérément de ne pas égale à zéro aujourd'hui, mais nous allons revenir à cela. En d'autres termes, si tel est le première fois que je suis en utilisant le programme, Je suis juste avoir de la chance et de la première morsure est à l'emplacement d'un puis deux puis trois à quatre. Et si je continuais à dessiner, numéro de boîte deux milliards serait en venant ici. 

Alors, que pensez-vous, alors, GetString retourne en fait? Il ne revient pas M-O-M barre oblique inverse zéro en soi parce que clairement ne tient pas dans la boîte que je l'ai dessiné. Alors quoi d'autre pourrait effectivement GetString être de retour toutes ces semaines? La réponse est sur le conseil ici, quelque part. Vous ne pouvez pas ajuster M-O-M barre oblique inverse zéro, donc ce qui pourrait donner un sens à la place? Si vous deviez être super intelligent, mettant sur la dite chapeau d'ingénierie, que pourriez-vous revenir? Quelle est la moins quantité d'informations vous pourriez rendement qui aurait encore vous permettent de trouver M-O-M dans la mémoire? Ouais? 

AUDIENCE: One. 

DAVID J. Malan: One. Et pourquoi on? AUDIENCE: Parce que ce serait dire vous où aller [inaudible]. DAVID J. Malan: Exactement. Je vais me contenter de renvoyer l'adresse de la chaîne que je l'ai obtenu. L'adresse de cette cas est un emplacement. Donc ce qui est vraiment est d'être stockées dans s-- et chaque variable de chaîne ainsi far-- vient de faire l' Adresse de cette chaîne. 

Pendant ce temps, si je l'appelle GetString une deuxième fois et je taper littéralement le même chose-- M-O-M avec M lowercase---O-M et une autre barre oblique inverse zéro, et maintenant peut-être mon programme de en cours depuis un certain temps alors peut-être cette est 10, cela est l'emplacement 11, cela est 12, cela est 13. Les ordinateurs utilisant un autre mémoire pour une raison quelconque. Ce qui se passe maintenant dans ma deuxième variable dans mon programme t? 10. Exactement. 

Et donc quand nous regardons le le code source du programme où je vais simplement essayer de comparer les deux valeurs, s est égal égal à t, ce qui est la réponse humaine évidente? Juste parce que pas une ne correspond pas à 10. Et ainsi se trouve ici une occasion pour nous vraiment juste revenir, encore une fois, d'abord principes et penser, ainsi, ce qui se passe sous le capot? Nous avons parlé bits et d'octets et de la mémoire, mais il est réellement utile pour comprendre parce que quand vous appelez GetString, même si nous pensons qu'il est retour M-O-M ou une chaîne maman ou Andy ou Zamila ou etc., techniquement il est juste de retourner l'adresse de ce morceau de mémoire. 

Mais cela est OK. Parce que sais-je où la chaîne se termine? Si je suis seulement donné le début? Eh bien, la barre oblique inverse de zéro, non? Juste à temps linéaire que je peux imprimer avec impression def M-O-M. Et dès que je vois barre oblique inverse zéro, je ne me soucie pas où je commencé, Je sais déjà implicitement où je dois mettre fin. 

Ainsi, aujourd'hui marque le beginning-- et laissez-moi faire ce spectaculaire parce que nous a traversé beaucoup de mal à obtenir ces ici formation wheels-- Donc, aujourd'hui, les roues de formation commencent à se détacher et nous révéler au moins: 

[Applaudissements] 

Cela valait bien le voyage pour cibler ce matin, oui? Donc maintenant-- il ya, elle se tourne dehors, rien de tel que chaîne. Chaîne ne existe pas. Il est synonyme que nous avons eu l'intérieur de la bibliothèque CS50. Désormais, nous allons commencer à appeler s et t pas les chaînes, mais étoiles char. Et la star char nous allons démêler avant longtemps. Mais cela est-à-dire, que, même si nous continuons utilisant GetString pour l'instant, techniquement je devrais dire étoiles char et l'omble étoiles. 

Et il se trouve que cette étoile va désigner quelque chose appelé un pointeur ou une adresse. Et en fait, un teaser pour ce qui nous attend est-ce 20 secondes clip de notre ami Nick Parlante à Stanford qui, il ya un certain temps, dépenser un montant ridicule de temps, du mieux que je peux dire, dans son cuisine ou son sous-sol, faisant claymation introduire dans le monde un personnage nommé Binky avec qui nous allons introduire la prochaine fois pour les pointeurs. Voici donc un aperçu de ce qui est à venir. 

[LECTURE VIDÉO] 

-Hé, Binky. Debout. Il est temps pour le plaisir pointeur. 

-Qu'est ce que c'est? En savoir plus sur les pointeurs? Oh, Goody. 

[FIN LECTURE] DAVID J. Malan: Et sur cette note, nous vous verrons mercredi. Bien. Qui est la danse? Allons. Qui est la danse? Vous voulez que je le lancer? Je vais le faire démarrer. Woooo! 

LAUREN: doux fantaisie Moïse.