DAVID J. MALAN: Dette er CS50 og dette er starten på uge fire. Og dreng, er Volkswagen i problemer alle på grund af software. Lad os tage et kig. [VIDEO PLAYBACK] -Cars, De smarteste tegn i Fast and Furious film. Denne uge tyske bilproducent Volkswagen befandt sig midt i en skandale af potentielt kriminelle proportioner. 

-Volkswagen Er forfriskende for milliarder i bøder, mulige kriminelle anklager for sine ledere, som selskabet undskylder til rigning 11 millioner biler til hjælpe det slog emissioner tests. 

-Certain Diesel modeller var designet med sofistikeret software at anvendte oplysninger, herunder placering af styring og køretøjet hastighed til at bestemme bilen var under afprøvning emissioner. Under denne omstændighed, at motoren ville reducere giftige emissioner. Men bilen blev rigget til bypass at når det blev køres. Emissionerne steg 10 til 40 gange over acceptable EPA niveauer. 

[END AFSPIL] 

DAVID J. MALAN: Så lad os tage et kig på dette og se præcis, hvordan det kan gennemføres og hvordan dette kan påvirke så mange biler som denne. Så i min hånd her er pressen udgivelse, der blev udstedt af EPA-- Environmental Protection Agency, som er den reguleringsorgan USA, håndterer miljøhensyn, og derefter den faktiske juridiske meddelelse, der var send til Volkswagen blot et par dage siden. 

Så EPA skriver, og beskriver nu offentligt, en sofistikeret software algoritme på visse Volkswagen biler registrerer når bilen er under test officielle emissioner og fik fuld emissioner styrer kun på under testen. Effektiviteten af disse køretøjer forurening kontrol emissioner enheder er i høj grad reduceret i alle normal kørsel situationer. Dette resulterer i biler, der opfylder standarder i laboratoriet eller afprøvning station, men under normal drift udsender kvælstof oxides-- eller NOx-- ved op til 40 gange den standard. Den software produceret af Volkswagen er et citat citat slut, manipulationsanordning, som defineret af Clean Air Act i USA. 

De går på at sige, at EPA og andet agentur afdækket nederlaget enhed softwaren efter selvstændig analyse af forskere ved West Virginia University. NOx forurening bidrager til nitrogendioxid, jordnær ozon, og fine partikler. Udsættelse for disse forurenende stoffer er blevet forbundet med en bred vifte af alvorlige sundhedsmæssige effekter, herunder øget astma angreb og andre respiratoriske sygdomme, der kan være nok alvorlige at sende folk til hospitalet. Udsættelse for ozon og partikler har også blevet associeret med tidlig dødsfald som følge af respiratoriske relaterede eller kardiovaskulær effekter. Børn, ældre, personer med allerede eksisterende luftvejssygdom er særligt udsatte for sundhedsmæssige virkninger af disse forurenende stoffer. 

Tilstrækkeligt det vil sige, det er ganske alvorligt. Og lad os gå videre til at læse blot endnu uddrag og så vil vi tage et kig på de underliggende konsekvenser af denne i forbindelse med en bil. Specifikt Volkswagen fremstillet og installeret software i det såkaldte elektronisk styring module-- eller ECM-- af disse køretøjer, der fornemmede når køretøjet blev testet for overholdelse af EPA emissionsnormer. Baseret på forskellige input, herunder stilling af rattet, køretøj hastighed, varighed af motorens drift og barometertryk, disse indgange præcist spores parametrene af den føderale testprocedure, der anvendes til emission test for EPA certificering formål. 

Under Miljøstyrelsens emission test, den køretøjer ECM-software løb software, som er fremstillet emissioner overensstemmende resultater. På alle andre tidspunkter, den køretøj ECM-software løb en separat vej kalibrering som reducerede effektiviteten af samlede emission styresystem, specifikt selektiv katalytisk reduktion af Lean NOx trap-- som vi vil se om et øjeblik. Som et resultat, emissioner af NOx øges med en faktor på 10 til 40 gange over de økonomiske partnerskabsaftaler kompatible niveauer afhængigt af typen af ​​drevet cyklus. 

Så hvad det egentlig betyder, og kildekoden til softwaren kører på Volkswagens har ikke endnu ikke blevet offentliggjort, er, at en effektiv, dette tilsvarende er et sted der inde af Volkswagens kode. Hvis du er ved at blive testet, og hvis bilen registrerer visse miljømæssige faktorer ligesom rattet position eller bevægelse eller mangel på samme af bilen eller en række andre faktorer der i øjeblikket hypotese at være en del af denne formel, de simpelthen tænder fuld emissioner kontrol. Med andre ord, de begynder udsender mindre af de forurenende stoffer. 

Else, i enhver anden situation, når det ikke er påvist som værende i laboratoriet, de gør bare ikke. Og så du kan forenkle denne til mere beton pseudokode med noget sådan her. Hvis hjulene vender men rattet er ikke, suggestivt at bilen er på nogle slags roterende cylinder men i en slags lageret, der testes, derefter opføre sig som den EPA vil gerne have dig til. Ellers ikke. Så lad os tage et kig på en kort video, der tager et kig på, hvad konsekvenserne er af denne faktisk mekanisk. 

[VIDEO PLAYBACK] 

-Sidste Fredag ​​EPA meddelt, at nogle Volkswagen Audi biler lavet mellem 2009 og i år brugte en såkaldt manipulationsanordning at komme rundt emissioner love designet til at holde luften ren. Men hvad betyder det præcist? 

Nå, moderne biler har snesevis computere inde i dem. Og nogle af disse computere hjælpe med at koordinere funktionerne af motoren til optimal ydeevne samtidig med at sikre at der ikke er for meget skrald kommer ud af udstødningsrøret. De har faktisk arbejdet på denne måde i flere årtier nu. Dybest set, hver en del af en moderne bils motor har en sensor eller controller på det, og disse computere læser i data tusindvis af gange i sekundet justeringer gør ligesom forholdet mellem brændstof og den luft der kommer ind i cylindrene. 

Disse snyd Volkswagen og Audi modeller er dieselmotorer, og dieselmotorer har en mere virkelig vigtigt computer styrede parametre, som er mængden af ​​uforbrændt brændstof kommer i udstødningen. Nu, lyder slemt. Lyder ikke som du ønsker uforbrændt brændstof kommer ind i udstødningen. Men i tilfælde af en diesel, du har noget kaldes en NOx-fælde, som er en enhed, absorberer og fælder for nitrogenoxider der er forurenende stoffer, der ville ellers gå i atmosfæren. Og effekten af ​​denne NOx fælde er forbedret med uforbrændt brændstof. Så en manipulationsanordning er et særligt program inde i disse computere, der kan gøre det ligne bilen opfylder emission standarder, selv når det ikke gør. Volkswagen havde et problem på sine hænder. Dens dieselmotorer var kendt for at få store brændstoføkonomi, men NOx fælden fungerer kun godt når der anvendes mere brændstof. Så bilen ville afsløre, ved hjælp af denne manipulationsanordning, da det fik en emission test, ville den bruge mere brændstof, gøre NOx fælden arbejde godt, emissioner ville være fint. Men så får du på vejen, enheden slukker, du brænder mindre brændstof men du lægger så meget som 40 gange flere forurenende stoffer i atmosfæren. Men hvordan dælen gjorde bilen ved, at det var bliver testet for overholdelse emissioner? EPA siger, at det var en sofistikeret system, der kontrolleres ting ligesom rattet, hastighed, hvor længe motoren var på, og selv det atmosfæriske tryk. Med andre ord var der ingen måde var dette et uheld fordi softwaren var designet meget omhyggeligt for at opdage en officiel test emissioner. Det er nogle ret alvorlige bedrag, og det er hvorfor Volkswagen er i sådan alvorlige problemer. Faktisk deres CEO, Martin Winterkorn, bare trådte tilbage. 

