1
00:00:00,000 --> 00:00:10,550

2
00:00:10,550 --> 00:00:14,050
>> DAVID J. MALAN: Detta är CS50 och
detta är början på veckan fyra.

3
00:00:14,050 --> 00:00:18,630
Och pojke, är Volkswagen i
problem allt på grund av programvara.

4
00:00:18,630 --> 00:00:20,264
Låt oss ta en titt.

5
00:00:20,264 --> 00:00:20,930
[VIDEOAVSPELNING]

6
00:00:20,930 --> 00:00:25,560
-Cars, De smartaste tecken
i Fast and Furious filmer.

7
00:00:25,560 --> 00:00:29,100
Denna vecka tyska automaker
Volkswagen befann sig

8
00:00:29,100 --> 00:00:32,490
i mitten av en skandal
potentiellt kriminella proportioner.

9
00:00:32,490 --> 00:00:36,060
>> -Volkswagen Är stärkande för miljarder
i böter, eventuella åtal

10
00:00:36,060 --> 00:00:38,560
för sina chefer, som
företaget apologizes

11
00:00:38,560 --> 00:00:41,840
för riggning 11 miljoner bilar
hjälpa det slog utsläppsproven.

12
00:00:41,840 --> 00:00:44,950
>> -Vissa Dieslar var
utformad med avancerad programvara

13
00:00:44,950 --> 00:00:48,440
att använda information, inklusive
positionen av styrningen och fordonet

14
00:00:48,440 --> 00:00:51,870
hastighet för att bestämma bilen var
genomgår tester utsläpp.

15
00:00:51,870 --> 00:00:55,650
Under denna omständighet, motorn
skulle minska giftiga utsläpp.

16
00:00:55,650 --> 00:00:59,070
Men bilen var riggad att kringgå
att när den körs.

17
00:00:59,070 --> 00:01:03,320
Utsläppen ökade 10 till 40
gånger högre än acceptabla EPA nivåer.

18
00:01:03,320 --> 00:01:04,280
>> [END SPELA]

19
00:01:04,280 --> 00:01:05,220
>> DAVID J. MALAN: Så låt oss
ta en titt på denna

20
00:01:05,220 --> 00:01:07,250
och se exakt hur detta
skulle kunna genomföras

21
00:01:07,250 --> 00:01:09,680
och hur detta skulle kunna påverka
så många bilar som detta.

22
00:01:09,680 --> 00:01:12,840
Så i min hand här är pressen
släpp som utfärdades av EPA--

23
00:01:12,840 --> 00:01:14,620
Miljö
Protection Agency som

24
00:01:14,620 --> 00:01:18,032
är den amerikanska tillsynsmyndighet som
hanterar miljöfrågor,

25
00:01:18,032 --> 00:01:19,740
och sedan själva
rättsligt meddelande som var

26
00:01:19,740 --> 00:01:22,420
skicka till Volkswagen bara några dagar sedan.

27
00:01:22,420 --> 00:01:26,530
>> Så EPA skriver och beskriver nu
offentligt, en sofistikerad programvara

28
00:01:26,530 --> 00:01:29,390
algoritmen på vissa
Volkswagen fordon upptäcker

29
00:01:29,390 --> 00:01:32,630
när bilen genomgår
testning officiella utsläpps

30
00:01:32,630 --> 00:01:36,505
och vänder hela utsläpp
kontrollerar på endast under testet.

31
00:01:36,505 --> 00:01:38,380
Effektiviteten av
dessa fordon föroreningar

32
00:01:38,380 --> 00:01:43,260
kontrollutsläppsenheter är kraftigt
minskas under all normal körning

33
00:01:43,260 --> 00:01:44,320
situationer.

34
00:01:44,320 --> 00:01:48,190
Detta resulterar i bilar som uppfyller
standarder i laboratoriet eller provning

35
00:01:48,190 --> 00:01:52,790
station, men under normal drift
avger kväve oxides-- eller NOx--

36
00:01:52,790 --> 00:01:54,950
vid upp till 40 gånger standarden.

37
00:01:54,950 --> 00:01:58,220
Den egenproducerad programvara Volkswagen
är ett citat unquote, manipulationsanordning,

38
00:01:58,220 --> 00:02:00,650
enligt definitionen i Clean
Air Act i USA.

39
00:02:00,650 --> 00:02:03,410
>> De går med att säga att
EPA och en annan byrå

40
00:02:03,410 --> 00:02:07,020
avslöjade manipulationsanordning
programvaran efter oberoende analys

41
00:02:07,020 --> 00:02:09,660
av forskare vid West
Virginia University.

42
00:02:09,660 --> 00:02:14,160
NOx föroreningar bidrar till
kvävedioxid, marknära ozon,

43
00:02:14,160 --> 00:02:15,700
och fina partiklar.

44
00:02:15,700 --> 00:02:18,090
Exponering för dessa
föroreningar har kopplats

45
00:02:18,090 --> 00:02:20,870
med ett brett spektrum av
allvarliga hälsoeffekter,

46
00:02:20,870 --> 00:02:23,637
inklusive ökad astma
attacker och andra luftvägs

47
00:02:23,637 --> 00:02:26,470
sjukdomar som kan vara tillräckligt allvarliga
att skicka människor till sjukhuset.

48
00:02:26,470 --> 00:02:28,660
Exponering för ozon och
partiklar har också

49
00:02:28,660 --> 00:02:31,960
förknippats med tidig
dödsfall på grund av andningsrelaterad

50
00:02:31,960 --> 00:02:35,690
eller kardiovaskulär relaterade effekter.

51
00:02:35,690 --> 00:02:38,940
Barn, äldre, personer med
tidigare existerande respiratorisk sjukdom

52
00:02:38,940 --> 00:02:42,840
är särskilt utsatta för
hälsoeffekter av dessa föroreningar.

53
00:02:42,840 --> 00:02:45,056
>> Det räcker det vill säga, det är ganska allvarligt.

54
00:02:45,056 --> 00:02:46,930
Och låt oss gå vidare för att läsa
bara en utdrag

55
00:02:46,930 --> 00:02:49,370
och sedan tar vi en titt på
de underliggande implikationer

56
00:02:49,370 --> 00:02:50,920
av detta i samband med en bil.

57
00:02:50,920 --> 00:02:53,730
Specifikt Volkswagen
tillverkat och monterat

58
00:02:53,730 --> 00:02:56,210
programvara i den s.k.
elektronisk styrning

59
00:02:56,210 --> 00:02:59,320
module-- eller ECM-- av
dessa fordon som avkända

60
00:02:59,320 --> 00:03:03,580
när fordonet testas för
överensstämmelse med normer EPA utsläpps.

61
00:03:03,580 --> 00:03:07,510
Baserat på olika ingångar inklusive
positionen av ratten, fordon

62
00:03:07,510 --> 00:03:11,280
hastighet, varaktighet av motorns
drift och barometertryck,

63
00:03:11,280 --> 00:03:13,720
dessa ingångar exakt
spårade parametrar

64
00:03:13,720 --> 00:03:17,600
av den federala testförfarandet används för
utsläppsprovning för EPA certifiering

65
00:03:17,600 --> 00:03:18,400
ändamål.

66
00:03:18,400 --> 00:03:21,850
>> Under EPA: s utsläppsprovet,
fordonets ECM programvara

67
00:03:21,850 --> 00:03:25,060
sprang programvara som producerade
resultat kompatibla utsläpp.

68
00:03:25,060 --> 00:03:28,340
Vid alla andra tider,
fordonets ECM programvara

69
00:03:28,340 --> 00:03:31,090
körde en separat väg
kalibrering som minskade

70
00:03:31,090 --> 00:03:34,360
effektiviteten av
övergripande avgasreningssystemet,

71
00:03:34,360 --> 00:03:37,864
specifikt selektiv katalytisk
minskning av mager-NOx trap--

72
00:03:37,864 --> 00:03:39,280
som vi får se om ett ögonblick.

73
00:03:39,280 --> 00:03:43,040
Som ett resultat, utsläpp av NOx
ökas med en faktor av 10 till 40 gånger

74
00:03:43,040 --> 00:03:47,450
ovanför EPA kompatibla nivåer
beroende på vilken typ av arbetscykeln.

75
00:03:47,450 --> 00:03:50,800
>> Så vad detta egentligen innebär, och
källkoden till programmet körs

76
00:03:50,800 --> 00:03:53,190
på Volkswagens har inte
ännu inte offentliggjorts,

77
00:03:53,190 --> 00:03:56,460
är att, på ett effektivt sätt, detta
motsvarigheten är någonstans där inne

78
00:03:56,460 --> 00:03:57,830
Volkswagen kod.

79
00:03:57,830 --> 00:04:02,200
Om du håller på att testas, och om bilen
detekterar vissa miljöfaktorer

80
00:04:02,200 --> 00:04:04,330
liknande ratten
läge eller rörelse

81
00:04:04,330 --> 00:04:06,710
eller avsaknaden av bilen eller
ett antal andra faktorer

82
00:04:06,710 --> 00:04:09,940
som för närvarande är en hypotes
att vara en del av denna formel,

83
00:04:09,940 --> 00:04:12,370
de helt enkelt slå på
kontrollerar hela utsläpp.

84
00:04:12,370 --> 00:04:15,670
Med andra ord, de börjar
avger mindre av föroreningar.

85
00:04:15,670 --> 00:04:18,769
>> Else, i varje annan situation
när det inte upptäcks vara

86
00:04:18,769 --> 00:04:20,790
i laboratoriet, de gör bara inte.

87
00:04:20,790 --> 00:04:24,320
Och så du kan förenkla detta i mer
betong pseudokod med något

88
00:04:24,320 --> 00:04:24,820
så här.

89
00:04:24,820 --> 00:04:27,810
Om hjulen vänder men
ratten är inte suggestiva

90
00:04:27,810 --> 00:04:30,060
att bilen är på vissa
typ av roterande cylinder

91
00:04:30,060 --> 00:04:32,550
men i något slags
lagret som testas,

92
00:04:32,550 --> 00:04:36,070
sedan beter sig som den
EPA skulle vilja att ni.

93
00:04:36,070 --> 00:04:37,960
Annars inte.

94
00:04:37,960 --> 00:04:40,420
Så låt oss ta en titt
på en kort video som

95
00:04:40,420 --> 00:04:45,391
tar en titt på vad konsekvenserna
är av detta faktiskt mekaniskt.

96
00:04:45,391 --> 00:04:48,620
>> [VIDEOAVSPELNING]

97
00:04:48,620 --> 00:04:52,800
>> -Sista Fredag ​​EPA meddelade att vissa
Volkswagen Audi mellan 2009

98
00:04:52,800 --> 00:04:55,840
och i år använde
en s.k. manipulationsanordning

99
00:04:55,840 --> 00:04:59,060
att komma runt lagar utsläpps
utformade för att hålla luften ren.

100
00:04:59,060 --> 00:05:01,700
Men vad betyder det exakt?

101
00:05:01,700 --> 00:05:04,666
>> Tja, moderna bilar har dussintals
av datorer inuti dem.

102
00:05:04,666 --> 00:05:07,040
Och några av dessa datorer
hjälpa till att samordna de funktioner

103
00:05:07,040 --> 00:05:09,590
av motorn för optimal
prestanda samtidigt se

104
00:05:09,590 --> 00:05:12,340
att det inte finns alltför mycket skräp
kommer ut ur avgasröret.

105
00:05:12,340 --> 00:05:15,170
De har faktiskt arbetat
detta sätt under flera decennier nu.

106
00:05:15,170 --> 00:05:17,380
I grund och botten, varje del
av en modern bils motor

107
00:05:17,380 --> 00:05:20,080
har en sensor eller styrenhet
på den, och dessa datorer

108
00:05:20,080 --> 00:05:23,460
läser i uppgifter tusentals
gånger per sekund gör justeringar

109
00:05:23,460 --> 00:05:26,220
som förhållandet mellan bränsle och luft
som kommer in i cylindrarna.

110
00:05:26,220 --> 00:05:28,730
>> Dessa fusk Volkswagen
och Audi-modeller är dieslar,

111
00:05:28,730 --> 00:05:30,890
och dieselmotorer har ett mer
verkligen viktigt dator

112
00:05:30,890 --> 00:05:34,030
kontrollerade parametrar, som är
mängden oförbränt bränsle kommer

113
00:05:34,030 --> 00:05:35,200
in i avgaserna.

114
00:05:35,200 --> 00:05:36,310
Nu låter illa.

115
00:05:36,310 --> 00:05:39,642
Låter inte som du vill
oförbränt bränsle som går in i avgaserna.

116
00:05:39,642 --> 00:05:41,600
Men i fallet med en
diesel, har du något

117
00:05:41,600 --> 00:05:46,110
kallas en NOx-fälla som är en enhet som
absorberar och fällor för kväveoxider

118
00:05:46,110 --> 00:05:48,880
som är föroreningar som skulle
annars gå ut i atmosfären.

119
00:05:48,880 --> 00:05:53,040
Och effekten av den NOx-fällan
är förstärkt med oförbränt bränsle.

120
00:05:53,040 --> 00:05:56,650
Så en manipulationsanordning är ett speciellt program
inuti dessa datorer som kan göra det

121
00:05:56,650 --> 00:05:59,527
ser ut bilen uppfyller utsläpps
standarder även när det inte gör det.

122
00:05:59,527 --> 00:06:01,110
Volkswagen hade ett problem på sina händer.

123
00:06:01,110 --> 00:06:04,050
Dess dieselmotorer var kända
för att få bra bränsleekonomi,

124
00:06:04,050 --> 00:06:07,510
men NOx-fällan fungerar bara bra
när mer bränsle används.

125
00:06:07,510 --> 00:06:10,460
Så bilen skulle upptäcka,
använder denna manipulationsanordning,

126
00:06:10,460 --> 00:06:13,870
när det var att få ett utsläpp
testet, skulle det använder mer bränsle,

127
00:06:13,870 --> 00:06:16,830
göra NOx-fällan fungerar bra,
utsläpp skulle vara bra.

128
00:06:16,830 --> 00:06:21,130
Men sedan får du på vägen, enheten
stängs, du bränner mindre bränsle

129
00:06:21,130 --> 00:06:24,256
men du lägger så mycket som 40 gånger
fler föroreningar i atmosfären.

130
00:06:24,256 --> 00:06:26,130
Men hur heck gjorde
bilen vet att det var

131
00:06:26,130 --> 00:06:27,720
testas för överensstämmelse utsläpp?

132
00:06:27,720 --> 00:06:30,590
EPA säger att det var en sofistikerad
system som kontrolleras saker

133
00:06:30,590 --> 00:06:34,090
som rattläge,
hastighet, hur länge motorn var på,

134
00:06:34,090 --> 00:06:35,507
och till och med det atmosfäriska trycket.

