[Powered by Google Translate] [Hoofdstuk 4] [minder comfortabel] [Nate Hardison] [Harvard University] [Dit is CS50.] [CS50.TV] 

Oke, welkom terug te vinden in hoofdstuk. In paragraaf van deze week gaan we een paar dingen te doen. We gaan eerst recap Probleem Set 2, dat is de Caesar en Vigenère probleem set. En dan gaan we duiken in Quiz 0 beoordeling en breng een beetje tijd recapping wat we hebben gesproken over in elk van de lezingen tot nu toe, en we doen ook een paar problemen van vorig jaar quizzen. Op die manier jullie een goede manier voor te bereiden voor. 

Om te beginnen, ik heb opgestart een paar goede oplossingen voor het vorige probleem set, Probleem Set 2, in deze ruimte. Als jullie allemaal raken deze link, en als je op mijn naam en klik op mijn eerste herziening je zult zien caesar.c, dat is precies wat ik ben op zoek naar. Laten we praten over dit heel snel. Dit is slechts een monsteroplossing. Dit is niet noodzakelijkerwijs de perfecte oplossing. Er zijn verschillende manieren om dit te schrijven, maar er zijn een paar dingen die ik wilde benadrukken die ik zag toen ik de indeling, veel voorkomende fouten die ik denk deze oplossing heeft een zeer goed werk van handling. 

De eerste is, dat iets header geplaatst op de top. Op de lijnen 1 tot en met 7 ziet u de details, wat precies dit programma aan het doen is. Een goede standaard praktijk wanneer je C-code schrijven ongeacht of uw programma is opgenomen in een bestand of of het nu verdeeld over meerdere bestanden is om een ​​soort van oriënteren geplaatst op de top. Dit is ook voor mensen die naar buiten gaan en code schrijven in de echte wereld. Dit is waar ze zetten copyright informatie. Hieronder staan ​​de # omvat. Op lijn 16 is er dit # define, die we zullen terugkomen om in slechts een beetje. En dan als de functie begint, zodra de belangrijkste start, omdat dit programma is allemaal in een enkele functie het eerste wat er gebeurt en dit is zeer idiomatisch en typisch voor een C-programma dat duurt in de command line argumenten-is dat het onmiddellijk controleert 

voor het argument tellen, argc. Hier zien we dat dit programma is 2 argumenten precies verwacht. Vergeet niet er is dat eerste argument is dat de special one dat is altijd de naam van het programma dat wordt uitgevoerd, de naam van het uitvoerbare bestand. En dus wat dit doet is het voorkomt dat de gebruiker van het uitvoeren van het programma met meer of minder argumenten. De reden dat we willen om weg te controleren op dit recht is omdat we kunnen niet echt toegang tot deze argv serie hier betrouwbaar totdat we gecontroleerd om te zien hoe groot het is. 

Een van de gemeenschappelijke fouten die ik zag was mensen zouden meteen gaan in en grijper argv [1]. Ze zouden grijpen de sleutel argument uit de array en doe de een tot en met i controleren op het, en ze doen testen van argc en de volgende test of het eerste argument inderdaad een geheel getal tegelijkertijd, en dat is niet omdat werken in het geval dat er geen leveringen van argumenten je zult grijpen een argument dat er niet is of een poging om een ​​die er niet is te grijpen. 

De andere grote ding dat je zou moeten opvallen is dat u altijd wilt afdrukken een soort van nuttige foutmelding De gebruiker moet oriënteren. Ik weet zeker dat je hebt alle programma's uitvoeren waarin alle van een plotselinge het crasht, en je krijgt deze belachelijke kleine dialoogvenster dat verschijnt en zegt iets vreselijk cryptische en misschien geeft u een foutcode of iets dergelijks dat heeft geen zin. Dit is waar je echt iets wilt behulpzaam te bieden en gericht op de gebruiker, zodat wanneer ze het uit te voeren gaan ze "Oh," gezicht palm. "Ik weet precies wat te doen. Ik weet hoe dit op te lossen." 

Als u niet wilt afdrukken een bericht, dan moet je eigenlijk omhoog beëindigen het verlaten van de gebruiker om te gaan onderzoeken uw broncode om erachter te komen wat er mis ging. Er zijn ook een aantal keer dat u gebruik maken van verschillende foutcodes. Hier zijn we net gebruikt een te zeggen dat er is een fout opgetreden, Er is een fout opgetreden, er is een fout opgetreden. Grotere programma's, vaak programma's die worden aangeroepen door andere programma's, zal terugkeren een soort van speciale foutcodes in verschillende scenario's programmatisch communiceren wat je anders zou gewoon gebruik maken van een mooi Engels boodschap voor. Cool. Omdat we werken naar beneden, kun je zien dat we trek de sleutel uit. Wij testen om te zien of de sleutel past. We krijgen een bericht van de gebruiker. De reden dat we het doen in dit te doen terwijl loop-en dit is iets dat wij doen in een klein beetje, maar het blijkt dat als je typt controle D als je dat GetString prompt op de terminal wat dat eigenlijk doet is het stuurt een speciaal teken het programma. Het heet de ELF of het einde van het bestand karakter. En in dat geval, zal onze boodschap string zijn null, dus dit was niet iets wat we voor ingecheckt het probleem zich. 

Maar als we verder gaan, nu we begonnen te praten over pointers en dynamische geheugentoewijzing op de heap, controleren op null wanneer u een functie die misschien terug null als een waarde is iets dat je wilt krijgen in de gewoonte van het doen. Dit is hier voornamelijk ter illustratie. Maar als je dat doet zie GetString in de toekomst, dus vanaf Probleem Set 4 op, wil je dit in gedachten te houden. Nogmaals, dit is geen probleem voor Probleem Set 3 ofwel omdat we hadden niet onder het nog niet. Tot slot komen we bij dit deel, waar we naar de belangrijkste encryptie lus, en er zijn een paar dingen aan de hand. Ten eerste, we itereren over het hele bericht string zelf. Hier hebben we hielden de strlen oproep in de staat, die een aantal van u hebben erop gewezen is niet een geweldige manier om te gaan. Het blijkt in dit geval is het niet ook geweldig, deels omdat we het wijzigen van de inhoud van het bericht zelf in de for-lus, dus als we een bericht dat is 10 tekens lang zijn, de eerste keer dat we beginnen met dat voor lus strlen wat zal terugkeren? 10. 

Maar als we dan bericht te wijzigen, zeggen dat we te wijzigen zijn 5de karakter, en we gooien in een \ 0 personage in de 5e positie, op een volgende iteratie strlen (bericht) keert niet terug wat het deed de allereerste keer dat we herhaald, maar het zal in plaats daarvan terug 5 omdat we gooide in dat null-terminator, en de snaar lengte wordt weergegeven door de positie van die \ 0. In dit geval, is dit een geweldige manier om te gaan omdat we wijzigen het op zijn plaats. Maar je merkt dat dit eigenlijk verrassend eenvoudig te coderen als je kunt krijgen de wiskunde correct. Het enige dat nodig is, is het al dan niet de letter controleren of u op zoek bent naar is hoofdletters of kleine letters. 

De reden dat we alleen maar te controleren op dat, en we hoeven niet te controleren op het is alfa geval omdat als een teken een hoofdletter of als het kleine letters dan is het zeker een alfabetisch teken, omdat we niet over hoofd-en kleine cijfers. Het andere wat we doen-en dat is een beetje lastig- is die we hebben aangepast de standaard Caesar cipher formule die wij in het probleem set specificatie. Wat is hier anders is dat we afgetrokken in het geval hoofdletters hoofdletter A, en dan hebben we toegevoegd hoofdletter A terug in eind. 