Så hvad sker der nu? Tja, hvis du er en af ​​den halve million diesel jettas, Beatles, Golfs, Passat, eller Audi A3S gennemført, den gode nyhed er, er at din bil er stadig sikkert at køre. Du behøver ikke at sætte det væk indtil Volkswagen udsteder en tilbagekaldelse. Men på et tidspunkt, de er sandsynligvis vil have at opdatere softwaren i din bil. Når det sker du måske få færre miles pr tank. Advokater er allerede geare op til kollektive søgsmål så ejere kan få kompenseret på et tidspunkt i fremtiden. Men det kommer ikke til at ske enhver tid snart. 

[END AFSPIL] DAVID J. MALAN: Så det faktisk rejser et interessant større billede spørgsmål som at stole på. Højre? Vi har alle iPhones eller Androids eller noget i vores lommer sandsynligvis disse dage, eller bærbare computere på vores omgange, der er kører software lavet af Apple og Microsoft og bundter af andre selskaber. Men hvordan kan vi vide, at hvad disse software produkter gør er faktisk, hvad disse virksomheder siger, at de gør? 

For eksempel, der er til sige, at hver gang du foretage et telefonopkald på din iPhone eller Android-telefon eller lignende, at dette telefonnummer er heller ikke bliver uploadet til nogle virksomhedens server på grund af nogle program, du har skrevet, uanset om det er operativsystemet selve systemet ligesom iOS eller Android, eller fordi du har downloadet nogle tredjeparts app at en eller anden måde er at lytte til alt, hvad du skriver i eller alt, hvad du rent faktisk siger. Hvordan ved du, at når du fyre kører Dunk Eller Kom med til at oversætte din egen software i CS50, hvordan gør dig, at CS50 eget personale, i form af CS50 bibliotek, har ikke været logge alle streng, du nogensinde har fået eller hver tomme, du nogensinde har fået? Nå, kunne du sikkert se på kildekoden til noget ligesom CS50 bibliotek, du kunne se på kildekoden til Linux-operativsystem kører på CS50 IDE. Men en fantastisk præsentation blev givet tilbage i 1984 i modtagelse af Turing Award af en meget berømt datalog kendt as-- navngivet Ken Thompson, der modtaget Turing Award, som er en slags datalogi s Nobelprisen, hvis du vil, for hans arbejde med en operativsystem kaldet Unix, som er meget ens i ånd til hvad vi bruger som er Linux. Og det spørgsmål, han stillede i sin takketale, hovedsagelig om rammerne for år og års drøftelser om tillid og sikkerhed, var dette. I hvilket omfang bør man tillid et erklæring om, at en program-- et stykke af software-- er fri for trojanske heste? Måske er det mere vigtigt at have tillid de mennesker, der skrev softwaren. 

Og i virkeligheden, har vi knyttet til snak om, at han gav ved tiltrædelsen af ​​denne pris i 80'erne på CS50 hjemmeside under Forelæsninger siden for i dag. Fordi det, du vil se er, at han faktisk giver en forholdsvis simpelt eksempel på, hvordan selv en compiler som Dunk eller hvad compilere andre har brugt i fortiden, hvad nu hvis indlejret i compiler vi selv bruger, er lidt, hvis forudsat at hovedsagelig siger, hvis du bemærker, at denne kode er at bruge den getString funktionen eller GetInt funktion, gå videre og indsætte en bagdør eller en trojansk hest således at dette program nu har nogle nuller og dem, der gør noget ondsindet. Logning alle dine tastetryk, uploade, at data til nogle server, eller virkelig noget. 

Og hvad Ken Thompson går på at gøre i sin tale er at vise, at selv om du har adgang til kilden koden for en compiler, der skadeligt kunne gøre dette, det gør ikke noget, fordi der er denne hønen og ægget virkelighed af fortiden mange år hvorved compilere bruges til at kompilere selv. Med andre ord vej tilbage, når en person havde at have skrevet den første compiler. Og derefter, når som helst de har opdateret en compiler ved at ændre dens kildekode, tilføje funktioner og omkompilering det for folk som os at bruge, godt, de bruger den gamle version af compileren at kompilere den nye version af compileren. Og hvis du tager et kig ved snak om, at han gav, vil du se, at fordi af denne cirkularitet, du kan faktisk har fejl eller Trojanske heste indlejret i software vi bruger. Og selv hvis man ser på den kildekoden til disse programmer, det måske ikke engang være indlysende fordi svindel er faktisk i nogle ældre version af en compiler, lige siden har været injektion truslen i vores software. 

Hvilket er kun at sige, vi virkelig kan ikke bør og ikke tillid software, der kører på vores bærbare pc'er eller telefoner eller et vilkårligt antal steder. Og i virkeligheden, senere i dette semester, når vi begynder at tale om webprogrammering og faktisk begynde at bygge webapplikationer os selv, Vi vil tale om disse trusler og andre. Nu har du måske undret og bemærket at der var en lille smule Darth Vader i de klip, Den Verge var viser der om Volkswagen. Hvis du aldrig har set, jeg troede, vi skulle lette stemningen, fordi det er alt meget deprimerende og skræmmende. Jeg har tænkt mig at se tilbage Super Bowl 2011 når en kommerciel ved Volkswagen-- og dette næsten gør dem vellidte igen-- luftet for første gang på TV. Det er de 60 andet klip at jeg tror, ​​du vil nyde. [VIDEO PLAYBACK] [MUSIC - temaet fra "Star Wars"] [Hund gør] [Bilen begynder] [END AFSPIL] DAVID J. MALAN: Ja. Jeg var bare kontrol. At bilen er på listen over overtrædelser. Okay. Så vi ser på nogle pseudokode for et øjeblik siden. Og her er en større uddrag af pseudokode kode at vi har set et par gange hidtil. Og lad os bruge denne er en mulighed nu at indføre en ny programmering teknik, som vi gjorde se algoritmisk sidste uge, da vi kiggede på mergesort. Men lad os formalisere det og se, hvordan vi måske bruge det i konkrete kode, og så vil vi bruge denne teknik ned ad vejen mest sandsynligvis løse en række andre problemer. 

Så det var et af de første programmer, vi nogensinde skrev, omend i pseudokode kode. Og hvad dette program tilladt os at gøre kurset var at finde Mike Smith i en telefonbog. Og bemærk især linjer otte og 11, som havde denne Gå til erklæring. Og faktisk visse sprog, C blandt dem, faktisk har en erklæring om, at er bogstaveligt talt gå til, hvor du kan springe til en bestemt linje. Det er generelt ildeset, fordi Det kan meget nemt misbruges og du kan begynde at hoppe din program over det hele i modsætning at bruge den slags logik og reguleringsflowet at vi har brugt hidtil med blot loops og betingelser og lignende. 