135
00:06:35,507 --> 00:06:37,673
Med andra ord fanns det
inget sätt detta var oavsiktlig

136
00:06:37,673 --> 00:06:40,260
eftersom programvaran var
utformade mycket noga för att upptäcka

137
00:06:40,260 --> 00:06:41,630
ett officiellt avgasprovet.

138
00:06:41,630 --> 00:06:43,588
Det är några ganska allvarliga
bedrägeri och det är

139
00:06:43,588 --> 00:06:45,420
varför Volkswagen är i
sådana allvarliga problem.

140
00:06:45,420 --> 00:06:48,600
I själva verket, deras VD, Martin
Winter, bara avgick.

141
00:06:48,600 --> 00:06:49,820
>> Så vad händer härnäst?

142
00:06:49,820 --> 00:06:53,900
Tja, om du är en av de halv miljon
diesel Jettas, Beatles, Golfs, Passats,

143
00:06:53,900 --> 00:06:56,220
eller Audi A3s åstadkommes,
Den goda nyheten är är

144
00:06:56,220 --> 00:06:57,886
att din bil är fortfarande säker att köra.

145
00:06:57,886 --> 00:07:00,510
Du behöver inte lägga undan
tills Volkswagen utfärdar ett återkallande.

146
00:07:00,510 --> 00:07:02,509
Men någon gång de är
förmodligen kommer att ha

147
00:07:02,509 --> 00:07:04,230
att uppdatera programvaran i bilen.

148
00:07:04,230 --> 00:07:06,927
När det händer du kanske
får färre miles per tank.

149
00:07:06,927 --> 00:07:09,260
Advokater redan utväxling
för grupptalan

150
00:07:09,260 --> 00:07:12,500
så ägare kan bli kompenserad
någon gång i framtiden.

151
00:07:12,500 --> 00:07:15,832
Men det kommer inte att
hända någon gång snart.

152
00:07:15,832 --> 00:07:16,711
>> [END SPELA]

153
00:07:16,711 --> 00:07:19,960
DAVID J. MALAN: Så detta faktiskt väcker
en intressant större bild fråga

154
00:07:19,960 --> 00:07:20,660
att lita på.

155
00:07:20,660 --> 00:07:21,160
Höger?

156
00:07:21,160 --> 00:07:24,300
Alla av oss har iPhone eller Androids eller
något i våra fickor troligtvis

157
00:07:24,300 --> 00:07:26,500
dessa dagar, eller bärbara datorer
på våra varv som är

158
00:07:26,500 --> 00:07:28,510
kör mjukvara gjord
av Apple och Microsoft

159
00:07:28,510 --> 00:07:30,710
och klasar av andra företag.

160
00:07:30,710 --> 00:07:34,240
Men hur vet vi att vad
dessa program gör

161
00:07:34,240 --> 00:07:37,680
är faktiskt vad dessa
företag säger att de gör?

162
00:07:37,680 --> 00:07:39,610
>> Till exempel, som är att
säga att varje gång du

163
00:07:39,610 --> 00:07:42,200
ringa ett samtal på din iPhone
eller Android-telefon eller liknande,

164
00:07:42,200 --> 00:07:45,650
att det telefonnumret är inte heller
att överföras till något företag server

165
00:07:45,650 --> 00:07:48,399
på grund av något program du har
skriftligt, oavsett om det är drifts

166
00:07:48,399 --> 00:07:51,070
själva systemet som iOS eller Android,
eller för att du har hämtat

167
00:07:51,070 --> 00:07:53,880
en tredje part app
som på något sätt lyssnar

168
00:07:53,880 --> 00:07:57,120
allt du skriver in eller
allt du faktiskt säger.

169
00:07:57,120 --> 00:07:59,500
Hur vet du det, när
ni kör Clang

170
00:07:59,500 --> 00:08:02,590
Eller Lägg till kompilera
egen programvara i CS50, hur

171
00:08:02,590 --> 00:08:06,080
gör du det CS50 egen personal,
med hjälp av CS50 biblioteket

172
00:08:06,080 --> 00:08:08,690
har inte varit att logga varje
sträng du någonsin fått

173
00:08:08,690 --> 00:08:10,276
eller varje tum du någonsin fått?

174
00:08:10,276 --> 00:08:12,900
Tja, kan du säkert se
på källkoden för något

175
00:08:12,900 --> 00:08:15,233
som CS50 biblioteket, du
kunde titta på källkoden

176
00:08:15,233 --> 00:08:18,170
för Linux operativsystem
körs på CS50 IDE.

177
00:08:18,170 --> 00:08:23,090
Men en fantastisk presentation
gavs igen 1984

178
00:08:23,090 --> 00:08:26,730
i mottagandet av Turing Award av en
mycket berömd datavetare känd

179
00:08:26,730 --> 00:08:29,750
as-- namnges Ken Thompson som
fick turingpriset som

180
00:08:29,750 --> 00:08:33,500
är en slags datavetenskap s
Nobelpriset, om ni så vill,

181
00:08:33,500 --> 00:08:35,309
för hans arbete på ett
operativsystem kallat

182
00:08:35,309 --> 00:08:39,039
Unix, som är mycket lik i
ande vad vi använder som är Linux.

183
00:08:39,039 --> 00:08:41,960
Och frågan frågade han i sitt
tacktal, huvudsakligen

184
00:08:41,960 --> 00:08:44,910
om ramen för
åratal av diskussioner

185
00:08:44,910 --> 00:08:46,970
om tillit och säkerhet, var detta.

186
00:08:46,970 --> 00:08:50,410
I vilken utsträckning bör ett förtroende en
uttalande om att en program-- en bit

187
00:08:50,410 --> 00:08:53,010
av software-- är fri från trojanska hästar?

188
00:08:53,010 --> 00:08:56,500
Kanske är det viktigare att lita
de personer som skrev programvaran.

189
00:08:56,500 --> 00:08:58,650
>> Och i själva verket har vi länkat
till föredrag som han

190
00:08:58,650 --> 00:09:02,400
gav när det godtog denna utmärkelse
på 80-talet på CS50 hemsida

191
00:09:02,400 --> 00:09:04,030
under Föreläsningar sida för idag.

192
00:09:04,030 --> 00:09:06,071
För vad du ser
är att han faktiskt ger

193
00:09:06,071 --> 00:09:09,430
ett ganska enkelt exempel på hur även
en kompilator som Clang eller vad

194
00:09:09,430 --> 00:09:13,950
kompilatorer andra har använt i tidigare,
vad händer om inbäddade i kompilatorn vi

195
00:09:13,950 --> 00:09:18,190
själva använder är lite om
villkor att väsentligen säger,

196
00:09:18,190 --> 00:09:22,360
om du märker att denna kod använder
getString funktion eller getInt

197
00:09:22,360 --> 00:09:26,600
funktion, gå vidare och sätta
en bakdörr eller en trojansk häst

198
00:09:26,600 --> 00:09:29,340
så att detta program
har nu några nollor

199
00:09:29,340 --> 00:09:30,930
och de som gör något skadligt.

200
00:09:30,930 --> 00:09:33,080
Logga alla dina
tangenttryckningar, ladda upp dessa data

201
00:09:33,080 --> 00:09:35,100
till viss server, eller egentligen vad som helst.

202
00:09:35,100 --> 00:09:37,290
>> Och vad Ken Thompson
fortsätter med att göra i sitt tal

203
00:09:37,290 --> 00:09:40,580
är att visa att även om
du har tillgång till källan

204
00:09:40,580 --> 00:09:43,794
kod för en kompilator som
uppsåtligt kan göra detta,

205
00:09:43,794 --> 00:09:46,210
det spelar ingen roll eftersom
Det är det här hönan och ägget

206
00:09:46,210 --> 00:09:49,500
verklighet av det förflutna många
år vari kompilatorer

207
00:09:49,500 --> 00:09:51,960
används för att kompilera själva.

208
00:09:51,960 --> 00:09:55,440
Med andra ord, vägen tillbaka när någon
hade att ha skrivit den första kompilatorn.

209
00:09:55,440 --> 00:09:59,060
Och därefter, när som helst de har uppdaterat
en kompilator genom att ändra dess källkod,

210
00:09:59,060 --> 00:10:02,020
att lägga till funktioner och kompilera det
för människor som oss att använda, ja,

211
00:10:02,020 --> 00:10:04,270
de använder den gamla
version av kompilatorn

212
00:10:04,270 --> 00:10:06,370
att sammanställa nya
version av kompilatorn.

213
00:10:06,370 --> 00:10:08,370
Och om du tar en titt
på tal som han gav,

214
00:10:08,370 --> 00:10:10,970
ser du att eftersom
i nämnda cirkularitet

215
00:10:10,970 --> 00:10:14,330
du faktiskt kan ha fel eller
Trojanska hästar inbäddade i programvara

216
00:10:14,330 --> 00:10:14,990
vi använder.

217
00:10:14,990 --> 00:10:18,010
Och även om du tittar på
källkoden för dessa program,

218
00:10:18,010 --> 00:10:21,550
Det kanske inte ens vara uppenbart
eftersom knep är faktiskt

219
00:10:21,550 --> 00:10:24,710
i vissa äldre version av en
kompilator som sedan dess har varit

220
00:10:24,710 --> 00:10:27,340
injicera hotet i vår mjukvara.

221
00:10:27,340 --> 00:10:29,740
>> Vilket är bara att säga, vi
verkligen kan inte och bör inte

222
00:10:29,740 --> 00:10:32,939
förtroende programvara som körs på våra bärbara datorer
eller telefoner eller valfritt antal platser.

223
00:10:32,939 --> 00:10:36,230
Och i själva verket senare i den här terminen när
Vi börjar prata om webbprogrammering

224
00:10:36,230 --> 00:10:38,521
och faktiskt börja bygga
webbapplikationer själva,

225
00:10:38,521 --> 00:10:40,285
vi pratar om dessa
hot och andra.

226
00:10:40,285 --> 00:10:43,410
Nu kanske du har undrat och märkte
att det fanns en liten liten Darth

227
00:10:43,410 --> 00:10:45,842
Vader i klipp som
The Verge visade det

228
00:10:45,842 --> 00:10:47,550
om Volkswagen. Om
du aldrig sett, jag

229
00:10:47,550 --> 00:10:49,190
trodde vi skulle lätta
stämningen eftersom det är allt

230
00:10:49,190 --> 00:10:50,780
mycket deprimerande och skrämmande.

231
00:10:50,780 --> 00:10:52,910
Jag kommer att se tillbaka
på Super Bowl 2011

232
00:10:52,910 --> 00:10:55,300
när en kommersiell med
Volkswagen-- och detta

233
00:10:55,300 --> 00:10:59,620
nästan gör dem sympatisk igen--
sändes för första gången på TV.

234
00:10:59,620 --> 00:11:04,039
Det är 60 andra klippet
som jag tror att du kommer att njuta av.

235
00:11:04,039 --> 00:11:04,705
[VIDEOAVSPELNING]

236
00:11:04,705 --> 00:11:08,198
[MUSIK - tema från "Star Wars"]

237
00:11:08,198 --> 00:11:35,643

238
00:11:35,643 --> 00:11:38,138
[Hunden skäller]

239
00:11:38,138 --> 00:11:50,114

240
00:11:50,114 --> 00:11:53,607
[Bil startar]

241
00:11:53,607 --> 00:12:04,086

242
00:12:04,086 --> 00:12:05,955
[END SPELA]

243
00:12:05,955 --> 00:12:06,830
DAVID J. MALAN: Ja.

244
00:12:06,830 --> 00:12:07,663
Jag var bara kontroll.

245
00:12:07,663 --> 00:12:11,360
Bilen är på listan över kränkningar.

246
00:12:11,360 --> 00:12:12,000
Okej.

247
00:12:12,000 --> 00:12:14,040
Så vi titta på några
pseudokod för en stund sedan.

248
00:12:14,040 --> 00:12:15,380
Och här är en större
utdrag av pseudokod kod

249
00:12:15,380 --> 00:12:16,921
att vi har sett ett par gånger hittills.

250
00:12:16,921 --> 00:12:19,970
Och låt oss använda detta är en möjlighet
nu att införa en ny programmering

251
00:12:19,970 --> 00:12:23,776
teknik som vi gjorde
se algoritm

252
00:12:23,776 --> 00:12:25,400
förra veckan när vi tittat på merge sort.

253
00:12:25,400 --> 00:12:28,270
Men låt oss formalisera den och se hur
vi kan använda den i faktiska koden,

254
00:12:28,270 --> 00:12:30,350
och sedan ska vi använda denna
teknik på vägen mest

255
00:12:30,350 --> 00:12:32,000
sannolikt att lösa vissa andra problem.

256
00:12:32,000 --> 00:12:35,790
>> Så det här var en av de första programmen vi
någonsin skrev, om än i pseudokod kod.

257
00:12:35,790 --> 00:12:37,790
Och vad detta program
tillät oss att göra kursen

258
00:12:37,790 --> 00:12:41,510
var att hitta Mike Smith i en telefonbok.

259
00:12:41,510 --> 00:12:46,216
Och lägg märke till särskilt linjer åtta
och 11 som hade denna Go To uttalande.

260
00:12:46,216 --> 00:12:48,090
Och i själva verket, vissa
språk, C bland dem,

261
00:12:48,090 --> 00:12:50,006
faktiskt har en
uttalande som är bokstavligen

262
00:12:50,006 --> 00:12:52,710
gå till som låter dig
hoppa till en viss linje.

263
00:12:52,710 --> 00:12:55,470
Det är allmänt ogillande eftersom
Det kan vara mycket lätt missbrukas

264
00:12:55,470 --> 00:12:58,490
och du kan börja hoppa din
program överallt i motsats

265
00:12:58,490 --> 00:13:00,690
till att använda den typ av
logik och styrflödet

266
00:13:00,690 --> 00:13:04,000
att vi har använt hittills med bara
loopar och villkor och liknande.

267
00:13:04,000 --> 00:13:08,660
>> Men vi kan förenkla denna algoritm
i pseudokod kod enligt följande.

268
00:13:08,660 --> 00:13:11,250
I stället för detta iterativa
eller looping tillvägagångssätt

269
00:13:11,250 --> 00:13:14,160
där vi hålla tillbaka och
tillbaka och tillbaka till linje tre,

270
00:13:14,160 --> 00:13:18,300
varför inte vi bara typ av punt och mer
brukar säga i linje sju och 10,

271
00:13:18,300 --> 00:13:20,570
bara ersätta de två
par rader med,

272
00:13:20,570 --> 00:13:22,810
else if Smith är tidigare
i boken vi ska

273
00:13:22,810 --> 00:13:25,110
söka för Mike i
vänstra halvan av boken.

274
00:13:25,110 --> 00:13:28,560
Else if Smith är senare i
bok, söka efter Mike i höger

275
00:13:28,560 --> 00:13:29,540
halv boken.