Ik ken een paar van jullie hebben dit gedaan in de code. Heeft een van jullie dit doen in uw inzendingen? Jij hebt dit gedaan. Kunt u uitleggen wat dit doet, Sahb? Door het aftrekken van het uit, want je hebt een mod direct na het, je moet het nemen, zodat op die manier krijg je [hoesten] positie. En vervolgens door het toe te voegen later terug kunt verschuiven over degene die je wilde. Ja, precies. Wat Sahb zei was dat als we willen toevoegen onze boodschap en onze toets samen en dan mod dat mod dat door NUM_LETTERS, als we onze boodschap niet eerst te schalen naar de juiste 0 tot 25 range, dan kunnen we misschien uiteindelijk het krijgen van een echt raar nummer omdat de waarden die we kijken naar als we kijken naar bericht [i], als we kijken naar de i-karakter van onze plain-text-bericht, is een waarde ergens in deze 65-122 serie gebaseerd op de ASCII waarden voor hoofdletters A t kleine z. En dus toen we mod door 26 of door NUM_LETTERS, want dat was onze # define in de rechterbovenhoek hier, dat gaat ons een waarde die in de 0-25 serie, en we moeten een manier vinden om vervolgens opgeschaald dat een back-up en krijg het in de juiste ASCII-bereik. De eenvoudigste manier om dat te doen is om gewoon alles op schaal in het bereik 0 tot 25 om te beginnen en weer verschuiven alles aan het eind. 

Een andere veel voorkomende fout die ik zag mensen tegenkomen is dat als u niet daadwerkelijk te doen scaling meteen en u bij elkaar optelt en toets en je ze toevoegt, zeg, in een char variabele, het probleem met die is sinds bericht [i] is een relatief groot aantal te beginnen- herinner me het is ten minste 65 als het een hoofdletter- als u een grote sleutel, zeg, zoiets als 100, en u bij elkaar optelt die 2 in een signed char je gaat een overloop te krijgen. Je gaat naar een waarde die groter is dan 127 te krijgen, dat is de grootste waarde die een char variabele kan opslaan. Nogmaals, dat is waarom je dat zou willen dat soort dingen om mee te beginnen doen. Sommige mensen werd dat geval door het doen van een of ander en het testen van om te zien of het zou overstromen voor u dit doet, maar op deze manier krijgt rond dat. En dan in deze oplossing hebben we uitgeprint de hele reeks aan het einde. Andere mensen uitgeprint een teken tegelijk. Beide zijn geweldig. Op dit punt, hebben jullie nog vragen, opmerkingen over dit? Dingen die je wilt, dingen die je niet vinden? 

Ik had een vraag. Misschien heb ik het gemist tijdens uw uitleg, maar hoe werkt dit programma overslaan ruimtes voor het aansluiten van de sleutel van de lengte van de tekst? Dit is gewoon Caesar cipher. >> Oh, sorry, ja. Ja, we zien. In de Caesar cipher kregen we rond die, omdat we alleen omgedraaid karakters. We hebben alleen gedraaid als ze waren hoofdletters of kleine letters. Jullie een goed gevoel over dit? Voel je vrij om dit huis te kopiëren, neem het, Vergelijk het met wat jullie geschreven. Zeker te voelen vrij om te sturen vragen over. En nogmaals, beseffen dat het doel hier met uw probleem stelt is niet om jullie een perfecte code voor uw probleem sets te schrijven. Het is een leerzame ervaring. Ja. 

Terug naar de do while lus, als het gelijk is aan nul, dus null gewoon niets betekent, maar ze druk op enter? Null is een speciale pointer-waarde, en we gebruiken null wanneer we willen zeggen we een pointer variabele die wijst niets. En zo typisch dat betekent dat deze variabele, dit bericht variabele is leeg, en hier, omdat we met behulp van de CS50 speciale string type, wat is de CS50 string type? Heb je gezien wat het is als David trok het kap in college? Het is een funky, het is een pointer, toch? Oke, ja. >> Het is een char *. En dus we echt kunnen vervangen deze hier bij char * bericht, en dus de GetString functie, als het niet met goed gevolg een string te krijgen van de gebruiker, kan niet ontleden een string, en een geval waarin het niet kunnen ontleden een string is als de gebruiker typt het einde van het bestand karakter, de controle D, dat is niet iets wat je normaal gesproken doen, maar als dat gebeurt dan is de functie zal terugkeren dit null-waarde als een manier om te zeggen "He, heb ik niet een string." Wat zou er gebeuren als we niet plaatsen message = null, dat is iets dat we nog niet aan het doen? Waarom zou dat hier een probleem? Omdat ik weet dat we een beetje gepraat in lezing over het geheugen lekken. Ja, laten we dat doen, en laten we zien wat er gebeurt. 

Basil's vraag was wat er gebeurt als we niet echt Deze message = null test? Laten we naar boven naar de top. Jullie kunnen dit uitgecommentarieerd. Eigenlijk, ik sla het op in een herziening. Dit Wijziging 3 zijn. Wat je moet doen om dit programma uit te voeren is dat je zult moeten dit vistuig pictogram hier, en je moet een argument aan toe te voegen. Je moet geven de sleutel argument omdat we langs wilt op een opdrachtregel argument. Hier ga ik geef het de nummer 3. Ik hou van 3. Nu zoomen weer uit, het uitvoeren van het programma. Het draait, samenstellen, bouwen. Daar gaan we. Het is klaar om te worden gevraagd. Als ik in iets typ als hello-waar ging die verder gaan? Oh, mijn programma duurde te lang om te draaien. Ik was jawing te lang. Hier gaat. Nu typ ik in hello. We zien dat het een goed versleutelt. Wat gebeurt er nu als we prompt GetString aan null terug te keren? Vergeet niet, ik zei dat we dat deden door het indrukken van controle D op hetzelfde moment. Ik zal hier omhoog. We zullen weer draaien. Building. Daar gaat hij. Nu als ik controle D geraakt Ik heb deze lijn die zegt opt/sandbox50/bin/run.sh, Segmentation fault. Hebben jullie dat eerder gezien? 

[Student] Waarom is er geen >> Sorry? [Student] Waarom is er geen core dump in dit geval? De kern dump is-de vraag is waarom is er geen core dump hier? De vraag is dat er ook mag zijn, maar de core dump is een bestand dat wordt opgeslagen op de harde schijf. In dit geval hebben we uitgeschakeld core dumps op de vlucht server, zodat we niet mensen hebben seg vastgelopen en het opbouwen van ton van core dumps. Maar u kunt krijgen een. Core dumps zijn het soort dingen die je kunt vaak uit te schakelen, en soms moet je doen. De segmentatie fout, om je vraag te beantwoorden, Basil, zegt dat we geprobeerd om een ​​pointer te openen dat niet is ingesteld om te wijzen op wat dan ook. Vergeet niet Binky in de video waarop Binky probeert te ga toegang tot een pointer die niet is te wijzen op iets? In dit geval denk ik technisch de wijzer wijst naar iets. Het is te wijzen op null, dat is technisch gezien 0, maar wordt gedefinieerd als een segment dat niet toegankelijk door uw programma, zodat je een segmentation fault omdat je niet de toegang tot het geheugen dat is in een geldige segment zoals de heap-segment of de stapel segment of de gegevens segment. Cool. Nog vragen over Caesar? 

Laten we verder gaan. Laten we eens kijken naar Revisie 2 echt snel. Dat is Vigenère. Hier in Vigenère lopen we via deze vrij snel, want, nogmaals, Vigenère en Caesar lijken veel op elkaar. Header opmerking is voor, Definiëren # is voordat om te voorkomen dat het gebruik van deze magische getallen. Het leuke is dat we wilden gaan naar een ander alfabet of iets dergelijks. In plaats van met de hand gaan alle 26's in de code te wijzigen We kunnen dit wijzigen naar 27 of vallen naar beneden als we met behulp van verschillende alfabetten, verschillende talen. Nogmaals, we hebben deze controle van het argument tellen, en echt je kunt bijna zien dit als een sjabloon. Vrijwel elk programma dat u schrijft moet- als het duurt opdrachtregelargumenten-enkele opeenvolging van lijnen dat luidt als volgt aan het begin. Dat is een van de eerste geestelijke gezondheid tests die u wilt doen. 