Men vi kan forenkle denne algoritme i pseudokode kode som følger. I stedet for denne iterative eller looping tilgang hvor vi holde gå tilbage og tilbage og tilbage til linje tre, hvorfor vi ikke bare slags punt og mere generelt siger på linje syv og 10, bare erstatte dem to par linjer med, ellers hvis Smith er tidligere i bogen vi får søge efter Mike i venstre halvdel af bogen. Ellers hvis Smith er senere i bog, søge efter Mike i den rigtige halvdelen af ​​bogen. Og mærke allerede cirkularitet. Højre? Jeg søger efter Mike i telefonbogen og derefter Jeg til sidst ramte måske line syv eller måske linie 10 og min instruktion til mig selv er at søge til Mike i halvdelen af ​​telefonbogen. Nå, hvordan søger jeg efter Mike? Jeg er midt i søger efter Mike, hvorfor er du slags sende mig i en cirkel? Men det er OK, fordi det, der er sker med størrelsen af ​​problemet, som skrevet i linje 7 og 10? Vi er ikke bare at sige søgning til Mike, søge efter Mike. Vi specifikt sige, hvad? Søg efter ham i den venstre halvdel af den højre halvdel, som er effektivt halv størrelse af problemet. Så det er OK, at vi er sådan engagere sig i denne cirkularitet, dette cirkulære argument, fordi der i mindst vi er at gøre problemet mindre og mindre. Og til sidst vil vi nå at den såkaldte base case, hvor Vi har kun én side left-- som vores frivillige i sidste uge did-- vi havde en side til venstre og derefter gør vi ikke nødt til at holde søger efter Mike Smith fordi han er enten på den pågældende side eller han er ikke. 

Så hvordan kan vi gennemføre denne idé, dette slags cirkularitet i konkrete kode? Nå, kan vi udnytte en teknik der er almindeligt kendt som rekursion. Og vi har set det i pseudokode for mergesort sidste uge. Husk på, at dette var den pseudokode til mergesort. Det er velsagtens endnu enklere end boble eller valg eller indsættelse sortere kun med hensyn til enkelhed som du kan udtrykke det. 

Men det er fordi vi er slags cirkulært siger, søge efter noget ved at søge efter det igen. Men vi søger enten på den venstre halvdel eller den højre halvdel og så til sidst er vi sammenlægning i dette tilfælde. Men også her med disse to sortere linjer, vi igen har denne tanken om rekursion. Og konkret, hvad det betyder, i forbindelse med en algoritme, er, at en algoritme er rekursiv hvis den bruger eller kalder sig. 

Eller i form af C, en funktion recursive-- en funktion kaldet foo er rekursiv, hvis foo, et eller andet sted i sin kildekode, kalder funktionen foo selv. Og det er slemt, hvis alle foo nogensinde gør er kalde sig igen og igen. Det er OK, hvis foo sidst stopper, som gør mergesort, ved at sige, vent et minut, Hvis problemet er super lille, for eksempel, eller jeg fandt ham, hvem jeg er leder efter, bare vende tilbage. Må ikke rekursivt, ikke cyklisk kalde mig selv igen. 

Og så lad os tage et kig på hvordan dette kan faktisk fungere. Så jeg har tænkt mig at gå videre og åbne op to source kode eksempler her. Hvoraf den ene kaldes sigma 0. Og det er ikke på alle rekursive, men lad os tage et kig på, hvad dette program gør. Jeg har strippet ud af alt kommentarer fra det, men alle af kildekoden på CS50 s hjemmeside har kommentarer, hvis du ønsker at læse den igen senere. Og lad os gøre et par af tilregnelighed kontrollerer her. 

Så i toppen af ​​denne kode, vi har inkludere CS50.h. Hvad betyder dette gøre? Hvorfor er det her? I rimelig lægmandssprog. Hvad gør den? Ja. 

PUBLIKUM: Så GetInt funktion virker. 

DAVID J. MALAN: Så det den GetInt funktionen fungerer. Fordi indersiden af ​​denne fil, CS50.h, som vi vil se inden længe i form af sin kildekode, har en masse funktioner declared-- GetInt, getString, og en flok others-- og medmindre vi faktisk har at Medtag linje, compileren Dunk ikke kommer til at vide, at det eksisterer. Og samme gælder for linje to hvor int defineres printf, som er en funktion vi fortsætte med at bruge ganske lidt. Nu linje fire virker lidt funky fordi det er bare en one liner. Det har fået et semikolon, ingen krøllede seler, ingen kode inde i den. Men hvad gjorde vi kalder denne ting i uger tidligere? Ja. Så en prototype. Og hvorfor har vi en prototype som synes at være lidt overflødigt typisk fordi vi normalt se funktionen igen senere i filen, ikke? Så hvorfor skal vi have-- du bare skrabe dit hoved, men jeg tager det. Ja. 

PUBLIKUM: [uhørligt] funktion efter den vigtigste. DAVID J. MALAN: Præcis. Således at compileren kender dig i sidste ende vil definere eller gennemføre denne funktion efter vigtigste, formentlig. Så Dunk og mest compilere er lidt dum og de vil kun kender hvad du fortæller dem. Og hvis du ønsker at bruge en funktion kaldet sigma, du bedre lære compileren at det eksisterer i forvejen. 

Nu main sig selv, selv selvom det er en flok af linjer, er temmelig velkendt forhåbentlig ved nu. Det har fået en gør while-løkke hvis formål i livet her åbenbart er at få en positivt heltal fra brugeren. Og bare holde plage ham eller hende, indtil de samarbejder. Så på linje 16 Jeg har en interessant opkald. IntAnswer. Hvilket på venstre side giver mig en Int som kan store-- kaldes Answer-- der skal opbevares, tilsyneladende, returværdien af ​​sigma. Så sigma er blot en vilkårlig men meningsfyldt navn at jeg har givet til en funktion hvis formål i livet er at tage en argument-- vi vil kalde det N i denne case-- og bare for at tage summen af ​​dette nummer plus ethvert positivt tal, der er mindre end det. 

Så hvis jeg passere i nummer 2 til sigma, jeg ønsker at tilføje 2 plus 1 plus 0-- ikke 0-- så mig 3 giver. Hvis jeg går i 3 til sigma, jeg ønsker at har 3 plus 2 plus 1, som giver mig 6. Og så videre. Så det bare tilføjer op alle tal mindre end eller lig med det. 

Nu herned jeg bare at udskrive svaret. Så som en hurtig tilregnelighed check, lad os gøre sigma 0-- dot skråstreg sigma 0-- og lad mig skrive i 2. Og jeg faktisk får 3. Lad mig skrive i 3. I faktisk får 6. Og hvis nogen kan gøre det math hurtigt, hvis jeg gør 50 hvad skal jeg få? 

PUBLIKUM: [uhørligt]. DAVID J. MALAN: Nå, nej. Men 1.275 som er temmelig tæt på. Så dette er et resultat af at gøre 50 plus 49 plus 48 plus 47 plus 46 hele vejen ned til 1. Så det er alt sigma gør. Men lad os se, hvordan vi har gennemført det nu. Så hernede er funktionen selv. Og det ser ikke ud til at have noget at gøre med rekursion endnu. Faktisk er vi ved hjælp af en gamle skole teknik. Jeg initialisering en variabel kaldet sum til nul, så har jeg en foreloop her, og jeg erklærer en Int kaldet Jeg, sætte den lig med 1-- selvom jeg kunne sætte det lig med nul, men da jeg gør kommer, Hvem bekymrer sig om det er nul eller én. Det kommer til at have nogen effekt. 

