>> DAVID J. MALAN: Dit is CS50 en dit is die begin van die week vier.
En, seun, is Volkswagen in moeilikheid alles as gevolg van sagteware.
Kom ons neem 'n blik.
[Video speel]
-Cars, Die slimste karakters in die Fast and Furious films.
Hierdie week Duitse automaker Volkswagen self gevind
in die middel van 'n skandaal van potensieel kriminele proporsies.
>> -Volkswagen Is versterkend vir miljarde in boetes, moontlike kriminele aanklagte
vir sy bestuurders, as die maatskappy vra om verskoning
vir rigging 11.000.000 motors help klop uitstoot toetse.
>> -Certain Diesel modelle was ontwerp met gesofistikeerde sagteware
wat gebruik word om inligting, insluitend die posisie van die stuurwiel en die voertuig
spoed te bepaal die motor was ondergaan uitstoot toets.
Onder daardie omstandighede, die enjin sou giftige uitlaatgasse te verminder.
Maar die motor is getuig te omseil dat wanneer dit was gedryf.
Uitstoot verhoog 10-40 keer bo aanvaarbare vlakke EPA.
>> [Einde afspeel]
>> DAVID J. MALAN: So laat neem 'n blik op hierdie
en sien presies hoe dit kan geïmplementeer word
en hoe dit kan beïnvloed so baie motors soos hierdie.
So in my hand hier is die pers vrylating wat uitgereik is deur die EPA--
die Omgewing Protection Agency wat
is die VSA regulerende agentskap wat hanteer die omgewing betref,
en dan die werklike legal notice wat
stuur na Volkswagen net 'n paar dae gelede.
>> So het die EPA skryf, en openbaar nou openbaar, 'n gesofistikeerde sagteware
algoritme op sekere Volkswagen voertuie ontdek
wanneer die motor ondergaan amptelike uitstoot toets
en draai volle uitstoot beheer oor slegs tydens die toets.
Die doeltreffendheid van hierdie voertuie besoedeling
uitstoot beheer toestelle is baie verminder tydens al normale ry
situasies.
Dit lei in 'n motor wat aan die standaarde in die laboratorium of toetsing
stasie, maar tydens normale werking uitstraal stikstof oxides-- of NOx--
by tot 40 keer die standaard.
Die sagteware wat deur Volkswagen is 'n aanhaling unquote, nederlaag toestel
soos gedefinieer deur die Skoon Air Wet in die VSA.
>> Hulle gaan om te sê dat die EPA en ander agentskap
ontbloot die nederlaag toestel sagteware na onafhanklike ontleding
deur navorsers by West Virginia University.
NOx besoedeling bydra tot stikstofdioksied, grondvlak osoon,
en fyn deeltjies.
Blootstelling aan hierdie besoedelingstowwe is gekoppel
met 'n wye verskeidenheid van ernstige gevolge vir die gesondheid,
insluitende 'n groter asma aanvalle en ander respiratoriese
siektes wat kan ernstig genoeg om mense te stuur na die hospitaal.
Blootstelling aan osoon en deeltjies het ook
wat verband hou met voortydige dood as gevolg van respiratoriese verwante
of kardiovaskulêre verwant effekte.
Kinders, bejaardes, mense met preexisting respiratoriese siekte
is veral 'n risiko vir gevolge vir die gesondheid van die besoedeling.
>> Voldoende is om te sê, dit is baie ernstig.
En laat ons gaan op om te lees net nog 'n uittreksel
en dan sal ons 'n blik op te neem die onderliggende implikasies
van hierdie in die konteks van 'n motor.
Spesifiek, Volkswagen vervaardig en geïnstalleer
sagteware in die sogenaamde elektroniese beheer
module-- of ECM-- van hierdie voertuie wat aangevoel
wanneer die voertuig getoets vir nakoming EPA emissie standaarde.
Gebaseer op verskeie insette insluitend die posisie van die stuurwiel, voertuig
spoed, die duur van die enjin se operasie, en barometriese druk,
hierdie insette juis nagespoor die parameters
van die federale toets prosedure vir toetsing vir EPA sertifisering emissie
doeleindes.
>> Gedurende emissie toets EPA se die voertuie ECM sagteware
hardloop sagteware wat geproduseer voldoen uitstoot resultate.
Alle ander tye, die voertuig ECM sagteware
hardloop 'n aparte pad kalibrasie wat verminder
die doeltreffendheid van die algehele vrystelling beheer stelsel,
spesifiek die selektiewe katalitiese vermindering van die Lean NOx trap--
wat ons sal sien oor in 'n oomblik.
As gevolg hiervan, die vrystelling van NOx verhoog deur 'n faktor 10 tot 40 keer
bo die EPA voldoen vlakke afhangende van die tipe van ry siklus.
>> So, wat dit regtig beteken, en die bronkode om die sagteware loop
op die Volkswagen se het nie nog openbaar gemaak,
is dat, effektief, hierdie ekwivalent is daar iewers in
Volkswagen se kode.
As jy word getoets, en as die motor sekere omgewingsfaktore ontdek
soos die stuurwiel posisie of die beweging
of die gebrek daaraan van die motor of enige aantal ander faktore
wat tans vermoed om deel van hierdie formule wees,
hulle eenvoudig draai op volle uitstoot beheer.
Met ander woorde, hulle begin afgee minder van die besoedeling.
>> Anders, in elke ander situasie wanneer dit nie opgespoor word as
in die laboratorium, het hulle net nie doen nie.
En so kan jy dit vereenvoudig in meer beton pseudokode met iets
soos hierdie.
As die wiele draai, maar die stuurwiel is nie, suggestief
dat die motor is op 'n paar soort roterende silinder
maar in 'n soort van pakhuis getoets,
tree dan as die EPA wil jy.
Anders doen nie.
So laat ons 'n blik op 'n kort video wat
neem 'n blik op wat die implikasies is van hierdie eintlik meganies.
>> [Video speel]
>> -Last Vrydag die EPA aangekondig dat sommige Volkswagen Audi motors tussen 2009
en hierdie jaar is die gebruik van 'n sogenaamde nederlaag toestel
om te kry om die uitstoot wette ontwerp om die lug skoon te hou.
Maar wat beteken dit presies?
>> Wel, moderne motors het dekades van rekenaars in hulle.
En sommige van die rekenaars help koördineer die funksies
van die enjin vir optimum prestasie, terwyl om seker te maak
dat daar nie te veel vullis uit te kom van die uitlaatpyp.
Hulle het eintlik is besig hierdie manier vir 'n paar dekades.
Basies, elke deel van die enjin 'n moderne motor se
het 'n sensor of beheerder op dit, en hierdie rekenaars
lees in die data duisende keer per sekonde maak aanpassings
soos die verhouding van brandstof na die lug wat gaan in die silinders.
>> Hierdie verneuk Volkswagen en Audi-modelle is diesels,
en diesels het nog ' werklik belangrik rekenaar
beheer parameters, wat die bedrag van die onverbrande brandstof gaan
in die uitlaat.
Nou dit klink sleg.
Klink nie soos jy graag wil hê onverbrande brandstof gaan in die uitlaat.
Maar in die geval van 'n diesel, jy iets
bekend as 'n NOx trap wat is 'n toestel wat absorbeer en 'n strik vir stikstofoksiede
dat besoedeling is wat sou anders gaan in die atmosfeer.
En die effek van daardie NOx trap is versterk met onverbrande brandstof.
So 'n nederlaag toestel is 'n spesiale program binne hierdie rekenaars wat dit kan maak
lyk soos die motor aan emissie standaarde, selfs wanneer dit nie.
Volkswagen het 'n probleem op sy hande.
Sy diesel enjins is bekend vir die kry groot brandstofverbruik,
maar die NOx trap werk net goed wanneer meer brandstof gebruik word.
So het die motor sou opspoor, die gebruik van hierdie nederlaag toestel
wanneer dit was om 'n uitstoot toets, sou dit meer brandstof gebruik,
maak die NOx trap werk goed, uitstoot sal goed wees.
Maar dan kry jy op die pad, die toestel draai af, jy brand minder brandstof
maar jy sit so veel as 40 keer meer besoedelingstowwe in die atmosfeer.
Maar hoe die heck het die motor weet dat dit was
getoets vir uitstoot nakoming?
Die EPA sê dit was 'n gesofistikeerde stelsel wat dinge nagegaan
soos stuurwiel posisie, spoed, hoe lank die enjin was,
en selfs die atmosferiese druk.
Met ander woorde, daar was geen manier toevallige was hierdie
omdat die sagteware was ontwerp baie versigtig te spoor
'n amptelike toets uitstoot.
Dit is 'n paar mooi ernstige misleiding en dit is
hoekom Volkswagen is in so 'n ernstige moeilikheid.
In werklikheid, hul uitvoerende hoof, Martin Winterkorn, net uitgetree.
>> So wat gebeur volgende?
Wel, as jy een van die half miljoen diesel Jettas, Beatles, Golfs, Passats,
of Audi A3s bewerkstellig, die goeie nuus is, is
dat jou motor is nog veilig om te ry.
Jy hoef nie om dit weg te sit totdat Volkswagen reik 'n herroeping.
Maar op 'n sekere punt hulle is waarskynlik gaan hê
om die sagteware in jou motor te werk.
Wanneer dit gebeur jy dalk kry minder myl per tenk.
Prokureurs is reeds gereed vir klas-aksie regsgedinge
so eienaars kan kry vergoed op 'n sekere punt in die toekoms.
Maar dit is nie van plan om gebeur nie enige tyd gou.
>> [Einde afspeel]
DAVID J. MALAN: So dit is eintlik verhoog 'n interessante groter prentjie vraag
as om te vertrou.
Reg?
Almal van ons het iPhones of Androids of iets in ons sakke waarskynlik
hierdie dae, of skootrekenaars op ons rondtes wat
hardloop sagteware gemaak deur Apple en Microsoft
en trosse van ander maatskappye.
Maar hoe weet ons dat dit wat hierdie sagteware produkte doen
is eintlik wat hierdie maatskappye sê hulle doen?
>> Byvoorbeeld, wat om te sê dat elke keer as jy
maak 'n oproep op jou iPhone of Android-selfoon of die wil,
dat telefoonnommer is ook nie word opgelaai na bediener paar maatskappy se
as gevolg van 'n program wat jy het geskryf, of dit nou die bedryfstelsel
stelsel self soos IOS of Android, of omdat jy afgelaai
sommige derde party app wat een of ander manier is om te luister
alles wat jy tik in of alles wat jy eintlik sê.
Hoe weet jy dat wanneer julle ouens loop klang
of maak om op te stel jou eie sagteware in CS50, hoe
doen jy eie personeel se CS50, deur middel van die CS50 biblioteek,
is nie 'meld elke string wat jy al ooit gekry
of elke duim wat jy nog ooit gekry?
Wel, jy kan beslis kyk by die bron-kode vir iets
soos die CS50 biblioteek, jy kan kyk na die bronkode
vir Linux bedryfstelsel loop op CS50 IDE.
Maar 'n ongelooflike aanbieding gegee terug in 1984
in die ontvangs van die Turing-toekenning deur 'n baie bekende rekenaar wetenskaplike bekend
as-- naam Ken Thompson wat ontvang die Turing-toekenning wat
is 'n soort van die rekenaar wetenskap se Nobelprys, as jy wil,
vir sy werk op 'n bedryfstelsel genoem
Unix, wat baie soortgelyk in gees wat ons gebruik wat Linux.
En die vraag gevra wat hy in sy aanvaarding toespraak, in wese
gehou die raamwerk vir jare en jare van bespreking
oor vertroue en sekuriteit, was hierdie.
Tot watter mate moet 'n mens 'n trust stelling dat 'n program-- 'n stuk
van software-- is gratis Trojaanse perde?
Miskien is dit is meer belangrik om te vertrou die mense wat die sagteware geskryf het.
>> En in die feit, het ons verbind om die gesprek dat hy
gegee het toe aanvaar hierdie toekenning in die 80's op die webwerf CS50 se
onder die bladsy Lesings vir vandag.
Want wat jy sien is dat hy eintlik gee
'n redelik eenvoudige voorbeeld van hoe selfs 'n samesteller soos klang of wat ook al
opstellers ander gebruik het in die verlede, wat as ingebed in die samesteller ons
onsself gebruik is 'n bietjie as voorwaarde wat in wese sê,
as jy sien dat hierdie kode gebruik die GetString funksie of die GetInt
funksie, gaan voort en voeg 'n agterdeur of 'n Trojaanse perd
sodanig dat die program het nou 'n paar nulle
en diegene wat iets kwaadwillige doen.
Meld al jou toetsaanslagen, oplaai dat data
sommige bediener, of regtig iets.
>> En wat Ken Thompson gaan voort om te doen in sy praatjie
is om aan te toon dat selfs as jy toegang tot die bron het
kode van 'n samesteller wat kwaadwillig kan dit doen,
dit nie omdat saak daar is hierdie hoender en die eier
werklikheid van die verlede baie jaar waardeur opstellers
word gebruik om hulself op te stel.
Met ander woorde, die pad terug wanneer iemand het geskryf het die eerste samesteller.
En daarna, enige tyd wat hulle het verander 'n samesteller deur die verandering van die bron-kode,
die toevoeging van funksies en hercompileren dit vir mense soos ons om te gebruik, goed,
hulle gebruik die ou weergawe van die samesteller
om die nuwe stel weergawe van die samesteller.
En as jy 'n blik by die sprake dat hy,
jy sal sien dat omdat van daardie sirkulariteit,
jy kan eintlik het foute of Trojaanse perde ingebed in sagteware
ons gebruik.
En selfs as jy kyk na die bron-kode vir die programme,
dit kan nie eens duidelik wees omdat die bedrieëry is eintlik
in sommige ouer weergawe van 'n samesteller wat sedertdien
spuit die bedreiging in ons sagteware.
>> Wat net om te sê, ons regtig kan nie en behoort nie
trust sagteware op ons skootrekenaars of selfone of enige aantal plekke.
En in die feit, wat later in die semester wanneer ons begin praat oor web programmering
en eintlik begin met die bou web aansoeke onsself,
ons sal praat oor hierdie dreigemente en ander.
Nou, kan jy al gewonder en opgemerk dat daar 'n klein bietjie Darth
Vader in die clips wat Die rand is daar wat
oor Volkswagen. As jy nog nooit gesien het nie, ek
gedink ons ​​moet verlig die bui, want dit is al
baie neerdrukkend en skrikwekkend.
Ek gaan om terug te kyk op Super Bowl 2011
wanneer 'n kommersiële deur Volkswagen-- en dit
maak byna hulle aangenaam again-- uitgesaai vir die eerste keer op TV.
Dit is die tweede clip 60 dat ek dink jy sal geniet.
[Video speel]
[MUSIEK - tema uit "STAR WARS"]
[DOG blaf]
[Motor begin]
[Einde afspeel]
DAVID J. MALAN: Ja.
Ek was net te keur.
Dat die motor is op die lys van oortredings.
Alles reg.
So ons kyk na 'n paar pseudokode 'n oomblik gelede.
En hier is 'n groter uittreksel van pseudokode kode
dat ons 'n paar keer tot dusver gesien het.
En laat ons gebruik dit is 'n geleentheid nou 'n nuwe ontwikkeling bekend
tegniek wat ons gedoen het sien algoritmies
verlede week toe ons gekyk na merge soort.
Maar laat ons formaliseer dit en sien hoe ons kan dit gebruik in die werklike kode,
en dan gaan ons dit gebruik tegniek in die pad af die meeste
waarskynlik sekere ander probleme op te los.
>> So dit was een van die eerste programme wat ons ooit geskryf het, al is dit in pseudokode-kode.
En wat hierdie program ons toegelaat om kursus
was om Mike Smith in 'n telefoon boek.
En let veral lyne agt en 11 wat hierdie Go To verklaring gehad het.
En in die feit, sekere tale, C onder hulle,
eintlik 'n stelling wat letterlik
gaan na wat jou toelaat om spring na 'n spesifieke lyn.
Dit is oor die algemeen afgekeur omdat dit kan baie maklik misbruik word
en jy kan begin spring jou program oor die hele plek in teenstelling
om die gebruik van die soort logika en die beheer vloei
dat ons tot dusver gebruik het met net loops en voorwaardes en dies meer.
>> Maar ons kan hierdie algoritme vereenvoudig in pseudokode kode soos volg.
In plaas van hierdie iteratiewe of herhaling benadering
waar ons bly om terug te gaan en terug en terug na drie lyn,
Daarom het ons nie net soort van punt en meer algemeen sê in lyn sewe en 10,
vervang net die twee pare lyne met,
anders as Smith vroeër is in die boek wat ons sal
soek Mike in die links helfte van die boek.
Anders as Smith is later in die boek, soek Mike in die regte
die helfte van die boek.
En let reeds rondom die ontstaan.
Reg?
Ek is op soek na Mike in die telefoon boek en dan
Ek het uiteindelik getref miskien lyn sewe of miskien lyn 10
en my opdrag aan myself is soek vir Mike in die helfte van die telefoon boek.
Wel, hoe kan ek soek vir Mike?
Ek is in die middel van soek vir Mike, hoekom
jy soort van die stuur my in 'n sirkel?
Maar dit is OK, want wat is gebeur met die omvang van die probleem,
soos geskryf in die lyn 7 en 10?
Ons is nie net soek sê vir Mike, soek Mike.
Ons spesifiek sê wat?
Soek hom in die linker helfte van die regter helfte wat effektief is
die helfte van die grootte van die probleem.
So dit is OK dat ons soort betrokke te raak in hierdie sirkulariteit,
hierdie omsendbrief argument, want ten minste is ons
die maak van die probleem kleiner en kleiner.
En uiteindelik gaan ons bereik dat die sogenaamde basis geval waar
ons het net een bladsy left-- as ons vrywilliger laaste week
did-- ons het 'n bladsy links en dan moet ons dit nie doen nie
te hou soek na Mike Smith want hy is óf op daardie bladsy
of hy is nie.
>> So, hoe kan ons hierdie idee, hierdie soort van sirkulariteit in werklike kode?
Wel, ons kan 'n tegniek hefboom dit is algemeen bekend as rekursie.
En ons het dit in die gesien pseudokode vir merge soort verlede week.
Onthou dat dit was die pseudokode vir merge soort.
Dit is waarskynlik nog makliker as borrel of keuse of invoeging soort
net in terme van die eenvoud waarmee jy kan dit uit te druk.
>> Maar dit is omdat ons is soort van sirkulêr
sê, soek vir iets deur weer soek vir dit.
Maar ons is op soek hetsy op die linker helfte of die regter helfte
en dan uiteindelik ons samesmelting in hierdie geval.
Maar hier, ook met daardie twee soort lyne,
het ons dit het weer idee van rekursie.
En konkreet wat dit beteken, in die konteks van 'n algoritme,
is dat 'n algoritme is rekursiewe as dit gebruik of noem homself.
>> Of in terme van C, 'n funksie is recursive-- 'n funksie genoem
cat is rekursiewe as cat, iewers in die bron-kode,
noem die funksie cat self.
En dit is sleg as al cat ooit doen is noem homself weer en weer.
Dit is OK as cat uiteindelik tot stilstand kom, net soos saamsmelt soort, deur te sê, wag 'n minuut,
as die probleem is super klein, byvoorbeeld,
of ek het hom gevind wie ek is soek, net terug te keer.
Moenie rekursief nie, moenie siklies myself weer te bel.
>> En so laat ons neem 'n blik op hoe dit eintlik kan werk.
So ek gaan om voort te gaan en oop twee bronkode voorbeelde hier.
Een van die sogenaamde sigma 0.
En dit is glad nie rekursiewe, maar laat ons neem
'n blik op wat hierdie program nie.
Ek het uitgetrek uit al kommentaar van dit, maar almal
van die bron-kode op CS50 se webwerf het kommentaar as jy
wil weer later deur te lees.
En laat ons doen 'n paar van gesonde verstand tjeks hier.
>> So aan die bokant van hierdie kode, ons het, sluit CS50.h.
Wat beteken dit?
Hoekom is dit hier?
In terme redelike leek se.
Wat doen dit?
Ja.
>> GEHOOR: So wat GetInt funksie werk.
>> DAVID J. MALAN: Sodat die GetInt funksie werk.
Omdat die binnekant van hierdie lêer, CS50.h, wat
ons sal sien voor lank in terme van die bron-kode,
het 'n klomp van die funksies declared-- GetInt, GetString,
en 'n klomp van die others-- en tensy ons eintlik wat insluit lyn,
samesteller klang is nie gaan om te weet dat dit bestaan.
En dieselfde geld vir lyn twee, waar int gedefinieer
printf, wat is 'n funksie ons hou die gebruik nogal 'n bietjie.
Nou, lyn vier lyk 'n bietjie funky want dit is net 'n een sak.
Dit het 'n kommapunt, geen krullerige draadjies, geen kode binnekant van dit.
Maar wat het ons 'n beroep hierdie ding in weke verlede?
Ja.
So 'n prototipe.
En hoekom het ons 'n prototipe wat blyk
om 'n bietjie oorbodig wees gewoonlik omdat ons gewoonlik
sien die funksie weer later in die lêer, reg?
So hoekom doen ons have-- jy net krap jou kop, maar ek sal dit vat.
Ja.
>> GEHOOR: [onhoorbaar] funksie na die hoof.
DAVID J. MALAN: Presies.
Sodat die samesteller weet jy sal uiteindelik definieer of te implementeer
daardie funksie na hoof, vermoedelik.
So klang en mees samestellers is soort van stom
en hulle sal net weet wat jy hulle vertel.
En as jy wil gebruik 'n funksie genoem sigma,
jy beter leer samesteller dat dit bestaan ​​in advance.
>> Nou, hoof self, selfs al is dit 'n klomp van lyne,
is redelik vertroud hopelik deur die nou.
Dit het 'n do while lus wie se doel in die lewe
hier blykbaar is om 'n te kry positiewe heelgetal van die gebruiker.
En net hou hom neul of haar totdat hulle saam te werk.
Toe ek in lyn 16 Ek het 'n interessante gesprek.
IntAnswer.
Wat aan die linkerkant kant gee my 'n Int
wat kan store-- genoem Answer-- wat gaan om te slaan, glo,
die terugkeer waarde van sigma.
So sigma is net 'n arbitrêre maar betekenisvolle naam
wat ek aan 'n funksie wie se doel in die lewe
is een argument-- neem ons sal dit N bel in hierdie case--
en net die som van dat die getal neem plus elke positiewe getal wat
kleiner as wat dit.
>> So as ek slaag in die nommer 2 te sigma, ek wil byvoeg 2 plus 1
plus 0-- nie 0-- sodat gee my 3.
As ek slaag in 3 tot sigma, ek wil het 3 plus 2 plus 1, wat gee my 6.
En so meer.
So dit voeg net al die getalle minder as of gelyk aan dit.
>> Nou, hier af Ek gaan net om die druk van die antwoord.
So as 'n vinnige gesonde verstand tjek, laat maak sigma 0-- dot streep sigma 0--
en laat my tik in 2.
En Ek het wel kry 3.
Laat my tik in 3.
Ek het wel kry 6.
En as iemand die wiskunde vinnig kan doen nie, as ek dit doen 50 wat gaan ek kry?
>> GEHOOR: [onhoorbaar].
DAVID J. MALAN: Wel, nee.
Maar 1275 wat is redelik naby.
So, dit is die gevolg van doen 50 plus 49 plus 48 plus 47 plus 46
al die pad af na 1.
So dit is al sigma doen.
Maar laat ons sien hoe ons het geïmplementeer nou.
So af hier is die funksie self.
En dit lyk nie te hê iets te doen met nog rekursie.
In werklikheid, is ons met behulp van 'n ou skool tegniek.
Ek is 'n bedrag initializing veranderlike genoem nul, dan het ek 'n foreloop hier
en ek verklaar 'n Int genoem Ek, die opstel van dit gelyk aan 1--
al het ek dit gelyk aan kon stel nul, maar aangesien ek doen Daarbenewens
Wie gee om as dit is zero of een.
Dit gaan geen effek.
>> So ek so lank as wat ek is iterating minder as of gelyk aan m, wat
is die argument dat geslaag in.
En dan het ek hou net die verhoog en insig I.
van die lus al wat ek doen is som doen plus gelyk I. En dit is doelbewuste.
Ek wil nie te doen nie, in hierdie geval, soos 'n bedrag plus plus.
Ek wil eintlik voeg die huidige waarde van I
wat word steeds groter en groter en groter om die lopende kerfstok.
>> En dan het ek som terugkeer.
En so antwoord kry die waarde som.
En dan druk ek dit uit.
So is daar 'n geleentheid hier alhoewel, soort vereenvoudig
hierdie kode konseptueel en die aard van die slag een is
omgee in terme van die eenvoud selfs al is dit
neem 'n rukkie om te sorteer van verstaan ​​waarom hierdie
is sterk in hierdie klein voorbeelde.
Hier is sigma one-- so die tweede weergawe van hierdie kode.
Alles up top identies so wat dieselfde storie geld as voorheen.
Maar nou laat ons kyk na die implementering van sigma wat
Ek het af Uiteindelik net hierdie lines-- vier reëls van die kode, regtig,
plus 'n paar krulhakies en wit ruimte.
>> Maar wat doen ek?
As m minder as of gelyk aan zero, ek moet soort van hanteer
dat super eenvoudige geval.
En as jy my hand nul of enigiets negatiewe wat net vreemd,
Ek gaan net na willekeur maar konsekwent nul terugkeer.
Ek wil nie hierdie ding kry in 'n paar weird oneindige
lus gevolg van 'n negatiewe waarde.
So ek net sê, as jy my gee nul of minder, ek terugkeer nul.
>> Maar dit is goed, want dit is dat enkele bladsy van die telefoon boek
wat oorbly.
Ek byt af 'n baie spesifieke probleem en nie iets rekursief roep.
Maar in lyn 31, wat ek blyk te wees doen?
Die hakies is net om dinge, hopelik, 'n bietjie duideliker.
Maar al wat ek doen is ek is terugkeer m-- ookal
jy me-- plus die hand waarde van m-- jammer,
plus die waarde van sigma van m minus 1.
So, wat beteken dit?
As jy vir my die nommer 3 as insette, die antwoord wat ek wil uiteindelik kry
6 want 3 plus 2 plus 1 gee my 6.
Maar hoe ek dink oor hoe hierdie kode loop?
Die eerste keer wat ek noem sigma en ek slaag in die waarde 3,
dit is soos om te sê op 'n stuk papier, hier is die waarde 3
en ek het dit geslaag is as sigma.
3 is natuurlik nie minder as 0, sodat die IF voorwaarde geld nie.
Die anders nie.
So, wat moet ek doen?
Ek wil m terugkeer, wat 3, plus sigma van m minus 1.
So laat my spoor van hierdie hou.
Ek gaan hierdie plaas stuk papier neer.
En watter waarde te wees duidelik, ek gaan om te slaag
in sigma op hierdie punt in die verhaal?
Watter getal?
2, reg?
3 minus 1 is 2.
So ek moet net 'n bietjie stukkie papier hier.
So nou sigma is om weer genoem.
En ek het doelbewus gestel dit neer, want dit is
soort van soos pousering dat die weergawe van die storie
want nou is ek gefokus op sein van m minus 1.
So m was 3, m minus 1 is 2.
So hier is 2 wat ek geslaag het.
2 is natuurlik nie minder nie as 0 sodat geval nie van toepassing nie.
Anders kom Ek terug m, wat is hierdie ding, plus sigma van watter waarde?
So as sigma van 1-- omdat m is nou 2 so 2 minus 1 is 1.
So nou het ek net die waarde 1.
Ek is verby net die aantal 1 om die funksie sigma--
of myself here-- so 1 is natuurlik nie minder as nul, nog nie van toepassing.
>> Anders terugkeer 1 plus sigma van wat?
0.
So laat my onthou net dat.
Ek kom terug na wat later kry.
Nou gaan ek voort en jota gaan die nommer 0, want dit is
my argument of parameter.
Ek is verby die getal 0 en uiteindelik hierdie proses
van net herhaal myself advertensie nauseum nie ophou want wat
ek onmiddellik doen wanneer ek sien dit 0?
Ek nul terugkeer.
So nou moet jy die storie rewind.
>> As ek nou terug gaan in tyd, wat was die mees onlangse ding
Ek het as jy letterlik was omwikkelen n video?
Ek gaan haal die mees onlangse 1 en dit gee my 1 plus 0 is 1.
As ek hou omwikkelen die storie, wat gaan om te gee my
2 plus hierdie hardloop waarde, wat 1.
So dit is 3.
En dan gaan ek omwikkelen hou.
Toe ek die eerste keer die nommer 3-- so 3 plus 3 gee my 6.
>> En nou, as jy het teruggedraai die video tot hierdie punt,
dit was die eerste vraag het ek gevra.
Wanneer geslaag 3, wat is sigma van 3?
Dit is inderdaad 6, die som van al hierdie stukkies papier.
So as dit neem 'n rukkie om draai jou gedagtes rond, is dit goed.
Maar is van mening dit was 'n little-- dit was baie doelbewuste dat ek gestapel
hierdie getalle op die top van mekaar.
Dit is soort van soos 'n memory-- 'n rekord in die tyd,
soos 'n scrubber in 'n video, dat ek inderdaad kan rewind in.
En ons gaan om terug te kom om dat metafoor in net 'n bietjie.
>> Maar eers, dit blyk dat daar 'n baie geeks en snaakse mense,
Ek dink, op Google.
Sou iemand wat baie goed op Googlen gedagte
kom vir 'n oomblik en help my soek vir iets?
Baie, baie lae sleutel.
Iemand wat nooit kom voor, miskien.
OK.
Ja?
Kom op.
Kom af.
Wat is jou naam?
>> SAM: Sam.
>> DAVID J. MALAN: Sam, kom op sit.
Dit is dieselfde nie.
Bly te kenne.
Hey.
Kom oor.
So al wat ek nodig het om te doen, as jy kan, Sam, hier is Google.
Jy kan soek vir die term rekursie?
Buit nie.
>> En let's-- nou ja.
OK Klik dit.
Beter klik nie.
Ahh, kry dit.
Geen?
OK.
So kom ons doen 'n paar ander.
Nie soseer verwante akademies hier, maar het jy
ooit gesoek Google vir anagram?
>> SAM: No.
>> DAVID J. MALAN: OK.
Soek anagram plaas van rekursie.
Hoe gaan skeef.
Jy al ooit gesoek skeef?
Nou, hierdie een is 'n bietjie moeilik om te sien, maar hopelik everything's-- OK.
Dis net ek en jy hierdie geniet.
OK.
>> So uiteindelik, hierdie one's-- dit is 'n bietjie skeef.
Nou 'n vat roll.
Wonderlik.
Alles reg.
Baie dankie aan Sam.
Hier gaan jy.
Dankie.
>> So wat gaan aan in alle van hierdie dom voorbeelde?
So regtig, onder die kap van Miljoene reëls van die kode Google se
blykbaar is 'n paar dom AS voorwaardes wat in wese
seker te maak dat die gebruiker getik in hierdie frase,
iets wat waarskynlik het te doen 'n triviaal bedrag van die tyd
te implementeer net wees amusant op hierdie manier.
Maar dit is al wat dit kook af na onder die kap.
Maar, natuurlik, rekursie meer van die geekier
byvoorbeeld onder diegene spesiale truuks.
En sekerlik daar is ander daar buite so goed dat ons dalk nie eens
nog net ontdek.
>> So 'n blik of te oorweeg nou die volgende program,
en beslis enige gryp van hierdie op jou pad uit.
Ek gaan om voort te gaan en maak 'n program wat
gaan probeer om twee waardes te ruil.
Maar voordat ons daar te gaan, laat ons dit doen.
Kon ons kry 'n meer vrywilliger, dink ek?
Wil jy om vrywillig?
Geen?
Kom up.
Alles reg.
Sodat jou naam is wat?
>> LAUREN: Lauren.
>> DAVID J. MALAN: Lauren.
Kom op, Lauren.
So Lauren is om hier uitgedaag soos volg.
Bly te kenne.
So Lauren hier het in die voorkant haar twee leë koppies.
En ons het 'n paar oranje sap en melk
en ons gaan om te gaan voor en doen die volgende.
Ons is net gaan om dit te vul.
'N Paar onse melk oor hier en laat ons vul 'n bietjie lemoensap hier.
>> En in die voorkant van al hierdie gehoor,
ruil die twee waardes van hierdie koppies.
Sit die lemoensap in die melk beker en die melk in die koppie lemoensap.
Hoe sou jy dit doen as jy by huis en het toegang tot ander voorrade?
LAUREN: Sit dit in 'n ander koppie.
DAVID J. MALAN: OK.
So laat ons 'n tydelike veranderlike, as ons wil.
En gaan nou voort en implementeer dieselfde uitruiling prosedure.
So goed.
Ons het PB sit in die tydelike veranderlike, melk in die PB veranderlike,
En nou het die tydelike veranderlike in die melk veranderlike.
OK.
So baie goed tot dusver gedoen.
So dit blyk dat out-- hou gedink vir net 'n oomblik.
Hier net geek dit 'n bietjie, hierdie sou die ooreenstemmende C-kode wees
dat ons net geïmplementeer word.
Ons het twee insette, A en B, beide van wat ons nou net sal sê vir die eenvoud is
int se.
En let hier, as ek wil ruil die waardes van die twee veranderlikes, A en B,
ons inderdaad 'n middelman nodig, 'n tydelike veranderlike, 'n tydelike beker,
waarin die gooi een van die waardes sodat ons 'n plekhouer vir dit.
Maar dan die kode is presies Lauren hier geïmplementeer.
>> Nou, net om 'n te kry bietjie crazier, blyk
dat jy dit kan doen sonder 'n tydelike veranderlike.
Om dit behoorlik te doen, al is, ons gaan om te kul met 'n paar chemie.
Ons het 'n paar ekstra koppies hier.
So die naaste ding wat lyk soos melk en water perhaps--
of melk en OJ-- is ons 'n paar water, so ons sal hierdie een vul
met 'n paar onse helder water.
Dit is waarskynlik te veel.
Ja.
Dit is beslis te veel.
Hou op een sek.
>> En nou het ons olie, wat, soos ek onthou vanaf middel skool chemie klas,
Hopelik sal dit nie meng met water.
Maar dit soort van soort lyk soos melk en PB.
So nou, sonder die gebruik van 'n tydelike veranderlike,
kan jy daardie twee waardes te ruil?
So olies gaan in die water beker, water gaan in die olie koppie.
LAUREN: Geen ander koppies?
DAVID J. MALAN: Geen ander koppies.
En ek het nie eintlik hierdie getoets voordat vanjaar
so ek weet nie of dit sal eintlik werk chemies.
Dit is nie veronderstel om te gebeur.
Is dit werk?
Alles reg.
So skei?
Goed.
Nou het ons die kry water in die ander beker.
Slimmer chemie konsentreerders kon waarskynlik doen beter as ek.
>> LAUREN: Die water is op die bodem.
>> DAVID J. MALAN: Die water-- dit was wat is die sleutel van die laaste keer dat ons dit gedoen het.
Jy het om dit te doen in die regte volgorde.
Ja.
That's-- OK.
So nou het ons twee koppies olie.
OK.
Dit is OK.
Maar as dit chemies gewerk as I--
>> LAUREN: Dit is water.
>> DAVID J. MALAN: Dit is meestal water.
Alles reg.
Maar dit is nog steeds dieselfde beker as tevore.
So gooi it-- probeer om dit daar.
OK.
Dit is 'n goeie gebruik van klastyd vandag.
OK.
So nou we-- nice.
Soortvan.
Alles reg.
So baie goed.
Dankie aan Lauren.
Baie goed gedoen.
>> So net jou gedagtes blaas, en dit is dalk iets
om te speel met as jy wil in CS50 ID, jy kan, in werklikheid, ruil twee veranderlikes
sonder die gebruik van 'n tydelike heelgetal.
En dit is die ooreenstemmende C-kode.
En as jy onthou van verlede Woensdag, het ons ', as kortliks,
'n paar nuwe operateurs in C. En doen iemand onthou wat die klein wortel
simbool is, wat min driehoekige simbool van die sleutelbord verteenwoordig?
Wat bis operateur?
>> GEHOOR: EXOR.
>> DAVID J. MALAN: EXOR.
Exclusive Or.
So as jy wil, net vir die pret op huis, om 'n en b twee arbitrêre gee
waardes soos enige eight-- en ek sou 'n agt bietjie waarde te kies.
As jy dit doen met 32 ​​stukkies, jy sal baie vinnig verveeld.
Maar net gee 'n bietjie van 'n agt waarde wat ook al, een of twee,
en gee b 'n soortgelyke waarde.
En dan met behulp van die definisie van XOR van verlede Woensdag,
toepas bietjie vir bietjie, elk van diegene agt bisse in elk van a en b,
en dan doen dit presies per hierdie kode.
En dit is nie korrek wat jy sien hier op die skerm.
Dit kom wel af drie XOR bedrywighede
en een of ander manier mettertyd 'n en b sal posisies te ruil
sonder dat enige inligting.
>> So het die olie en water truuk is die naaste werklike wêreld inkarnasie
Ek kon dink om na te boots nie.
Maar dit is sekerlik makliker om gebruik 'n tydelike veranderlike,
soos in hierdie geval hier.
En dit is ook 'n geleentheid sê Ook hierdie soort van mikro optimalisering,
as 'n rekenaar wetenskaplike sou sê, terwyl soort pret
om te spog oor hoe jy dit gedoen het sonder soos uitruiling met 'n ekstra veranderlike,
dit is nie al wat dwingende.
Want om 32 stukkies, soos red in die geval van 'n werklike int,
is nie al wat dwingende op 'n stelsel waar
jy kan met behulp van tien megagrepe of selfs meer so geheue hierdie dae.
En in die feit, wanneer ons tot 'n later probleem stel
en jy spel implementeer checker en jy sal
uitgedaag word om so te doen met hierdie so min geheue en so min
tyd as moontlik op die computer-- jy nog
'n week om te implementeer it-- jy have-- jy sal
uitgedaag om daardie hulpbronne te verminder.
En dit is werklik die enigste occasion hierdie semester
waar jy aangemoedig word om te skeer af selfs die beste prestasie
kos anders.
>> So hoe kan ons what-- sien dit in die werklike kode?
Laat my nou gaan voort en maak 'n voorbeeld
wat doelbewus genoem Geen Swap omdat dit nie
in die feit dat die veranderlikes te ruil as jy eintlik kan verwag.
So laat ons neem 'n blik.
Hier is 'n program wat nie CS50 het biblioteek gaan, net standaard I / O.
Nou het ons 'n prototipe vir swap up top wat net
beteken dit het later gedefinieer.
En hier is die hoof.
>> Ek arbitrêr opgedra x en y, onderskeidelik, die waardes een en twee
net omdat hulle is klein en maklik om te dink oor.
En dan het ek net 'n klomp van die printfs waar ek 'n gesonde verstand tjek. x is 1
en y is 2 is vermoedelik wat daardie printfs sal sê.
Sodat daar geen magic dusver.
>> Dan gaan ek om te eis met druk def, uitruiling dot dot dot.
Ek gaan die swap noem funksie, verby in x en y.
En laat ons veronderstel vir nou dat swap presies geïmplementeer
soos dit was 'n oomblik gelede met 'n tydelike veranderlike.
En so het ek beweer vrymoedigheid, verruil.
x is nou hierdie en y is nou dat.
Maar die lêer, natuurlik, genoem Geen Swap.
So laat eintlik sien wat gebeur.
As ek nie ruil en dan stel doen ./noswap, x is 1, y is 2.
Uitruiling verruil.
x is 1, y is 2.
So dit lyk eintlik selfs gebrekkig al swap-- laat rol af now--
presies geïmplementeer per die Ek code 'n oomblik gelede voorgestel.
So ons is nie van plan om fancy kry met die XOR dinge vir nou.
Dit is ook, moet net werk soos met die melk en PB,
maar dit lyk nie te werk.
>> So laat dit weer te doen.
Miskien het ek net nie hardloop dit reg.
So laat weer loop Geen Swap.
Miskien I-- no.
So dit is net nie werk nie.
So kom ons doen 'n bietjie gesonde verstand tjek.
Laat my hier gaan voort in Swap en voeg net, wag 'n minuut,
n is% i / n en laat plug-in die waarde van a.
Want ek wil regtig om te sien wat aangaan.
En inderdaad, dit is 'n debugging tegniek
wat jy kan gebruik in kantoorure of by al die huis,
soortgelyk aan die eerste helfte van Dan Video Armendariz in PSET3
waarin ons druk bekendgestel def as 'n aanbevole tegniek, ten minste
vir eenvoudige gevalle.
Laat my gaan voort en loop maak nie weer omruil, ./noswap.
>> Interessant.
So sien wat lyk om waar te wees. x is 1, y is 2, maar 'n 2 indien b 1.
So die twee een of ander manier het omgeruil maar x en y kry nie omgeruil.
So duidelik wees, wat gebeur is, hier het ek x en y
en dié veranderlikes in die plaaslike omvang van die belangrikste, ek verby in x en y
om te ruil.
Nou, ruil, as 'n afsonderlike funksie, is vry om sy argumente noem
of sy parameters enigiets wat dit wil hê.
Cat of kroeg of x of y of a of b.
Net om duidelik te maak dat hulle nie identies aan x en y per se,
Ek het gesê 'n en b.
Maar ons kon hulle niks wat ons wil noem.
>> En so lyk dit soos swap word geslaag
x-- AKA a-- en dit is oorgedra y-- AKA b.
Een of ander manier hierdie drie lyne uitruiling presies daardie waardes
Lauren het met die melk en PB.
Maar wanneer ons uit te druk die waardes, A en B
is inderdaad ruil, maar x en y het geen verandering aan hulle.
Onthou dat x en y hier.
>> So kan ons sien via Nog 'n tegniek as well.
En dit is ook 'n tegniek ingebed in die probleem stel drie.
Kom ons gaan voort en doen dit in CS50 ID as jy nie reeds.
Op die regterkant ons hierdie blad Debugger.
En as jy dit oopmaak, daar is 'n paar arcane inligting
dit is gegooi by jou aanvanklik.
Maar laat ons terg hierdie uitmekaar ware vinnig.
>> So een, jy sien plaaslike veranderlikes.
Blyk dat bou in CS50 IDE, en 'n baie van die ontwikkeling omgewings meer
algemeen, is 'n debugger.
'N instrument wat jou toelaat om te sien visueel wat gaan aan die binnekant van jou program
sonder om plek te te voeg printfs en die opstel en bestuur van
en die toevoeging van printf en die opstel en hardloop, wat reeds in kantoorure
of 'n huis, is waarskynlik kry mooi saai.
>> So hier, in 'n oomblik, ons is gaan om te sien in real time
die waardes van ons plaaslike veranderlikes.
Ons gaan ook in staat wees om op te rig wat is inspeksiepunte genoem wat
geleenthede in my program te breek uitvoering op 'n spesifieke reël van die kode
dat ek nuuskierig oor.
Reg?
Hierdie programme hardloop in 'n split sekonde.
Dit is soort van mooi vir ons stadiger mense in staat wees om te breek, neem 'n oomblik, sien
wat gaan aan om 'n sekere lyn van die kode
sonder die program geploeg deur dit en heeltemal afwerking.
So 'n inbreekpunt gaan ons toelaat om breek en breek op 'n sekere punt.
>> Call stack is 'n fancy manier sê wat funksies is tans
genoem op die oomblik.
Main word altyd eerste genoem.
Maar as Main noem 'n funksie genoem Swap,
ons eintlik gaan om dit te sien toring van funksies wat gewees
genoem in omgekeerde chronologiese volgorde.
So laat sien.
>> Ek gaan om te vergroot.
Ek gaan om terug te gaan na my kode.
En net omdat ek wil hier pedanties wees,
Ek gaan om voort te gaan en klik net aan die linkerkant van die lyn vyf.
En dit skep 'n rooi dot.
En let op die regterkant dat die debugger weet, hey,
Ek het net gesê 'n breekpunt op noswap.c line vyf spesifiek
op hierdie lyn van die kode.
So die debugger weet dat ek het versoek dat die volgende keer
Ek hardloop my program dit breek uitvoering daar eerder as om net
die bestuur van die hele ding super vinnig.
>> So nou gaan ek op die Debug knoppie op die top van die IDE
en wat gaan die volgende te doen.
Dit gaan 'n oop aanvanklik ietwat scary soek tweede terminale window--
remote debugging van gasheer so en such--
en ons sal terug te kom wat al beteken dit dat voor lank.
Maar wat belangrik is vir nou is dat die rooi dot getref,
die debugger het doelbewus gestop execution--
nie op daardie lyn per se, maar op die eerste lyn van werklike kode in daardie funksie.
En dit is hoekom lyn sewe is nou geel gemerk.
>> En nou, laat ons 'n blik op die regte kant.
Dit lyk, by verstek, mooi genoeg nie, x het watter waarde?
0.
En y het watter waarde?
Zero.
En dit is wat verwag kan word in die sin dat x en y-- geel line-- het
nog nie uitgevoer word.
So x moet nie die waarde 1.
Dit mag dalk 'n ander waarde, 'n sogenaamde vullis waarde.
En ons het gelukkig in die sin dat dit nul op hierdie punt, wese.
>> So nou is daar net 'n paar knoppies ons nodig om te sorg
oor wanneer debugging op hierdie manier.
Let hier, ons het 'n Play knoppie.
En as ons speel of druk hervat, dit is net
gaan om te loop deur die res van die program
of totdat dit treffers ander breekpunt.
Maar ek het nie enige ander stel inspeksiepunte so dit is net
gaan om te loop deur die einde.
Dat die soort van nederlae die doel van skeer rond.
>> So in plaas, ek omgee hierdie ikone na regs.
En as ek Beweeg oor hulle, soos jy moet ook
jy sal sien bietjie tips-- instrument wenke.
Hierdie een is stap oor.
Nou dit beteken nie skip die volgende lyn van die kode.
Dit beteken net dit uit te voer en skuif na die volgende, skuif na die volgende,
skuif na die volgende.
Met ander woorde, via dat die knoppie, kan ek loop
deur my kode een stap op 'n tyd.
Reël vir reël, letterlik.
Nou, aan die regterkant van dat daar 'n ander een
dat ons sal sien in net 'n oomblik.
Dit is die sogenaamde Stap in ikoon wat
gaan my toelaat duik in 'n ander funksie.
Maar laat ons sien dit in net 'n oomblik.
So ek gaan klik stap oor.
En nou sien, as ek op hierdie knoppie regs bo,
hou jou oë rofweg onder Plaaslike Veranderlikes en kyk wat gebeur met x.
x is nou 1, want die geel lyn is nou uitgevoer
en ons het verhuis na reël 8.
En in net 'n oomblik y moet hopelik geword 2.
>> Nou, niks wat interessante gebeur vir 'n bietjie.
Dit alles is is printf.
En sien, in my sekondêre terminale venster, sien ek die uitset van die gedrukte def.
En nou het ek 'n maak besluit as die programmeerder.
Ek kan stap oor die lyn van kode, die uitvoering van dit, maar nie
kry nuuskierig oor wat die binnekant.
Of ek kan eintlik stap in dit en gaan binne Swap self.
So kom ons doen die laasgenoemde.
>> Laat my gaan voort en klik nie oorstap maar stap in.
Kennisgewing, al van 'n skielike die venster veranderinge
om die eerste hoogtepunt reël van die kode in te ruil.
Dit is lyn 21.
En nou, wat is soort van funky is dat, As jy kyk hier oor, soos verwag,
'n komma b is 1 en 2, onderskeidelik.
Hoekom is temp 32767?
Daaraan te herinner dat temp, baie soos die leë koppie 'n oomblik gelede
word hier verklaar op die lyn 21.
Hoekom 32,000- Ek bedoel, hoekom is dit is net 'n paar weird waarde?
Ja?
>> GEHOOR: Dit is nie geïnisialiseer.
>> DAVID J. MALAN: Dis nie geïnisialiseer.
So ons rekenaar altyd het fisiese geheue.
Dit het altyd fisiese RAM.
En daar is altyd nul se en een is daar, reg?
Omdat ons met behulp van ons rekenaar die hele dag lank,
jy gebruik die CS50 IDE of die bedieners hele dag lank.
Sodat RAM óf het 'n paar nulle of iemand se of 'n nulle en ene.
Maak nie saak of nie jy gebruik hulle.
Jy kan nie net leeg ruimtes waar jy wil stukkies.
Hulle is óf nulle en ene.
>> So dit blyk dat temp, want ons het dit nog nie geïnisialiseer,
ons het die 32 stukkies, maar hulle het nie geïnisialiseer om enige bekende waardes.
So wat hulle vroeër was die meeste onlangs gebruik for-- diegene 32 bits--
ons is maar net die sien van die artefakte van 'n paar vorige gebruik van die spesifieke 32
stukkies.
So gou as ek klik stap oor al is, Sjoe, temp gaan om die waarde 1 te kry.
En as ek dit weer doen, 'n is gaan wees gegewe die waarde 2
en dan b gaan gegee word om die waarde 1.
>> En so wat is lekker nou op hierdie punt in die verhaal
is dat die debugger is wys my, super stadig
op my eie pas, wat die toestand van Swap is.
Maar let op die top hier, kennisgewing dat die oproep stapel eintlik
het twee lae om dit te.
Nou is die een wat uitgelig is, soos Swap, as ek op Main plaas,
sien hoe die plaaslike veranderlikes omdat die ontwikkelaar kan net hop
rond en gaan in 'n verskillende omvang.
So selfs al is ons almal om dit te doen werk en korrek uitruiling A en B,
as ek gaan heen en weer tussen Swap waar a 2 en b is 1 en Main,
het Main geraak het nie?
Geen.
So, wat is die afhaal hier?
Wel, dit blyk dat enige tyd jy 'n funksie roep soos Swap,
en jy het dit argumente, slaag wat jy verby die funksie Swap
in hierdie geval is 'n afskrif van daardie argumente.
So as x en y elke onderskeidelik 32 stukkies, wat Swap is om
is twee nuwe plaaslike veranderlikes, of argumente,
bekend as 'n en-b, maar dit is arbitrêre names-- maar die patroon van die nulle
en dié van binnekant a en b opgelyn identies aan x en y
maar hulle is nie die dieselfde as x en y.
>> Dit is asof Main het op sy stuk papier die nommer 1 en 2 vir x en y,
en dan wanneer dit hande wat stuk papier te ruil,
Swap baie vinnig kry sy eie pen, skryf neer
1 en 2 op sy eie vel papier, hande terug die oorspronklike xy om Main
en dan doen sy eie ding met a en b.
En dit is nou super belangrik omdat dit het nontrivial implikasies
vir eintlik skryf korrekte kode want dit wil voorkom asof ons nie kan ruil
twee veranderlikes.
>> Ek het 'n korrekte Swap funksie geskryf.
Ons het dit geïmplementeer met Lauren as 'n korrekte swap funksie in werklikheid,
maar blykbaar nie een van daardie sake as jy nie kan nie eintlik
ruil twee waardes permanent.
Sodat ons 'n ander manier moet om werklik te kry op hierdie,
en ons moet in staat wees om eintlik die probleem op te los.
En dit blyk out-- en ons sal kom terug na hierdie spesifieke prentjie
voordat long-- dit is een manier wat jy dalk jou rekenaar se geheue te trek.
Dit is net 'n reghoek.
Jy kan dit enige teken aantal maniere, maar dit is
gerieflik om dit te trek as 'n reghoek vir die volgende rede.
>> Ons gaan vandag begin en verder praat oor die sogenaamde stapel.
En die stapel is net 'n stuk van RAM-- 'n stuk van memory--
wat funksioneer toegang wanneer hulle genoem.
En so is dit blyk dat by die heel onderkant van die stapel
is waar al die plaaslike veranderlikes Main se en org C en org V en al daardie dinge
gaan om te gaan by verstek. En as Main roep 'n ander funksie soos Swap,
Wel, Swap gaan na 'n ander te kry laag geheue bo dit.
>> En so net om jou 'n vinnige oppervlakkige gee prentjie van hierdie, as ek gaan oor here--
en laat my spieël op die oorhoofse as well-- wat regtig ek het,
As ons omgee net oor die onderkant van hierdie foto vir nou,
is dat wanneer ek 'n program uit te voer en Main kry genoem,
Main gegee 'n stuk van RAM in my rekenaar wat
aan die onderkant van hierdie sogenaamde stapel.
En ek gaan om dit te trek doelbewus as 'n vierkant.
So dit is soos 32 stukkies of vier grepe.
En as dit hooffunksie het 'n veranderlike genoem x met 'n waarde van 1
en dit het 'n veranderlike genoem y met die waarde van 2, dis
soos die neem van hierdie splinter van geheue wat Main gegee is deur die bedryfstelsel
stelsel en deel dit op sodat die eerste plaaslike veranderlike gaan hier,
die tweede een gaan hier, en dit is dit.
>> Wanneer Main oproepe Swap, Swap kry sy eie deel van die geheue
dat ons sal trek soos hierdie van die bedryfstelsel,
en dit gaan om die eie plaaslike veranderlikes gebaseer
op ons implementering vroeër met plaaslike veranderlikes 'n
en b wat aanvanklik kry die waardes 1 en 2.
Maar dan, sodra die Swap kode voer,
en Lauren eintlik swaps die PB en melk, wat gebeur?
Wel, dit 2 steeds 'n 1, hierdie 1 is besig om 'n 2, en, by the way,
daar is 'n tydelike veranderlike wat die wese gebruik dat die hele tyd wat uiteindelik
gaan weg.
Maar dit maak nie saak hoeveel werk wat jy doen
in hierdie lyn of-- in hierdie geheue spasie, x en y is heeltemal onaangeraak.
>> Sodat ons 'n manier van gee nodig Ruil en funksies soos dit
geheime, as jy wil, om funksies like-- om geheue soos x en y.
So laat ons neem 'n blik op 'n voorbeeld wat help
ons sien presies wat was gaan oor hierdie hele tyd.
Ek gaan om voort te gaan en maak Vergelyk Zero.
En ek gaan om te sluit ons debugger, ek gaan
om hierdie scary soek boodskap sluit die regverdige sê, wag 'n minuut,
jy is in die middel debugging.
Ek gaan hierdie blad hier wegsteek net om terug te gaan eenvoud.
So moenie bekommerd wees as GDB is vermoor.
Dit beteken net dat die program het is op te hou, doelbewus in hierdie geval,
deur My nie.
>> En nou Vergelyk Zero doen dit.
Ek gebruik die CS50 biblioteek in standaard I / O.
Ek het 'n hoof funksie wat die eerste keer het sê, sê iets, en kry 'n string.
Weer en sê dit dan kry 'n ander string.
En sien dat hierdie twee stringe geroep s en t, onderskeidelik.
En nou hierdie program Vergelyk Nul, sy doel in die lewe,
dit veronderstel is om my te vertel, het ek tik dieselfde ding?
En so gaan ek terug na week een.
Ek gebruik my gelyk gelyk operateur wat is die kwaliteit operateur.
Nie die opdrag operateur, die operateur gelykheid.
Ek is net te vergelyk s en t.
>> So laat eintlik gaan voort en doen dit.
En ek gaan om voort te gaan en maak Vergelyk Zero.
Ek gaan ./comparezero doen.
En ek gaan om te gaan voort en iets te sê
soos, kom ons doen ma in klein en hoe oor ma in hoofletters.
En natuurlik het ek verskillende dinge te tik.
Alles reg.
Dit is te verwagte.
>> Kom ons weer uit te voer nie.
Beide kere doen klein, klein.
Wat lyk super identies aan my.
Betree.
OK.
Miskien is dit net vreemd, want dit is nie my smaak grammatika.
So kom ons doen 'n kapitale MOM, kapitaal MOM, identies.
Verskillende dinge.
>> So hoekom is dit?
Wel, wat eintlik gaan op onder die kap hier?
So laat ons gaan terug oor hier vir 'n oomblik
en kyk wat GetString is eintlik.
Wanneer jy GetString noem, dit is 'n funksie wat ons
onsself geskryf het en dit op 'n manier kry 'n volgorde van die karakters van die gebruiker.
En laat ons aanneem dat die eerste keer as ek bel GetString, wat gee my
'n stuk van die geheue wat lyk soos hierdie.
En as ek getik in alle klein m-o-m-- en wat gaan nadat dit?
Net 'n vinnige gesonde verstand tjek.
>> Agteroorskuinsstreep nul.
Ons weet dat.
En onthou dat ons gespeel rond met die naam Zamila se
en 'n klomp van die ander name wanneer Rob is hier op soek
op wat gaan aan die binnekant van die geheue.
Sodat storie is presies dieselfde.
Dit is wat GetString terugkeer na my.
Nou, my kode 'n oomblik gelede gestoor die terugkeer waarde van GetString
in 'n veranderlike genaamd s.
En dan is die tweede keer wat ek dit noem, dit gestoor in 'n veranderlike genoem t.
>> So as ek gaan hier, ek moet om hierdie plaaslike variable-- trek
en ek oor die algemeen gaan trek 'n string as just-- ons sal
noem dit s-- as 'n klein vierkant hier.
En nou, somehow-- hoe werk ma gaan binne hierdie veranderlike s?
Wel, ons moet teruggaan eerste beginsels hier.
Wat is GetString eintlik terugkeer?
>> So dit blyk dat M-O-M backslash nul, en 'n aantal
van ander snare in die geheue soos Zamila en Rob of Andy of enige ander,
is natuurlik in ons RAM of geheue se rekenaar.
En jou geheue het like-- jy 'n gig RAM, twee gigs RAM,
of 'n miljard of twee miljard grepe, of miskien selfs meer van hierdie dae.
So laat ons veronderstel vir doeleindes vandag se dat dit maak nie saak hoe ons tel
hulle, maar ons kan elke nommer van daardie miljard of twee miljard
of 4000000000 grepe.
>> En laat ons net sê dat arbitrêr dit is die eerste hap, tweede byt,
derde, vierde.
Ek is doelbewus nie vir die gebruik van nul vandag, maar ons sal terug kom.
So met ander woorde, as dit is die heel eerste keer dat ek die gebruik van die program,
Ek is maar net gelukkig en die eerste byt is op plek mens dan twee
dan drie as vier.
En as ek gehou teken, Posbus nommer twee biljoen sal hier te wees nie.
>> So wat dink jy dan GetString terug eintlik?
Dit is nie die terugkeer van M-O-M backslash zero per se, want dit duidelik
sal nie pas in die boks wat ek geteken het.
So wat anders kan eintlik GetString terugkeer al hierdie weke?
Die antwoord is op die raad hier iewers.
Jy kan nie pas M-O-M backslash nul, so wat kan sin plaas te maak?
As jy het super slim te wees, om op die sogenaamde ingenieurswese hoed,
wat jy kan terugkeer?
Wat is die minste hoeveelheid van die inligting jy kan nog steeds opbrengs wat sou
laat vind M-O-M in die geheue?
Ja?
>> GEHOOR: Een.
>> DAVID J. MALAN: Een.
En waarom die een?
GEHOOR: Omdat dit sal vertel jy waar om te gaan [onhoorbaar].
DAVID J. MALAN: Presies.
Ek gaan net na die adres terugkeer van die string wat ek gekry het.
Die adres in hierdie geval is plek een.
So wat werklik word gestoor in s-- en elke string veranderlike dus far--
het nou net die adres van daardie string.
>> Intussen, as ek roep GetString 'n tweede keer en ek
tik in letterlik dieselfde thing-- M-O-M met lowercase-- M-O-M
en 'n ander backslash nul, en nou miskien my program se
reeds vir 'n geruime tyd so miskien hierdie is 10, is dit plek 11, dit is 12,
dit is 13.
Die rekenaars met behulp van 'n paar ander geheue vir watter rede ookal.
Wat nou gaan in my tweede veranderlike in my program t?
10.
Presies.
>> En so wanneer ons kyk na die bronkode van hierdie program
waar ek net probeer om die twee waardes te vergelyk,
is s gelyk gelyk aan t, wat is die ooglopende menslike antwoord?
Net geen want 1 is nie gelyk 10.
En so hierin lê 'n geleentheid vir ons regtig
om net terug te, weer, eerste beginsels en dink oor, wel,
wat gaan aan onder die enjinkap?
Ons het gepraat oor bits en bytes en geheue,
maar dit is eintlik nuttig om te verstaan want as jy GetString noem,
selfs al dink ons ​​dit is terugkeer M-O-M of string ma
of Andy of Zamila of die wil, tegnies
dit is net die terugkeer van die adres van daardie deel van die geheue.
>> Maar dit is OK.
Want hoe weet ek waar die string eindig?
As ek net is gegee die begin?
Wel, agteroorskuisstreep nul, reg?
Net in lineêre tyd wat ek kan druk met die druk def M-O-M.
En so gou as ek sien backslash zero, ek gee nie om waar ek begin het,
Ek weet reeds implisiet waar ek nodig het om te eindig.
>> En so vandag dui die beginning-- en laat my dit doen dramaties omdat ons
het deur 'n baie moeite gedoen om kry hierdie hier opleiding wheels--
So vandag is die opleiding wiele begin om af te kom en ons te openbaar op least--
>> [Applous]
>> Dit was goed om die reis die moeite werd vanoggend teiken, ja?
So now-- daar, dit blyk uit nie so iets soos tou.
String bestaan ​​nie.
Dit is 'n sinoniem wat ons gehad het binnekant van die CS50 biblioteek.
Voortaan gaan ons begin bel s en t nie snare maar char sterre.
En die kar ster sal ons terg uitmekaar voor lank.
Maar dit is om te sê, dat selfs as ons voortgaan
gebruik van GetString vir nou, tegnies ek moet
wees sê char ster en char ster.
>> En dit blyk dat die ster wat gaan om aan te dui is iets
bekend as 'n wyser of 'n adres.
En in die feit, 'n teaser vir wat voorlê
is dit 20 tweede clip van ons vriend Nick Parlante by Stanford
wat 'n geruime tyd gelede, spandeer 'n belaglike bedrag van die tyd,
as die beste wat ek kan sê in sy kombuis of sy kelder,
maak claymation bekendstelling aan die wêreld
'n karakter genaamd Binky met wie ons sal
volgende keer bekendgestel word aan wysers.
So hier is 'n voorbeeld van wat om te kom.
>> [Video speel]
>> Hey, Binky.
Word wakker.
Dit is tyd vir wyser pret.
>> -Wat is dit?
Meer inligting oor die riglyne?
O, goody.
>> [Einde afspeel]
DAVID J. MALAN: En op daardie noot, Ons sal sien dat jy op Woensdag.
Alles reg.
Wie is dans?
Kom op.
Wie is dans?
Jy wil my om dit te kry begin?
Ek kry dit begin het.
WOOOO!
>> LAUREN: Sweet fancy Moses.