Hier is wat we deden was dat we er voor gezorgd dat het sleutelwoord geldig was, en dat was de tweede controle die we deden. Let nog eens op dat we deze gescheiden van argc en 2. Merk op dat in dit geval een ding dat we moesten doen in plaats daarvan was van het gebruik van een tot en met i wilden we de hele reeks te valideren, en om te doen dat je eigenlijk moet gewenste teken te gaan voor teken de string. Er is geen goede manier om iets te doen op het want ook bijvoorbeeld een te i terug 0 als het niet kan een geheel getal ontleden, zodat zelfs niet werkt. Nogmaals, leuke bericht dat de gebruiker precies wat er gebeurde. Dan hier, nogmaals, we ook instaan ​​voor het geval dat de gebruiker een controle D willekeurig karakter. 

En dan Charlotte had een vraag eerder over hoe wij erin slagen om ruimtes overslaan in onze string hier. Dit was een soort van vergelijkbaar met wat we hebben gedaan met de Myspace-programma dat we in sectie, en de manier waarop deze werkte is dat we het aantal brieven dat we hadden gezien bijgehouden. Als we liepen over het bericht string, en we wandelden we meer dan teken voor teken, We volgden de index als onderdeel van onze for-lus, en dan kunnen we ook bijgehouden het aantal letters, dus niet-speciale tekens, niet-cijfers, niet-blanco die we hadden gezien in de afzonderlijke variabele beschouwd. En deze oplossing wijzigt de toets tot een werkelijke sleutel integer te krijgen, en het doet dat op de vlieg, net voor het coderen gaat dan naar het eigenlijke bericht karakter. Er zijn een aantal oplossingen die waren perfect ook geweldig dat zou wijzigen omhoog bij het testen voor de geldigheid van de sleutel. In aanvulling op ervoor te zorgen dat het karakter en het zoekwoord werd een alfabetisch teken bleek ook dat in een integer in de 0-25 bereik om dan slaan met dat later doen in deze for-lus. Nogmaals, zie je hier dit is echt precies dezelfde code die we in Caesar op dit punt. Je precies hetzelfde te doen, zodat de echte truc is het uitzoeken hoe het zoekwoord te zetten in een geheel getal. 

Een ding dat we hier hebben, dat is een beetje dicht is dat we deze uitdrukking herhaald, ik denk dat je zou kunnen noemen, 3 separate keer op lijnen 58, 59 en 61. Kan iemand uitleggen wat er precies deze zin doet? Het is de toegang tot een karakter, zoals je zei. Ja, het is [onverstaanbaar] een karakter in het zoekwoord, en dus is het aantal waargenomen letters omdat je alleen beweegt langs het trefwoord als je eenmaal hebt de brief gezien, zodat dat gaat om effectief te slaan ruimten en dat soort dingen. Ja, precies. En dan als je eenmaal hebt gezien het trefwoord leeg je gewoon mod zodat u zich weer rond. Precies. Dat is een perfecte uitleg. Wat Kevin zei is dat we willen index in het zoekwoord. We willen de num_letters_seen teken te krijgen, als je wil, maar als num_letters_seen dan de lengte van het zoekwoord, de manier waarop we terug in het juiste bereik is gebruiken we de mod operator effectief in wikkelen. Bijvoorbeeld, zoals in de korte, onze sleutelwoord is spek, en het is 5 letters lang. Maar we hebben gezien 6 letters in onze gewone tekst op dit punt en gecodeerde 6. We zullen uiteindelijk de toegang tot de num_letters_seen, die 6, mod de lengte van het zoekwoord, 5, en dus krijgen we 1, en dus wat we doen is zullen we toegang tot het eerste teken binnenkant van onze zoekwoorden op dat punt. 

Oke, vragen over Vigenère voordat we verder gaan? Jullie een goed gevoel over dit? Cool, geweldig. Ik wil ervoor zorgen dat jullie de kans krijgen om de code te zien krijgt waarvan we denken dat ziet er goed uit en hebben de kans om te leren van. Dit zal de laatste we-ruimtes gebruiken voor het moment, en we gaan om de overgang nu, en ik ga naar cs50.net/lectures dus we kunnen doen een beetje quiz beoordeling. De beste manier denk ik dat gaan doen quiz beoordeling is om te komen tot deze Lezingen pagina, cs50.net/lectures, en onder elk van de week rubrieken, dus als ik kijk hier in week 0, Ik zie dat we een lijst met onderwerpen die we behandeld in week 0. 

Als een van deze onderwerpen lijken onbekend voor je zijn u zult zeker willen terug te gaan en schuren de dictaten en eventueel zelfs sneller door de lezingen, nogmaals te bekijken hen als u wilt om een ​​gevoel voor wat er gebeurt met elk van deze onderwerpen te krijgen. Ik zal bovendien zeggen dat dit jaar een van de koele middelen die we hebben is deze shorts die we hebben gecreëerd, en als je kijkt naar week 0, we hebben niet alle onderwerpen aan bod, maar we hebben een flink aantal van hen, een aantal van de lastige degenen, dus kijken naar deze korte broek weer is een goede manier om je op snelheid te komen. In het bijzonder, ik ga in een plug zetten voor de 3 op de bodem, want ik heb die. Maar als je moeite hebt met binaire, bits, hex, dat soort dingen, binaire is een geweldige plek om te beginnen. ASCII is een ander dat is goed om te bekijken. U kunt zelfs naar me kijken bij 1,5-voudige snelheid als ik ga te langzaam voor je. Sinds de beoordeling, voel je vrij om dat te doen. 

Gewoon om heel snel te beginnen, we gaan om te gaan door een paar van deze quiz problemen alleen maar om snel churn door deze. Bijvoorbeeld, laten we eens kijken naar problemen 16 die ik heb recht omhoog hier kwam op het bord. We hebben dit volgende berekening in binaire, en we willen alle werk te laten zien. Oke, ik ga geven deze een schot. Jullie moeten volgen samen met papier, en we doen dit echt snel. We willen de volgende berekening in binaire uit te voeren. Ik heb 00110010. En ik ga aan toe te voegen 00110010. Voor de wiskunde genieën volgende mee thuis, hiermee eigenlijk vermenigvuldigen met 2. Laten we beginnen. We gaan naar dezelfde toevoeging algoritme dat we doen volgen als we decimale getallen bij elkaar optellen. Echt het enige verschil hier is dat we lus terug rond als we eenmaal hebben 1 + 1 in plaats van als we eenmaal tot 10. 

Als we uitgaan van het recht, heel snel, wat is het eerste cijfer? [Student] 0. >> [Nate H.] 0. Geweldig, het tweede cijfer? [Student] 1. [Nate H.] Is het een 1? 1 + 1? [Student] 10. [Nate H.] Precies, dus wat is het cijfer dat ik gelijk schrijven onder de 2 die bij elkaar opgeteld? [Student] 1, 0, of 0 en voer vervolgens de 1. [Nate H.] 0 en 1, precies dragen. Volgende up, Basil, je bent wakker. Wat is de derde? >> [Basil] 1. [Nate H.] 1, perfect. Kevin? [Kevin] 0. >> [Nate H.] 0, Charlotte? [Charlotte] 0. >> [Nate H.] Ja, en wat moet ik doen? [Student] De 1. [Nate H.] En wat moet ik doen? En dan heb ik voorzien van het 1. Perfect, Sahb? >> [Sahb] Nu heb je 1. [Nate H.] En doe ik hier iets? [Sahb] Dan voor de volgende heb je 1 omdat je overgedragen 1. [Nate H.] Geweldig, dus hier kunnen we afmaken it up. Cool. [Student] Heeft 0 + 0 = 0? 0 + 0 = 0. 1 + 1, zoals je zei, is 10, of 1, 0, in plaats van. 10 is een verkeerde benaming, want voor mij 10 betekent het getal 10, en het is de gril van hoe we die het als we het schrijven ervan. We geven het aantal 2 bij 1, 0, en het getal 10 is iets anders. 