Så jeg iteration, så længe jeg er mindre end eller lig med m, hvilket er det argument, der blev vedtaget i. Og så er jeg bare holde forøgelse I. og indsigt af løkken alt jeg gør gør sum plus lig I. Og det er bevidst. Jeg ønsker ikke at gøre, i denne tilfælde som summen plus plus. Jeg ønsker at faktisk tilføje den aktuelle værdi af I der holder bliver større og større og større til driften tally. 

Og så er jeg tilbage sum. Og så svar får værdien sum. Og så er jeg printe det ud. Så der er en mulighed her, dog slags at forenkle denne kode begrebsmæssigt og den slags pudse sin huske i form af enkelhed selvom det tager et stykke tid at sortere af forstå, hvorfor denne er stærk i disse små eksempler. Her er sigma en-- så anden version af denne kode. Alt op øverst er identisk, så at samme historie gælder som før. Men lad os nu se på den gennemførelse af sigma som Jeg har skåret ned til bare disse lines-- fire linjer kode, virkelig, plus nogle krøllede parenteser og hvide rum. 

Men hvad gør jeg? Hvis m er mindre end eller lig med nul, jeg har brug for at slags håndtere at super enkel sag. Og hvis du afleverer mig nul eller noget negativ som er lige underligt, Jeg vil blot vilkårligt men konsekvent vende tilbage til nul. Jeg ønsker ikke denne ting til komme ind i nogle underlige uendelige loop på grund af en negativ værdi. Så jeg siger bare, hvis du giver mig nul eller mindre, jeg vender tilbage nul. 

Men det er godt, fordi det er at enkelt side af telefonbogen der er tilbage. Jeg bide et meget specifikt problem og ikke kalde noget rekursivt. Men i ledningen 31, hvilket skal jeg synes at gøre? De parentes er bare holder ting forhåbentlig lidt klarere. Men alt jeg gør er jeg returnering m-- uanset du aflevere mig-- plus værdien af ​​m-- sorry, plus værdien af ​​sigma m minus 1. Så hvad betyder det? Hvis du giver mig det nummer 3 som input, det svar, jeg ønsker at få i sidste ende er 6, fordi 3 plus 2 plus 1 giver mig 6. Men hvordan kan jeg tænke over hvordan denne kode kører? Første gang jeg kalder sigma og jeg passerer i værdien 3, det er ligesom at sige på et stykke papir, her er værdien 3 og jeg har bestået dette som sigma. 3 er naturligvis ikke mindre end 0, så IF betingelse gælder ikke. Den andre gør. Så hvad skal jeg gøre? Jeg ønsker at vende tilbage m, hvilket er 3, plus sigma m minus 1. Så lad mig holde styr på dette. Jeg har tænkt mig at sætte dette stykke papir ned. Og hvilken værdi, at være klar, vil jeg videregive ind sigma på dette tidspunkt i historien? Hvilket nummer? 2, ikke? 3 minus 1 er 2. Så jeg har bare brug for lidt skrot af papir her. Så nu sigma er at få kaldt igen. Og jeg har med vilje lagt dette ned, fordi det er lidt ligesom pause denne version af historien fordi nu er jeg fokuseret på signalet af m minus 1. Så m var 3, m minus 1 er 2. Så her er 2 at jeg har bestået. 2 er naturligvis ikke mindre end 0 således at sagen ikke finder anvendelse. Else Jeg vender tilbage m, hvilket er det ting, plus sigma af hvilken værdi? Så hvis sigma af 1-- fordi m er lige nu 2 så 2 minus 1 er 1. Så nu har jeg bare værdien 1. Jeg passerer lige antal 1 til funktionen sigma-- eller mig selv her-- så 1 er naturligvis ikke mindre end nul, stadig ikke gælder. 

Else afkast 1 plus sigma af hvad? 0. Så lad mig bare huske, at. Jeg vil vende tilbage til senere. Nu vil jeg gå videre og tøddel ned på antallet 0, fordi det er mit argument eller parameter. Jeg bestået nummer 0 og endelig denne proces for bare at gentage mig selv annonce nauseum betyder ophører, fordi det, gør jeg straks gøre, når jeg ser dette 0? Jeg vender tilbage nul. Så nu er du nødt til at spole tilbage historien. 

Hvis jeg nu gå baglæns i tid, hvad var den seneste ting Jeg gjorde, hvis du var bogstaveligt tilbagespoling en video? Jeg har tænkt mig at afhente den seneste 1 og det giver mig 1 plus 0 er 1.. Hvis jeg holder tilbagespoling af historie, der kommer til at give mig 2 plus det kører værdi, som er 1. Så det er 3. Og så jeg har tænkt mig at holde tilbagespoling. Da jeg først satte antallet 3-- så 3 plus 3 giver mig 6. 

Og nu, hvis du har spolet tilbage videoen indtil dette punkt, dette var meget første spørgsmål spurgte jeg. Når passeret 3, hvad der er sigma 3? Det er faktisk 6, summen af alle disse stykker papir. Så hvis der tager lidt tid at wrap dit sind omkring, det er fint. Men overveje det var en little-- det var meget bevidst, at jeg stablet disse numre oven på hinanden. Det er lidt som at have en memory-- en rekord i tiden, som en skrubber i en video, at jeg faktisk kan spole tilbage i. Og vi vil komme tilbage til at metafor i bare en lille smule. 

Men først, det viser sig, at der er en masse nørder og sjove mennesker, Jeg gætter på Google. Ville en person, der er meget god til Googling sind kommer op for bare et øjeblik og hjælp mig søge efter noget? Meget, meget lav nøgle. Nogen, der er aldrig kommer op før, måske. OK. Ja? Kom nu. Kom ned. Hvad er dit navn? 

SAM: Sam. 

DAVID J. MALAN: Sam, kom ned. Dette er den samme. Dejligt at møde dig. Hey. Kom forbi. Så alt jeg har brug for dig til at gøre, hvis du kunne, Sam, her er Google. Kan du søge efter ordet rekursion? Må ikke ødelægge. 

Og nu let's-- ja. OK Klik det. Bedre klikke det. Ahh, få det. Nej? OK. Så lad os gøre et par andre. Ikke så meget relateret fagligt her, men har du nogensinde søgte på Google efter anagram? 

SAM: Nej. 

DAVID J. MALAN: OK. Søg efter anagram stedet for rekursion. Hvordan omkring skævt. Har du nogensinde søgt efter skævt? Nu, dette ene er lidt svært at se, men forhåbentlig everything's-- OK. Det er bare dig og mig nyder dette. OK. 

Så til sidst, denne one's-- det er lidt skævt. Nu gør en tønde roll. Vidunderligt. Okay. Stor tak til Sam. Vær så god. Tak. 

Så hvad der foregår i alle af disse tåbelige eksempler? Så virkelig, under kølerhjelmen af Googles millioner af linjer kode tilsyneladende er et par fjollet IF forhold, der er væsentlige kontrollere, om brugeren har skrevet i denne sætning, gøre noget, der formentlig fandt en nontrivial mængde tid at gennemføre blot at være morsom på denne måde. Men det er alt det koger ned til under motorhjelmen. Men naturligvis rekursion er mere af geekier eksempel blandt de særlige tricks. Og mon der ikke er andre derude så godt, at vi måske har ikke engang opdaget endnu. 

