>> 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.
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.