Wat is wel leuk over binair is dat er eigenlijk niet zo veel gevallen moet je leren. Er is 0 + 0 = 0, 0 + 1 = 1, 1 + 1 is 0, en dragen een 1, en dan kun je hier op de derde kolom van rechts hadden we 1, 1 en 1. En 1 + 1 + 1 a 1, en je draagt ​​een andere 1. Als je binaire Daarnaast doet, vrij eenvoudig. Ik zou doen een paar meer van deze geestelijk gezond te controleren jezelf voordat je naar binnen, want dit is waarschijnlijk iets dat we zien op de quiz. Nu laten we dit doen volgende ook. Laten we probleem 17. We gaan het volgende binaire getal te converteren naar decimaal. Ik heb 10100111001. Vergeet niet in het binaire video die ik heb Ik liep door een paar voorbeelden, en ik liet zien hoe alles werkt als je het doet in decimalen. Als u werkt in decimale representatie Ik denk dat we op dit punt in ons leven zo vloeiend in het dat het is erg makkelijk te verdoezelen de mechanica van hoe het eigenlijk werkt. 

Maar om een ​​korte samenvatting te doen, als ik het nummer 137 dit betekent-en echt nogmaals, dit is de decimale weergave van- het nummer 137 in decimale betekent dat I 1 x 100 + 3 x 10 + 7 x 1 hebben. Dit is allemaal verblijf op het scherm. En dan als je kijkt naar deze nummers hier, 100, 10 en 1, dan zie je dat ze eigenlijk zijn alle machten van 10. Ik heb 10 ², 10 ¹, en 10 van de nul. We hebben een gelijkaardige soort dingen in binaire, behalve dat onze basis, zoals wij het noemen, is 2 in plaats van 10. Deze 10s die ik hier opgeschreven op de bodem, deze 10 ², 10 ¹, 10 tot de nul, 10 is onze basis, en de exponent, 0, 1, of 2, wordt geïmpliceerd door de positie van het cijfer in het nummer dat we schrijven. 1, als we kijken naar het, dit 1 is in de 2e positie. De 3 in de 1e positie en 7 in de 0e positie. Dat is hoe we de verschillende exponenten hieronder voor onze bases te krijgen. 

Naar aanleiding van dit alles we zullen-eigenlijk, weet je wat? We doen-waar heb ik ongedaan maken-knop gebleven? Daar gaat hij. Ik hou van deze ongedaan te maken ding. Naar aanleiding van deze Ik denk dat voor mij in ieder geval de makkelijkste manier om te beginnen het omzetten van een binair getal of een hexadecimaal getal waar de basis is 16 en niet 10 of 2 is om verder te gaan en uit te schrijven de bases en exponenten voor alle getallen in mijn binaire getal aan de top. Als we uitgaan van links naar rechts weer, dat is een beetje contra-intuïtief, Ik zal hier terug te veranderen naar zwart, hebben we de 2 naar de 0e positie, en dan hebben we 2 ¹, 2 ², en 2 van de 3, 2 van de 4, 2 de 5, 6, 7, 8, 9 en 10. Deze nummers heb ik geschreven zijn alle exponenten. Ik schreef de bases hier in de eerste 3 alleen voor de ruimte. 

Op dit punt ga ik verder te gaan en ik ben eigenlijk aan de hand om te wissen de dingen die we deden in decimale, als dat goed is. Je hebt allemaal dat. Degenen van jullie kijken naar online Ik ben er zeker in staat zal zijn om me terug te spoelen als je wilt. Terugschakelen naar de pen. Nu, wat we kunnen doen, als jullie zijn niet helemaal op snelheid op uw machten van 2, dat is helemaal cool. Het gebeurt. Ik begrijp het. Ik had eens een sollicitatiegesprek waar ik kreeg te horen dat ik alle machten van 2 weten omhoog door 2 tot 30. Het was niet een baan die ik kreeg. Hoe dan ook, jullie kunnen gaan en hier do the math, maar met binaire het niet echt zinvol, en evenmin heeft het zin ook te maken met decimaal of hexadecimaal, om de wiskunde te doen waar u nullen. U kunt zien heb ik hier 0, een 0 hier, 0 hier, 0 hier, 0 hier, 0 hier. Waarom zou het geen zin om de werkelijke wiskunde te doen naar de juiste macht van 2 te berekenen voor die positie? Precies zoals Charlotte gezegd, zal het 0. Kan net zo goed bespaar jezelf de tijd als het berekenen van machten van 2 is niet uw sterkste punt. In dit geval hoeven we alleen maar om het te berekenen voor 2 tot de 0, die-? [Student] 1. [Nate H.] 1, 2 van de 3 die-? [Student] 8. >> [Nate H.] 8. 2 van de 4? [Student] 2. Het spijt me, 1. [Nate H.] 2 om de 4 is 16, precies. 2 van de 5, Kevin? >> 32. [Nate H.] 32, 2 om de 8? [Student] 32 x 8, 256. [Nate H.] Perfect. En 2 van de 10? [Student] 1024. [Nate H.] Ja, 1024. 

Zodra we hebben deze cijfers kunnen we samenvatten ze allemaal. En dit is waar het is echt belangrijk om te doen een paar dingen. Een daarvan is gaan vertragen en controleer je werk. U dat er een 1 tip aan het eind van dit aantal, dus ik moet een oneven aantal zeker krijgen als mijn resultaat, omdat alle anderen zullen zelfs nummers gezien het feit dat het een binair getal. Het andere ding om te doen is als je op dit punt op de test en je hebt geschreven het uit zo ver en je bent niet veel tijd meer kijken naar het aantal punten dat dit probleem de moeite waard is. Dit probleem, zoals je kunt zien, als ik terug bladeren om mijn laptop echt snel- dit probleem is 2 punten waard, dus dit is niet het soort toevoeging je moet gaan door als je echt weinig tijd. Maar we zullen terug te schakelen naar de iPad, en we gaan door het echt snel. 

Ik hou van het doen van de kleine nummers eerst omdat ik vind dat makkelijker. Ik hou van 32 en 8, omdat ze samen gaan vrij gemakkelijk, en we krijgen 50. 16 en 1 krijgt 17. Daar krijgen we 57, en dan kunnen we de rest van deze, zodat we kunnen doen 57, 156. Kom op. Man, goed, laten we eens kijken. We hadden 57, 256, en 1024. Op dit punt, zou ik liever gewoon doorlopen. Ik heb geen idee. Ik heb duidelijk nodig hebben om te lezen over dit. 7, 6, en 4, krijg je 17. 1, 5, 5, 2, 13. Dan krijgen we 3 en dan krijgen we 1. 1337. Paasei, iemand? Iedereen herkent dit nummer? Chris het nummer herkent. Wat betekent het, Chris? [Chris] Leet. Leet, dus als je kijkt naar dit, het lijkt erop dat leet. Hacker spul. Kijk uit voor dat soort dingen op de tussentijdse of de quiz, in plaats van. Als je ziet dat soort dingen en je je afvraagt ​​"Huh," die daadwerkelijk zou kunnen betekenen iets. Ik weet het niet. David houdt waardoor het erin Het is een goede manier om gezond verstand controleren. Net als oke, kan ik zien wat er gaande is. 

Dat is Week 0/Week 1 spul. Als we terug te schakelen naar onze laptop nu, uitzoomen, en een paar andere dingen. Er is ASCII, die we al heel wat te doen met het probleem sets. Dit begrip van het kapitaal A. Wat is dat eigenlijk? Weten is het decimale gehele getal. 65 is wat het is toegewezen aan in de ASCII-tabel, en dat is dan ook de manier waarop de computer het schrijft, en dat is hoe we zijn ermee weg daadwerkelijk schrijven het karakter hoofdletter A en het karakter kleine letter a in sommige van deze oplossingen en probleem sets die je hebt gedaan. Een paar andere dingen. We hebben verklaringen, boolean expressies, condities, lussen, variabelen en draden. 