Så tag et kig, eller overveje nu følgende program, og helt sikkert få fat i nogen af disse på din vej ud. Jeg har tænkt mig at gå videre og åbne op for et program, der er vil forsøge at bytte to værdier. Men før vi går der, lad os gøre det. Kunne vi få en mere frivillig, jeg tror? Kunne du tænke dig at arbejde frivilligt? Nej? Kom op. Kom op. Okay. Så dit navn er hvad? 

LAUREN: Lauren. 

DAVID J. MALAN: Lauren. Kom op, Lauren. Så Lauren er ved at blive Her udfordres som følger. Dejligt at møde dig. Så Lauren her har foran af hendes to tomme kopper. Og vi har nogle orange saft og nogle mælk og vi kommer til at gå videre og gøre følgende. Vi er lige kommer til at fylde dette. Et par ounces mælk herover og lad os fylde lidt appelsinjuice herovre. 

Og foran alle disse tilhørerne, bytte de to værdier for disse kopper. Sæt appelsinjuice i mælken koppen og mælken i appelsinsaft cup. Hvordan ville du gøre det, hvis du var på hjem og havde adgang til andre forsyninger? LAUREN: Put det i en anden kop. DAVID J. MALAN: OK. Så lad os få en midlertidig variabel, hvis vi vil. Og gå videre nu og implementere samme swapping procedure. Så godt. Vi har lagt OJ i den midlertidige variabel, mælk i EFT variabel, og nu midlertidig variabel i mælkevariablen. OK. Så meget godt gjort hidtil. Så det viser out-- fastslå, at tænkte for bare et øjeblik. Her, bare til Geek det lidt op, det ville være den tilsvarende C-kode at vi implementeret bare. Vi havde to indgange, a og b, der begge som vi vil bare sige til enkelhed er int s. Og mærke her, hvis jeg ønsker at bytte værdierne af to variabler, a og b, vi faktisk har brug for en mellemmand, en midlertidig variabel, en midlertidig kop, i hvilken hældes en af ​​værdierne således at vi har en pladsholder for det. Men så koden er præcis som Lauren her implementeret. 

Nu, bare for at få en lidt mere skørt, viser sig at du kan gøre dette uden en midlertidig variabel. For at gøre dette korrekt, men vi vil nødt til at snyde med nogle kemi. Vi har nogle ekstra kopper her. Så det tætteste, der ser ligesom mælk og vand perhaps-- eller mælk og OJ-- er vi har nogle vand, så vi vil udfylde dette en op med et par ounces klart vand. Det er nok for meget. Ja. Det er helt sikkert for meget. Hold på én sek. 

Og nu har vi olie, som, så vidt jeg husker fra midten skole kemi klasse, forhåbentlig er det ikke blandes med vand. Men den slags slags ligner mælk og EFT. Så nu, uden at bruge en midlertidig variabel, kan du bytte disse to værdier? Så olier går i vandet kop, vand går ind i olie koppen. LAUREN: Ingen andre kopper? DAVID J. MALAN: Ingen andre kopper. Og jeg har faktisk ikke testet dette før dette år så jeg ved ikke, om dette vil rent faktisk arbejder kemisk. Det var ikke meningen at ske. Er det til at virke? Okay. Så adskillelse? Godt. Nu fik vi at få den vand i det andet bæger. Smartere kemi koncentratorer kunne sandsynligvis gøre det bedre end mig. 

LAUREN: Vandet er på bunden. 

DAVID J. MALAN: Det water--, der var hvad der er nøglen sidste gang vi gjorde dette. Du er nødt til at gøre det i den rigtige rækkefølge. Ja. Det er ok. Så nu har vi to kopper olie. OK. Det er ok. Men kemisk hvis dette arbejdede end jeg-- 

LAUREN: Dette er vand. 

DAVID J. MALAN: Det er for det meste vand. Okay. Men det er stadig den samme kop som før. Så hæld det-- prøve det derovre. OK. Det er en god brug af klassen tid i dag. OK. Så nu we-- rart. Slags. Okay. Så meget godt. Tak til Lauren. Meget godt klaret. 

Så bare at blæse jeres sind, og det er måske noget at lege med, hvis du gerne i CS50-id, du kan faktisk bytte to variabler uden brug af en midlertidig heltal. Og dette er den tilsvarende C-kode. Og hvis du husker fra sidste Onsdag introducerede vi, hvis kort, nogle nye operatører i C. Og gør nogen huske, hvad den lille gulerod symbolet er, at lille trekantede symbol fra tastaturet repræsenterer? Hvad bitvis operatør? 

PUBLIKUM: EXOR. 

DAVID J. MALAN: EXOR. Eksklusiv Or. Så hvis du ønsker, bare for sjov på hjem, til opnåelse a og b to vilkårlige værdier som helst eight-- og jeg ville vælge en otte bit værdi. Hvis du gør dette med 32 bits, vil du meget hurtigt kede sig. Men bare give en en otte bit værdi, der er hvad, en eller to, og give b samme værdi. Og derefter bruge definitionen af XOR fra sidste onsdag, anvende denne lidt efter lidt, idet hver af disse otte bit i hver af a og b, og derefter gøre det nøjagtigt pr denne kode. Og det er ikke forkert, hvad du ser her på skærmen. Det faktisk koges ned til tre XOR operationer og på en måde magisk a og b vil udveksle holdninger uden at miste nogen oplysninger. 

Så olien og vandet trick er tættest virkelige verden inkarnation Jeg kunne tænke på at efterligne det. Men det er helt sikkert nemmere at bruge en midlertidig variabel, som i dette tilfælde her. Og også dette er en mulighed sige, Også denne form for mikro optimering, som en datalog ville sige, mens slags sjov at prale om, hvordan du gjorde det uden ligesom at bytte med en ekstra variabel, det er ikke alt, overbevisende. Fordi at spare 32 bit, som i tilfælde af en faktisk int, er ikke alt, overbevisende på et system, hvor du bruger måske snesevis af megabytes eller endnu mere sådan hukommelse disse dage. Og i virkeligheden, når vi får til et senere problem sæt og du implementere magi brik og du vil blive udfordret til at gøre det med dette så lidt RAM og så lidt tid som muligt på computer-- du stadig har en uge til at gennemføre det-- du vil have-- du vil være udfordret til at minimere disse ressourcer. Og det er virkelig den eneste anledning dette semester hvor du vil blive opfordret til at barbere off selv de fineste resultater koster andet. 

Så Hvad-- hvordan kan vi se dette i konkrete kode? Lad mig gå videre nu og åbne op et eksempel der bevidst hedder Ingen Swap fordi det ikke faktisk bytte variablerne som du faktisk kunne forvente. Så lad os tage et kig. Her er et program, der ikke har nogen CS50 bibliotek foregår, bare standard I / O. Nu har vi en prototype til swap op øverst, som netop betyder, at det er nødt til at være defineret senere. Og her er vigtigste. 

Jeg vilkårligt tildelt x og y, henholdsvis værdier et og to bare fordi de er små og let at tænke over. Og så er jeg bare har en masse printfs hvor jeg har en tilregnelighed check. x er 1 og y er 2, er formentlig hvad disse printfs vil sige. Så ingen magisk hidtil. 