276
00:13:29,540 --> 00:13:31,180
Och märker redan cirkularitet.

277
00:13:31,180 --> 00:13:31,680
Höger?

278
00:13:31,680 --> 00:13:34,250
Jag letar efter Mike
telefonboken och sedan

279
00:13:34,250 --> 00:13:37,090
Jag slog så småningom kanske
line sju eller kanske ledningen 10

280
00:13:37,090 --> 00:13:41,089
och min undervisning till mig själv är att söka
för Mike i hälften av telefonboken.

281
00:13:41,089 --> 00:13:42,380
Nå, hur gör jag söker efter Mike?

282
00:13:42,380 --> 00:13:44,213
Jag är i mitten av
söka efter Mike, varför

283
00:13:44,213 --> 00:13:45,860
du slags skicka mig i en cirkel?

284
00:13:45,860 --> 00:13:49,590
Men det är OK eftersom det är
händer med storleken på problemet,

285
00:13:49,590 --> 00:13:52,630
som det står skrivet i linje 7 och 10?

286
00:13:52,630 --> 00:13:54,989
Vi är inte bara säga sökning
för Mike, söka efter Mike.

287
00:13:54,989 --> 00:13:56,280
Vi är särskilt säga vad?

288
00:13:56,280 --> 00:13:58,694

289
00:13:58,694 --> 00:14:01,610
Sök efter honom i den vänstra halvan av
den högra halv som är effektivt

290
00:14:01,610 --> 00:14:03,440
halv storlek av problemet.

291
00:14:03,440 --> 00:14:07,170
Så det är OK att vi är typ av
engagera sig i denna cirkel,

292
00:14:07,170 --> 00:14:09,180
Detta cirkelresonemang,
eftersom åtminstone är vi

293
00:14:09,180 --> 00:14:11,090
vilket gör problemet mindre och mindre.

294
00:14:11,090 --> 00:14:14,220
Och så småningom vi ska nå
det så kallade referensscenariot där

295
00:14:14,220 --> 00:14:16,780
Vi har bara en sida left--
som vår volontär förra veckan

296
00:14:16,780 --> 00:14:18,684
did-- vi hade en sida
vänster och sedan gör vi inte

297
00:14:18,684 --> 00:14:21,600
måste fortsätta söka efter Mike Smith
eftersom han är antingen på den sidan

298
00:14:21,600 --> 00:14:23,080
eller han inte.

299
00:14:23,080 --> 00:14:27,480
>> Så hur kan vi genomföra denna idé, detta
slags cirkel i själva koden?

300
00:14:27,480 --> 00:14:31,030
Tja, kan vi utnyttja en teknik
som är allmänt känd som rekursion.

301
00:14:31,030 --> 00:14:33,960
Och vi har sett detta i
pseudokod för merge sort förra veckan.

302
00:14:33,960 --> 00:14:37,190
Minns att detta var den
pseudokod för merge sort.

303
00:14:37,190 --> 00:14:40,560
Det är utan tvekan ännu enklare än
bubbla eller urval eller insättningssortering

304
00:14:40,560 --> 00:14:43,310
bara i termer av enkelhet
med vilken du kan uttrycka det.

305
00:14:43,310 --> 00:14:46,750
>> Men det beror på
vi slags cirkulärt

306
00:14:46,750 --> 00:14:51,350
sade söka efter något
genom att söka efter det igen.

307
00:14:51,350 --> 00:14:53,960
Men vi söker antingen på
den vänstra halv eller den högra halv

308
00:14:53,960 --> 00:14:56,070
och sedan så småningom vi är
sammanslagning i det här fallet.

309
00:14:56,070 --> 00:14:58,520
Men även här, med
dessa två sorteringslinjer,

310
00:14:58,520 --> 00:15:01,320
vi återigen har detta
tanken på rekursion.

311
00:15:01,320 --> 00:15:05,350
Och konkret vad detta innebär,
i samband med en algoritm,

312
00:15:05,350 --> 00:15:10,880
är att en algoritm är rekursiv
om det använder eller kallar sig.

313
00:15:10,880 --> 00:15:14,330
>> Eller med avseende på C, är en funktion
recursive-- en funktion som kallas

314
00:15:14,330 --> 00:15:18,510
foo är rekursiv om foo,
någonstans i dess källkod,

315
00:15:18,510 --> 00:15:21,250
anropar funktionen foo själv.

316
00:15:21,250 --> 00:15:25,790
Och det är illa om alla foo någonsin gör
är kalla sig om och om igen.

317
00:15:25,790 --> 00:15:30,600
Det är OK om foo stannar så småningom, liksom
merge sort, genom att säga, vänta en minut,

318
00:15:30,600 --> 00:15:32,980
om detta problem är super
liten, till exempel,

319
00:15:32,980 --> 00:15:35,840
eller fann jag honom som jag
söker, bara tillbaka.

320
00:15:35,840 --> 00:15:41,000
Inte rekursivt, inte
cykliskt kalla mig igen.

321
00:15:41,000 --> 00:15:44,200
>> Och så låt oss ta en titt på
hur detta kan faktiskt fungera.

322
00:15:44,200 --> 00:15:48,430
Så jag kommer att gå vidare och öppna
upp två källa kodexempel här.

323
00:15:48,430 --> 00:15:50,321
En av som kallas sigma 0.

324
00:15:50,321 --> 00:15:52,320
Och det är inte alls
rekursiv, men låt oss ta

325
00:15:52,320 --> 00:15:53,694
En titt på vad det här programmet gör.

326
00:15:53,694 --> 00:15:55,737
Jag har avskalade ut alla
synpunkter från det men alla

327
00:15:55,737 --> 00:15:58,070
av källkoden på CS50: s
webbplats har synpunkter om så du

328
00:15:58,070 --> 00:15:59,570
vill läsa igenom den igen senare.

329
00:15:59,570 --> 00:16:02,010
Och låt oss göra ett par
av sanity kontrollerar här.

330
00:16:02,010 --> 00:16:06,640
>> Så på toppen av denna kod,
vi har inkludera CS50.h.

331
00:16:06,640 --> 00:16:07,650
Vad gör detta?

332
00:16:07,650 --> 00:16:08,990
Varför är det här?

333
00:16:08,990 --> 00:16:11,740
I rimlig lekmannaspråk.

334
00:16:11,740 --> 00:16:12,424
Vad gör den?

335
00:16:12,424 --> 00:16:12,858
Yeah.

336
00:16:12,858 --> 00:16:14,160
>> PUBLIK: Så att getInt funktionen fungerar.

337
00:16:14,160 --> 00:16:16,243
>> DAVID J. MALAN: Så det
den getInt funktionen fungerar.

338
00:16:16,243 --> 00:16:18,115
Eftersom insidan av denna
fil, CS50.h, vilket

339
00:16:18,115 --> 00:16:20,950
vi får se snart i
fråga om källkoden,

340
00:16:20,950 --> 00:16:23,270
har en massa funktioner
declared-- getInt, getString,

341
00:16:23,270 --> 00:16:26,950
och ett gäng mot andra, och om
vi faktiskt har att Inkludera linje,

342
00:16:26,950 --> 00:16:29,320
kompilatorn Clang är inte
kommer att veta att den existerar.

343
00:16:29,320 --> 00:16:32,400
Och samma sak gäller för linje
två där int definieras

344
00:16:32,400 --> 00:16:35,101
printf, som är en funktion
vi fortsätta att använda en hel del.

345
00:16:35,101 --> 00:16:37,850
Nu verkar linje fyra lite funky
eftersom det är bara en liner.

346
00:16:37,850 --> 00:16:41,570
Det har fått ett semikolon, inte lockigt
hängslen, ingen kod inne i den.

347
00:16:41,570 --> 00:16:44,640
Men vad gjorde vi kallar
den här saken i veckor tidigare?

348
00:16:44,640 --> 00:16:45,140
Yeah.

349
00:16:45,140 --> 00:16:46,060
Så en prototyp.

350
00:16:46,060 --> 00:16:48,390
Och varför har vi en
prototyp som verkar

351
00:16:48,390 --> 00:16:51,050
att vara lite överflödig
vanligtvis eftersom vi vanligtvis

352
00:16:51,050 --> 00:16:53,474
se funktionen igen
senare i filen, eller hur?

353
00:16:53,474 --> 00:16:56,390
Så varför vi have-- du bara
skrapa huvudet men jag tar det.

354
00:16:56,390 --> 00:16:57,302
Yeah.

355
00:16:57,302 --> 00:17:00,000
>> PUBLIK: [OHÖRBAR]
funktion efter huvud.

356
00:17:00,000 --> 00:17:01,000
DAVID J. MALAN: Exakt.

357
00:17:01,000 --> 00:17:04,089
Så att kompilatorn känner dig
så småningom kommer att definiera eller genomföra

358
00:17:04,089 --> 00:17:06,579
som fungerar efter huvud, förmodligen.

359
00:17:06,579 --> 00:17:08,462
Så Clang och mest
kompilatorer är typ av dum

360
00:17:08,462 --> 00:17:10,510
och de ska bara veta
vad du säger dem.

361
00:17:10,510 --> 00:17:12,569
Och om du vill använda
en funktion som kallas sigma,

362
00:17:12,569 --> 00:17:15,710
du bättre lär kompilatorn
att den existerar i förväg.

363
00:17:15,710 --> 00:17:17,970
>> Nu, huvud själv, även
även om det är ett gäng linjer,

364
00:17:17,970 --> 00:17:19,839
är ganska bekant förhoppningsvis nu.

365
00:17:19,839 --> 00:17:21,942
Det har fått en gör while-slinga
vars syfte i livet

366
00:17:21,942 --> 00:17:24,400
här tydligen är att få en
positivt heltal från användaren.

367
00:17:24,400 --> 00:17:27,349
Och bara hålla tjat honom
eller henne tills de samarbetar.

368
00:17:27,349 --> 00:17:30,670
Sedan i linje 16 Jag har
ett intressant samtal.

369
00:17:30,670 --> 00:17:31,570
IntAnswer.

370
00:17:31,570 --> 00:17:33,710
Som på den vänstra sidan
sidan ger mig en Int

371
00:17:33,710 --> 00:17:36,650
vilket kan store-- kallas Answer--
som kommer att lagra, som synes,

372
00:17:36,650 --> 00:17:39,090
returvärdet för sigma.

373
00:17:39,090 --> 00:17:41,840
Så sigma är bara en
godtyckligt men meningsfullt namn

374
00:17:41,840 --> 00:17:44,500
att jag har gett till en funktion
vars syfte i livet

375
00:17:44,500 --> 00:17:47,680
är att ta en argument--
vi kallar det N i detta case--

376
00:17:47,680 --> 00:17:52,280
och bara ta summan av det antal
plus varje positivt tal som är

377
00:17:52,280 --> 00:17:53,200
mindre än det.

378
00:17:53,200 --> 00:17:58,140
>> Så om jag klarar av antalet 2
sigma, jag vill lägga till två plus ett

379
00:17:58,140 --> 00:18:00,240
plus 0-- inte 0-- så det ger mig tre.

380
00:18:00,240 --> 00:18:05,320
Om jag passera i 3 till sigma, jag vill
har 3 plus 2 plus 1, vilket ger mig sex.

381
00:18:05,320 --> 00:18:05,900
Och så vidare.

382
00:18:05,900 --> 00:18:09,750
Så det lägger bara upp alla
tal mindre än eller lika med det.

383
00:18:09,750 --> 00:18:12,040
>> Nu, här nere jag bara gå
att skriva ut svaret.

384
00:18:12,040 --> 00:18:17,330
Så som en snabb kontroll sanity, låt oss
göra sigma 0-- punkt snedstreck sigma 0--

385
00:18:17,330 --> 00:18:18,690
och låt mig skriva in 2.

386
00:18:18,690 --> 00:18:19,960
Och jag verkligen få 3.

387
00:18:19,960 --> 00:18:21,240
Låt mig skriva in 3.

388
00:18:21,240 --> 00:18:22,860
Jag får faktiskt sex.

389
00:18:22,860 --> 00:18:27,636
Och om någon kan göra matten snabbt,
om jag gör 50 vad ska jag få?

390
00:18:27,636 --> 00:18:29,839
>> PUBLIK: [OHÖRBAR].

391
00:18:29,839 --> 00:18:30,880
DAVID J. MALAN: Tja, nej.

392
00:18:30,880 --> 00:18:33,340
Men 1275 som är ganska nära.

393
00:18:33,340 --> 00:18:38,850
Så detta är ett resultat av att göra 50
plus 49 plus 48 plus 47 plus 46

394
00:18:38,850 --> 00:18:40,349
hela vägen ner till ett.

395
00:18:40,349 --> 00:18:41,390
Så det är allt sigma gör.

396
00:18:41,390 --> 00:18:43,350
Men låt oss se hur vi har
genomfört det nu.

397
00:18:43,350 --> 00:18:45,790
Så här nere är själva funktionen.

398
00:18:45,790 --> 00:18:49,000
Och det verkar inte ha
något att göra med rekursion ännu.

399
00:18:49,000 --> 00:18:51,070
I själva verket använder vi en
old school teknik.

400
00:18:51,070 --> 00:18:56,680
Jag initiera en variabel som heter summa
till noll, då jag har en foreloop här,

401
00:18:56,680 --> 00:19:00,790
och jag förklarar en Int kallas
Jag, sätta det lika med 1--

402
00:19:00,790 --> 00:19:04,080
även om jag kunde ställa in den lika med
noll, men eftersom jag gör dessutom

403
00:19:04,080 --> 00:19:05,340
vem bryr sig om det är noll eller ett.

404
00:19:05,340 --> 00:19:06,660
Det kommer att ha någon effekt.

405
00:19:06,660 --> 00:19:10,110
>> Så jag iteration så länge jag är
mindre än eller lika med m, vilket

406
00:19:10,110 --> 00:19:11,671
är argumentet som antogs i.

407
00:19:11,671 --> 00:19:13,670
Och då jag bara hålla
uppräkning I. Och insikt

408
00:19:13,670 --> 00:19:20,010
av slingan allt jag gör gör summa
plus lika I. Och det är avsiktligt.

409
00:19:20,010 --> 00:19:22,326
Jag vill inte göra, i detta
fall som summan plus plus.

410
00:19:22,326 --> 00:19:24,790
Jag vill verkligen lägga
det aktuella värdet av I

411
00:19:24,790 --> 00:19:28,190
vilket blir bara större och större
och större för att den löpande stämmer.

412
00:19:28,190 --> 00:19:30,210
>> Och då jag återvänder summan.

413
00:19:30,210 --> 00:19:33,850
Och så svaret blir värdet summan.

414
00:19:33,850 --> 00:19:35,282
Och då jag skriva ut den.

415
00:19:35,282 --> 00:19:37,740
Så det finns en möjlighet här,
dock att sådan förenkling