Die lijken allemaal zinvol voor het grootste deel? Een deel van deze terminologie is een beetje funky op keer. Ik wil graag van een verklaring denken als voor het grootste deel iets dat eindigt met een puntkomma. Instructies zoals x = 7, die een variabele wordt, waarschijnlijk wel x = 7. Vermoedelijk x is een type dat het getal 7 kan opslaan, dus het is een int of eventueel een vlotter of een korte of een char, zoiets. Een boolean expressie wordt met behulp van deze dubbel is en de knal gelijk is aan of het niet gelijk is aan, kleiner dan, groter dan, minder dan of gelijk aan, al dat soort dingen. Voorwaarden zijn dan als else statements. Ik zou denken dat je niet een anders hebben zonder een overeenkomstige indien. Ook kan je niet een ander als dat zonder een overeenkomstige indien. Loops, herinneren aan de 3 soorten lussen we al hameren in je voor de laatste paar secties en probleem sets. Met behulp van niet terwijl als je het krijgen van input van de gebruiker, met behulp van while loops totdat een bepaalde voorwaarde waar is, en vervolgens met behulp van die voor loops als u weten welke iteratie van de lus die u momenteel op is hoe ik erover denk. Of als je doet een voor elk karakter in een string Ik wil iets doen, voor elk element in een array wil ik iets doen om dat element. 

Draad en evenementen. Deze hebben we niet zo expliciet aan bod in C, maar vergeet niet dat dit vanaf het begin. Dit is het idee van het hebben van verschillende scripts. Dit is ook dit idee in het uitzenden van een evenement. Sommige mensen niet uitzenden in eerste instantie te gebruiken in hun projecten, dat is helemaal cool, maar deze zijn 2 verschillende manieren om met deze grotere kwestie heet concurrency, dat is hoe krijg je programma's uit te voeren of schijnbaar uit te voeren op hetzelfde moment? Verschillende taken uitgevoerd terwijl u andere taken worden ook uitgevoerd. Dit is hoe uw besturingssysteem lijkt te werken. Daarom, hoewel bijvoorbeeld Ik heb mijn browser draaien, kan ik ook inschakelen Spotify en speel een nummer. Dat is meer van een conceptueel ding om te begrijpen. Ik zou een kijkje nemen op de draden korte als je wilt om meer te leren over. 

Laten we eens kijken, ik geloof dat er misschien wel een probleem dat in een van deze. Nogmaals, ik denk dat discussies en gebeurtenissen zijn niet iets dat wij doen dat in C alleen omdat het aanzienlijk moeilijker dan in Scratch. Je moet er niet zorgen over te maken, maar zeker inzicht in de concepten, begrijpen wat er gaande is. Voordat we verder gaan, vragen in week 0 materiaal? Iedereen een goed gevoel? Inzicht in variabelen en wat een variabele is? 

Verder. Week 1. Een paar dingen hier dat niet bijzonder waren bedekt in de quiz herziening noodzakelijk en ook meer conceptuele dingen te denken. De eerste is deze notie van wat broncode, compilers en objectcode zijn. Iemand? Basil. Is objectcode-ik bedoel broncode is wat je in kletteren, en object code is wat clang zet zo uit dat je computer kan lezen het programma. Precies. De broncode is de C-code die je eigenlijk uittypen. Object code is wat je krijgt uit clang. Het is de 0s en 1s in die binair formaat. Wat gebeurt er dan is als je een bos van object bestanden, zeggen dat je een project of een programma dat meerdere broncode bestanden gebruikt samenstellen, die volgens afspraak gegeven. c bestandsextensie. Dat is waarom we hebben caesar.c, vigenère.c. Als je het schrijven van Java-programma's je ze de extensie. Java. Python-programma's hebben de extensie. Py vaak. 

Zodra je meerdere. C-bestanden hebt, kunt compileren. Clang spuugt al deze binaire rommel. Dan, omdat u alleen 1 programma heb je de linker band al deze object-bestanden samen in 1 uitvoerbaar bestand. Dit is ook wat er gebeurt als u de CS50 bibliotheek, bijvoorbeeld. De CS50 bibliotheek is zowel dat. H header-bestand dat je leest, dat # includecs50.h. En dan is het ook een speciale binaire bibliotheekbestand die is samengesteld dat is 0s en 1s, en dat-l vlag, dus als we terug gaan naar onze ruimtes en we kijken echt snel naar wat er hier aan de hand als we kijken naar onze clang commando, wat we hebben is dit onze broncode bestand hier. Dit zijn een stelletje compiler vlaggen. En dan helemaal aan het eind, deze-l vlaggen link in de feitelijke binaire bestanden voor deze 2 bibliotheken, de CS50 bibliotheek en vervolgens de math library. 

Inzicht in elk type van bestanden 'doel in de compilatie proces is iets wat je wilt in staat zijn om geven in ieder geval een hoog niveau overzicht van. Broncode komt binnen Objectcode komt. Objectcode bestanden met elkaar te verbinden, en je krijgt een mooie, uitvoerbaar bestand. Cool. Dit is ook waar je kunt fouten krijgen op meerdere punten in de compilatie proces. Dit is waar, bijvoorbeeld, als je hier wat linken vlag, de CS50 vlag, en je het weg laten in Spaces of wanneer u gebruik maakt van uw code, dit is waar krijg je een fout in de koppeling fase, en de linker zal zeggen: "He, je belt een functie GetString dat is in de CS50 bibliotheek. " "Je vertelde me dat het in de CS50 bibliotheek, en ik kan de code niet voor te vinden." Dat is waar je het moet koppelen, en dat is een aparte van een compiler fout omdat de compiler is op zoek naar syntaxis en dat soort dingen. Het is goed om te weten wat er gaande is wanneer. 

Andere dingen om te weten over. Ik zou zeggen dat je zeker wilt een kijkje nemen op de korte op typecasting gedaan door Jordan om te begrijpen wat ints zijn onder de motorkap, wat chars zijn onder de motorkap. Wanneer we praten over ASCII en we kregen eigenlijk kijken naar de ASCII-tabel, wat dat doet is het geven van ons een onder de motorkap kijken op de manier waarop de computer in feite vertegenwoordigt het kapitaal A en het cijfer 7 en een komma en een vraagteken. De computer heeft ook speciale manieren te vertegenwoordigen het getal 7 als een geheel getal. Het heeft een speciale manier om het getal 7 voor te stellen als een getal met drijvende komma, en die zijn zeer verschillend. Typecasting is hoe vertel je de computer "He, ik wil dat je om te zetten ene naar de andere representatie weergave. " Waarom gaan we niet een kijkje nemen op die. 

Ik zou ook een kijkje nemen op de korte op bibliotheken en de korte over compilers. Die praten over het proces van het opstellen, wat een bibliotheek is, en gaan over een aantal van deze vragen die u zou kunnen krijgen vroeg. Vragen over Week 1-materiaal? Zijn er onderwerpen in hier die lijken ontmoedigend u wilt dekken? Ik probeer op te blazen door middel van de meeste van deze eerdere onderwerpen, zodat we kunnen krijgen om pointers en doe een beetje van recursie. Gedachten? Iets te dekken? Tijd voor wat chocolade misschien? Jullie werken doorheen. Ik ga houden het genot van mijn koffie. Week 2. Goede oproep, goed gesprek. In week 2 hadden we het een beetje meer over de functies. 