Så jeg har tænkt mig at hævde med udskrive def, bytte dot dot dot. Jeg har tænkt mig at ringe til swap funktion, der passerer i x og y. Og lad os antage, for nu at swap gennemføres nøjagtigt som det var for et øjeblik siden med en midlertidig variabel. Og så jeg hævder dristigt, byttes. X er nu dette, og y er nu, at. Men filen, selvfølgelig, kaldes Ingen Swap. Så lad os faktisk se hvad der sker. Hvis jeg kompilere ikke bytte, og derefter gør ./noswap, x er 1, y er 2. Bytte byttes. x er 1, y er 2. Så det faktisk ser ud til at være behæftet med fejl, selv selvom swap-- lad os rulle ned nu-- gennemføres nøjagtigt pr kode Jeg foreslog for et øjeblik siden. Så vi kommer ikke til at få lyst med XOR ting for nu. Også dette bør arbejde bare gerne med mælk og EFT, men det ser ikke ud til at virke. 

Så lad os gøre det igen. Måske jeg bare var ikke kører det rigtigt. Så lad os løbe Ingen Swap igen. Måske jeg-- nej. Så det er bare ikke i orden. Så lad os gøre en lille tilregnelighed check. Lad mig gå videre her i Swap og blot tilføje, vent et minut, a er% i / n og lad os plug-in værdien af ​​en. Fordi jeg virkelig ønsker for at se, hvad der foregår. Og ja, det er en debugging teknik at du bruger måske i kontortid eller derhjemme allerede, beslægtet med den første halvdel af Dan Armendariz video i PSET3 hvor vi introducerede print def som en anbefalet teknik, i det mindste for simple sager. Lad mig gå videre og køre gøre ingen swap igen, ./noswap. 

Interessant. Så mærke til, hvad der synes at være sandt. x er 1, y er 2, men er 2 når b er 1. Så dem to en eller anden måde fik byttet men x og y er ikke at få byttet. Så for at være klar, hvad der sker er, heroppe har jeg x og y og dem er variable lokale i omfanget af vigtigste, jeg passerer i x og y at bytte. Nu swap, som en separat funktion, er velkommen til at ringe sine argumenter eller dens parametre noget den ønsker. Foo eller bar eller x eller y eller a eller b. Blot for at gøre det klart, at de er ikke er identisk med x og y per se, Jeg har sagt a og b. Men vi kunne kalde dem noget, vi ønsker. 

Og så det ligner swap bliver passeret x-- AKA en-- og det er forbikøres y-- AKA b. På en måde disse tre linjer er bytte disse værdier nøjagtigt som Lauren gjorde med mælk og EFT. Men når vi udskriver værdierne, a og b er faktisk bytte, men X og Y har ingen ændring til dem. Husk på, at x og y er heroppe. 

Så vi kan se det via en anden teknik samt. Og også dette er en teknik indlejret i problemet sæt tre. Lad os gå videre og gøre dette i CS50-id, hvis du ikke allerede har. På højre side, vi har denne fane Debugger. Og hvis du åbner dette op, der er nogle mystiske oplysninger der er kastet på dig i første omgang. Men lad os drille det fra hinanden rigtig hurtigt. 

Så en, du se lokale variabler. Viser sig, at bygge ind i CS50 IDE, og en masse programmering miljøer mere generelt, er en debugger. Et værktøj, der giver dig mulighed for visuelt at se hvad der foregår inde i dit program uden at skulle ty til at tilsætte printfs og kompilering og kører og tilføje printf-og kompilering og løb, som allerede i kontortiden eller hjemme, er sandsynligvis at få temmelig trættende. 

Så her, på bare et øjeblik, vi er kommer til at se i realtid værdierne i vores lokale variable. Vi er også vil være i stand til at sætte hvad der kaldes breakpoints, som er muligheder i mit program til at holde pause bearbejdning fra et bestemt linje kode at jeg er nysgerrig. Højre? Disse programmer kører i et splitsekund. Det er slags rart for os langsommere mennesker at være i stand til at holde pause, tage et øjeblik, se hvad der foregår omkring en vis linje kode uden programmet pløjning gennem det og efterbehandling helt. Så en breakpoints kommer til at tillade os at bryde og pause på et bestemt tidspunkt. 

Kaldstakkens er en fancy måde sige, hvad funktioner er i øjeblikket bliver kaldt i øjeblikket. Vigtigste altid kaldes først. Men hvis Main kalder en funktion kaldet Swap, vi faktisk kommer til at se denne tårn af funktioner, der har været kaldte i omvendt kronologisk rækkefølge. Så lad os se det. 

Jeg har tænkt mig at zoome ud. Jeg har tænkt mig at gå tilbage til min kode. Og bare fordi jeg ønsker at være pedantisk her, Jeg har tænkt mig at gå videre og klik lige til venstre for linjen fem. Og det skaber en rød prik. Og bemærk på højre side at debugger kender, hey, Jeg sagde bare et breakpoint på noswap.c linje fem, specielt på dette linje kode. Så debugger ved, at jeg har anmodet om, at næste gang Jeg køre mit program det pause udførelse der snarere end blot kører det hele super hurtigt. 

Så nu vil jeg til at klikke på Debug knappen på toppen af ​​IDE og det kommer til at gøre følgende. Det kommer til at åbne en oprindeligt noget skræmmende leder anden terminal window-- remote debugging fra vært sådan og such-- og vi vil komme tilbage til det, alt, betyder inden længe. Men hvad der er vigtigt for nu er, at der red dot blev ramt, debugger har bevidst standsede execution-- på denne linje sådan, men på den første linje faktiske kode i denne funktion. Og det er derfor linie syv er nu markeret med gult. 

Og lad os nu tage et kig på højre side. Det ligner, som standard, pænt nok, x har hvilken værdi? 0. Og y har hvad værdi? Zero. Og det er der kan forventes i den forstand, at x og y-- at gul line-- har udføres ikke endnu. SOx bør ikke have værdien 1. Det kunne have en anden værdi, en såkaldt garbage værdi. Og vi fik heldig i, at det er nul på dette tidspunkt i det væsentlige. 

Så nu er der kun få knapper, vi har brug for at pleje om, når debugging på denne måde. Bemærk her, har vi en knappen Afspil. Og hvis vi spiller eller hit genoptage, det er bare kommer til at løbe gennem resten af ​​programmet eller indtil den rammer en anden breakpoint. Men jeg har ikke sat nogen anden breakpoints så det er bare kommer til at køre gennem enden. Den slags nederlag de Formålet med rode rundt. 

Så i stedet, jeg holder disse ikoner til højre. Og hvis jeg svæve over dem, som du bør også, vil du se lidt tips-- værktøjstip. Denne ene er trin over. Nu betyder det ikke, skip følgende linje kode. Det betyder blot udføre det og flytte til den næste, flytte til den næste, flytte til det næste. Med andre ord, via denne knap, kan jeg gå gennem min kode et skridt ad gangen. Linje for linje, bogstaveligt talt. Nu til højre for det, er der en anden at vi vil se på bare et øjeblik. Dette er den såkaldte Step Into ikon, der er vil tillade mig dykke i en anden funktion. Men lad os se det i bare et øjeblik. Så jeg har tænkt mig at klikke på trin over. Og nu mærke til, da jeg klikker denne knap øverst til højre, holde dine øjne nogenlunde under Local Variabler og se hvad der sker til x. X er nu 1 fordi gule linje er nu udført og vi har flyttet til linje 8. Og på bare et øjeblik y skulle forhåbentlig blive 2. 

Nu intet, interessant sker for lidt. Alt dette er er printf. Og bemærk, i min sekundære terminal vindue, ser jeg produktionen af ​​print def. Og nu er jeg nødt til at gøre en afgørelse som programmøren. Jeg kan træde over denne linje af kode, udfører det, men ikke få nysgerrig efter, hvad der er indeni. Eller jeg kan faktisk træde ind i det og gå inde i Swap selv. Så lad os gøre det sidste. 

