[Powered by Google Translate] [Section 4] [Moins confortable] [Nate Hardison] [Université de Harvard] [C'est CS50.] [CS50.TV] 

Très bien, bon retour à la section. Dans la section de cette semaine, nous allons faire une ou deux choses. Nous allons Set récapitulatif premier problème 2, qui est le problème posé César et Vigenère. Et puis, nous allons plonger dans Quiz 0 avis et passer un peu de temps récapituler ce que nous avons parlé dans chacune des conférences à ce jour, et nous allons également faire quelques problèmes à partir de questionnaires année précédente. De cette façon, vous les gars ont une bonne façon de se préparer à cela. 

Pour commencer, j'ai démarré un couple de bonnes solutions pour l'ensemble précédent problème, un problème Set 2, dans cet espace. Si vous les gars tous atteint ce lien, et si vous cliquez sur mon nom et cliquez sur mon première révision vous verrez caesar.c, ce qui est exactement ce que je vois. Parlons un peu de ce très rapidement. Ceci est juste un exemple de solution. Ce n'est pas forcément la solution idéale. Il existe de nombreuses manières différentes d'écrire cela, mais il ya quelques petites choses que je voulais mettre en évidence que j'ai vu que j'étais classement, erreurs les plus courantes que je pense Cette solution fait un très bon travail de manutention. 

La première est d'avoir une sorte de commentaire d'en-tête en haut. Sur les lignes 1 à 7, vous voyez les détails, exactement ce que ce programme fait. Une bonne pratique standard lorsque vous écrivez du code C peu importe si votre programme est contenu dans un seul fichier ou que ce soit réparti sur plusieurs fichiers, c'est d'avoir une sorte de orienter commentaire en haut. C'est aussi pour les personnes qui sortent et écrire du code dans le monde réel. C'est là qu'ils vont mettre les informations de copyright. Voici les # includes. Sur la ligne 16, il ya ce # define, qui nous y reviendrons dans un instant. Et puis une fois que la fonction commence, commence une fois que les principaux, parce que ce programme a été tout contenu dans une seule fonction la première chose qui se passe et ce qui est très idiomatique et typique d'un programme C qui prend en ligne de commande arguments, c'est que celui-ci vérifie immédiatement 

pour le nombre d'arguments, argc. Ici, nous voyons que ce programme attend 2 arguments exactement. Rappelez-vous, il ya ce premier argument, c'est le spécial c'est toujours le nom du programme qui est en cours d'exécution, le nom du fichier exécutable. Et qu'est-ce que cela fait est qu'il empêche l'utilisateur d'exécuter le programme avec des arguments plus ou moins. La raison pour laquelle nous voulons vérifier ça tout de suite parce que nous ne pouvons pas réellement accéder à ce tableau argv ici de manière fiable jusqu'à ce que nous avons vérifié pour voir comment elle est grande. 

Une des erreurs les plus courantes que j'ai vu était des gens se rendre immédiatement dans et grappin argv [1]. Ils avaient saisir l'argument clé de la matrice et ne l'a à i vérifier sur elle, et puis ils font le test argc, ainsi que la prochaine épreuve, si le premier argument est en effet un nombre entier au même moment, et cela ne fonctionne pas, car dans le cas où il n'y a pas d'arguments fournis vous serez saisissant un argument qui n'est pas là ou de tenter d'attraper un qui n'est pas là. 

L'autre chose importante que vous devriez remarquer est que vous voulez toujours imprimer une sorte de message d'erreur utile à l'utilisateur de les orienter. Je suis sûr que vous avez tous les programmes gérés par où tout d'un coup il se bloque, et vous obtenez cette boîte de dialogue qui apparaît peu ridicule et dit quelque chose de terriblement cryptique et peut-être vous donne un code d'erreur ou quelque chose comme ça qui n'a aucun sens. C'est là que vous voulez vraiment apporter quelque chose d'utile et ciblées à l'utilisateur de sorte que quand ils l'exécuter ils vont "Oh," visage de palme. «Je sais exactement ce qu'il faut faire. Je sais comment résoudre ce problème." 

Si vous n'avez pas à imprimer un message, puis vous vous retrouvez en fait laissant à l'utilisateur d'aller examiner le code source de comprendre ce qui s'est mal passé. Il ya aussi des moments que vous allez utiliser différents codes d'erreur. Ici, nous avons utilisé un pour dire qu'il ya eu une erreur, il y avait une erreur, une erreur s'est produite. Bigger programmes, souvent des programmes qui sont appelés par d'autres programmes, sera de retour une sorte de codes d'erreur spécifiques dans différents scénarios par programmation communiquer ce que vous feriez autrement il suffit d'utiliser un gentil message en anglais pour. Cool. Comme nous travaillons en bas, vous pouvez voir que nous tirez la clé. Nous tester pour voir si la clé correspond. Nous recevons un message à l'utilisateur. La raison pour laquelle nous le faisons dans ce do-while et c'est quelque chose que nous allons couvrir dans un petit peu, mais il s'avère que si vous tapez control D quand vous obtenez ce GetString rapide sur le terminal ce qui revient en fait il envoie un caractère spécial pour le programme. C'est ce qu'on appelle l'ELF ou le caractère de fin de fichier. Et dans ce cas, notre chaîne de message sera nulle, donc ce n'était pas quelque chose où nous sommes arrivés dans le problème lui-même fixé. 

Mais, comme nous allons, maintenant que nous avons commencé à parler de pointeurs et l'allocation dynamique de la mémoire sur le tas, le contrôle de null chaque fois que vous avez une fonction qui pourrait return null comme valeur de quelque chose que vous aurez envie de prendre l'habitude de faire. Il s'agit ici principalement à titre d'illustration. Mais quand vous voyez GetString à l'avenir, afin de problème Set 4, vous aurez envie de garder cela à l'esprit. Encore une fois, ce n'est pas un problème pour un problème Set 3, soit depuis que nous n'avions pas encore couvertes. Enfin, nous arrivons à cette partie où nous arrivons à la boucle de cryptage principale, et il ya un certain nombre de choses qui se passent ici. Tout d'abord, nous avons une itération sur la chaîne de la totalité du message lui-même. Ici, nous avons gardé l'appel strlen dans l'état, laquelle un certain nombre d'entre vous l'ont souligné n'est pas un grand chemin à parcourir. Il s'avère dans ce cas, il n'est pas non plus grand, en partie parce que nous sommes modifier le contenu du message lui-même l'intérieur de la boucle for, donc si nous avons un message qui fait 10 caractères de long, la première fois que nous partons pour la boucle strlen retourne quoi? 10. 

Mais si nous alors modifier un message, par exemple, nous modifions sa 5ème caractère, et nous jeter dans un caractère \ 0 en 5ème position, sur une itération ultérieure strlen (message) ne retournera pas ce qu'il a fait la première fois que nous itéré, mais il sera plutôt revenir 5 parce que nous avons jeté dans cette fin nulle, et la longueur de la corde est défini par la position de ce \ 0. Dans ce cas, il s'agit d'un excellent moyen d'aller parce que nous sommes le modifier en place. Mais vous remarquerez que c'est en fait étonnamment simple à chiffrer si vous pouvez obtenir le calcul exact. Tout ce qu'il faut est de vérifier si oui ou non la lettre que vous cherchez à est en majuscule ou en minuscule. 

La raison pour laquelle nous ne disposons pas de consulter pour cela et nous n'avons pas à vérifier le cas parce que l'alpha est si un caractère est en majuscule ou en minuscule si c'est alors il est certainement un caractère alphabétique, parce que nous n'avons pas les chiffres majuscules et minuscules. L'autre chose que nous faisons, et c'est un peu difficile- est que nous avons modifié la norme de chiffrement de César formule que nous avons donné dans la spécification du jeu de problème. Ce qui est différent ici, c'est que nous avons soustrait cas dans la capitale majuscule, puis nous avons ajouté majuscule sauvegarder à la fin. 

Je sais que certains d'entre vous l'ont fait ceci dans votre code. Avez-vous tout de cela dans vos mémoires? Vous l'avez fait. Pouvez-vous expliquer ce que cela fait, Sahb? En le soustrayant, parce que vous avez fait un mod juste après, vous devez l'enlever, si cette façon vous obtenez [toux] position. Et puis en l'ajoutant revenir plus tard vous avez changé sur celui que vous vouliez. Oui, exactement. Qu'est-ce Sahb dit, c'est que quand nous voulons ajouter notre message et notre touche en même temps puis mod qui, mod que par NUM_LETTERS, si nous ne s'adaptent pas notre message approprié dans la gamme de 0 à 25 d'abord, alors nous pourrions finir par avoir un nombre vraiment bizarre parce que les valeurs qui nous intéressent quand on regarde message [i], quand on regarde le ième caractère de notre message en texte ordinaire, est une valeur quelque part dans cette fourchette de 65 à 122 sur la base des valeurs ASCII pour les majuscules A à Z minuscules. Et quand nous le mod par 26 ou par NUM_LETTERS, puisque c'était notre # define en haut à droite ici, qui va nous donner une valeur qui se trouve dans la plage de 0 à 25, et nous avons besoin d'un moyen de l'échelle alors que les secours et le faire dans l'intervalle ASCII approprié. La meilleure façon de le faire est de simplement étendre tout vers le bas dans la plage de 0 à 25, pour commencer, et passer ensuite tout remettre en place à la fin. 

Une autre erreur commune que j'ai vu des gens courir en est que si vous n'avez pas fait cela tout de suite mise à l'échelle et que vous ajoutez un message et touche en même temps et vous les ajoutez, par exemple, dans une variable de type char, le problème avec cette C'est depuis le message [i] est un nombre relativement important de commencer par- n'oubliez pas que c'est au moins 65 ans si c'est une majuscule caractère si vous avez une grosse clef, disons, quelque chose comme 100, et vous ajoutez les 2 ensemble dans un char signé que vous allez obtenir un débordement. Vous allez obtenir une valeur qui est plus grand que 127, qui est la plus grande valeur qu'une variable de type char peut contenir. Encore une fois, c'est pourquoi vous voulez faire ce genre de chose pour commencer. Certaines personnes ont autour de ce cas en faisant un if else et tester pour voir si elle provoque un débordement avant de faire cela, mais de cette manière permet de contourner cela. Et puis, dans cette solution, nous avons imprimé sur toute la chaîne à la fin. D'autres personnes imprimé un caractère à la fois. Les deux sont super. À ce stade, que vous les gars avez des questions, des commentaires à ce sujet? Choses que vous aimez, des choses que vous n'aimez pas? 

J'avais une question. Peut-être que je l'ai raté lors de votre explication, mais comment ce programme sauter les espaces pour connecter la clé à la longueur du texte? Ce n'est qu'un chiffre de César. >> Oh, désolé, ouais. Ouais, on va voir ça. Dans le chiffrement de César nous nous sommes promenés que parce que nous ne retournée caractères. Nous ne les ai tournés s'ils étaient en majuscules ou en minuscules. Les gars, vous sentez assez bien à ce sujet? N'hésitez pas à copier cette maison, prenez-la, le comparer à ce que vous les gars ont écrit. Certainement, n'hésitez pas à envoyer vos questions à ce sujet aussi. Et encore une fois, se rendre compte que le but ici avec votre problème fixe n'est pas de faire de vous pour écrire du code parfait pour vos séries de problèmes. C'est une expérience d'apprentissage. Ouais. 

Retour à la boucle Do While, si elle est égale nulle, donc nulle signifie rien du tout, ils ont juste frappé entrer? Null est une valeur de pointeur spécial, et nous utilisons nulle lorsque nous voulons dire nous avons une variable pointeur qui pointe vers rien. Et si typiquement cela signifie que cette variable, cette variable message est vide, et ici, parce que nous utilisons le type CS50 chaîne spéciale, quel est le type de chaîne CS50? Avez-vous vu ce que c'est quand David tiré vers l'arrière de la hotte dans la conférence? C'est une musique funky-c'est un pointeur, pas vrai? Ok, ouais. >> C'est un char *. Et si vraiment on pourrait remplacer cette ici avec un message char *, et si la fonction GetString, si elle n'a pas réussi à obtenir une chaîne de caractères provenant de l'utilisateur, il ne peut pas analyser une chaîne, et le seul cas dans lequel il ne peut pas analyser une chaîne est que si l'utilisateur tape le caractère de fin de fichier, la commande D, ce qui n'est pas quelque chose que vous faites normalement, mais si cela se produit alors la fonction retourne cette valeur null comme une façon de dire "Hé, je n'ai pas une chaîne." Qu'arriverait-il si nous ne mettons pas un message = null, qui est quelque chose que nous n'avons pas fait encore? Pourquoi serait-ce un problème? Parce que je sais que nous avons parlé un peu de lecture sur les fuites de mémoire. Oui, nous allons le faire, et nous allons voir ce qui se passe. 

Question Basile était ce qui se passe si nous n'avons pas vraiment ce message de test = null? Faisons défiler vers le haut vers le haut. Les gars, vous pouvez commenter cette option. En fait, je vais l'enregistrer dans une révision. Ce sera la révision 3. Qu'est-ce que vous avez à faire pour exécuter ce programme est que vous aurez à cliquer sur cette icône d'engrenage ici, et vous aurez à ajouter un argument à lui. Vous devez lui donner l'argument clé, car nous voulons passer un argument de ligne de commande. Ici, je vais lui donner le numéro 3. J'aime 3. Maintenant zoom revenir en arrière, l'exécution du programme. Il fonctionne, la compilation, la construction. Nous y voilà. Il attend d'être invité. Si je tape dans quelque chose comme bonjour, où ça s'est passé? Oh, mon programme a pris trop de temps à s'exécuter. J'ai été jawing depuis trop longtemps. Ici, il va. Maintenant je tape bonjour. Nous voyons que le chiffre de manière appropriée. Maintenant ce qui se passe si nous faisons GetString invite pour revenir nulle? Rappelez-vous, j'ai dit que nous l'avons fait en appuyant sur commande D dans le même temps. Je vais défiler vers le haut ici. Nous allons l'exécuter à nouveau. Bâtiment. Là, il va. Maintenant, quand je frappe le contrôle D J'ai eu cette ligne qui indique opt/sandbox50/bin/run.sh, Segmentation fault. Avez-vous les gars vu ça avant? 

[Étudiants] Pourquoi n'y at-il >> Désolé? [Étudiants] Pourquoi aucune core dump dans ce cas? Le core dump est-la question est pourquoi est-il pas de core dump ici? La question, c'est qu'il ya peut-être, mais le core dump est un fichier qui est stocké sur le disque dur. Dans ce cas, nous avons désactivé core dumps sur le serveur d'exécution de sorte que nous n'avons pas les gens seg failles et le renforcement des tonnes de core dump. Mais vous pouvez en obtenir un. Core dumps sont le genre de chose que vous pouvez souvent désactiver, et parfois vous faites. L'erreur de segmentation, pour répondre à votre question, Basil, dit que nous avons essayé d'accéder à un pointeur qui n'a pas été définie pour pointer sur quoi que ce soit. Se souvenir de Binky dans la vidéo lors de Binky tente de allez accéder à un pointeur qui ne pointe pas vers qui se quoi que ce soit? Dans ce cas, je suppose que, techniquement, le pointeur pointe vers quelque chose. Il pointe vers nulle, ce qui est techniquement 0, mais qui est définie pour être dans un segment qui n'est pas accessible par votre programme, vous obtenez une erreur de segmentation parce que vous n'êtes pas accéder à la mémoire qui se trouve dans un segment valide comme le segment de pile ou le segment de pile ou le segment de données. Cool. D'autres questions à propos de César? 

Passons à autre chose. Regardons Révision 2 très rapidement. C'est Vigenère. Ici, dans Vigenère nous allons marcher à travers celui-ci assez rapidement parce que, encore une fois, Vigenère et César sont assez similaires. Commentaire d'en-tête est devant, # Define est avant pour éviter d'utiliser ces nombres magiques. La bonne chose est que nous voulions passer à un alphabet différent ou quelque chose comme ça. Plutôt que d'avoir à aller modifier manuellement tous les 26 dans le code de nous pourrions changer cela pour 27 ou le faire tomber si nous utilisions des alphabets différents, des langues différentes. Encore une fois, nous avons cette vérification de l'argument nombre, et vraiment, on peut presque considérer cela comme un modèle. Presque chaque programme que vous écrivez doit avoir- si elle a des arguments de ligne de commande-une séquence de lignes qui se lit comme ça au début. C'est l'un des tests sanity abord, vous voulez faire. 

Voici ce que nous avons été nous nous sommes assurés que les le mot-clé est valide, et que c'était la deuxième vérification que nous avons fait. Notez encore une fois que nous nous sommes séparés de cette argc et 2. Notez que dans ce cas, une chose que nous avions à faire était plutôt de l'utilisation de a à i nous voulions valider la totalité de la chaîne, et pour ce faire que vous avez réellement besoin d'aller caractère par caractère sur la chaîne. Il n'ya pas de bonne façon d'appeler quelque chose à ce sujet parce que même, par exemple, a à i retourne 0 si elle ne peut pas analyser un nombre entier, ce qui ne fonctionne même pas. Encore une fois, joli message indiquant à l'utilisateur exactement ce qui s'est passé. Alors voilà, encore une fois, nous avons également gérer le cas où l'utilisateur tape un caractère de contrôle D aléatoire. 

Et puis, Charlotte a eu plus tôt une question sur la façon dont nous gérons pour passer espaces dans notre chaîne ici. C'était un peu similaire à ce que nous avons fait avec le programme Myspace que nous avons fait dans la section, et la façon dont cela a fonctionné est que nous avons suivi le nombre de lettres que nous avions vu. Tandis que nous marchions sur la chaîne de message, alors que nous marchions sur le caractère par caractère, nous avons suivi l'indice dans le cadre de notre boucle for, puis nous avons également suivi le nombre de lettres, de sorte non des caractères spéciaux, chiffres, non-non-Blancs espace que nous avions vu dans la variable distincte. Et puis cette solution modifie la clé pour obtenir un nombre entier de clé réelle, et il le fait à la volée, juste avant qu'il ne se rend ensuite à chiffrer le caractère réel des messages. Il existe des solutions qui étaient parfaitement très bien aussi qui modifierait la touche vers le haut lors du test de validité de la clé. En plus de s'assurer que le caractère et le mot-clé a un caractère alphabétique elle a également tourné que dans un nombre entier dans l'intervalle 0 à 25 puis passez à avoir à le faire plus tard dans cette boucle for. Encore une fois, vous voyez ici c'est vraiment exactement le même code que nous avons utilisé dans César à ce stade. Vous faites exactement la même chose, de sorte que le vrai truc est de trouver comment mettre la clé dans un entier. 

Une chose que nous avons fait ici c'est un peu dense est, nous avons répété cette phrase, je suppose que vous pourriez l'appeler, 3 fois séparées sur les lignes 58, 59, et 61. Quelqu'un peut-il expliquer ce qu'est exactement cette phrase fait? Il accède à un personnage, comme vous avez dit. Ouais, c'est [inaudible] un caractère dans le mot-clé, et il est donc certain nombre de lettres vus parce que vous êtes seulement se déplaçant le long le mot-clé une fois que vous avez vu la lettre, de sorte que ça va passer efficacement des espaces et des trucs comme ça. Oui, exactement. Et puis une fois que vous avez vu l'ébauche de mot-clé que vous venez de mod si vous vous déplacez en arrière autour. Exactement. C'est une explication parfaite. Que Kevin a dit, c'est que nous voulons index dans la clé. Nous voulons obtenir le caractère num_letters_seen, si vous voulez, mais si num_letters_seen dépasse la longueur de la clé, la façon dont nous serons de retour dans la gamme appropriée est que nous utilisons l'opérateur mod efficacement envelopper. Par exemple, comme dans le court, le mot clé est notre bacon, et c'est 5 lettres. Mais nous avons vu 6 lettres dans notre texte à ce stade et crypté 6. Nous allons finir par accéder à la num_letters_seen, qui est 6, la longueur du mod le mot 5, et ainsi nous aurons 1, et donc ce que nous allons faire, c'est nous allons accéder à l'intérieur du premier caractère de notre mot à ce point. 

Tout droit, toute question sur Vigenère avant de passer? Les gars, vous sentez assez bien à ce sujet? Cool, génial. Je tiens à vous assurer que vous les gars ont la chance de voir le code que nous pensons semble bon et avoir la chance d'apprendre de lui. Ce sera le dernier que nous allons utiliser les espaces pour le moment, et nous allons faire la transition maintenant, et je vais aller à cs50.net/lectures afin que nous puissions faire un peu de révision quiz. La meilleure façon je pense que pour commencer à faire questionnaire examen est d'arriver à cette page Conférences, cs50.net/lectures, et sous chacune des rubriques semaine, donc si je regarde ici à la semaine 0, Je vois que nous avons une liste de sujets que nous avons vu dans la semaine 0. 

Si l'un de ces sujets semblent pas familier pour vous vous aurez certainement envie de revenir en arrière et parcourir les notes de cours et, éventuellement, même parcourir les conférences, les regarder à nouveau si vous voulez pour avoir une idée de ce qui se passe avec chacun de ces sujets. Je dirai plus, cette année, une des ressources fraîches que nous avons obtenu est ce short que nous avons créés, et si vous regardez à la semaine 0, nous n'avons pas tous les sujets abordés, mais nous avons un assez grand nombre d'entre eux, quelques-uns des plus délicates, donc regarder ce short à nouveau est un bon moyen pour vous mettre au courant. En particulier, je vais mettre dans une prise pour le 3 sur le fond, depuis que j'ai fait ceux-ci. Mais si vous êtes aux prises avec binaire, bits, hexagonales, ce genre de choses, binaire est un excellent endroit pour commencer. ASCII est un autre qui est bon de voir aussi. Vous pouvez même me regarder à la vitesse de 1.5x si je vais trop lent pour vous. Depuis sa révision, n'hésitez pas à le faire. 

Juste pour commencer très rapidement, nous allons passer par un couple de ces problèmes de quiz juste pour rapidement le taux de désabonnement à travers celles-ci. Par exemple, regardons problème 16 que je dois juste ici sur le plateau. Nous avons ce calcul suivant en binaire, et nous voulons montrer tout le travail. Ok, je vais vous donner ce coup. Vous devriez suivre avec le papier, et nous ferons ce très rapidement. Nous voulons effectuer le calcul suivant en binaire. J'ai 00110010. Et je vais y ajouter 00110010. Pour le calcul des génies suivant le long à la maison, ceci est effectivement multiplier par 2. Commençons. Nous allons suivre l'algorithme d'addition même que nous faisons si l'on ajoute les nombres décimaux ensemble. En réalité, la seule différence ici est que nous bouclage autour une fois que nous avons 1 + 1 au lieu d'une fois nous arrivons à 10. 

Si nous partons de la droite, très rapidement, ce qui est le premier chiffre? [Étudiants] 0. >> [Nate H.] 0. Grande, le deuxième chiffre? [Étudiants] 1. [Nate H.] Est-ce un 1? 1 + 1 est? [Étudiants] 10. [Nate H.] Exactement, alors quel est le chiffre que je vous écris juste en dessous des 2 ceux ajoutés ensemble? [Étudiants] 1, 0, ou 0, puis porter la 1. [Nate H.] 0 et porter un 1, exactement. Prochaine étape un, Basil, c'est à vous. Quelle est la troisième? >> [Basil] 1. [Nate H.] 1, parfait. Kevin? [Kevin] 0. >> [Nate H.] 0, Charlotte? [Charlotte] 0. >> [Nate H.] Ouais, et qu'est-ce que je dois faire? [Étudiants] Le 1. [Nate H.] Et que dois-je faire? Et puis je porte le 1. Parfait, Sahb? >> [Sahb] Maintenant, vous avez 1. [Nate H.] Et dois-je faire quelque chose ici? [Sahb] Alors, pour le prochain vous avez 1 parce que vous reportés 1. [Nate H.] Super, ici, nous pouvons le terminer. Cool. [Étudiants] Est-ce que 0 + 0 = 0? 0 + 0 = 0. 1 + 1, comme vous l'avez dit, est de 10, ou 1, 0, plutôt. 10 est un abus de langage car pour moi, 10 signifie que le nombre 10, et c'est le caprice de la façon dont nous le représenter lorsque nous l'écrire. Nous représentons le numéro 2 de 1, 0, et le nombre 10 est légèrement différente. 

Ce qui est plutôt agréable à propos de binaire est qu'il ya vraiment pas beaucoup des cas, vous avez besoin d'apprendre. Il ya 0 + 0 = 0, 0 + 1 = 1, 1 + 1 est égal à 0, puis effectuer un 1, et puis vous pouvez voir ici sur la troisième colonne de droite nous avons eu cette 1, 1 et 1. Et 1 + 1 + 1 est un 1, et vous portez un autre 1. Lorsque vous faites l'addition binaire, assez simple. Je ferais un couple de ces plus à la raison vous vérifiez avant d'entrer parce que ce n'est probablement quelque chose que nous verrons sur le quiz. Maintenant, nous allons le faire suivant ainsi. Faisons problème 17. Nous allons convertir le nombre binaire en décimal suivant. J'ai 10100111001. Rappelez-vous dans la vidéo binaire que j'ai fait Je marchais à travers quelques exemples, et j'ai montré comment tout fonctionne lorsque vous le faites en décimal. Lorsque vous travaillez en représentation décimale, je pense que nous sommes à ce stade dans nos vies afin couramment dans ce que il est assez facile de passer sous silence les mécanismes de la façon dont il fonctionne réellement. 

Mais pour ce faire un bref récapitulatif, si j'ai le numéro 137 cela signifie-et vraiment nouveau, c'est dans la représentation décimale- le numéro 137 en décimal signifie que je dois 1 x 100 + 3 x 10 + 7 x 1. Ceci est d'autant rester sur l'écran. Et puis, si vous regardez ces chiffres ici, 100, 10 et 1, on voit que ce sont en fait toutes les puissances de 10. J'ai 10 ², 10 ¹, et 10 à zéro. Nous avons une sorte de chose semblable en binaire, sauf que notre base, comme nous l'appelons, est de 2 au lieu de 10. Ces 10s que j'ai écrit ici-bas au fond, ce ² 10, 10 ¹, 10 au zéro, est notre base 10, et l'exposant, 0, 1, ou 2, est impliqué par la position du chiffre dans le nombre que nous écrivons. 1, si l'on regarde, ce 1 est en 2ème position. La figure 3 est en position 1, et la figure 7 est en position 0e. C'est ainsi que nous obtenons les divers exposants ci-dessous pour nos bases. 

Après tout cela, we'll-en fait, vous savez quoi? Nous ferons-Où est mon bouton Annuler aller? Là, il va. J'aime cette annulation chose. Suite à cela, je pense que pour moi au moins la meilleure façon de commencer la conversion d'un nombre binaire ou un nombre hexadécimal dans lequel la base est de 16 et non pas 10 ou 2 est d'aller de l'avant et d'écrire les bases et les exposants pour tous les numéros dans mon nombre binaire en haut. Si nous partons de gauche à droite à nouveau, ce qui est assez paradoxal, Je vais revenir au noir ici, nous avons la 2 à la position 0e, et puis nous avons 2 ¹, 2 ², puis 2 à la 3, 2 à la 4, 2 à la 5, 6, 7, 8, 9, et 10. Ces chiffres que j'ai écrites sur tous les exposants sont. J'ai seulement écrit les bases ici dans les 3 premiers seulement pour l'espace. 

A ce stade, je vais aller de l'avant et je suis vraiment en train d'effacer les choses que nous avons fait en décimal, si cela vous convient. Vous avez tous compris. Ceux d'entre vous regarder en ligne Je suis sûr, sera en mesure de me revenir en arrière si vous le souhaitez. Le retour à la plume. Maintenant, ce que nous pouvons faire, si vous les gars ne sont pas totalement au courant de vos puissances de 2, c'est vraiment cool. Il ne se passe. Je comprends. Une fois, j'ai eu un entretien d'embauche où on m'a dit que je devrais savoir toutes les puissances de 2 à travers 2 à la 30e. Ce n'était pas un travail que j'ai eue. Quoi qu'il en soit, les gars vous pouvez aller de l'avant et faire le calcul ici, mais avec des binaires, il n'a pas vraiment de sens, et ne porte pas de sens avec décimal ou hexadécimal soit, de faire le calcul sur lequel vous avez des zéros. Vous pouvez voir que j'ai 0 ici, un 0 ici, 0 ici, 0 ici, 0 ici, 0 ici. Pourquoi serait-il pas judicieux de faire le calcul réel à calculer la puissance appropriée de 2 pour que la position? Exactement, comme dit Charlotte, ce sera 0. Pourrait tout aussi bien vous épargner du temps, si le calcul des puissances de 2 n'est pas votre point fort. Dans ce cas, nous avons seulement besoin de le calculer pour 2 à 0, ce qui est la-? [Étudiants] 1. [Nate H.] 1, 2 et 3, qui est la-? [Étudiants] 8. >> [Nate H.] 8. 2 à la 4? [Étudiants] 2. Je suis désolé, 1. [Nate H.] 2 au 4 a 16 ans, exactement. 2 au 5, Kevin? >> 32. [Nate H.] 32, 2 au 8? [Étudiants] 32 x 8, 256. [Nate H.] Parfait. Et 2 à la 10? [Etudiant] 1024. [Nate H.] Ouais, 1024. 

Une fois que nous avons ces chiffres, nous pouvons résumer le tout. Et c'est là que c'est vraiment important de faire un certain nombre de choses. On est aller lentement et vérifier votre travail. Vous pouvez dire qu'il ya un 1 à la fin de ce nombre, donc je devrais certainement obtenir un nombre impair de mon résultat, parce que tous les autres vont être des nombres pairs étant donné que c'est un nombre binaire. L'autre chose à faire, c'est si vous arrivez à ce point sur le test et vous l'avez écrit sur ce bien et vous êtes à court de temps regardez le nombre de points que ce problème vaut la peine. Ce problème, comme vous pouvez le voir, si je retourner en arrière à mon ordinateur portable très rapidement- ce problème vaut 2 points, donc ce n'est pas le genre d'addition vous devez passer par si vous êtes vraiment pressé par le temps. Mais nous allons revenir à l'iPad, et nous allons passer en revue très rapidement. 

J'aime faire les numéros petits d'abord parce que je trouve cela plus facile. J'aime 32 et 8 parce qu'elles s'accompagnent assez facilement, et nous obtenons 50. 16 et 1 obtient 17. Il nous obtenons 57, et nous pourrons alors faire le reste de ce fait, de sorte que nous pouvons faire 57, 156. Allez. L'homme, eh bien, nous allons voir. Nous avons eu 57, 256 et 1024. À ce stade, je préfère passer. Je n'ai aucune idée. J'ai bien besoin de lire à ce sujet. 7, 6, et 4, vous obtenez 17. 1, 5, 5, 2, 13. Ensuite, on obtient 3, puis on a 1. 1337. Oeufs de Pâques, tout le monde? Tout le monde reconnaît ce numéro? Chris reconnaît le nombre. Qu'est-ce que ça veut dire, Chris? [Chris] Leet. Leet, donc si vous regardez cela, il ressemble à leet. Hacker choses. Méfiez-vous de ce genre de trucs sur le moyen terme ou le quiz, plutôt. Si vous voyez ce genre de choses et vous vous demandez "Euh," qui pourrait réellement signifier quelque chose. Je ne sais pas. David aime le mettre po C'est un bon moyen de vérifier la validité de celui. Comme bien, je peux voir ce qui se passe. 

C'est la Semaine 0/semaine une substance. Si nous revenir à notre ordinateur portable maintenant, effectuer un zoom arrière, et un couple d'autres choses. Il ya ASCII, que nous avons fait beaucoup de problèmes avec les jeux. Cette notion de capital A. Qu'est-ce que vraiment? Sachant que c'est l'entier décimal. 65 est ce qu'il est mappé à la table ASCII, et c'est donc de savoir comment l'ordinateur, il écrit: et c'est ainsi que nous avons reçu de suite avec de l'écrire la capitale caractère A et le caractère en minuscule un dans certains de ces solutions et ensembles de problèmes que vous avez fait. Un couple d'autres choses. Nous avons déclarations, expressions booléennes, conditions, boucles, variables et les threads. 

Ceux semblent tous sens pour la plupart? Une partie de cette terminologie est un peu funky à la fois. J'aime à penser de la déclaration de la chose la plus partie qui se termine par un point-virgule. Des déclarations telles que x = 7, qui définit une variable, vraisemblablement appelé x = 7. On peut supposer que x est aussi un type qui peut stocker le numéro 7, il est donc un int ou un float ou peut-être un court-circuit ou un char, quelque chose comme ça. Une expression booléenne est l'utilisation de ces deux égaux et le bang est égal ou égale pas, inférieur à, supérieur à, inférieur ou égal à, tout ce genre de trucs. Conditions ensuite sont des déclarations si d'autre. Je voudrais vous rappeler que vous ne pouvez pas avoir un autre sans une correspondante si. De même, vous ne pouvez pas avoir un autre si sans correspondant si. Boucles, rappellent les 3 types de boucles, nous avons été en martelant que vous pour les deux dernières sections et ensembles de problèmes. L'utilisation, ne tandis que lorsque vous obtenez une entrée utilisateur, en utilisant des boucles while jusqu'à ce qu'une condition est vraie, puis en utilisant les boucles for, si vous avez besoin d' savoir quelle itération de la boucle que vous êtes actuellement sur ce que je pense à ce sujet. Ou si vous faites un pour chaque caractère dans une chaîne que je veux faire quelque chose, pour chaque élément dans un tableau que je veux faire quelque chose à cet élément. 

Fils et événements. Ceux-ci nous n'avons pas couvert de manière explicite en C, mais rappelez-vous à partir de zéro. C'est l'idée d'avoir des scripts différents. C'est aussi cette notion de diffuser un événement. Certaines personnes n'ont pas la diffusion dans leurs projets de départ, ce qui est vraiment cool, mais ce sont 2 manières différentes de traiter cette question plus vaste appelé la concurrence, qui est comment obtenez-vous les programmes à exécuter ou apparemment exécuter en même temps? Différentes tâches en cours d'exécution tandis que d'autres tâches sont également en cours d'exécution. C'est ainsi que votre système d'exploitation semble fonctionner. C'est pourquoi, même si, par exemple, J'ai obtenu mon navigateur fonctionne, je peux aussi mettre sur Spotify et jouer une chanson. C'est plus d'une chose conceptuelle pour comprendre. Je voudrais jeter un oeil à des fils courts si vous souhaitez en savoir plus à ce sujet. 

Voyons, je crois qu'il aurait pu être un problème à ce sujet dans une de celles-ci. Encore une fois, je pense que les discussions et les événements ne sont pas quelque chose que nous allons couvrir dans C juste parce que c'est beaucoup plus difficile que dans Scratch. Ne vous inquiétez pas à ce sujet, mais certainement comprendre les concepts, comprendre ce qui se passe. Avant de passer, des questions sur la Semaine 0 matérielles? Tout le monde sent assez bon? Comprendre les variables et ce qu'est une variable? 

Passons. Semaine 1. Un couple de choses ici qui ne sont pas particulièrement couvertes dans la revue questionnaire nécessairement et aussi des choses plus conceptuels pour penser. La première est la notion de ce code source, le code objet et compilateurs sont. Il ya quelqu'un? Basil. Est objet de code, je veux dire le code source est ce que vous mettez dans clang, et le code objet est ce bruit met de telle sorte que votre ordinateur peut lire le programme. Exactement. Le code source est le code C que vous avez réellement taper. Code objet est ce que vous sortez de bruit. C'est le 0 et de 1 dans ce format binaire. Alors qu'est-ce qui se passe, c'est quand vous avez un tas de fichiers objets, dire que vous compilez un projet ou d'un programme qui utilise plusieurs fichiers de code source, qui, par convention ont l'extension de fichier. c. C'est pourquoi nous avons caesar.c, vigenère.c. Si vous écrivez des programmes Java que vous leur donner l'extension. Java. Programmes Python ont l'extension. Py souvent. 

Une fois que vous avez plusieurs fichiers. C, vous les compiler. Clang crache toute cette ordure binaire. Ensuite, parce que vous ne voulez 1 programme vous avez le lien linker tous ces objets ensemble des fichiers dans 1 fichier exécutable. C'est aussi ce qui se passe lorsque vous utilisez la bibliothèque CS50, par exemple. La bibliothèque est à la fois CS50 cela. Fichier d'entête h que vous lisez, ce que # includecs50.h. Et puis, il ya aussi un fichier binaire spécial bibliothèque qui a été compilé qui est 0 et de 1, et que l'option-l, donc si nous revenons à nos espaces et nous sommes très vite à ce qui se passe ici quand nous regardons notre commande clang, ce que nous avons, c'est que c'est notre fichier de code source ici. Il s'agit d'un tas d'options de compilation. Et puis à la fin, ceux-ci l-drapeaux lien les fichiers binaires pour ces 2 bibliothèques, la bibliothèque CS50 et ensuite de la bibliothèque mathématique. 

Comprendre chaque type de finalité des fichiers » dans le processus de compilation est quelque chose que vous aurez envie d'être en mesure de donner au moins un aperçu de haut niveau de l'. Le code source entre en jeu. Le code objet sort. Fichiers de code objet lier ensemble, et vous obtenez un beau, un fichier exécutable. Cool. C'est également là que vous pouvez avoir des erreurs sur plusieurs points dans le processus de compilation. C'est là que, par exemple, si vous prenez cette option de liaison, le drapeau CS50, et vous l'omettez dans les espaces ou lorsque vous exécutez votre code, c'est là que vous aurez une erreur dans la phase de liaison, et l'éditeur de liens va dire: «Hé, vous avez appelé un GetString fonction C'est dans la bibliothèque CS50. " "Tu m'as dit qu'il était dans la bibliothèque CS50, et je ne trouve pas le code pour elle." C'est là que vous devez le lier à, et c'est séparé d'une erreur de compilation car le compilateur se penche sur la syntaxe et ce genre de choses. Il est bon de savoir ce qui se passe quand. 

D'autres choses à connaître. Je dirais que vous voulez absolument jeter un oeil à la court de transtypage fait par la Jordanie de comprendre ce qui ints sont sous le capot, ce que les caractères sont sous le capot. Lorsque nous parlons ASCII et nous fait regarder la table ASCII, ce qui est fait est de nous donner une hotte sous le regard à la façon dont l'ordinateur représente en fait majuscule et le chiffre 7 et une virgule et un point d'interrogation. L'ordinateur dispose également des moyens spéciaux pour représenter le nombre 7 comme un entier. Il a une façon spéciale pour représenter le nombre 7 en tant que nombre à virgule flottante, et ceux qui sont très différents. Transtypage est de savoir comment vous dire à l'ordinateur "Hé, je veux que vous convertissez d'une représentation à une autre représentation. " Pourquoi ne pas jeter un oeil à ça. 

Je voudrais aussi jeter un oeil à court sur les bibliothèques et le court sur les compilateurs. Ceux parler du processus de compilation, ce qu'est une bibliothèque, et passer en revue certaines de ces questions que vous pourriez vous poser. Questions sur semaine 1 matériel? Y at-il des sujets qui semblent ici en intimidant que vous aimeriez aborder? Je suis en train de souffler à travers la plupart de ces sujets précédents afin que nous puissions arriver à pointeurs et faire un peu de récursivité. Pensées? Rien recouvrir? Temps pour un peu de chocolat peut-être? Les gars, vous travaillez à travers elle. Je vais continuer à siroter mon café. Semaine 2. Bon appel, bon appel. Lors de la semaine 2, nous avons parlé un peu plus sur les fonctions. 

Dans les premiers ensembles problème années, nous n'avons pas vraiment écrire des fonctions à tous autre que ce qui fonctionne? [Étudiants] Principal. >> Main, exactement. Et nous avons vu les différents costumes que principal porte. Il ya celui dans lequel il ne prend aucun argument, et nous venons de dire vide entre les parenthèses, et puis il ya l'autre où nous voulons prendre des arguments de ligne de commande, et comme nous l'avons vu, c'est là que vous avez argc int et string argv ensemble ou maintenant que nous avons réellement exposés chaîne à la char * qu'il est nous allons commencer à l'écrire en tant que char * argv puis entre parenthèses. En 3 Set problème, les gars vous vu un tas de fonctions, et vous mis en place un tas de fonctions, dessiner, regarder, bousculade. Les prototypes ont toutes été écrites là pour vous. 

Ce que je voulais parler ici avec des fonctions très rapidement est qu'il ya 3 parties à eux chaque fois que vous écrivez une fonction. Vous devez spécifier le type de retour de la fonction. Vous devez spécifier un nom pour la fonction, puis vous devez spécifier la liste des arguments ou la liste des paramètres. Par exemple, si je devais écrire une fonction pour résumer un ensemble de nombres entiers et puis revenez me voir la somme quel serait mon type de retour si je voulais résumer entiers, puis retourner la somme? Puis le nom de la fonction. Si je vais de l'avant et écrire en vert, cette partie est le type de retour. Cette partie est le nom. Et puis entre parenthèses C'est là que je donne des arguments, souvent abrégé en args, parfois appelés params pour les paramètres. Et si vous en avez un, il vous suffit de spécifier l'un. Si vous avez plusieurs, vous les séparer par une virgule. Et pour chaque argument que vous lui donner 2 choses qui sont-Kevin? [Kevin] Vous devez donner le type et le nom. Et puis le nom, et le nom est le nom que vous allez utiliser se référer à cet argument dans la fonction somme, au sein de la fonction que vous êtes en train d'écrire. 

Vous n'avez pas à, par exemple, si je vais résumer, dire, un tableau d'entiers-we'll do tableau int, et je vais me donner quelques accolades il- puis quand je passe d'un tableau à la fonction somme Je passe à la première position de la liste des arguments. Mais le tableau que je passe à ne pas avoir le nom arr. Arr va être comment je me réfère à cet argument dans le corps de la fonction. L'autre chose que nous devons prendre en compte, et ce qui est légèrement différent de fonctions, mais je pense que c'est un point important, est que, dans C lorsque j'écris une fonction comme ceci comment puis-je savoir combien d'éléments sont dans ce tableau? Il s'agit en quelque sorte d'une question piège. Nous en avons parlé un peu dans la section de la semaine dernière. Comment puis-je savoir le nombre d'éléments à l'intérieur d'un tableau en C? Est-il possible? 

Il s'avère qu'il n'y a aucun moyen de savoir. Vous devez passer en séparément. Il ya un truc que vous pouvez faire si vous êtes dans la même fonction dans laquelle le réseau a été déclaré, et vous travaillez avec un tableau de pile. Mais cela ne fonctionne que si vous êtes dans la même fonction. Une fois que vous passer un tableau à une autre fonction ou si vous avez déclaré un tableau et vous mettez ce tableau sur le tas, vous avez utilisé malloc  et ce genre de choses, alors tous les paris sont éteints. Ensuite, vous avez réellement à faire circuler un argument spécial ou un autre paramètre vous dire combien grande est la matrice. Dans ce cas, je voudrais utiliser une virgule-je suis désolé, ça va hors de l'écran ci- et je voudrais passer un autre argument  et appelez-le len int pour la longueur. 

Une chose qui pourrait arriver sur le quiz vous demande d'écrire ou de mettre en œuvre une fonction particulière appelée quelque chose. Si nous ne vous donne pas le prototype, donc tout cela ici, tout ce gâchis est appelé la déclaration de fonction ou le prototype de fonction, c'est l'une des premières choses que vous aurez envie de clouer si elle n'est pas donnée à vous tout de suite sur le questionnaire. L'autre truc que j'ai appris, c'est que dire que nous ne vous donner un prototype pour une fonction, et nous dire: «Hé, vous avez à écrire." A l'intérieur des accolades que vous avez sur le quiz si vous remarquez qu'il ya un type de retour et vous remarquerez que le type de retour est autre chose que nul, ce qui signifie que la fonction ne retourne rien, puis une chose que vous voulez faire est d'écrire une sorte de déclaration de retour à la fin de la fonction. Retour, et dans ce cas, nous allons mettre un blanc parce que nous voulons remplir le vide. Mais cela fait réfléchir dans le bon sens sur la façon dont je vais aborder ce problème? Et il vous rappelle que vous allez avoir à renvoyer une valeur à l'appelant de la fonction. 

Ouais. >> [Étudiants] Est-ce que le style s'applique pas lorsque nous écrivons du code sur le quizz? Tels que l'indentation et ce genre de choses? >> [Étudiants] Ouais. Non, pas autant. Je pense que beaucoup de-c'est quelque chose que nous allons préciser sur le questionnaire le jour de, mais en général se soucier # includes et ce genre de choses, c'est un peu en dehors. [Étudiants] Avez-vous besoin de commenter votre code écrit à la main? Avez-vous besoin de commenter votre code écrit à la main? Commentant est toujours bon si vous êtes inquiet à propos de crédit partiel ou si vous voulez communiquer votre intention de la niveleuse. Mais moi, encore une fois, permettra de clarifier le questionnaire lui-même et le jour quiz, mais je ne crois pas que vous serez tenus de rédiger des commentaires, non. Généralement non, mais il est certainement le genre de chose où vous pouvez communiquer votre intention, comme "Hey, c'est là où je vais avec elle." Et parfois cela peut aider à crédit partiel. Cool. 

Basil. [Basil] Quelle est la différence entre déclarer, par exemple, int lang dans les arguments ou paramètres par rapport à la déclaration d'une variable à l'intérieur de la fonction? Wow, le café est descendu de la trachée. [Basil] Comme les choses qui nous voulons mettre en arguments. Oui, c'est une très bonne question. Comment choisissez-vous les choses que vous voulez mettre dans les arguments par rapport à ce que vous devriez faire à l'intérieur de la fonction? Dans ce cas, nous avons inclus ces deux arguments que parce qu'ils sont quelque chose que la personne qui va utiliser la fonction somme doit préciser les choses. 

La fonction somme, comme nous en avons parlé, n'a aucun moyen de savoir la taille du tableau est qu'elle reçoit de son appelant ou celui qui utilise la fonction somme. Il n'a aucun moyen de savoir la taille que tableau est. La raison pour laquelle nous passons dans cette longueur ici comme un argument c'est parce que c'est quelque chose que nous sommes fondamentalement indiquer à l'appelant de la fonction, celui qui va utiliser la fonction somme, "Hé, non seulement vous devez nous donner un tableau d'entiers, vous avez également à nous dire la taille du tableau que vous nous avez donné est. " [Basil] Ceux qui seront tous deux arguments de ligne de commande? Non, ce sont des arguments réels que vous passez à la fonction. 

Permettez-moi de faire une nouvelle page ici. [Basil] Comme le nom passerait- [Nate H.] Si j'ai int main (void), et je vais mettre dans mon retour 0 ici-bas au fond, et dire que je veux appeler la fonction somme. Je veux dire int x = sum (); Pour utiliser la fonction somme je dois passer à la fois dans le tableau que je voudrais résumer et la longueur du réseau, de sorte que c'est le cas en supposant que j'avais un tableau d'entiers, dire que j'ai eu Numbaz int [] = 1, 2, 3, type d'utilisation que piraté syntaxe là, alors ce que je ferais, c'est en somme je voudrais passer en à la fois Numbaz et le chiffre 3 de dire la fonction sum "Ok, voici le tableau que je veux vous faire la somme." «Ici, c'est sa taille." Est-ce logique? Est-ce que cela répond à votre question? 

À bien des égards c'est le cas en parallèle ce que nous faisons avec les principaux quand nous avons les arguments de ligne de commande. Un programme comme César chiffre, par exemple, ce qui est nécessaire arguments de ligne de commande ne serait pas en mesure de faire quoi que ce soit. Il ne saurait pas comment crypter si vous n'avez pas dit ce qu'elle touche à utiliser ou si vous ne l'avez pas dit ce que vous vouliez chaîne à chiffrer. Incitation pour l'entrée, c'est là que nous avons 2 mécanismes différents pour la prise d'entrée en provenance de l'utilisateur, des informations pour la prise en provenance de l'utilisateur. Pour un problème Set 1, nous avons vu ce getInt, GetString, ainsi GetFloat des invites d'intervention, et c'est ce qu'on appelle l'aide du flux d'entrée standard. C'est légèrement différent. C'est quelque chose que vous pouvez faire à un moment donné, par opposition à Lorsque vous lancez le programme, lorsque vous démarrez le programme en cours. Les arguments de ligne de commande sont tous spécifiés lorsque vous démarrez le programme lancé. Nous avons été de mélanger les deux d'entre eux. Lorsque nous utilisons des arguments à une fonction, c'est un peu comme arguments de ligne de commande à principal. C'est lorsque vous appelez la fonction, vous devez le dire exactement ce dont il a besoin pour accomplir ses tâches. Une autre bonne chose à regarder, et je vous laisse regarder dans votre temps libre, et elle était couverte dans le quiz était cette notion de champ et des variables locales par rapport à des variables globales. Faites attention à cela. 

Maintenant que nous arrivons à ce genre de choses d'autres, à la semaine 3, nous avons commencé à parler sur la recherche et le tri. Recherche et de tri, au moins en CS50, est beaucoup une introduction à certaines des parties les plus théoriques de l'informatique. Le problème de la recherche, le problème du tri sont grandes, les problèmes canoniques. Comment trouvez-vous un numéro particulier d'un tableau de milliards de nombres entiers? Comment trouvez-vous un nom particulier à l'intérieur d'un annuaire téléphonique qui est stocké sur votre ordinateur portable? Et si nous introduisons cette notion de temps d'exécution asymptotiques pour vraiment quantifier combien de temps, à quel point ces problèmes sont, combien de temps ils prennent à résoudre. En, je crois, 2011 au quiz il ya un problème que je pense mérite couvrant très rapidement, ce qui est celui-ci, problème 12. Oh non, c'est Omega. 

Ici, nous parlons de la durée d'exécution la plus rapide possible pour un algorithme particulier, puis le temps d'exécution plus lente possible. Cette Omega et O ne sont que des raccourcis. Ils sont raccourcis typographiques pour dire la rapidité dans le meilleur des cas possibles sera notre course algorithme, et la lenteur dans le pire des cas possibles sera notre algorithme de fonctionner? Faisons un couple de ceux-ci, et ceux-ci ont également été couverts dans le court sur la notation asymptotique, que je recommande fortement. Jackson a fait un très bon travail. Avec binaire de recherche, nous parlons de recherche binaire comme étant un algorithme, et nous avons l'habitude en parler en termes de son grand O. Quel est le grand O? Quel est le temps d'exécution plus lente possible de recherche binaire? [Étudiants] N ²? Fermer, je suppose semblable. C'est beaucoup plus rapide que cela. [Étudiants] binaire? >> Ouais, recherche binaire. [Étudiants] Il est log n. Log n, alors qu'est-ce que vous n veut dire? Il divise par deux à chaque itération. Justement, dans le cas le plus lent possible, dire si vous avez un tableau trié d'un million de nombres entiers et le nombre que vous cherchez est soit le premier élément dans la matrice ou le dernier élément dans le même tableau. Rappelez-vous, l'algorithme de recherche binaire fonctionne en regardant l'élément central, voir si c'est le match que vous recherchez. Si c'est le cas, tant mieux, vous l'avez trouvé. 

Dans le meilleur des cas possible, comment est la vitesse d'exécution binaire de recherche? [Etudiants] 1. 1, il est temps constant, grand O de 1. Ouais. [Étudiants] J'ai une question. Quand vous dites que vous n, que vous voulez dire par rapport à la base 2, non? Oui, alors c'est autre chose. Nous disons n log, et je suppose que quand j'étais à l'école secondaire J'ai toujours pensé que c'était log base 10. Ouais, donc oui, log 2 de base est typiquement ce que nous utilisons. Pour en revenir à la recherche binaire, si vous êtes à la recherche pour les deux l'élément à la fin ou l'élément à l'origine, parce que vous commencez au milieu et puis vous jetez selon moitié ne répondent pas aux critères que vous cherchez, et vous allez à la prochaine moitié et la moitié prochaine et le prochain demi. Si je suis à la recherche du plus grand élément dans le tableau millions entier Je vais la réduire de moitié tout au plus log de 1 million de fois avant de finalement tester et voir ce que l'élément que je recherche est le plus grand ou le plus haut dans l'indice de la matrice, et cela prendra du log n, log de 1 million de fois. 

Tri à bulles. Ne vous vous souvenez de l'algorithme de tri à bulles? Kevin, peux-tu me donner un bref récapitulatif de ce qui s'est passé dans l'algorithme de tri à bulles? [Kevin] Fondamentalement, il passe par tout dans la liste. Il se penche sur les deux premiers. Si le premier est plus grand que le second il les swaps. Puis il compare les deuxième et troisième, la même chose, swaps, troisième et quatrième, tout le chemin vers le bas. Plus grands nombres suivra jusqu'à la fin. Et après de nombreuses boucles toutefois vous avez terminé. Exactement, ce que Kevin a dit, c'est que nous allons regarder les plus grands nombres bulle jusqu'à l'extrémité de la rangée. Par exemple, ne vous ennuierait de nous promener dans cet exemple, si ce n'est notre tableau? [Kevin] Vous prendrez 2 et 3. 3 est plus grand que 2, de sorte que vous les échanger. [Nate H.] Bon, alors nous échangeons ceux-ci, et on obtient 2, 3, 6, 4 et 9. [Kevin] Puis vous comparez les 3 et 6. 3 est inférieur à 6, de sorte que vous les laisser, et 6 et 4, vous les échanger parce que 4 est inférieur à 6. [Nate H.] Bon, alors j'ai 2, 3, 4, 6, 9. [Kevin] Et 9 est plus grand que 6, de sorte que vous laissez. Et vous voudriez revenir en arrière à travers elle à nouveau. 

[Nate H.] Suis-je fait en ce moment? >> [Kevin] No. Et pourquoi suis-je pas fait à ce point? Parce qu'il ressemble à mon tableau est trié. Je suis à la recherche dans ce domaine. [Kevin] Traversez-le à nouveau et assurez-vous qu'il n'y a pas d'autres swaps avant de pouvoir arrêter complètement. Exactement, vous devez donc continuer à travers et assurez-vous qu'il n'ya pas de swaps que vous pouvez faire à ce stade. C'était vraiment de la chance, comme vous l'avez dit, que nous nous sommes retrouvés que d'avoir à faire 1 passe à travers et nous triées. Mais pour ce faire, dans le cas général, nous allons effectivement obligé de le faire encore et encore. Et en fait, il s'agissait d'un exemple de cas le mieux possible, comme nous l'avons vu dans le problème. Nous avons vu que l'affaire a été mieux possible n. Nous sommes allés à travers le tableau 1 fois. Quel est le pire cas possible de cet algorithme? [Kevin] N ². Et qu'est-ce que ce regard parfait? Que serait un coup d'oeil ensemble comme ça prendrait du temps ² n? [Kevin] [inaudible] triées. Exactement, donc si je devais le tableau 9, 7, 6, 5, 2, d'abord le 9 serait bulle sur toute la hauteur. Après 1 itération nous aurions 7, 6, 5, 2, 9. Puis, le 7 serait bouillonner, 6, 5, 2, 7, 9, et ainsi de suite et ainsi de suite. 

Nous serions obligés de passer par le tableau entier n fois, et vous pouvez réellement obtenir un peu plus précis que ce car une fois que nous sommes passés de 9 tout le chemin vers le haut dans sa position possible dernière nous savons que nous n'avons jamais à comparer à cet élément nouveau. Une fois que nous commençons à faire barboter le 7 jusqu'à nous savons que nous pouvons nous arrêter une fois que le 7 est juste avant le 9 puisque nous avons déjà comparé le 9 à elle. Si vous faites cela de manière intelligente, ce n'est pas vraiment, je pense, que beaucoup de temps. Vous n'allez pas comparer tous les possibles combinaisons de [inaudible] à chaque fois que vous passez par chaque itération. Mais tout de même, quand on parle de cette borne supérieure nous disons que vous cherchez à n ² comparaisons tout au long. 

Revenons, et depuis que nous avons commencé à avoir un peu à court de temps Je dirais que vous devez absolument passer par le reste de ce tableau, remplir tout ça. Pensez à des exemples. Pensez à des exemples concrets. C'est vraiment pratique et utile de le faire. Y puiser. C'est le genre de tableau que vous passez par en informatique vous devriez vraiment commencer à savoir ce cœur par. Ce sont le genre de questions que vous obtenez dans les interviews. Ce sont des sortes de choses qui sont bonnes à savoir, et de réfléchir à ces cas limites, de discerner comment penser sachant que pour la bulle trier le tableau le plus sombre pour trier avec ça, c'est celui qui est dans l'ordre inverse. 

Pointeurs. Parlons un peu de pointeurs. Dans les dernières minutes que nous avons ici Je sais que c'est quelque chose avec le fichier I / O qui est assez nouveau. Lorsque nous parlons des pointeurs de la raison pour laquelle nous voulons parler de pointeurs C'est parce que, premièrement, quand nous travaillons en C nous sommes vraiment à un niveau relativement bas par rapport aux langages de programmation les plus modernes. Nous sommes effectivement en mesure de manipuler les variables en mémoire, savoir où ils sont en fait situés dans notre mémoire. Une fois que vous avez continué à prendre des cours de système d'exploitation que vous verrez que c'est, encore une fois, une sorte d'abstraction. Ce n'est pas vraiment le cas. Nous avons la mémoire virtuelle qui se cache ces détails de notre part. 

Mais pour l'instant vous pouvez supposer que si vous avez un programme, par exemple, lorsque vous démarrez l'exécution de votre programme de chiffrement de César Je vais revenir à mon iPad très rapidement- qu'au tout début de votre programme, si vous avez, par exemple, 4 Go de RAM sur votre ordinateur portable, vous êtes mis de côté ce morceau, et nous appellerons cette RAM. Et cela commence dans un endroit que nous allons appeler le 0, et se termine à un endroit que nous appellerons 4 gigaoctets. Je ne peux pas écrire. L'homme, qui est piraté. Lorsque votre programme exécute le système d'exploitation sculpte la RAM, et il précise les différents segments pour les différentes parties de votre programme à vivre po Ici-bas, ce domaine est une sorte de zone neutre de l'homme. Lorsque vous montez un peu plus loin ici vous avez réellement l'endroit où le code de votre vie du programme. Ce code binaire réel, que fichier exécutable se fait chargé en mémoire lorsque vous exécutez un programme, et il vit dans le segment de code. Et que votre programme exécute le processeur regarde ce segment de code de comprendre quelle est la prochaine instruction? Quelle est la prochaine ligne de code que j'ai besoin d'exécuter? 

Il ya aussi un segment de données, et c'est là que les constantes de chaîne sont stockés que vous avez utilisé. Et puis plus loin là-haut, c'est cet endroit appelé le tas. Nous avons accès à la mémoire là-bas à l'aide de malloc, puis vers le haut de votre programme il ya la pile, et c'est là que nous avons joué pour la plupart du début. Ce n'est pas à l'échelle ou quoi que ce soit. Beaucoup de ce qui est très dépendant de la machine, système d'exploitation à charge, mais cela est relativement comment les choses se chunked place. Lorsque vous exécutez un programme et vous déclarez une variable appelée x- Je vais faire une autre boîte en bas, et cela va être ainsi RAM. Et je vais regarder. Nous allons dessiner des lignes brisées pour indiquer qu'il s'agit juste d'une petite section de la RAM et pas tout comme nous attirons vers le haut. 

Si je déclare une variable entière nommée x, alors ce que je réellement obtenir une cartographie qui est stockée dans la table de symboles de programme de ma qui relie le nom x dans cette région du mémoire que j'ai rédigé ici entre les barres verticales. Si j'ai une ligne de code dans mon programme qui dit x = 7 le processeur sait "Oh, d'accord, je sais que la vie des x dans ce lieu de mémoire». «Je vais aller de l'avant et écrire un 7 là-bas." Comment sait-il quel endroit ce n'est dans la mémoire? Eh bien, que tout est fait au moment de la compilation. Le compilateur prend soin d'affecter où chacune des variables vont aller et la création d'une cartographie spécifique ou non reliant les points entre un symbole et où il va, d'une variable nom et où il va vivre dans la mémoire. Mais il s'avère que nous pouvons y accéder à nos programmes ainsi. Cela devient important quand on commence à parler de quelques-unes des structures de données, qui est un concept que nous allons vous présenter plus tard. 

Mais pour l'instant, ce que vous pouvez savoir, c'est que je peux créer un pointeur vers cet endroit, x. Par exemple, je peux créer une variable pointeur. Lorsque nous créons une variable pointeur on utilise la notation étoile. Dans ce cas, cela dit je vais créer un pointeur vers un int. C'est un type comme les autres. Nous lui donnons une variable comme y, puis nous avons mis en elle égale à l'adresse, à une adresse. Dans ce cas, nous pouvons mettre au point y à x en prenant l'adresse de x, ce que nous faisons avec ce esperluette, puis nous avons mis à y pointer vers elle. Ce qui ne l'essentiel est de savoir si nous regardons notre RAM cela crée une variable distincte. Il va y appeler, et lorsque cette ligne de code s'exécute il va vraiment créer un pointeur peu que nous en général dessiner comme une flèche, et il y met au point à x. Oui. [Étudiants] Si x est déjà un pointeur, pourriez-vous faire int * y = x au lieu d'avoir l'esperluette? Oui. Si x est déjà un pointeur, vous pouvez définir 2 pointeurs égales les unes aux autres, dans ce cas, y aurait pas signaler à x, mais il rappelle à tout ce que x pointe. Malheureusement, nous n'avons plus de temps. 

Ce que je voudrais dire à ce stade, on peut parler de cette ligne, mais je dirais de commencer à travailler à travers ce problème, n ° 14. Vous pouvez voir qu'il ya déjà un peu rempli pour vous ici. Vous pouvez voir que lorsque nous déclarons 2 pointeurs, int * x et y *, et notez que pointer du * côté de la variable est quelque chose qui a été fait l'année dernière. Il s'avère que ceci est similaire à ce que nous faisons cette année. Il n'a pas d'importance où vous écrivez le fichier * lorsque vous êtes en déclarant le pointeur. Mais nous avons écrit l'* à côté du type parce que il est très clair que vous déclarez une variable pointeur. Vous pouvez voir que la déclaration des 2 pointeurs nous donne 2 boîtes. Ici, lorsque nous avons créé x est égal à malloc ce que cela veut dire met de côté la mémoire dans le tas. Cette petite boîte ici, ce cercle, est situé sur le tas. X est orientée vers celui-ci. Notez que y est pas encore pointant vers quoi que ce soit. Pour obtenir de mémoire pour enregistrer le numéro 42 dans x nous devrions utiliser ce notation? [Étudiants] * x = 42. Exactement, * x = 42. Cela signifie suivre la flèche et jeter 42 en bas. Voici où nous installons y et x, nous avons y pointant vers x. Encore une fois, cela est juste comme ce que Kevin a dit où nous installons y égal à x. Y ne pointe pas vers x. Au contraire, il pointe vers ce qui est x désignant aussi bien. 

Et puis enfin, dans cette dernière case, il ya 2 choses possibles que nous pourrions faire. Premièrement, nous pourrions dire * x = 13. L'autre chose est que nous pourrions dire, Alex, savez-vous ce que nous pourrions faire ici? On pourrait dire * x = 13 ou- [Étudiants] Vous pouvez dire tout ce que int. [Nate H.] Si cela était appelée une variable int nous pourrions le faire. On pourrait aussi dire * y = 13, car ils sont tous deux pointant vers le même endroit, nous pouvons donc utiliser soit variable pour y arriver. Ouais. >> [Étudiants] Que faudrait-il ressembler si nous disons simplement x int est de 13? Ce serait de déclarer une nouvelle variable appelée x, qui ne fonctionnerait pas. Nous aurions une collision, car nous avons déclaré que x soit un pointeur vers le haut ici. [Étudiants] Si nous avons juste eu cette déclaration par lui-même ce qui ressemblerait-il en termes de cercle? Si nous avions x = 13 alors nous aurions une boîte, et plutôt que d'avoir une flèche sortir de la boîte, nous avions le dessiner comme un simple 13. [Étudiants] Dans la boîte. D'accord. 

Merci d'avoir regardé, et bonne chance Quiz 0. [CS50.TV]