In de eerste paar probleem sets we niet echt schrijven alle functies op alle anders dan welke functie? [Student] Main. >> Main, precies. En dus hebben we gezien dat de verschillende kostuums die de belangrijkste draagt. Er is die waarin het duurt geen argumenten, en we gewoon zeggen leegte tussen de haakjes, en dan is er de andere, waar we willen om commando regel argumenten te nemen, en zoals we zagen, dat is waar je int argc en string argv array- of nu we eigenlijk blootgesteld string naar de char * dat het zijn we gaan beginnen met het schrijven als char * argv en daarna tussen haakjes. In Probleem Set 3, jullie zagen een heleboel functies, en u een aantal functies uitgevoerd, tekenen, kijk omhoog, scramble. De prototypes werden er allemaal voor u geschreven. 

Wat ik wilde hier over praten met functies heel snel is dat er 3 delen aan hen wanneer u een functie schrijven. Je moet de return type van de functie op te geven. Je moet een naam voor de functie op te geven en dan moet je opgeven de lijst met argumenten of de parameterlijst. Bijvoorbeeld, als ik een functie te schrijven te vatten een bos van gehele getallen en dan terug naar mij de som wat zou mijn terugkeer type zijn als ik wilde gehele getallen optellen en dan de som terug te keren? Vervolgens de naam van de functie. Als ik ga je gang en schrijf in het groen, dit deel is de return type. Dit deel is de naam. En in tussen haakjes is waar ik de argumenten, vaak afgekort als args, ook wel params voor parameters. En als je er een hebt, je gewoon geef de een. Als u meerdere scheidt u elk met een komma. En voor elk argument geef je het 2 dingen die-Kevin? [Kevin] Je moet het type en vervolgens de naam te geven. En dan de naam, en de naam is de naam die je gaat gebruiken om op dit argument verwijzen binnen de som-functie, binnen de functie die u op dat moment aan het schrijven bent. 

Je hoeft niet te, bijvoorbeeld als ik ga om samen te vatten, zeggen, een array van integers-we zullen doen int array, en ik geef mezelf een aantal accolades er- toen ik een array met de som-functie Ik geef het in de eerste positie van de lijst met argumenten. De array I passeren hoeft niet de naam arr hebben. Arr gaat worden hoe ik verwijzen naar dat argument in het lichaam van de functie. Het andere ding dat we nodig hebben om rekening te houden, en dit is iets anders dan functies, maar ik denk dat het een belangrijk punt, is dat in C als ik een functie als deze schriftelijk hoe weet ik hoeveel elementen zijn in deze array? Dit is iets van een strikvraag. We spraken over dit een beetje in rubriek van vorige week. Hoe weet ik of het aantal elementen in een array in C? Is er een manier? 

Het blijkt dat er geen manier om te weten. Je moet het geschiedde in afzonderlijk. Er is een truc die je kunt doen als je in dezelfde functie waarin de array is verklaard, en je werkt met een stapel array. Maar dat werkt alleen als je in dezelfde functie. Zodra u een array naar een andere functie of als je hebt aangegeven een array en je zet die array op de heap, je hebt gebruikt malloc  en dat soort dingen, dan zijn alle weddenschappen zijn uitgeschakeld. Dan moet je eigenlijk om rond te gaan een speciale argument of andere parameter vertellen hoe groot de array is. In dit geval, zou ik willen een komma Het spijt me te gebruiken, het gaat van het scherm hier- en ik zou pas in een ander argument  en noem het int len ​​voor de lengte. 

Een ding dat zou kunnen komen op de quiz vraagt ​​je te schrijven of de tenuitvoerlegging van een functie genaamd iets. Als we niet geven u de prototype, dus dit hele ding hier, deze hele puinhoop wordt de functie declaratie of de functie prototype, Dit is een van de eerste dingen die je zult willen vastspijkeren als het niet gegeven u meteen op de quiz. De andere truc die ik heb geleerd is dat zeggen dat we geven je een prototype voor een functie, en we zeggen: "He, je hebt om het te schrijven." Binnen de accolades die je hebt op de quiz als u merkt dat er een return type en je merkt dat de return type is iets anders dan void, waardoor de functie niet terugkeert niets, dan een ding dat je zeker wilt doen is schrijven een soort van return-statement aan het einde van de functie. Return, en in dit geval zetten we een blanco want we willen het invullen van de blanco. Maar dit wordt de periode van op de juiste manier over hoe ga ik dit probleem aan te pakken? En het herinnert je dat je gaat te hebben om een ​​waarde te retourneren met de beller van de functie. 

Ja. >> [Student] Heeft stijl toe te passen als we het schrijven van code op de quiz? Zoals inspringen en dat soort dingen? >> [Student] Ja. Nee, niet zo veel. Ik denk dat veel van-dit is iets wat we op de quiz te verduidelijken op de dag van, maar meestal zorgen te maken over onder # en dat soort dingen, het is een soort van buiten. [Student] Moet u uw handgeschreven code commentaar geven? Moet u uw handgeschreven code commentaar geven? Commentaar is altijd goed als je je zorgen maakt over een gedeeltelijke credit of u wilt uw intentie aan de grader. Maar ik, nogmaals, zal duidelijkheid te verschaffen over de quiz zelf en op de quiz dag, maar ik geloof niet dat u verplicht om een ​​reactie te schrijven, nee. Meestal niet, maar het is zeker de soort dingen waar je kunt communiceren je intentie, zoals "He, dit is waar ik heen ga mee." En soms die kunnen helpen met gedeeltelijke krediet. Cool. 

Basil. [Basil] Wat is het verschil tussen verklaren, laten we zeggen, int lang in de argumenten of parameters ten opzichte van declaratie van een variabele binnen de functie? Wow, koffie ging de luchtpijp. [Basil] Net als die dingen die we willen zetten in argumenten. Ja, dat is een grote vraag. Hoe kies je wat dingen die je wilt zetten in de argumenten ten opzichte van wat dingen die je moet doen in de functie? In dit geval waren zowel deze als argumenten omdat ze iets dat wie gaat de som functie te gebruiken moet aangeven die dingen. 

De som functie, zoals we het over gehad, heeft geen manier om te weten hoe groot de array is het krijgt van de beller of wie dan ook is het gebruik van de som-functie. Het heeft geen manier om te weten hoe groot die array is. De reden dat we pas in deze lengte hier als argument is, want dat is iets dat we in feite zijn de beller van de functie te vertellen, wie gaat de som functie te gebruiken, "He, niet alleen moet je ons een array van ints, heb je ook om ons te vertellen hoe groot de array die u hebt ons is. " [Basil] Die zullen beide command line argumenten? Nee, dit zijn feitelijke argumenten die wordt meegegeven aan de functie. 

Laat mij hier te doen een nieuwe pagina. [Basil] Net als de naam zou gaan- [Nate H.] Als ik int main (void), en ik ga in mijn return 0 hier beneden op de bodem, en zeggen dat ik de som wilt functie aan te roepen. Ik wil zeggen int x = som (); Om de som functie te gebruiken moet ik gaan, zowel in de array die ik wil om samen te vatten en de lengte van de array, dus dit is waar de veronderstelling dat ik had een array van ints, zeggen dat ik int numbaz [] = 1, 2, 3, soort gebruik dat gehackte up syntaxis daar, dan wat ik zou doen is in som zou ik langs wilt op zowel numbaz en de nummer 3 aan de som-functie vertellen "Oke, hier is de array Ik wil dat je samenvatten." "Hier is de omvang ervan." Is dat logisch? Beantwoordt dit je vraag? 

In veel opzichten doet parallelle wat we doen met de belangrijkste wanneer we de opdracht regel argumenten hebben. Een programma zoals Caesar cipher, bijvoorbeeld dat nodig opdrachtregelargumenten zou niet in staat om iets te doen. Het zou niet weten hoe te coderen als je niet vertellen welke toets je moet gebruiken of als je niet te vertellen wat tekenreeks die u wilde versleutelen. Gevraagd voor input, dit is waar we hebben 2 verschillende mechanismen voor het nemen van input van de gebruiker, die informatie van de gebruiker. Voor Probleem Set 1 zagen we dit GetInt, GetString, GetFloat manier van vragen om input, en dat heet het gebruik van de standaard input stream. Het is iets anders. Het is iets dat je kunt doen in een keer, in tegenstelling tot Wanneer u het programma, te roepen wanneer u het programma start draait. De opdrachtregelargumenten alle worden opgegeven wanneer u het programma start running. We zijn het mengen van de twee van die. Wanneer we argumenten gebruiken om een ​​functie, het is net als command line argumenten naar de belangrijkste. Het is wanneer u beroep doen op de functie die u nodig hebt om het te vertellen wat het precies nodig heeft ter vervulling van zijn taken. Een ander goed ding om naar te kijken en ik laat je naar te kijken in je vrije tijd, en het was bedekt met de quiz-was deze notie van scope en lokale variabelen versus globale variabelen. Heeft aandacht besteden aan dat. 