Lad mig gå videre og klik ikke træde over men Step Into. Varsel, pludselig vinduet ændringer at fremhæve det første linje kode i Swap. Det er linje 21. Og nu, hvad er slags funky er, hvis man ser herovre, som forventet, et komma b er 1, og 2, henholdsvis. Hvorfor er temp 32.767? Erindrer om, at temp, ligesom den tomme kop for et øjeblik siden, erklæres her på linie 21. Hvorfor 32,000- Jeg mener, hvorfor er det bare nogle underlige værdi? Ja? 

PUBLIKUM: Det er ikke initialiseret. 

DAVID J. MALAN: Det er ikke blevet initialiseret. Så vores computer altid har fysisk hukommelse. Det har altid fysisk RAM. Og der er altid nul s og man er derinde, ikke? Fordi vi bruger vores computer hele dagen lang, du bruger CS50 IDE eller serverne hele dagen lang. Således at RAM enten har nogle nuller eller nogle ens eller nogle nuller og ettaller. Uanset om eller ikke du bruger dem. Du kan ikke bare have tom rum, hvor du vil have bits. De er enten nuller og ettaller. 

Så det viser sig, at temp, fordi vi har ikke initialiseret det endnu, vi har de 32 bit, men de er ikke har blevet initialiseret til alle kendte værdier. Så uanset hvad de var mest nylig brugt for-- dem 32 bits-- vi bare se artefakter af nogle tidligere brug af dem bestemt 32 bit. Så snart jeg klikker Step Over selv, phew, er temp vil få værdien 1. Og hvis jeg gør det igen, en er vil blive givet værdien 2 og derefter b kommer til at gives værdien 1. 

Og så hvad er rart nu på dette tidspunkt i historien er, at debugger er viser mig, super langsomt i mit eget tempo, hvad tilstanden af ​​Swap er. Men bemærk i toppen her, varsel at opkaldet stak faktisk har to lag til det. Nu en, der er fremhævet som Swap, hvis jeg klikker på Main stedet, mærke til, hvordan de lokale variabler ændrer fordi udvikleren kan bare hoppe rundt og gå ind i en hvilken som helst anden rækkevidde. Så selv om vi gør alt dette arbejde og korrekt swapping a og b, hvis jeg går frem og tilbage mellem Swap hvor a er 2, og b er 1, og Main, har Main blevet påvirket på alle? Nej. Så hvad er takeaway her? Tja, det viser sig, at hver gang du kalder en funktion som Swap, og du passerer det argumenter, hvad du passerer til Swap-funktionen i dette tilfælde er en kopi af disse argumenter. Så hvis x og y er hver henholdsvis 32 bit, hvad Swap bliver er to nye lokale variabler, eller argumenter, kaldes en og B-- men de er vilkårlige names-- men mønstret af nuller og dem inde i a og b er linet op at være identisk med x og y men de er ikke de er samme som x og y. 

Det er som om Main har på sin stykke papir nummer 1 og 2 for x og y, og så når det hænder, at stykke papir til Swap, Swap meget hurtigt får sin egen pen, skriver ned 1 og 2 på eget ark papir, hænder tilbage til den originale xy til Main og derefter gør sit eget ting med a og b. Og det er nu super vigtigt, fordi dette har nontrivial konsekvenser for faktisk skriver korrekte kode fordi det synes vi ikke kan bytte to variabler. 

Jeg har skrevet en korrekt Swap funktion. Vi har implementeret det med Lauren som en korrekt swap funktion i virkeligheden men tilsyneladende ingen af ​​der spørgsmål, hvis du kan faktisk ikke bytte to værdier permanent. Så vi har brug for en anden måde til rent faktisk at komme på dette, og vi skal være i stand til faktisk løse dette problem. Og det viser out-- og vi vil komme tilbage til denne særlige billede før long-- dette er en måde at du måske tegne computerens hukommelse. Det er bare et rektangel. Du kunne tegne det noget række måder, men det er bekvemt at tegne den som en rektangel af følgende grund. 

Vi kommer til at starte i dag og videre taler om den såkaldte stak. Og stakken er blot en luns af RAM-- en luns af memory-- der fungerer har adgang til, når de kaldes. Og så viser det sig, at der på den meget bunden af ​​denne stak er hvor alle Mains lokale variable og org C og org V og alt det der kommer til at gå som standard. Og hvis Main kalder nogle andre funktion som Swap, godt, er Swap kommer til at få en anden lag af hukommelsen op over det. 

Og så bare for at give dig en hurtig overfladisk billede af dette, hvis jeg gå over her-- og lad mig afspejle dette på overliggende som well-- hvad der virkelig har jeg, hvis vi interesserer kun om bunden af ​​dette billede for nu, er, at når jeg kører et program og Main bliver kaldt, Main gives et stykke RAM i min computer, der er i bunden af ​​denne såkaldte stak. Og jeg har tænkt mig at tegne det bevidst som en firkant. Så det er ligesom 32 bit eller fire bytes. Og hvis dette hovedfunktion har en variabel kaldet X med en værdi på 1 og det har en variabel kaldet y med værdien 2, der er som at tage denne splint af hukommelse, Vigtigste er blevet givet af operativsystemet systemet og dividere det op, så den første lokal variabel går her, den anden går her, og det er det. 

Når Main kalder swap, swap får sin egen skive hukommelse at vi vil trække på denne måde fra operativsystemet, og det kommer til at have sin egne lokale variabler baseret på vores implementering tidligere med lokale variable en og b, der oprindeligt få værdierne 1 og 2. Men så, så snart Swap-koden henretter, og Lauren faktisk swaps den EFT og mælk, hvad sker der? Nå, denne 2 bliver en 1, denne 1 er ved at blive en 2, og ved den måde, der er en temp variabel, der er at være brugte det hele tiden, som til sidst går væk. Men det gør ikke noget hvor meget arbejde du gør i denne linje of-- i denne hukommelsesplads, x og y er helt uberørt. 

Så vi har brug for nogle måde at give Swap og funktioner som det hemmelig adgang, hvis du vil, til funktioner like-- til hukommelse som x og y. Så lad os tage et kig på et eksempel, der hjælper os se præcis, hvad har været foregår hele denne gang. Jeg har tænkt mig at gå videre og åbne op sammenligne Zero. Og jeg har tænkt mig at lukke vores debugger, jeg har tænkt mig at lukke denne skræmmende leder besked det bare siger, vent et minut, du er midt debugging. Jeg har tænkt mig at skjule denne fane her bare at gå tilbage til enkelhed. Så du skal ikke bekymre dig, hvis GDB bliver dræbt. Det betyder blot, at programmet har blevet quit, bevidst i denne sag, af mig. 

Og nu sammenligne Zero gør dette. Jeg bruger CS50 bibliotek i standard I / O. Jeg har en hovedfunktion, der først siger, sige noget, og får en streng. Så siger det igen og får en anden streng. Og bemærk, at disse to strenge kaldes s og t hhv. Og nu dette program, sammenligne Zero, dens formål i livet, det er meningen at fortælle mig, jeg skriver det samme? Og så jeg vil tilbage til uge et. Jeg bruger min lige lige operatør som er kvaliteten operatør. Ikke tildelingsoperatoren, operatøren lighed. Jeg er bare sammenligne s og t. 