416
00:19:37,740 --> 00:19:41,260
denna kod begrepps
och vilken typ av slaget ett är

417
00:19:41,260 --> 00:19:43,250
tänka i termer av den
enkelhet trots att det

418
00:19:43,250 --> 00:19:45,700
tar ett tag att sortera
av förstå varför detta

419
00:19:45,700 --> 00:19:47,330
är kraftfull i dessa små exempel.

420
00:19:47,330 --> 00:19:50,380
Här är sigma en-- så
andra version av denna kod.

421
00:19:50,380 --> 00:19:55,290
Allt upp topp är identiska så
samma berättelse gäller som tidigare.

422
00:19:55,290 --> 00:19:59,220
Men nu ska vi titta på
genomförandet av sigma som

423
00:19:59,220 --> 00:20:05,040
Jag har reducerats till bara dessa
lines-- fyra rader kod, verkligen,

424
00:20:05,040 --> 00:20:06,980
plus några klamrar och blanktecken.

425
00:20:06,980 --> 00:20:07,930
>> Men vad gör jag?

426
00:20:07,930 --> 00:20:11,050
Om m är mindre än eller lika med
noll, jag behöver typ av hantera

427
00:20:11,050 --> 00:20:12,490
det super enkelt fall.

428
00:20:12,490 --> 00:20:15,450
Och om du lämnar mig noll eller något
negativt vilket är bara konstigt,

429
00:20:15,450 --> 00:20:17,909
Jag kommer bara att godtyckligt
men genomgående retur noll.

430
00:20:17,909 --> 00:20:20,200
Jag vill inte att denna sak att
få in några konstiga oändliga

431
00:20:20,200 --> 00:20:21,810
slinga på grund av ett negativt värde.

432
00:20:21,810 --> 00:20:25,070
Så jag säger bara, om du ger mig
noll eller mindre, jag återvänder noll.

433
00:20:25,070 --> 00:20:28,220
>> Men det är bra eftersom det är
som enda sida av telefonboken

434
00:20:28,220 --> 00:20:28,790
som är kvar.

435
00:20:28,790 --> 00:20:32,660
Jag bita av ett mycket specifikt problem
och inte kräver något rekursivt.

436
00:20:32,660 --> 00:20:36,580
Men i linje 31, vilken
jag verkar göra?

437
00:20:36,580 --> 00:20:39,780
De parenteser bara hålla
saker, förhoppningsvis, lite tydligare.

438
00:20:39,780 --> 00:20:42,110
Men allt jag gör är att jag är
återvända m-- oavsett

439
00:20:42,110 --> 00:20:45,790
du lämnar mig-- plus
Värdet av m-- ledsen,

440
00:20:45,790 --> 00:20:49,052
plus värdet av sigma m minus 1.

441
00:20:49,052 --> 00:20:50,010
Så vad betyder det?

442
00:20:50,010 --> 00:20:53,965
Om du ger mig siffran 3 som indata,
det svar jag vill komma i slutändan

443
00:20:53,965 --> 00:20:57,307
är 6 eftersom tre plus två plus en ger mig sex.

444
00:20:57,307 --> 00:20:59,390
Men hur gör jag tänker på
hur denna kod körs?

445
00:20:59,390 --> 00:21:03,070
Första gången jag kallar sigma
och jag passerar i värdet 3,

446
00:21:03,070 --> 00:21:07,960
det är som att säga på en bit
papper, här är värdet 3

447
00:21:07,960 --> 00:21:09,920
och jag har klarat detta som sigma.

448
00:21:09,920 --> 00:21:13,090
3 är naturligtvis inte mindre än 0 så
IF villkor gäller inte.

449
00:21:13,090 --> 00:21:14,020
Den andra gör.

450
00:21:14,020 --> 00:21:14,990
Så vad ska jag göra?

451
00:21:14,990 --> 00:21:19,902
Jag vill återvända m, som är
3, plus sigma m minus 1.

452
00:21:19,902 --> 00:21:21,110
Så låt mig hålla reda på detta.

453
00:21:21,110 --> 00:21:22,710
Jag kommer att sätta detta
papper ned.

454
00:21:22,710 --> 00:21:24,668
Och vilket värde, att vara
klart, jag kommer att passera

455
00:21:24,668 --> 00:21:26,540
i sigma vid denna tidpunkt i historien?

456
00:21:26,540 --> 00:21:28,080
Vilket nummer?

457
00:21:28,080 --> 00:21:28,610
2, eller hur?

458
00:21:28,610 --> 00:21:29,670
3 minus 1 är 2.

459
00:21:29,670 --> 00:21:32,000
Så jag behöver bara lite
papperslapp här.

460
00:21:32,000 --> 00:21:33,931
Så nu sigma är att få kallas igen.

461
00:21:33,931 --> 00:21:35,930
Och jag har medvetet lagt
ner det eftersom det är

462
00:21:35,930 --> 00:21:38,070
ungefär som pausa
den versionen av berättelsen

463
00:21:38,070 --> 00:21:40,720
för nu är jag fokuserad
på signalen av m minus ett.

464
00:21:40,720 --> 00:21:42,660
Så m var 3, m minus 1 är 2.

465
00:21:42,660 --> 00:21:45,110
Så här är två som jag har gått.

466
00:21:45,110 --> 00:21:48,510
2 är naturligtvis inte mindre än
0 så att fallet inte gäller.

467
00:21:48,510 --> 00:21:53,445
Annars jag återvänder m, som är
sak, plus sigma vilket värde?

468
00:21:53,445 --> 00:21:56,160

469
00:21:56,160 --> 00:21:59,650
Så om sigma av 1-- eftersom m är
just nu två så 2 minus 1 är en.

470
00:21:59,650 --> 00:22:01,950
Så nu har jag bara värdet 1.

471
00:22:01,950 --> 00:22:04,810
Jag passerar bara antalet
1 till funktionen sigma--

472
00:22:04,810 --> 00:22:09,120
eller själv här-- så en är uppenbarligen inte
mindre än noll, fortfarande inte gäller.

473
00:22:09,120 --> 00:22:12,970
>> Else avkastning 1 plus sigma av vad?

474
00:22:12,970 --> 00:22:13,470
0.

475
00:22:13,470 --> 00:22:14,678
Så låt mig bara ihåg att.

476
00:22:14,678 --> 00:22:15,920
Jag återkommer till det senare.

477
00:22:15,920 --> 00:22:18,060
Nu ska jag gå vidare och jota
minska antalet 0 eftersom det är

478
00:22:18,060 --> 00:22:19,470
mitt argument eller parameter.

479
00:22:19,470 --> 00:22:22,400
Jag passerade siffran 0
och slutligen denna process

480
00:22:22,400 --> 00:22:25,760
för att bara upprepa mig annons
nauseum inte upphör eftersom det

481
00:22:25,760 --> 00:22:28,820
jag omedelbart göra när jag ser detta 0?

482
00:22:28,820 --> 00:22:29,790
Jag återvänder noll.

483
00:22:29,790 --> 00:22:31,790
Så nu har du att spola tillbaka historien.

484
00:22:31,790 --> 00:22:34,430
>> Om jag nu går bakåt i tiden,
Vad var det senaste sak

485
00:22:34,430 --> 00:22:36,670
Jag gjorde om du var bokstavligen
en video spolar tillbaka?

486
00:22:36,670 --> 00:22:41,630
Jag kommer att ta upp den senaste
1 och det ger mig en plus 0 är 1.

487
00:22:41,630 --> 00:22:44,100
Om jag håller bakåt av
historia, som kommer att ge mig

488
00:22:44,100 --> 00:22:46,880
2 plus det löpande värdet, vilket är 1.

489
00:22:46,880 --> 00:22:47,789
Så det är tre.

490
00:22:47,789 --> 00:22:49,330
Och sedan kommer jag att hålla omrullningen.

491
00:22:49,330 --> 00:22:54,220
När jag först lägga ner numret
3-- så 3 plus 3 ger mig sex.

492
00:22:54,220 --> 00:22:57,272
>> Och nu, om du har lindas
video fram till denna punkt,

493
00:22:57,272 --> 00:22:58,980
detta var mycket
första fråga jag.

494
00:22:58,980 --> 00:23:01,450
När passerade 3, vad är sigma 3?

495
00:23:01,450 --> 00:23:04,204
Det är i själva verket 6, summan av
alla dessa bitar av papper.

496
00:23:04,204 --> 00:23:07,120
Så om det tar ett tag att
linda ditt sinne kring, det är bra.

497
00:23:07,120 --> 00:23:10,700
Men anser att det var en little-- det
var mycket medveten om att jag staplade

498
00:23:10,700 --> 00:23:12,990
dessa siffror ovanpå varandra.

499
00:23:12,990 --> 00:23:17,440
Det är ungefär som att ha en
memory-- en post i tid,

500
00:23:17,440 --> 00:23:19,940
som en skrubber i en video,
att jag verkligen kan spola tillbaka in.

501
00:23:19,940 --> 00:23:24,350
Och vi kommer att komma tillbaka till
som metafor i bara lite.

502
00:23:24,350 --> 00:23:28,240
>> Men först, visar det sig att det finns
en hel del nördar och roliga människor,

503
00:23:28,240 --> 00:23:29,614
Jag antar på Google.

504
00:23:29,614 --> 00:23:31,530
Skulle någon som är mycket
bra på att googla sinne

505
00:23:31,530 --> 00:23:34,270
kommer upp för ett ögonblick och
hjälpa mig att söka efter något?

506
00:23:34,270 --> 00:23:35,650
Mycket, mycket låg nyckeln.

507
00:23:35,650 --> 00:23:37,870
Någon som är aldrig
komma upp innan, kanske.

508
00:23:37,870 --> 00:23:38,370
OK.

509
00:23:38,370 --> 00:23:39,030
Yeah?

510
00:23:39,030 --> 00:23:39,530
Kom igen.

511
00:23:39,530 --> 00:23:41,410
Kom ner.

512
00:23:41,410 --> 00:23:42,183
Vad heter du?

513
00:23:42,183 --> 00:23:42,870
>> SAM: Sam.

514
00:23:42,870 --> 00:23:44,290
>> DAVID J. MALAN: Sam, kom ner.

515
00:23:44,290 --> 00:23:45,320
Detta är samma.

516
00:23:45,320 --> 00:23:46,280
Trevligt att träffas.

517
00:23:46,280 --> 00:23:46,780
Hallå.

518
00:23:46,780 --> 00:23:47,580
Kom över.

519
00:23:47,580 --> 00:23:51,290
Så allt jag vill att du gör, om
du kan, Sam, här är Google.

520
00:23:51,290 --> 00:23:53,240
Kan du söka efter termen rekursion?

521
00:23:53,240 --> 00:23:55,770

522
00:23:55,770 --> 00:23:56,270
Förstör inte.

523
00:23:56,270 --> 00:23:59,940

524
00:23:59,940 --> 00:24:00,970
>> Och nu let's-- ja.

525
00:24:00,970 --> 00:24:03,380
OK Klicka på den.

526
00:24:03,380 --> 00:24:04,315
Bättre klickar du på den.

527
00:24:04,315 --> 00:24:07,020

528
00:24:07,020 --> 00:24:08,020
Ahh, få det.

529
00:24:08,020 --> 00:24:08,520
Nej?

530
00:24:08,520 --> 00:24:09,050
OK.

531
00:24:09,050 --> 00:24:10,430
Så låt oss göra ett par andra.

532
00:24:10,430 --> 00:24:12,830
Inte så mycket närstående
akademiskt här, men du har

533
00:24:12,830 --> 00:24:14,520
någonsin sökt Google för anagram?

534
00:24:14,520 --> 00:24:15,280
>> SAM: Nej

535
00:24:15,280 --> 00:24:15,520
>> David J. MALAN: OK.

536
00:24:15,520 --> 00:24:17,186
Sök efter anagram istället för rekursion.

537
00:24:17,186 --> 00:24:22,540

538
00:24:22,540 --> 00:24:23,790
Vad sägs om snett.

539
00:24:23,790 --> 00:24:25,515
Du någonsin sökte efter sned?

540
00:24:25,515 --> 00:24:29,260

541
00:24:29,260 --> 00:24:32,692
Nu är det här en lite svårt att
se men förhoppningsvis everything's-- OK.

542
00:24:32,692 --> 00:24:34,150
Det är bara du och jag njuta av detta.

543
00:24:34,150 --> 00:24:34,690
OK.

544
00:24:34,690 --> 00:24:38,950
>> Så till sist, detta one's--
det är lite sned.

545
00:24:38,950 --> 00:24:40,810
Nu gör ett fat rulle.

546
00:24:40,810 --> 00:24:44,460

547
00:24:44,460 --> 00:24:45,310
Underbart.

548
00:24:45,310 --> 00:24:45,910
Okej.

549
00:24:45,910 --> 00:24:47,110
Stort tack till Sam.

550
00:24:47,110 --> 00:24:49,416
Här får du.

551
00:24:49,416 --> 00:24:50,400
Tack.

552
00:24:50,400 --> 00:24:52,807
>> Så vad som händer i alla
av dessa fåniga exempel?

553
00:24:52,807 --> 00:24:55,640
Så egentligen, under huven på
Googles miljontals rader kod

554
00:24:55,640 --> 00:24:58,860
tydligen är några dum IF
förhållanden som är väsentligen

555
00:24:58,860 --> 00:25:01,160
kontrollera om användaren har
skrev i denna fras,

556
00:25:01,160 --> 00:25:03,760
göra något som antagligen tog
en icke-triviala mängd tid

557
00:25:03,760 --> 00:25:06,080
att genomföra bara
vara underhållande på detta sätt.

558
00:25:06,080 --> 00:25:08,430
Men det är allt det kokar
ned till under huven.

559
00:25:08,430 --> 00:25:11,570
Men, naturligtvis, rekursion
är mer av geekier

560
00:25:11,570 --> 00:25:13,880
exempel bland de speciella trick.

561
00:25:13,880 --> 00:25:16,880
Och säkert finns det andra där ute
samt att vi kanske inte ens

562
00:25:16,880 --> 00:25:18,230
upptäckt ännu.

563
00:25:18,230 --> 00:25:22,830
>> Så ta en titt, eller överväga
nu följande program,

564
00:25:22,830 --> 00:25:24,830
och definitivt ta någon
av dessa på väg ut.

565
00:25:24,830 --> 00:25:28,820
Jag kommer att gå vidare och
öppna upp ett program som är

566
00:25:28,820 --> 00:25:30,920
kommer att försöka byta två värden.

567
00:25:30,920 --> 00:25:33,210
Men innan vi åker dit, låt oss göra detta.

568
00:25:33,210 --> 00:25:38,500
Skulle vi kunna få en mer
volontär, tror jag?

569
00:25:38,500 --> 00:25:40,480
Vill du volontär?

570
00:25:40,480 --> 00:25:40,980
Nej?