Nu krijgen we op deze andere dingen, in week 3 we begonnen te praten over zoeken en sorteren. Zoeken en sorteren, althans in CS50, is heel erg een introductie tot enkele van de meer theoretische delen van de informatica. Het probleem van zoeken, het probleem van sorteren zijn groot, canonieke problemen. Hoe vind je een bepaald getal in een reeks van miljarden getallen? Hoe maak je een bepaalde naam te zoeken in een telefoonboek die is opgeslagen op uw laptop? En dus introduceren we dit begrip van asymptotische looptijden om echt te kwantificeren hoe lang, hoe hard deze probleemgebieden zijn, hoe lang zij nemen om op te lossen. In, ik geloof, 2011's quiz er een probleem is dat ik denk dat verdient die heel snel, dat is deze, probleem 12. O nee, het is Omega. 

Hier hebben we het over de snelst mogelijke looptijd voor een bepaald algoritme en de laagst mogelijke uitvoering. Deze Omega en O zijn eigenlijk gewoon snelkoppelingen. Ze zijn notatie snelkoppelingen voor het zeggen hoe snel in het beste geval zal ons algoritme run, en hoe traag in het ergste geval zal ons algoritme lopen? Laten we een paar van deze, en deze werden ook behandeld in het kort op asymptotische notatie, die ik sterk aanbevelen. Jackson deed echt goed werk. Met binair zoeken, we praten over binary search als een algoritme, en we meestal over praten in termen van de grote O. Wat is het grote O? Wat is de laagst mogelijke looptijd van binaire zoeken? [Student] N ²? Sluiten, ik denk vergelijkbaar met die. Het is een stuk sneller dan dat. [Student] Binary? >> Ja, binaire zoekopdracht. [Student] Het is log n. Meld u n, dus wat doet inloggen betekenen n? Halveert het elke iteratie. Precies, dus in de langzaamste mogelijke geval, zeggen dat als u een gesorteerde array van een miljoen integers en het nummer dat u zoekt ofwel het eerste element in de matrix of het laatste element in de array. Vergeet niet, het binaire zoekalgoritme werkt door te kijken naar het middelste element, kijken of dat is de wedstrijd die u zoekt. Zo ja, dan is dat geweldig, je het gevonden hebt. 

In het beste geval, hoe snel gaat binaire zoekopdracht run? [Studenten] 1. 1, het is een constante tijd, big O van 1. Ja. [Student] Ik heb een vraag. Als je zegt te loggen van n, je bedoelt met betrekking tot basis 2, toch? Ja, dus dat is het andere ding. Wij zeggen log n, en ik denk dat toen ik op de middelbare school Ik heb altijd aangenomen dat log was basis 10. Ja, dus ja, log basis 2 is typisch wat we gebruiken. Nogmaals, terug te gaan naar binair zoeken, als je op zoek bent naar een van beide het element helemaal aan het eind of het element aan het begin, omdat je begint in het midden en dan gooi welke half niet voldoet aan de criteria die u zoekt, en je gaat naar de volgende helft en de volgende halve en de volgende helft. Als ik ben op zoek naar het grootste element in de miljoen integer-array Ik ga het halveren ten hoogste log van 1 miljoen keer voordat ik eindelijk testen en te zien dat het element Ik ben op zoek naar is de grootste of de hoogste index van de array, en dat zal log van n, log van 1 miljoen keer. 

Bubble sort. Hebben jullie herinneren de bubble sort-algoritme? Kevin, kunt u mij een korte samenvatting van wat er gebeurd is in de bubble sort-algoritme? [Kevin] In principe gaat het door alles in de lijst. Er wordt gekeken naar de eerste twee. Als de eerste groter is dan de tweede het swaps hen. Dan vergelijkt tweede en derde, hetzelfde, swaps, derde en vierde, helemaal naar beneden. Grotere aantallen zal volgen tot het einde. En na hoeveel lussen je klaar bent. Precies, dus wat Kevin zei is dat we kijken naar grotere aantallen bubble tot het einde van de array. Bijvoorbeeld, vind je het erg loopt ons door dit voorbeeld als dit ons aanbod? [Kevin] Je neemt 2 en 3. 3 is groter dan 2, dus je ruilen. [Nate H.] Juist, dus we wisselen deze, en dus krijgen we 2, 3, 6, 4 en 9. [Kevin] Dan moet je vergelijken met de 3 en 6. 3 is kleiner dan 6, dus je laat ze, en 6 en 4, zou je ruilen, want 4 is kleiner dan 6. [Nate H.] Juist, dus ik krijg 2, 3, 4, 6, 9. [Kevin] En 9 is groter dan 6, dus laat je het. En dat je terug zou gaan door het weer. 

[Nate H.] Ben ik gedaan op dit punt? >> [Kevin] Nee. En waarom ben ik nog niet klaar op dit punt? Omdat het lijkt erop dat mijn array wordt gesorteerd. Ik ben op zoek naar het. [Kevin] gaan door het weer en zorg ervoor dat er niet meer swaps voordat u volledig kunt stoppen. Precies, dus je moet blijven gaan door en zorg ervoor dat er geen swaps die u kunt maken op dit punt. Het was echt gewoon geluk, zoals je zei, dat we uiteindelijk alleen te hoeven 1 pas te maken door en we zijn gesorteerd. Maar om dit te doen in het algemene geval zullen we eigenlijk om dit te doen over en weer. En in feite was dit een voorbeeld van het beste geval, zoals we zagen in het probleem. We zagen dat de best mogelijke zaak werd n. We gingen door de array 1 keer. Wat is het ergste geval voor dit algoritme? [Kevin] N ². En wat betekent dat eruit? Wat zou een array eruit dat zou n ² tijd? [Kevin] [onverstaanbaar] gesorteerd. Precies, dus als ik had de array 9, 7, 6, 5, 2, eerst de 9 zou zeepbel helemaal naar boven. Na 1 iteratie we hebben 7, 6, 5, 2, 9. Dan zou de 7 borrelen, 6, 5, 2, 7, 9 enzovoort, enzovoort. 

We zouden moeten gaan door de hele array n keer, en je kunt eigenlijk krijgen iets nauwkeuriger zijn dan deze want zodra we verhuisd de 9 helemaal tot in zijn laatste mogelijke positie we weten dat we nooit meer te vergelijken met dat element. Zodra we beginnen borrelen de 7-up we weten dat we kunnen stoppen wanneer de 7 is vlak voor de 9 omdat we al vergeleken de 9 aan. Als je dit op een slimme manier is het niet echt, denk ik, dat veel tijd. Je gaat niet om alle mogelijke [onverstaanbaar] combinaties vergelijken elke keer je door elke iteratie. Maar toch, als we het over deze bovengrens we zeggen dat u op zoek bent naar n ² vergelijkingen helemaal door. 

Laten we terug gaan, en aangezien we beginnen om een ​​beetje weinig tijd Ik zou zeggen dat je zeker moet gaan door middel van de rest van deze tabel, vul het allemaal uit. Denk aan voorbeelden. Denk aan concrete voorbeelden. Dat is echt handig en nuttig om te doen. Trek het uit. Dit is het soort tabel die als je door in de informatica moet je echt beginnen met deze uit het hoofd te leren kennen. Dit zijn de soort vragen krijg je in interviews. Dit zijn allerlei dingen die goed zijn om te weten, en na te denken over de rand gevallen, echt uitzoeken hoe te denken over wetende dat voor bubble het slechtst mogelijke array te sorteren sorteren daarmee is er een die in omgekeerde volgorde. 