Så lad os faktisk gå videre og gøre dette. Og jeg har tænkt mig at gå videre og gøre Sammenlign Zero. Jeg har tænkt mig at gøre ./comparezero. Og jeg har tænkt mig at gå videre og sige noget lignende, lad os gøre mor med små bogstaver og hvad med mor med store bogstaver. Og selvfølgelig jeg skriver forskellige ting. Okay. Det kan forventes. 

Lad os køre den igen. Begge gange gør små bogstaver, små bogstaver. Det ser super identisk med mig. Enter. OK. Måske er det bare underligt, fordi det er ikke lide min grammatik. Så lad os gøre en hovedstad MOM, hovedstad MOM, identiske. Forskellige ting. 

Så hvorfor er det? Nå, hvad er faktisk at gå på under kølerhjelmen her? Så lad os gå tilbage over her for blot et øjeblik og overveje, hvad getString er faktisk gør. Når du ringer getString, det er en funktion, vi selv skrev og det på en måde får en sekvens af tegn fra brugeren. Og lad os antage, at den første gang jeg kalder getString, der giver mig en luns af hukommelse, der ser sådan ud. Og hvis jeg har skrevet i alle små bogstaver m-o-m-- og hvad der går efter det? Bare en hurtig tilregnelighed check. 

Backslash nul. Vi ved, at. Og huske, at vi spillede rundt med Zamila navn og en masse andre navne da Rob var her søger ved, hvad der foregår inde i hukommelsen. Så den historie er præcis det samme. Dette er, hvad getString vender tilbage til mig. Nu er min kode for et øjeblik siden gemt returværdien af ​​getString i en variabel kaldet s. Og så anden gang, jeg kaldte det, Det opbevares det i en variabel kaldet t. 

Så hvis jeg går herovre, jeg har brug for at tegne denne lokale variable-- og jeg generelt vil tegne en streng som bare-- vi får kalder det S-- som en lille firkant her. Og nu, somehow-- hvordan gør mor gå inde i denne variabel s? Nå, er vi nødt til at gå tilbage til første principper her. Hvad der er getString egentlig tilbage? 

Så det viser sig, at M-O-M backslash nul, og et antal af andre strenge i hukommelse som Zamila og Rob eller Andy eller nogen andre, er naturligvis i vores computerens RAM eller hukommelse. Og din RAM har like-- du har en koncert RAM, to koncerter RAM, eller en milliard eller to milliarder bytes, eller måske endnu flere i disse dage. Så lad os antage, for nutidens formål, at det er ligegyldigt, hvordan vi nummer dem, men vi kan nummerere hver af disse milliarder eller to milliarder eller fire milliarder byte. 

Og lad os bare vilkårligt sige, at dette er den første bid, andet bid, tredje, fjerde. Jeg bevidst ikke bruger nul for i dag, men vi vil vende tilbage til. Så med andre ord, hvis dette er allerførste gang jeg bruger programmet Jeg er lige ved at komme heldig og den første bid er på placering en så to derefter tre end fire. Og hvis jeg holdt tegning, kasse nummer to milliarder ville være vejen herovre. 

Så hvad tror du da, GetString faktisk vender tilbage? Det er ikke returnere M-O-M backslash nul i sig selv, fordi det klart vil ikke passe i boksen, som jeg har tegnet. Så hvad der ellers måtte getString faktisk tilbage alle disse uger? Svaret er på bord her et sted. Du kan ikke passe M-O-M omvendt skråstreg nul, så hvad kan give mening i stedet? Hvis du skulle være super dygtig, at sætte på den såkaldte engineering hat, hvad kunne du vender tilbage? Hvad er den mindste mængde af information du kunne vende tilbage, der ville stadig lade dig finde M-O-M i hukommelsen? Ja? 

PUBLIKUM: One. 

DAVID J. MALAN: One. Og hvorfor en? PUBLIKUM: Fordi det ville fortælle dig, hvor at gå [uhørligt]. DAVID J. MALAN: Præcis. Jeg vil blot returnere adressen af strengen, som jeg har fået. Adressen i dette tilfælde er placering én. Så hvad der virkelig bliver gemt i S-- og hver strengvariablen således far-- har netop været adresse på den pågældende streng. 

I mellemtiden, hvis jeg kalder GetString en anden gang og jeg skrive i bogstaveligt samme thing-- M-O-M med lowercase-- M-O-M og en anden skråstreg nul, og nu måske min programmets kørt i et stykke tid, så måske dette er 10, er det i lokation 11, er 12, dette er 13. De computere, der bruger nogle andre hukommelse uanset årsagen. Hvad nu går i mit andet variabel i mit program t? 10. Præcis. 

Og så når vi ser på kildekode af dette program hvor jeg blot forsøger at sammenligne de to værdier, er S lig lig t, hvad er det indlysende menneskelige svar? Bare nej, fordi 1 ikke er lig 10. Og så heri ligger en mulighed for os virkelig at bare gå tilbage til, igen, først principper og tænke over, godt, hvad der foregår under kølerhjelmen? Vi har talt om bits og bytes og hukommelse, men det er faktisk nyttigt at forstå fordi når du kalder getString, selv om vi tænker på det er tilbage M-O-M eller snor mor eller Andy eller Zamila eller lignende, teknisk det er bare at returnere adressen af denne chunk hukommelse. 

Men det er OK. Fordi hvordan kan jeg vide hvor streng ender? Hvis jeg kun har tænkt givet begyndelsen? Nå, backslash nul, ikke? Bare i lineær tid, jeg kan udskrive med print def M-O-M. Og så snart jeg ser omvendt skråstreg nul, jeg er ligeglad, hvor jeg startede, Jeg ved allerede implicit hvor jeg skal ende. 

Og så i dag markerer beginning-- og lad mig gøre det dramatisk, fordi vi gik igennem en masse problemer til få disse her uddannelse wheels-- så i dag de støttehjul starter at komme ud, og vi afslører på least-- 

[Applaus] 

Det var værd at rejse til Target morges, ja? Så nu-- der er, viser det sig ud, ikke sådan noget som streng. String findes ikke. Det er et synonym, som vi har haft indersiden af ​​CS50 biblioteket. Fremover vil vi begynde at kalde s og t ikke strygere men char stjerner. Og char stjerne vi får drille hinanden inden længe. Men det vil sige, at selv hvis vi fortsætter hjælp getString for nu, teknisk jeg skulle være at sige char stjerne og char stjerne. 

Og det viser sig, hvad det stjerne kommer til at betegne er noget kaldes en pegepind eller en adresse. Og i virkeligheden, en teaser for, hvad der ligger forude er denne 20 andet klip fra vores ven Nick Parlante på Stanford der, et godt stykke tid siden, tilbringer et latterligt beløb af tid, så godt jeg kan fortælle i hans køkken eller hans kælder, gør claymation indføre til verden en figur ved navn Binky med hvem vi vil indføres næste gang pointere. Så her er et eksempel på, hvad der er at komme. 

[VIDEO PLAYBACK] 

-Hey, Binky. Vågn op. Det er tid til pointer sjov. 

-Hvad er det? Lær om pointers? Åh, goody. 

[END AFSPIL] DAVID J. MALAN: Og på dette notat, vi vil se dig på onsdag. Okay. Hvem er dans? Kom nu. Hvem er dans? Skal jeg få det i gang? Jeg vil få det i gang. Woooo! 

LAUREN: Søde fancy Moses.