571
00:25:40,980 --> 00:25:41,890
Kom upp.

572
00:25:41,890 --> 00:25:42,390
Kom upp.

573
00:25:42,390 --> 00:25:42,890
Okej.

574
00:25:42,890 --> 00:25:44,136
Så ditt namn är vad?

575
00:25:44,136 --> 00:25:44,810
>> LAUREN: Lauren.

576
00:25:44,810 --> 00:25:45,768
>> DAVID J. MALAN: Lauren.

577
00:25:45,768 --> 00:25:46,890
Kom upp, Lauren.

578
00:25:46,890 --> 00:25:50,140
Så Lauren håller på att
utmanade här enligt följande.

579
00:25:50,140 --> 00:25:52,310
Trevligt att träffas.

580
00:25:52,310 --> 00:25:55,730
Så Lauren här har framför
av sina två tomma koppar.

581
00:25:55,730 --> 00:25:57,570
Och vi har några apelsin
juice och mjölk

582
00:25:57,570 --> 00:26:00,301
och vi kommer att gå
vidare och göra följande.

583
00:26:00,301 --> 00:26:01,550
Vi kommer bara att fylla detta.

584
00:26:01,550 --> 00:26:07,840
Några uns av mjölk över här och låt oss
fylla en liten apelsinjuice hit.

585
00:26:07,840 --> 00:26:11,475
>> Och framför allt av
dessa publiken,

586
00:26:11,475 --> 00:26:13,550
byta de båda värdena för dessa koppar.

587
00:26:13,550 --> 00:26:16,970
Sätt apelsinjuice i mjölken cup
och mjölken i apelsinjuice koppen.

588
00:26:16,970 --> 00:26:22,380

589
00:26:22,380 --> 00:26:26,150
Hur skulle du göra detta om du var på
hem och hade tillgång till andra förnödenheter?

590
00:26:26,150 --> 00:26:27,400
LAUREN: Lägg den i en kopp.

591
00:26:27,400 --> 00:26:28,191
David J. MALAN: OK.

592
00:26:28,191 --> 00:26:31,940
Så låt oss ta en tillfällig
variabel, om vi kommer.

593
00:26:31,940 --> 00:26:35,871
Och gå vidare nu och genomföra
denna samma swapping procedur.

594
00:26:35,871 --> 00:26:36,370
Så bra.

595
00:26:36,370 --> 00:26:41,490
Vi har lagt EGT i den tillfälliga
variabel, mjölk i EUT variabeln,

596
00:26:41,490 --> 00:26:44,481
och nu den temporära variabeln
in i mjölkvariabel.

597
00:26:44,481 --> 00:26:44,980
OK.

598
00:26:44,980 --> 00:26:48,740
Så mycket bra gjort hittills.

599
00:26:48,740 --> 00:26:50,990
Så visar det sig out-- konstatera att
trodde för bara ett ögonblick.

600
00:26:50,990 --> 00:26:54,479
Här, bara nörd det upp lite, det här
skulle vara den motsvarande C-kod

601
00:26:54,479 --> 00:26:55,520
att vi bara genomförs.

602
00:26:55,520 --> 00:26:58,650
Vi hade två ingångar, a och b, som båda
som vi bara kan säga enkelhet är

603
00:26:58,650 --> 00:26:59,260
int s.

604
00:26:59,260 --> 00:27:02,780
Och lägg märke till här, om jag vill byta
värdena för två variabler, a och b,

605
00:27:02,780 --> 00:27:06,890
vi verkligen behöver en mellanhand, en
temporär variabel, en tillfällig kopp,

606
00:27:06,890 --> 00:27:10,830
in i vilken pour ett av värdena
så att vi har en platshållare för det.

607
00:27:10,830 --> 00:27:13,480
Men då koden är exakt
som Lauren här genomförs.

608
00:27:13,480 --> 00:27:15,500
>> Nu, bara för att få en
lite galnare, visar sig

609
00:27:15,500 --> 00:27:20,930
att du kan göra detta utan
en temporär variabel.

610
00:27:20,930 --> 00:27:24,870
För att göra detta på rätt sätt, men vi kommer
att ha att fuska med viss kemi.

611
00:27:24,870 --> 00:27:26,380
Vi har några extra koppar här.

612
00:27:26,380 --> 00:27:29,600
Så det närmaste som ser
som mjölk och vatten perhaps--

613
00:27:29,600 --> 00:27:34,090
eller mjölk och OJ-- är att vi har en del
vatten, så vi kommer att fylla detta en upp

614
00:27:34,090 --> 00:27:36,486
med några uns av rent vatten.

615
00:27:36,486 --> 00:27:38,332
Det är nog för mycket.

616
00:27:38,332 --> 00:27:38,832
Yeah.

617
00:27:38,832 --> 00:27:39,934
Det är definitivt för mycket.

618
00:27:39,934 --> 00:27:40,600
Håll på en sekund.

619
00:27:40,600 --> 00:27:43,520

620
00:27:43,520 --> 00:27:48,420
>> Och nu har vi olja, vilket, som jag minns
från högstadiet kemi klass,

621
00:27:48,420 --> 00:27:49,990
förhoppningsvis det inte blandas med vatten.

622
00:27:49,990 --> 00:27:53,650
Men det slags slags
ser ut som mjölk och EGT.

623
00:27:53,650 --> 00:27:55,760
Så nu, utan att använda
en temporär variabel,

624
00:27:55,760 --> 00:27:59,260
kan du byta dessa två värden?

625
00:27:59,260 --> 00:28:03,884
Så oljor går i vattnet koppen,
vatten går in i oljekoppen.

626
00:28:03,884 --> 00:28:04,800
LAUREN: Inga andra koppar?

627
00:28:04,800 --> 00:28:05,940
DAVID J. MALAN: Inga andra koppar.

628
00:28:05,940 --> 00:28:07,860
Och jag har faktiskt inte
testat detta innan år

629
00:28:07,860 --> 00:28:10,110
så jag vet inte om detta kommer att
faktiskt arbetar kemiskt.

630
00:28:10,110 --> 00:28:16,130

631
00:28:16,130 --> 00:28:18,650
Det var inte tänkt att ske.

632
00:28:18,650 --> 00:28:19,761
Är det att fungera?

633
00:28:19,761 --> 00:28:20,260
Okej.

634
00:28:20,260 --> 00:28:20,990
Så separera?

635
00:28:20,990 --> 00:28:21,490
God.

636
00:28:21,490 --> 00:28:24,714
Nu fick vi få
vatten i den andra koppen.

637
00:28:24,714 --> 00:28:27,630
Smartare kemi koncentratorer kunde
förmodligen göra detta bättre än mig.

638
00:28:27,630 --> 00:28:28,510
>> LAUREN: Vattnet är på botten.

639
00:28:28,510 --> 00:28:31,910
>> David J. MALAN: Den water-- som var
vad är nyckeln sista gången vi gjorde detta.

640
00:28:31,910 --> 00:28:33,950
Du måste göra det i rätt ordning.

641
00:28:33,950 --> 00:28:34,450
Yeah.

642
00:28:34,450 --> 00:28:35,270
Det är ok.

643
00:28:35,270 --> 00:28:37,290
Så nu har vi två koppar olja.

644
00:28:37,290 --> 00:28:37,790
OK.

645
00:28:37,790 --> 00:28:38,510
Det är ok.

646
00:28:38,510 --> 00:28:40,110
Men kemiskt om detta fungerat än jag--

647
00:28:40,110 --> 00:28:41,200
>> LAUREN: Detta är vatten.

648
00:28:41,200 --> 00:28:41,930
>> DAVID J. MALAN: Det är mestadels vatten.

649
00:28:41,930 --> 00:28:42,430
Okej.

650
00:28:42,430 --> 00:28:44,210
Men det är fortfarande samma kopp som tidigare.

651
00:28:44,210 --> 00:28:47,570
Så häll det-- prova det där borta.

652
00:28:47,570 --> 00:28:49,300
OK.

653
00:28:49,300 --> 00:28:51,010
Detta är en bra användning av lektionstid idag.

654
00:28:51,010 --> 00:28:51,510
OK.

655
00:28:51,510 --> 00:28:53,890
Så nu we-- trevligt.

656
00:28:53,890 --> 00:28:55,460
Ungefär.

657
00:28:55,460 --> 00:28:55,960
Okej.

658
00:28:55,960 --> 00:28:56,690
Så mycket bra.

659
00:28:56,690 --> 00:29:00,006
Tack till Lauren.

660
00:29:00,006 --> 00:29:01,950
Väldigt bra gjort.

661
00:29:01,950 --> 00:29:04,570
>> Så bara för att blåsa era sinnen,
och detta är kanske något

662
00:29:04,570 --> 00:29:08,660
att spela med om du vill i CS50 ID,
Du kan i själva verket, byta två variabler

663
00:29:08,660 --> 00:29:11,470
utan att använda en temporär heltal.

664
00:29:11,470 --> 00:29:13,060
Och detta är motsvarande C-koden.

665
00:29:13,060 --> 00:29:16,110
Och om du minns från förra
Onsdag, införde vi, om kortfattat,

666
00:29:16,110 --> 00:29:19,720
några nya aktörer i C och gör
någon ihåg vad den lilla morot

667
00:29:19,720 --> 00:29:23,660
symbol är den lilla trekantiga
symbol på tangentbordet representerar?

668
00:29:23,660 --> 00:29:26,003
Vad bitvis operatör?

669
00:29:26,003 --> 00:29:26,770
>> PUBLIK: EXOR.

670
00:29:26,770 --> 00:29:27,645
>> David J. MALAN: EXOR.

671
00:29:27,645 --> 00:29:28,560
Exklusiv Or.

672
00:29:28,560 --> 00:29:32,920
Så om du vill, bara för skojs skull på
hem, för att ge a och b två godtyckliga

673
00:29:32,920 --> 00:29:36,072
värden som alla eight-- och jag
skulle välja ett åtta bitars värde.

674
00:29:36,072 --> 00:29:38,530
Om du gör detta med 32 bitar,
du mycket snabbt uttråkad.

675
00:29:38,530 --> 00:29:42,150
Men bara ge en ett åttabitars
värde som är vad, ett eller två,

676
00:29:42,150 --> 00:29:43,790
och ge b ett liknande värde.

677
00:29:43,790 --> 00:29:46,810
Och sedan använda definitionen
av XOR från förra onsdagen,

678
00:29:46,810 --> 00:29:52,560
tillämpa detta bit för bit, var och en av
dessa åtta bitar i varje av a och b,

679
00:29:52,560 --> 00:29:54,980
och sedan göra det exakt per denna kod.

680
00:29:54,980 --> 00:29:58,170
Och det är inte fel vad
du ser här på skärmen.

681
00:29:58,170 --> 00:30:02,100
Det kokar verkligen ner
till tre XOR-operationer

682
00:30:02,100 --> 00:30:05,910
och något magiskt en och
b kommer att utbyta positioner

683
00:30:05,910 --> 00:30:08,010
utan att förlora någon information.

684
00:30:08,010 --> 00:30:11,580
>> Så att oljan och vatten tricket är den
närmast verkliga världen inkarnation

685
00:30:11,580 --> 00:30:12,980
Jag kunde tänka på att efterlikna det.

686
00:30:12,980 --> 00:30:15,950
Men det är säkert lättare att
använda en temporär variabel,

687
00:30:15,950 --> 00:30:16,920
som i detta fall här.

688
00:30:16,920 --> 00:30:21,190
Och även detta är en möjlighet att säga,
Även denna typ av mikro optimering,

689
00:30:21,190 --> 00:30:23,590
som en datavetare
skulle säga, medan ganska kul

690
00:30:23,590 --> 00:30:27,060
att skryta om hur du gjorde detta utan
som att byta med en extra variabel,

691
00:30:27,060 --> 00:30:28,640
Det är inte så övertygande.

692
00:30:28,640 --> 00:30:31,619
Eftersom att spara 32 bitar, som
i fallet med en verklig int,

693
00:30:31,619 --> 00:30:33,410
är inte så övertygande
på ett system där

694
00:30:33,410 --> 00:30:36,722
du kanske använder tiotals megabyte
eller ännu mer sådan minnes dessa dagar.

695
00:30:36,722 --> 00:30:38,680
Och faktiskt, när vi får
till ett senare problem set

696
00:30:38,680 --> 00:30:41,010
och du implementerar spell
checker och du

697
00:30:41,010 --> 00:30:43,550
utmanas att göra det med
detta så litet RAM och så litet

698
00:30:43,550 --> 00:30:46,820
tid som möjligt på
computer-- du fortfarande

699
00:30:46,820 --> 00:30:50,160
har en vecka för att genomföra
det-- du have-- kommer du att

700
00:30:50,160 --> 00:30:51,799
utmanas att minimera dessa resurser.

701
00:30:51,799 --> 00:30:53,840
Och det är egentligen den enda
föran denna termin

702
00:30:53,840 --> 00:30:57,940
där du kommer att uppmuntras att raka
av även de finaste prestanda

703
00:30:57,940 --> 00:30:59,340
kostar annars.

704
00:30:59,340 --> 00:31:02,200
>> Så Vad-- hur kan vi
se detta i själva koden?

705
00:31:02,200 --> 00:31:04,530
Låt mig gå vidare nu
och öppna upp ett exempel

706
00:31:04,530 --> 00:31:07,700
som avsiktligt kallas
Ingen Swap eftersom den inte

707
00:31:07,700 --> 00:31:10,670
i själva verket byta variablerna
som du faktiskt kan förvänta sig.

708
00:31:10,670 --> 00:31:12,260
Så låt oss ta en titt.

709
00:31:12,260 --> 00:31:17,050
Här är ett program som inte har någon CS50
bibliotek pågår, bara standard I / O.

710
00:31:17,050 --> 00:31:19,560
Nu har vi en prototyp
för swap där uppe som just

711
00:31:19,560 --> 00:31:21,540
betyder det måste fastställas senare.

712
00:31:21,540 --> 00:31:22,550
Och här är huvud.

713
00:31:22,550 --> 00:31:26,000
>> Jag godtyckligt x och y,
respektive, värdena en och två

714
00:31:26,000 --> 00:31:28,590
bara för att de är små
och lätt att tänka på.

715
00:31:28,590 --> 00:31:32,280
Och då har jag bara en massa printfs
där jag har en sanity check. x är ett

716
00:31:32,280 --> 00:31:35,110
och y är 2 är förmodligen
vad dessa printfs kommer att säga.

717
00:31:35,110 --> 00:31:36,530
Så ingen magi hittills.

718
00:31:36,530 --> 00:31:40,100
>> Då kommer jag att hävda med
ut def, byta dot dot dot.

719
00:31:40,100 --> 00:31:43,730
Jag kommer att kalla swap
funktionen, passerar x och y.

720
00:31:43,730 --> 00:31:47,350
Och låt oss anta nu att
swap genomförs exakt