Pointers. Laten we een beetje praten over pointers. In de laatste paar minuten hebben we hier Ik weet dat dit iets is, samen met file I / O, dat is vrij nieuw. Als we spreken over pointers de reden dat we willen praten over pointers is omdat men, wanneer we werken in C we zijn echt op een vrij laag niveau in vergelijking met de meeste moderne programmeertalen. We zijn eigenlijk in staat om de variabelen in het geheugen te manipuleren, erachter te komen waar ze eigenlijk gelegen binnen onze RAM. Als je eenmaal hebt gegaan op besturingssysteem klassen zie je nemen dat dat, opnieuw, een soort van abstractie. Dat is niet echt het geval. We hebben virtueel geheugen, dat die details verbergt van ons. 

Maar voor nu kun je ervan uitgaan dat als je een programma, bijvoorbeeld wanneer u begint met het runnen van uw Caesar cipher-programma- Ik kom terug te schakelen naar mijn iPad echt snel- dat aan het begin van uw programma, als je, laten we zeggen, 4 GB RAM op uw laptop, krijg je gereserveerd dit stuk, en we zullen dit RAM bellen. En het begint op een plaats waar we gaan op 0 te bellen, en het eindigt op een plaats die we bellen 4 gigabyte. Ik kan echt niet schrijven. Man, is dat gehackt. Wanneer uw programma wordt uitgevoerd het besturingssysteem kerft omhoog RAM, en specificeert de verschillende segmenten voor verschillende delen van het programma om te wonen Hier beneden dit gebied is een soort van niemandsland. Als je naar een beetje verder hier je hebt eigenlijk kreeg de plaats waar de code voor uw programma leven. Dat de werkelijke binaire code, die uitvoerbaar bestand daadwerkelijk wordt in het geheugen geladen wanneer u een programma, en het leeft in de code-segment. En als je het programma uitvoert kijkt de processor naar deze code segment om erachter te komen wat is de volgende instructie? Wat is de volgende regel code moet ik uitvoeren? 

Er is ook een data-segment, en dit is waar die string constanten krijgen opgeslagen die u hebt gebruikt. En dan verder op er is een plaats genaamd de heap. We openen het geheugen daar door het gebruik van malloc, en dan richting de top van uw programma er is de stapel, en dat is waar we al speelt voor het grootste deel van het begin. Dit is niet op schaal of iets. Een groot deel van deze machine is zeer afhankelijk is, besturingssysteem afhankelijk, maar dit is relatief hoe de dingen te krijgen chunked omhoog. Wanneer u een programma uitvoert en declareer je een variabele genaamd x- Ik ga naar een ander vak te tekenen beneden, en dit gaat worden RAM ook. En ik ga kijken. We trekken gekartelde lijnen om aan te geven dit is slechts een klein deel van RAM-geheugen en niet alles naarmate we bovenaan. 

Als ik verklaar een integer variabele genaamd x, dan wat ik eigenlijk krijgen is een mapping dat is opgeslagen in het symbool tabel van mijn programma dat verbindt de naam x om deze regio van het geheugen dat ik heb getekend hier tussen de verticale spijlen. Als ik een regel code in mijn programma dat zegt x = 7 de processor weet "Oh, oke, ik weet dat x leeft op deze locatie in het geheugen." "Ik ga om verder te gaan en daar schrijf een 7." Hoe weet het welke locatie dit is in het geheugen? Nou, dat is allemaal gedaan tijdens het compileren. De compiler zorgt verdeling waarbij elk van de variabelen ga door een speciaal mapping of niet verbinden van de stippen tussen een symbool en waar het heen gaat, een variabele naam en waar het heen gaat om te leven in het geheugen. Maar het blijkt dat we eigenlijk kunnen openen in onze programma's ook. Dit wordt belangrijk wanneer we beginnen te praten over een aantal van de data structuren, Dit is een concept dat we gaan later in te voeren. 

Maar voor nu, wat je kan weten is dat ik kan een pointer naar deze locatie, x. Zo kan ik een pointer variabele. Wanneer we een pointer variabele te maken gebruiken we de ster notatie. In dit geval zegt dat ik ga een pointer te creëren om een ​​int. Het is een soort net als elke andere. We geven het een variabele als y, en dan zetten we het gelijk is aan het adres, naar een adres. In dit geval kunnen we wijzen op y x door het nemen van het adres van x, dat we met deze ampersand, en dan zetten we y te wijzen op het. Wat dit betekent in essentie is als we kijken naar onze RAM dit leidt tot een afzonderlijke variabele beschouwd. Het zal noemen y, en wanneer deze lijn van code wordt uitgevoerd het is eigenlijk gaat om een ​​kleine pointer die meestal stellen we als een pijl te creëren, en bevat y te wijzen x. Ja. [Student] Als x is al een pointer, zou je gewoon doen int * y = x plaats van het teken? Ja. Als x is al een pointer, dan kunt u 2 pointers aan elkaar gelijk, waarbij y niet wijzen x, maar het zou wijzen op wat x wijst. Helaas, we hebben geen tijd meer. 

Wat ik zou zeggen op dit moment, kunnen we over praten niet beschikbaar, maar ik zou zeggen aan de slag door dit probleem, # 14. Je kunt zien dat er hier al een beetje voor u ingevuld. Je kunt zien dat wanneer we verklaren 2 pointers, int * x en * y, en merk op dat wijzen de * bij de variabele was iets dat werd gedaan vorig jaar. Het blijkt dat dit is vergelijkbaar met wat we doen dit jaar. Het maakt niet uit waar je schrijft de * als je verklaren de aanwijzer. Maar we hebben geschreven * naast het type want dat maakt het heel duidelijk dat je waarbij een pointer variabele. Je kunt zien dat waarbij de 2 pointers geeft ons 2 dozen. Hier toen we x gelijk aan malloc wat dit zegt is vernietiging geheugen in de heap. Dit doosje hier, deze cirkel, bevindt zich op de heap. X wijst ernaar. Merk op dat y nog niet wijst naar iets. Om geheugen naar het nummer 42 slaan in x we zouden gebruiken wat notatie? [Student] * x = 42. Precies, * x = 42. Dat betekent volg de pijl en gooi 42 in daar. Hier waar we y en x set hebben we y wijst naar x. Nogmaals, dit is net als wat Kevin zei waar we y gelijk aan x. Y verwijst niet naar x. Integendeel, het is wijzen op wat wijst x zo goed. 

En dan tot slot in deze laatste box zijn er 2 mogelijke dingen die we konden doen. Een daarvan is dat we kunnen zeggen * x = 13. Het andere ding is dat we kunnen zeggen-Alex, weet je wat we hier kunnen doen? Je zou kunnen zeggen * x = 13 of- [Student] Je zou kunnen zeggen int wat dan ook. [Nate H.] Als dit werd aangeduid als een int variabele die we konden doen. We kunnen ook zeggen * y = 13, omdat ze beiden wijzen naar dezelfde plek, dus we konden gebruik maken van een van beide variabele om er te komen. Ja. >> [Student] Hoe zou het eruit als we gewoon zeggen dat int x is 13? Dat zou verklaren een nieuwe variabele genaamd x, wat niet zou werken. We zouden een botsing, omdat we verklaard x om een ​​pointer hier niet komen. [Student] Als we net deze verklaring van zelf hoe zou het eruit zien in termen van de cirkel? Als we x = 13 dan zouden we een doos, en in plaats van een pijl die uit de doos we trekken het als gewoon een 13. [Student] In de doos. Oke. 

Bedankt voor het kijken, en veel geluk op Quiz 0. [CS50.TV]