721
00:31:47,350 --> 00:31:49,930
eftersom det var en stund sedan
med en temporär variabel.

722
00:31:49,930 --> 00:31:52,670
Och så jag hävdar djärvt, bytte.

723
00:31:52,670 --> 00:31:55,429
x är nu detta och y är nu att.

724
00:31:55,429 --> 00:31:57,220
Men filen, naturligtvis,
kallas Ingen Swap.

725
00:31:57,220 --> 00:31:58,678
Så låt oss faktiskt se vad som händer.

726
00:31:58,678 --> 00:32:04,450
Om jag sammanställer ingen swap och sedan
do ./noswap, x är 1, y är 2.

727
00:32:04,450 --> 00:32:05,770
Byta bytte.

728
00:32:05,770 --> 00:32:07,200
x är 1, y är 2.

729
00:32:07,200 --> 00:32:11,980
Så det verkar faktiskt vara bristfällig även
men swap-- låt oss rulla ned now--

730
00:32:11,980 --> 00:32:16,542
genomförs exakt per
kod föreslog jag för en stund sedan.

731
00:32:16,542 --> 00:32:19,000
Så vi kommer inte att få lust
med XOR grejer nu.

732
00:32:19,000 --> 00:32:21,890
Även detta bör fungera lika
som med mjölk och EGT,

733
00:32:21,890 --> 00:32:25,820
men det verkar inte fungera.

734
00:32:25,820 --> 00:32:27,180
>> Så låt oss göra det igen.

735
00:32:27,180 --> 00:32:29,310
Jag kanske bara inte kördes det rätt.

736
00:32:29,310 --> 00:32:32,010
Så låt oss köra Ingen Swap igen.

737
00:32:32,010 --> 00:32:32,900
Kanske jag-- nr.

738
00:32:32,900 --> 00:32:34,400
Så det är bara inte fungerar.

739
00:32:34,400 --> 00:32:36,060
Så låt oss göra en liten sanity check.

740
00:32:36,060 --> 00:32:39,690
Låt mig gå vidare här i Swap
och bara lägga till, vänta en minut,

741
00:32:39,690 --> 00:32:43,856
a är% i / n och låt oss
plug-in värdet av en.

742
00:32:43,856 --> 00:32:45,730
Eftersom jag verkligen vill
för att se vad som händer.

743
00:32:45,730 --> 00:32:47,570
Och faktiskt, är detta
en felsökning teknik

744
00:32:47,570 --> 00:32:50,028
som du kan använda i
kontorstid eller hemma redan,

745
00:32:50,028 --> 00:32:53,560
besläktad med den första halvan av Dan
Armendariz video i PSET3

746
00:32:53,560 --> 00:32:56,870
där vi introducerade tryck def som
en rekommenderad teknik, åtminstone

747
00:32:56,870 --> 00:32:58,080
för enkla fall.

748
00:32:58,080 --> 00:33:01,720
Låt mig gå vidare och kör make
ingen swap igen, ./noswap.

749
00:33:01,720 --> 00:33:04,370

750
00:33:04,370 --> 00:33:05,840
>> Intressant.

751
00:33:05,840 --> 00:33:11,670
Så märker vad som verkar vara sant. X
är ett, y är 2, men en är 2 när b är 1.

752
00:33:11,670 --> 00:33:16,790
Så de två på något sätt fick bytte
men x och y inte får växlas.

753
00:33:16,790 --> 00:33:21,090
Så för att vara tydlig, vad händer
är, här uppe har jag x och y

754
00:33:21,090 --> 00:33:25,380
och de är variabler lokala i
omfattningen av huvud, jag passerar x och y

755
00:33:25,380 --> 00:33:26,170
att byta.

756
00:33:26,170 --> 00:33:29,080
Nu, swap, som en separat funktion,
är att ringa sina argument

757
00:33:29,080 --> 00:33:30,590
eller dess parametrar något man vill.

758
00:33:30,590 --> 00:33:33,280
Foo eller bar eller x eller y eller a eller b.

759
00:33:33,280 --> 00:33:36,870
Bara för att klargöra att de är
inte är identiska med x och y i sig,

760
00:33:36,870 --> 00:33:38,020
Jag har sagt a och b.

761
00:33:38,020 --> 00:33:40,040
Men vi kan kalla dem vad vi vill.

762
00:33:40,040 --> 00:33:43,960
>> Och så det ser ut
swap förs vidare

763
00:33:43,960 --> 00:33:48,980
x-- AKA en-- och det är
får passera y-- AKA f.

764
00:33:48,980 --> 00:33:51,900
På något sätt dessa tre linjer är
byta dessa värden exakt

765
00:33:51,900 --> 00:33:53,510
som Lauren gjorde med mjölk och EGT.

766
00:33:53,510 --> 00:33:56,010
Men när vi skriver ut
värdena, a och b

767
00:33:56,010 --> 00:34:01,340
är verkligen byta men x och
y har ingen förändring av dem.

768
00:34:01,340 --> 00:34:03,150
Minns att x och y är här uppe.

769
00:34:03,150 --> 00:34:05,320
>> Så att vi kan se detta via
en annan teknik också.

770
00:34:05,320 --> 00:34:08,110
Och även detta är en teknik
inbäddade i problem som trede.

771
00:34:08,110 --> 00:34:10,780
Låt oss gå vidare och göra detta i
CS50-ID om du inte redan har gjort.

772
00:34:10,780 --> 00:34:13,730
På höger sida är vi
har den här fliken Debugger.

773
00:34:13,730 --> 00:34:16,159
Och om du öppnar upp denna,
det finns en del svårbegripliga uppgifter

774
00:34:16,159 --> 00:34:17,530
som kastas på dig från början.

775
00:34:17,530 --> 00:34:19,310
Men låt oss retas detta dem riktigt snabbt.

776
00:34:19,310 --> 00:34:21,620
>> Så en, ser du lokala variabler.

777
00:34:21,620 --> 00:34:26,230
Det visade sig att bygga in CS50 IDE, och
en hel del programmeringsmiljöer mer

778
00:34:26,230 --> 00:34:28,060
allmänt är en avlusare.

779
00:34:28,060 --> 00:34:31,340
Ett verktyg som låter dig visuellt se
vad som händer inne i ditt program

780
00:34:31,340 --> 00:34:34,380
utan att behöva tillgripa tillsätta
printfs och sammanställa och köra

781
00:34:34,380 --> 00:34:37,588
och lägga printf s och sammanställa och
kör, som redan i kontorstid

782
00:34:37,588 --> 00:34:40,070
eller hemma, är förmodligen
bli ganska tråkiga.

783
00:34:40,070 --> 00:34:43,090
>> Så här, i ett ögonblick, vi är
kommer att se i realtid

784
00:34:43,090 --> 00:34:44,760
värdena för våra lokala variabler.

785
00:34:44,760 --> 00:34:47,880
Vi kommer även att kunna sätta
vad som kallas brytpunkter som

786
00:34:47,880 --> 00:34:52,570
finns möjligheter i mitt program för att pausa
bearbetning på visst kodrad

787
00:34:52,570 --> 00:34:53,710
att jag är nyfiken på.

788
00:34:53,710 --> 00:34:54,210
Höger?

789
00:34:54,210 --> 00:34:55,969
Dessa program körs i en bråkdels sekund.

790
00:34:55,969 --> 00:35:00,450
Det är typ av trevligt för oss långsammare människor
att kunna pausa, ta en stund, se

791
00:35:00,450 --> 00:35:02,380
vad som händer runt
en viss kodrad

792
00:35:02,380 --> 00:35:05,050
utan programmet plöjning
igenom den och helt avslutad.

793
00:35:05,050 --> 00:35:08,510
Så en brytpunkter kommer att tillåta oss att
bryta och pausa vid en viss punkt.

794
00:35:08,510 --> 00:35:12,990
>> Anropsstacken är ett finare sätt att
säger vilka funktioner finns för närvarande

795
00:35:12,990 --> 00:35:14,140
kallas just nu.

796
00:35:14,140 --> 00:35:15,370
Main alltid kallas först.

797
00:35:15,370 --> 00:35:17,230
Men om huvud kallar en
Funktionen kallas Swap,

798
00:35:17,230 --> 00:35:20,470
vi faktiskt kommer att se ut
torn av funktioner som har varit

799
00:35:20,470 --> 00:35:22,400
kallas i omvänd kronologisk ordning.

800
00:35:22,400 --> 00:35:23,310
Så låt oss se det.

801
00:35:23,310 --> 00:35:24,327
>> Jag kommer att zooma ut.

802
00:35:24,327 --> 00:35:25,660
Jag kommer att gå tillbaka till min kod.

803
00:35:25,660 --> 00:35:27,540
Och bara för att jag vill ha
att vara pedantisk här,

804
00:35:27,540 --> 00:35:31,100
Jag kommer att gå vidare och klicka
precis till vänster om linjen fem.

805
00:35:31,100 --> 00:35:32,830
Och det skapar en röd prick.

806
00:35:32,830 --> 00:35:36,200
Och lägg märke på höger sida
att debugger vet, hej,

807
00:35:36,200 --> 00:35:41,020
Jag sa bara en brytpunkt på
noswap.c linje fem, särskilt

808
00:35:41,020 --> 00:35:42,480
vid denna kodrad.

809
00:35:42,480 --> 00:35:45,090
Så debugger vet att jag
har begärt att nästa gång

810
00:35:45,090 --> 00:35:48,530
Jag kör mitt program det paus
utförande det snarare än bara

811
00:35:48,530 --> 00:35:50,390
kör hela supersnabb.

812
00:35:50,390 --> 00:35:53,889
>> Så nu ska jag klicka Debug
knappen högst upp på IDE

813
00:35:53,889 --> 00:35:55,430
och det kommer att göra följande.

814
00:35:55,430 --> 00:36:00,680
Det kommer att öppna en initialt något
skrämmande ser andra terminal window--

815
00:36:00,680 --> 00:36:02,679
fjärrfelsökning från
värd för ett sådant och such--

816
00:36:02,679 --> 00:36:04,970
och vi ska återkomma till vad
allt vad det innebär inom kort.

817
00:36:04,970 --> 00:36:09,020
Men vad som är viktigt just nu
det vill säga att red dot drabbades,

818
00:36:09,020 --> 00:36:11,735
debugger har medvetet
pausas execution--

819
00:36:11,735 --> 00:36:15,560
inte på den linjen i sig utan på den första
raden av faktiska koden i denna funktion.

820
00:36:15,560 --> 00:36:18,040
Och det är därför linje sju är
nu gulmarkerad.

821
00:36:18,040 --> 00:36:20,550
>> Och nu ska vi ta en titt
på höger sida.

822
00:36:20,550 --> 00:36:27,300
Det ser ut, som standard,
fint nog, x har vilket värde?

823
00:36:27,300 --> 00:36:27,860
0.

824
00:36:27,860 --> 00:36:29,750
Och y har vilket värde?

825
00:36:29,750 --> 00:36:30,410
Noll.

826
00:36:30,410 --> 00:36:35,540
Och det är som kan förväntas i den mening
att x och y-- att gula line-- har

827
00:36:35,540 --> 00:36:36,770
inte utförs än.

828
00:36:36,770 --> 00:36:38,510
Så x bör inte ha värdet 1.

829
00:36:38,510 --> 00:36:41,470
Det kan ha något annat värde,
en så kallad skräpvärdet.

830
00:36:41,470 --> 00:36:44,320
Och vi fick tur att det är
noll vid denna tidpunkt, i huvudsak.

831
00:36:44,320 --> 00:36:46,400
>> Så nu finns det bara ett fåtal
knappar vi behöver bry

832
00:36:46,400 --> 00:36:48,100
om när felsökning på det här sättet.

833
00:36:48,100 --> 00:36:49,970
Lägg märke till här, har vi en Play-knappen.

834
00:36:49,970 --> 00:36:51,877
Och om vi spelar eller slå
återupptas, det är bara

835
00:36:51,877 --> 00:36:53,710
kommer att gå igenom
resten av programmet

836
00:36:53,710 --> 00:36:55,300
eller tills den träffar en annan brytpunkt.

837
00:36:55,300 --> 00:36:56,910
Men jag har inte satt någon annan
brytpunkter så det är bara

838
00:36:56,910 --> 00:36:58,118
kommer att köra till slutet.

839
00:36:58,118 --> 00:37:00,280
Denna typ av besegrar
Syftet med att peta runt.

840
00:37:00,280 --> 00:37:03,290
>> Så istället, jag bryr mig om
dessa ikoner till höger.

841
00:37:03,290 --> 00:37:05,360
Och om jag hovrar över
dem, som ni bör också,

842
00:37:05,360 --> 00:37:07,450
ser du lite tips-- verktygstips.

843
00:37:07,450 --> 00:37:09,020
Detta är steg över.

844
00:37:09,020 --> 00:37:11,290
Nu det betyder inte att hoppa
Följande kodrad.

845
00:37:11,290 --> 00:37:14,840
Det betyder bara köra den och
flytta till nästa, gå vidare till nästa,

846
00:37:14,840 --> 00:37:15,580
gå vidare till nästa.

847
00:37:15,580 --> 00:37:17,610
Med andra ord, genom
den knappen, kan jag gå

848
00:37:17,610 --> 00:37:20,390
genom min kod ett steg i taget.

849
00:37:20,390 --> 00:37:21,914
Rad för rad, bokstavligen.

850
00:37:21,914 --> 00:37:23,830
Nu, till höger om
att det finns en annan

851
00:37:23,830 --> 00:37:25,163
att vi får se på bara ett ögonblick.

852
00:37:25,163 --> 00:37:27,820
Detta är den så kallade
Step Into ikon som är

853
00:37:27,820 --> 00:37:30,300
kommer att låta mig dyka
in i en annan funktion.

854
00:37:30,300 --> 00:37:31,800
Men låt oss se detta på bara ett ögonblick.

855
00:37:31,800 --> 00:37:33,280
Så jag kommer att klicka kliva över.

856
00:37:33,280 --> 00:37:35,820
Och nu märker, när jag klickar
den här knappen uppe till höger,

857
00:37:35,820 --> 00:37:41,260
hålla ögonen ungefär under Lokal
Variabler och se vad som händer med x.

858
00:37:41,260 --> 00:37:44,115
x är nu ett eftersom
gul linje har nu verk

859
00:37:44,115 --> 00:37:45,840
och vi har gått vidare till linjen 8.

860
00:37:45,840 --> 00:37:49,840
Och på bara ett ögonblick y
förhoppningsvis bli 2.

861
00:37:49,840 --> 00:37:52,330
>> Nu, ingenting som intressant
händer för lite.

862
00:37:52,330 --> 00:37:53,390
Allt detta är är printf.

863
00:37:53,390 --> 00:37:58,010
Och lägg märke till, enligt min sekundära terminal
fönstret ser jag produktionen av utskrifts def.

864
00:37:58,010 --> 00:38:01,080
Och nu har jag att göra en
beslut som programmerare.

865
00:38:01,080 --> 00:38:04,360
Jag kan kliva över denna linje av
kod, verkställer det, men inte

866
00:38:04,360 --> 00:38:06,220
få veta vad som finns inuti.

867
00:38:06,220 --> 00:38:11,130
Eller jag kan faktiskt kliva in det
och gå inne i Swap själv.

868
00:38:11,130 --> 00:38:12,340
Så låt oss göra det senare.

869
00:38:12,340 --> 00:38:15,550
>> Låt mig gå vidare och klicka
inte Step Over men Step Into.

870
00:38:15,550 --> 00:38:17,300
Observera, helt plötsligt
fönstret ändras

871
00:38:17,300 --> 00:38:19,330
för att markera den första
kodrad i Swap.

872
00:38:19,330 --> 00:38:20,710
Det är linje 21.

873
00:38:20,710 --> 00:38:25,220
Och nu, vad är typ av funky är att
om man tittar hit, som väntat,

874
00:38:25,220 --> 00:38:29,720
ett komma b är 1 och 2, respektive.

875
00:38:29,720 --> 00:38:33,840
Varför är temp 32767?

876
00:38:33,840 --> 00:38:36,560
Erinrar om att temp, likt
den tomma koppen för en stund sedan,

877
00:38:36,560 --> 00:38:38,980
förklaras här på ledningen 21.

878
00:38:38,980 --> 00:38:43,390
Varför 32,000- Jag menar, varför är
det bara några konstiga värde?

879
00:38:43,390 --> 00:38:43,890
Yeah?

880
00:38:43,890 --> 00:38:45,190
>> PUBLIK: Det är inte initieras.

881
00:38:45,190 --> 00:38:46,940
>> DAVID J. MALAN: Det är
inte initierats.

882
00:38:46,940 --> 00:38:49,370
Så vår dator alltid
har fysiskt minne.

883
00:38:49,370 --> 00:38:50,544
Det har alltid fysiskt RAM.

884
00:38:50,544 --> 00:38:52,710
Och det finns alltid noll s
och en är där, eller hur?

885
00:38:52,710 --> 00:38:54,626
Eftersom vi använder vår
dator hela dagen lång,

886
00:38:54,626 --> 00:38:57,210
du använder CS50 IDE
eller servrarna hela dagen lång.

887
00:38:57,210 --> 00:39:01,159
Så att RAM antingen har några nollor eller
någon har eller några nollor och ettor.

888
00:39:01,159 --> 00:39:02,950
Oavsett huruvida
du inte använder dem.

889
00:39:02,950 --> 00:39:05,270
Du kan inte bara ha tomt
utrymmen där du vill ha bitar.

890
00:39:05,270 --> 00:39:06,850
De är antingen nollor och ettor.

891
00:39:06,850 --> 00:39:09,610
>> Så visar det sig att temp, eftersom
Vi har inte initierats det ännu,

892
00:39:09,610 --> 00:39:14,580
Vi har dessa 32 bitar, men de har inte
initierats till några kända värden.

893
00:39:14,580 --> 00:39:18,110
Så vad de var mest
nyligen använt for-- dem 32 bits--

894
00:39:18,110 --> 00:39:23,000
vi bara ser artefakter av vissa
tidigare användning av de särskilt 32

895
00:39:23,000 --> 00:39:23,500
bitar.

896
00:39:23,500 --> 00:39:27,780
Så fort jag klickar Step Over dock,
Puh är temp kommer att få värdet 1.

897
00:39:27,780 --> 00:39:31,600
Och om jag gör det igen, är en
kommer att ges värdet 2

898
00:39:31,600 --> 00:39:33,830
och sedan b kommer att
ges värdet 1.

899
00:39:33,830 --> 00:39:36,390
>> Så vad är trevligt nu på
denna punkt i historien

900
00:39:36,390 --> 00:39:39,750
är att debugger är
visar mig, super långsamt

901
00:39:39,750 --> 00:39:42,640
i min egen takt, vad
delstaten Swap är.

902
00:39:42,640 --> 00:39:47,490
Men märker på toppen här, meddelande
att anropsstacken faktiskt

903
00:39:47,490 --> 00:39:49,180
har två lager till det.

904
00:39:49,180 --> 00:39:53,240
Nu den som är markerad som
Swap, om jag klickar på Main i stället,

905
00:39:53,240 --> 00:39:57,100
Lägg märke till hur de lokala variablerna ändras
eftersom utvecklaren kan bara hopp

906
00:39:57,100 --> 00:39:59,740
runt och gå in i någon annan omfattning.

907
00:39:59,740 --> 00:40:04,070
Så även om vi gör allt detta
arbeta och korrekt byta a och b,

908
00:40:04,070 --> 00:40:09,080
om jag går fram och tillbaka mellan Swap
där a är 2 och b är 1 och Main,

909
00:40:09,080 --> 00:40:11,851
har huvud påverkats alls?

910
00:40:11,851 --> 00:40:12,350
Nej.

911
00:40:12,350 --> 00:40:13,930
Så vad är takeaway här?

912
00:40:13,930 --> 00:40:18,200
Tja, visar det sig att varje gång
du kallar en funktion som Swap,

913
00:40:18,200 --> 00:40:21,600
och du passerar det argument, vad
du passerar till Swap-funktionen

914
00:40:21,600 --> 00:40:24,730
i detta fall är en kopia
av dessa argument.

915
00:40:24,730 --> 00:40:28,620
Så om x och y vardera respektive
32 bitar, vad Swap blir

916
00:40:28,620 --> 00:40:30,760
är två nya lokala
variabler, eller argument,

917
00:40:30,760 --> 00:40:34,380
kallas en och b-- men de är godtyckliga
names-- men mönstret för nollor

918
00:40:34,380 --> 00:40:39,520
och ettor insidan av a och b är
uppradade för att vara identisk med x och y

919
00:40:39,520 --> 00:40:42,610
men de är inte
samma sak som x och y.

920
00:40:42,610 --> 00:40:46,880
>> Det är som om huvud har på sin bit av
papper nummer 1 och 2 för x och y,

921
00:40:46,880 --> 00:40:49,260
och sedan när det händer att
papper till Pendla,

922
00:40:49,260 --> 00:40:51,970
Swap blir mycket snabbt
sin egen penna, skriver ned

923
00:40:51,970 --> 00:40:56,240
1 och 2 på eget pappersark,
händer tillbaka den ursprungliga xy till Main

924
00:40:56,240 --> 00:40:58,790
och sedan gör sitt eget
sak med a och b.

925
00:40:58,790 --> 00:41:01,940
Och det är nu super viktigt eftersom
detta har icke-triviala implikationer

926
00:41:01,940 --> 00:41:06,260
för att faktiskt skriva korrekt kod
eftersom det verkar vi inte kan byta

927
00:41:06,260 --> 00:41:07,500
två variabler.

928
00:41:07,500 --> 00:41:09,150
>> Jag har skrivit en korrekt Swap funktion.

929
00:41:09,150 --> 00:41:12,770
Vi har infört den med Lauren som
en korrekt växlingsfunktion i verkligheten,

930
00:41:12,770 --> 00:41:16,700
men tydligen inget av detta
frågor om du inte kan faktiskt

931
00:41:16,700 --> 00:41:19,530
byta två värden permanent.

932
00:41:19,530 --> 00:41:21,970
Så vi behöver en annan väg
att faktiskt komma åt detta,

933
00:41:21,970 --> 00:41:24,472
och vi måste kunna
faktiskt lösa detta problem.

934
00:41:24,472 --> 00:41:27,180
Och det visar out-- och vi ska komma
tillbaka till just denna bild

935
00:41:27,180 --> 00:41:30,500
innan long-- detta är ett sätt att
du kanske göra din dators minne.

936
00:41:30,500 --> 00:41:31,460
Det är bara en rektangel.

937
00:41:31,460 --> 00:41:32,960
Du kan dra den något
antal sätt men det är

938
00:41:32,960 --> 00:41:35,740
bekvämt att rita det som en
rektangel av följande skäl.

939
00:41:35,740 --> 00:41:40,040
>> Vi kommer att börja idag och framöver
talar om den så kallade stack.

940
00:41:40,040 --> 00:41:43,870
Och stapeln är bara en bit
av RAM-- en bit av memory--

941
00:41:43,870 --> 00:41:47,100
som fungerar att ha tillgång
till när de kallas.

942
00:41:47,100 --> 00:41:49,800
Och så visar det sig att åtmin
allra längst ner på denna stack

943
00:41:49,800 --> 00:41:53,590
är där alla huvud lokala variabler
och org C och org V och allt det där

944
00:41:53,590 --> 00:41:56,950
kommer att gå som standard. Och om huvud
Parlamentet någon annan funktion som Swap,

945
00:41:56,950 --> 00:42:00,330
Tja, är Swap kommer att få en annan
skikt av minne upp ovanför.

946
00:42:00,330 --> 00:42:04,490
>> Och så bara för att ge dig en snabb ytlig
bild av detta, om jag går över här--

947
00:42:04,490 --> 00:42:09,450
och låt mig spegla detta på
overhead som well-- vad som verkligen har jag,

948
00:42:09,450 --> 00:42:12,100
om vi bryr oss bara om
nedre delen av denna bild för nu,

949
00:42:12,100 --> 00:42:15,070
är att när jag kör ett program
och Main anropas,

950
00:42:15,070 --> 00:42:18,330
Huvud ges en bit av
RAM i min dator som är

951
00:42:18,330 --> 00:42:20,060
längst ner i denna så kallade stack.

952
00:42:20,060 --> 00:42:22,143
Och jag kommer att dra det
avsiktligt som en fyrkant.

953
00:42:22,143 --> 00:42:24,540
Så det är som 32 bitar eller fyra byte.

954
00:42:24,540 --> 00:42:28,790
Och om detta huvudfunktion har ett
variabel som heter x till ett värde av 1

955
00:42:28,790 --> 00:42:32,626
och den har en variabel som heter
y med värdet 2, som är

956
00:42:32,626 --> 00:42:35,750
som att ta denna flisa av minne som
Huvud har givits av den operativa

957
00:42:35,750 --> 00:42:38,850
systemet och dela upp det så att
den första lokala variabeln går här,

958
00:42:38,850 --> 00:42:40,930
den andra går här, och det är det.

959
00:42:40,930 --> 00:42:45,590
>> När huvud kallar Swap, Pendla
får sin egen bit av minne

960
00:42:45,590 --> 00:42:48,280
att vi kommer att dra ut så här
från operativsystemet,

961
00:42:48,280 --> 00:42:50,820
och det kommer att få sin
egna lokala variabler baserade

962
00:42:50,820 --> 00:42:53,825
på vår implementering tidigare
med lokala variabler en

963
00:42:53,825 --> 00:42:58,010
och B som initialt
få värdena 1 och 2.

964
00:42:58,010 --> 00:43:00,450
Men sedan, så snart
Växla koden körs,

965
00:43:00,450 --> 00:43:03,760
och Lauren faktiskt swappar
EGT och mjölk, vad som händer?

966
00:43:03,760 --> 00:43:09,030
Nåväl, denna 2 blir 1, detta
1 blir en 2, och, förresten,

967
00:43:09,030 --> 00:43:13,360
Det finns en temp variabel som är att vara
använde den hela tiden som så småningom

968
00:43:13,360 --> 00:43:14,470
går iväg.

969
00:43:14,470 --> 00:43:16,720
Men det spelar ingen roll
hur mycket arbete du gör

970
00:43:16,720 --> 00:43:22,160
i denna linje of-- i denna minnesutrymme,
x och y är helt orörd.

971
00:43:22,160 --> 00:43:26,320
>> Så vi behöver något sätt att ge
Swap och funktioner som det

972
00:43:26,320 --> 00:43:32,640
hemlig tillgång, om ni så vill, till
funktioner like-- till minnet som x och y.

973
00:43:32,640 --> 00:43:35,110
Så låt oss ta en titt på
ett exempel som hjälper

974
00:43:35,110 --> 00:43:38,220
oss se exakt vad som varit
pågår hela tiden.

975
00:43:38,220 --> 00:43:40,284
Jag kommer att gå vidare
och öppna upp Jämför Zero.

976
00:43:40,284 --> 00:43:42,200
Och jag kommer att stänga
vår debugger, jag kommer

977
00:43:42,200 --> 00:43:44,360
att stänga denna skrämmande ser meddelandet
den bara säger, vänta en minut,

978
00:43:44,360 --> 00:43:45,800
du är i mitten felsökning.

979
00:43:45,800 --> 00:43:48,383
Jag kommer att dölja den här fliken här
bara för att gå tillbaka till enkelhet.

980
00:43:48,383 --> 00:43:50,160
Så oroa dig inte om GDB dödas.

981
00:43:50,160 --> 00:43:53,910
Det betyder bara att programmet har
blivit sluta, medvetet i det här fallet,

982
00:43:53,910 --> 00:43:54,820
av mig.

983
00:43:54,820 --> 00:43:57,700
>> Och nu Jämför Zero gör detta.

984
00:43:57,700 --> 00:44:00,110
Jag använder CS50
biblioteket i standard I / O.

985
00:44:00,110 --> 00:44:04,319
Jag har en huvuduppgift som först
säger, säga något, och får en sträng.

986
00:44:04,319 --> 00:44:06,110
Sedan säger det igen och
får en annan sträng.

987
00:44:06,110 --> 00:44:09,910
Och lägg märke till att dessa två strängar
kallas s och t, ​​respektive.

988
00:44:09,910 --> 00:44:12,910
Och nu detta program Jämför
Noll, dess syfte i livet,

989
00:44:12,910 --> 00:44:15,470
det är tänkt att berätta för mig,
jag skriver samma sak?

990
00:44:15,470 --> 00:44:16,910
Och så jag ska tillbaka till vecka ett.

991
00:44:16,910 --> 00:44:19,950
Jag använder min lika lika operatör
vilket är den kvalitetsoperatör.

992
00:44:19,950 --> 00:44:22,220
Inte uppdraget operatör,
likhetsoperatorn.

993
00:44:22,220 --> 00:44:23,890
Jag bara jämföra s och t.

994
00:44:23,890 --> 00:44:27,470
>> Så låt oss faktiskt gå vidare och göra det.

995
00:44:27,470 --> 00:44:32,680
Och jag kommer att gå vidare
och göra Jämför Zero.

996
00:44:32,680 --> 00:44:35,110
Jag kommer att göra ./comparezero.

997
00:44:35,110 --> 00:44:37,150
Och jag kommer att gå
framåt och säga något

998
00:44:37,150 --> 00:44:43,450
som, låt oss göra mamma i gemener
Och vad sägs om mamma i versaler.

999
00:44:43,450 --> 00:44:45,034
Och naturligtvis jag skriver olika saker.

1000
00:44:45,034 --> 00:44:45,533
Okej.

1001
00:44:45,533 --> 00:44:46,570
Det är att vänta.

1002
00:44:46,570 --> 00:44:47,640
>> Låt oss köra den igen.

1003
00:44:47,640 --> 00:44:49,740
Båda gångerna gör gemener, versaler.

1004
00:44:49,740 --> 00:44:51,490
Det ser super identisk med mig.

1005
00:44:51,490 --> 00:44:52,930
Enter.

1006
00:44:52,930 --> 00:44:53,430
OK.

1007
00:44:53,430 --> 00:44:55,804
Kanske är det bara konstigt eftersom
det är inte gilla min grammatik.

1008
00:44:55,804 --> 00:44:59,930
Så låt oss göra en kapital MOM,
huvudstad MOM, identiska.

1009
00:44:59,930 --> 00:45:01,490
Olika saker.

1010
00:45:01,490 --> 00:45:03,907
>> Så varför är det?

1011
00:45:03,907 --> 00:45:06,240
Tja, vad som faktiskt händer
på under huven här?

1012
00:45:06,240 --> 00:45:08,180
Så låt oss gå tillbaka över
här bara ett ögonblick

1013
00:45:08,180 --> 00:45:10,910
och fundera över vad getString
är faktiskt gör.

1014
00:45:10,910 --> 00:45:13,385
När du ringer getString,
det är en funktion som vi

1015
00:45:13,385 --> 00:45:16,510
själva skrev och det på något sätt blir en
sekvens av tecken från användaren.

1016
00:45:16,510 --> 00:45:20,280
Och låt oss anta att den första
gång jag ringer getString, som ger mig

1017
00:45:20,280 --> 00:45:21,930
en bit av minne som ser ut så här.

1018
00:45:21,930 --> 00:45:26,990
Och om jag skrev i gemener
m-o-m-- och vad som händer efter det?

1019
00:45:26,990 --> 00:45:28,840
Bara en snabb sanity check.

1020
00:45:28,840 --> 00:45:29,780
>> Omvänt snedstreck noll.

1021
00:45:29,780 --> 00:45:30,510
Vi vet att.

1022
00:45:30,510 --> 00:45:32,784
Och minns att vi spelade
runt med Zamila namn

1023
00:45:32,784 --> 00:45:34,950
och en massa andra namn
när Rob var här ute

1024
00:45:34,950 --> 00:45:36,280
på vad som händer inne i minnet.

1025
00:45:36,280 --> 00:45:37,780
Så att historien är exakt samma.

1026
00:45:37,780 --> 00:45:40,160
Detta är vad getString
återvänder till mig.

1027
00:45:40,160 --> 00:45:44,780
Nu, min kod för en stund sedan lagrats
returvärdet för getString

1028
00:45:44,780 --> 00:45:47,510
i en variabel som kallas s.

1029
00:45:47,510 --> 00:45:51,390
Och sedan den andra gången jag kallade det,
lagras den det i en variabel som heter t.

1030
00:45:51,390 --> 00:45:55,070
>> Så om jag går hit, jag behöver
att dra denna lokala variable--

1031
00:45:55,070 --> 00:45:59,610
och jag i allmänhet kommer att
rita en sträng som bara-- vi ska

1032
00:45:59,610 --> 00:46:02,360
kalla det s-- som ett litet torg här.

1033
00:46:02,360 --> 00:46:09,760
Och nu, somehow-- hur fungerar mamma
gå in i denna variabel s?

1034
00:46:09,760 --> 00:46:12,010
Tja, vi måste gå tillbaka
till första principer här.

1035
00:46:12,010 --> 00:46:15,660
Vad getString faktiskt återvänder?

1036
00:46:15,660 --> 00:46:19,030
>> Så visar det sig att M-O-M
bakstreck noll, och vilket som helst antal

1037
00:46:19,030 --> 00:46:22,364
andra strängar i minnet som
Zamila och Rob eller Andy eller några andra,

1038
00:46:22,364 --> 00:46:24,280
är naturligtvis i vår
datorns RAM eller minne.

1039
00:46:24,280 --> 00:46:27,760
Och RAM-minnet har like-- du har
en gig RAM, två gig RAM,

1040
00:46:27,760 --> 00:46:30,860
eller en miljard eller två miljard byte,
eller kanske ännu mer i dessa dagar.

1041
00:46:30,860 --> 00:46:34,070
Så låt oss anta, för dagens ändamål,
att det spelar ingen roll hur vi nummer

1042
00:46:34,070 --> 00:46:36,640
dem, men vi kan räkna varje
av dessa miljarder euro eller två miljarder

1043
00:46:36,640 --> 00:46:37,880
eller fyra miljarder byte.

1044
00:46:37,880 --> 00:46:42,240
>> Och låt oss bara godtyckligt säga att
Detta är den första tuggan, andra bite,

1045
00:46:42,240 --> 00:46:43,380
tredje, fjärde.

1046
00:46:43,380 --> 00:46:46,570
Jag medvetet inte använder noll för
idag men vi ska återkomma till det.

1047
00:46:46,570 --> 00:46:49,570
Så med andra ord, om detta är
första gången jag använder programmet,

1048
00:46:49,570 --> 00:46:52,715
Jag är bara att få tur och den första
bett är på plats en sedan två

1049
00:46:52,715 --> 00:46:53,590
sedan tre än fyra.

1050
00:46:53,590 --> 00:46:57,430
Och om jag höll teckning, boxnumret
två miljarder skulle vara vägen hit.

1051
00:46:57,430 --> 00:47:02,200
>> Så vad tror du, då,
GetString faktiskt återvänder?

1052
00:47:02,200 --> 00:47:06,010
Det är inte återvänder M-O-M bakstreck
noll i sig eftersom det tydligt

1053
00:47:06,010 --> 00:47:08,180
får inte plats i lådan som jag har ritat.

1054
00:47:08,180 --> 00:47:11,210
Så vad mer kan getString faktiskt
åter alla dessa veckor?

1055
00:47:11,210 --> 00:47:14,410

1056
00:47:14,410 --> 00:47:16,820
Svaret är på
styrelsen här någonstans.

1057
00:47:16,820 --> 00:47:20,390
Du kan inte montera M-O-M backslash noll,
så vad kan vara meningsfullt i stället?

1058
00:47:20,390 --> 00:47:23,424
Om du var tvungen att vara super smart, sätta
på så kallade ingenjörs hatt,

1059
00:47:23,424 --> 00:47:24,340
vad skulle du tillbaka?

1060
00:47:24,340 --> 00:47:27,340
Vad är den minsta mängden information
du kunde återvända som skulle fortfarande

1061
00:47:27,340 --> 00:47:30,610
Låt dig hitta M-O-M i minnet?

1062
00:47:30,610 --> 00:47:31,270
Yeah?

1063
00:47:31,270 --> 00:47:31,950
>> PUBLIK: One.

1064
00:47:31,950 --> 00:47:32,200
>> David J. MALAN: One.

1065
00:47:32,200 --> 00:47:33,021
Och varför ett?

1066
00:47:33,021 --> 00:47:35,520
PUBLIK: Eftersom det skulle berätta
vart du ska gå [OHÖRBAR].

1067
00:47:35,520 --> 00:47:38,391

1068
00:47:38,391 --> 00:47:39,390
DAVID J. MALAN: Exakt.

1069
00:47:39,390 --> 00:47:44,300
Jag bara kommer att återvända adressen
av strängen som jag har fått.

1070
00:47:44,300 --> 00:47:46,570
Adressen i denna
fallet är platsen ett.

1071
00:47:46,570 --> 00:47:51,280
Så vad som verkligen lagras i s--
och varje strängvariabel därmed far--

1072
00:47:51,280 --> 00:47:53,430
har just varit
adressen för den sträng.

1073
00:47:53,430 --> 00:47:57,840
>> Under tiden, om jag ringer
GetString en andra gång och jag

1074
00:47:57,840 --> 00:48:03,300
Skriv in bokstavligen samma thing--
M-O-M med lowercase-- M-O-M

1075
00:48:03,300 --> 00:48:06,200
och en annan omvänt snedstreck noll,
och nu kanske min programmets

1076
00:48:06,200 --> 00:48:09,820
pågått under en längre tid så kanske detta
är 10, är ​​denna plats 11, det är 12,

1077
00:48:09,820 --> 00:48:10,700
detta är 13.

1078
00:48:10,700 --> 00:48:13,590
De datorer som använder någon annan
minne av någon anledning.

1079
00:48:13,590 --> 00:48:18,172
Vad som nu går i mitt andra
variabel i mitt program t?

1080
00:48:18,172 --> 00:48:19,390
10.

1081
00:48:19,390 --> 00:48:20,050
Exakt.

1082
00:48:20,050 --> 00:48:23,910
>> Och så när vi tittar på
Källkoden till denna program

1083
00:48:23,910 --> 00:48:26,550
där jag försöker bara
att jämföra de två värdena,

1084
00:48:26,550 --> 00:48:32,180
är s motsvarar lika med t, vad är
det självklara mänskliga svaret?

1085
00:48:32,180 --> 00:48:34,890
Bara nej eftersom en inte är lika 10.

1086
00:48:34,890 --> 00:48:36,861
Och så ligger häri en
möjlighet för oss verkligen

1087
00:48:36,861 --> 00:48:39,610
att bara gå tillbaka till, igen, först
principer och tänka på, ja,

1088
00:48:39,610 --> 00:48:41,110
vad som händer under huven?

1089
00:48:41,110 --> 00:48:43,240
Vi har pratat om
bits och bytes och minne,

1090
00:48:43,240 --> 00:48:46,820
men det är faktiskt bra att förstå
eftersom när du ringer getString,

1091
00:48:46,820 --> 00:48:50,280
även om vi tänker på det är
åter M-O-M eller sträng mamma

1092
00:48:50,280 --> 00:48:53,120
eller Andy eller Zamila eller
liknande, tekniskt

1093
00:48:53,120 --> 00:48:55,510
det är bara att returnera adressen
av denna bit av minne.

1094
00:48:55,510 --> 00:48:56,910
>> Men det är OK.

1095
00:48:56,910 --> 00:49:00,570
För hur vet jag
där strängen slutar?

1096
00:49:00,570 --> 00:49:03,840
Om jag bara gett början?

1097
00:49:03,840 --> 00:49:05,380
Tja, det omvända snedstrecket noll, eller hur?

1098
00:49:05,380 --> 00:49:08,800
Precis i linjär tid jag kan
skriva ut med tryck def M-O-M.

1099
00:49:08,800 --> 00:49:11,820
Och så fort jag ser bakstreck
noll, jag bryr mig inte där jag började,

1100
00:49:11,820 --> 00:49:14,950
Jag vet redan underförstått
där jag måste avsluta.

1101
00:49:14,950 --> 00:49:18,700
>> Och så idag markerar beginning-- och
Låt mig göra det dramatiskt eftersom vi

1102
00:49:18,700 --> 00:49:21,800
gick igenom en massa problem för
få dessa här utbildning wheels--

1103
00:49:21,800 --> 00:49:29,840
så idag stödhjul startar
att komma ut och vi avslöjar vid least--

1104
00:49:29,840 --> 00:49:31,373
>> [Applåder]

1105
00:49:31,373 --> 00:49:33,220

1106
00:49:33,220 --> 00:49:36,160
>> Det var väl värt resan
till Target i morse, ja?

1107
00:49:36,160 --> 00:49:39,600
Så now-- finns, visar det
out, inget sådant som en sträng.

1108
00:49:39,600 --> 00:49:41,140
String existerar inte.

1109
00:49:41,140 --> 00:49:43,760
Det är en synonym som vi har haft
insidan av CS50 biblioteket.

1110
00:49:43,760 --> 00:49:48,660
Hädanefter kommer vi att börja ringa
s och t inte strängar men char stjärnor.

1111
00:49:48,660 --> 00:49:51,180
Och char stjärnan vi ska
retas isär inom kort.

1112
00:49:51,180 --> 00:49:53,510
Men detta är att säga,
att även om vi fortsätter

1113
00:49:53,510 --> 00:49:56,180
använder getString för nu,
tekniskt jag borde

1114
00:49:56,180 --> 00:49:59,010
vara att säga röding stjärna och röding stjärna.

1115
00:49:59,010 --> 00:50:01,720
>> Och det visar sig vad det stjärn
kommer att beteckna är något

1116
00:50:01,720 --> 00:50:04,340
kallas en pekare eller en adress.

1117
00:50:04,340 --> 00:50:06,110
Och faktiskt, en teaser
för vad som väntar

1118
00:50:06,110 --> 00:50:09,760
är detta 20 sekunders klipp från vår
vän Nick Parlante vid Stanford

1119
00:50:09,760 --> 00:50:12,927
som ganska länge sedan, tillbringar
en löjligt lång tid,

1120
00:50:12,927 --> 00:50:15,010
så gott jag kan berätta i hans
kök eller sin källare,

1121
00:50:15,010 --> 00:50:17,140
gör claymation
införande till världen

1122
00:50:17,140 --> 00:50:20,010
en karaktär som heter
Binky som vi kommer

1123
00:50:20,010 --> 00:50:22,010
införas nästa gång till pekare.

1124
00:50:22,010 --> 00:50:24,588
Så här är en förhandsvisning av vad som komma skall.

1125
00:50:24,588 --> 00:50:26,370
>> [VIDEOAVSPELNING]

1126
00:50:26,370 --> 00:50:27,510
>> -Hey, Binky.

1127
00:50:27,510 --> 00:50:28,260
Vakna.

1128
00:50:28,260 --> 00:50:30,672
Det är dags för pekaren kul.

1129
00:50:30,672 --> 00:50:31,616
>> -Vad är det?

1130
00:50:31,616 --> 00:50:33,032
Lär dig mer om pekare?

1131
00:50:33,032 --> 00:50:34,450
Åh, karamell.

1132
00:50:34,450 --> 00:50:35,431
>> [END SPELA]

1133
00:50:35,431 --> 00:50:38,055
DAVID J. MALAN: Och på att observera,
Vi kommer att se dig på onsdag.

1134
00:50:38,055 --> 00:50:47,590

1135
00:50:47,590 --> 00:50:48,090
Okej.

1136
00:50:48,090 --> 00:50:48,740
Vem är dans?

1137
00:50:48,740 --> 00:50:49,240
Kom igen.

1138
00:50:49,240 --> 00:50:50,330
Vem är dans?

1139
00:50:50,330 --> 00:50:51,820
Du vill att jag ska få det igång?

1140
00:50:51,820 --> 00:50:53,770
Jag ska få det började.

1141
00:50:53,770 --> 00:50:54,270
Woooo!

1142
00:50:54,270 --> 00:51:04,070

1143
00:51:04,070 --> 00:51:07,580
>> LAUREN: Söt snygga Moses.