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

2
00:00:10,550 --> 00:00:14,050
>> DAVID J. MALAN: Dette er CS50 og
dette er starten på uge fire.

3
00:00:14,050 --> 00:00:18,630
Og dreng, er Volkswagen i
problemer alle på grund af software.

4
00:00:18,630 --> 00:00:20,264
Lad os tage et kig.

5
00:00:20,264 --> 00:00:20,930
[VIDEO PLAYBACK]

6
00:00:20,930 --> 00:00:25,560
-Cars, De smarteste tegn
i Fast and Furious film.

7
00:00:25,560 --> 00:00:29,100
Denne uge tyske bilproducent
Volkswagen befandt sig

8
00:00:29,100 --> 00:00:32,490
midt i en skandale af
potentielt kriminelle proportioner.

9
00:00:32,490 --> 00:00:36,060
>> -Volkswagen Er forfriskende for milliarder
i bøder, mulige kriminelle anklager

10
00:00:36,060 --> 00:00:38,560
for sine ledere, som
selskabet undskylder

11
00:00:38,560 --> 00:00:41,840
til rigning 11 millioner biler til
hjælpe det slog emissioner tests.

12
00:00:41,840 --> 00:00:44,950
>> -Certain Diesel modeller var
designet med sofistikeret software

13
00:00:44,950 --> 00:00:48,440
at anvendte oplysninger, herunder
placering af styring og køretøjet

14
00:00:48,440 --> 00:00:51,870
hastighed til at bestemme bilen var
under afprøvning emissioner.

15
00:00:51,870 --> 00:00:55,650
Under denne omstændighed, at motoren
ville reducere giftige emissioner.

16
00:00:55,650 --> 00:00:59,070
Men bilen blev rigget til bypass
at når det blev køres.

17
00:00:59,070 --> 00:01:03,320
Emissionerne steg 10 til 40
gange over acceptable EPA niveauer.

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

19
00:01:04,280 --> 00:01:05,220
>> DAVID J. MALAN: Så lad os
tage et kig på dette

20
00:01:05,220 --> 00:01:07,250
og se præcis, hvordan det
kan gennemføres

21
00:01:07,250 --> 00:01:09,680
og hvordan dette kan påvirke
så mange biler som denne.

22
00:01:09,680 --> 00:01:12,840
Så i min hånd her er pressen
udgivelse, der blev udstedt af EPA--

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

24
00:01:14,620 --> 00:01:18,032
er den reguleringsorgan USA,
håndterer miljøhensyn,

25
00:01:18,032 --> 00:01:19,740
og derefter den faktiske
juridiske meddelelse, der var

26
00:01:19,740 --> 00:01:22,420
send til Volkswagen blot et par dage siden.

27
00:01:22,420 --> 00:01:26,530
>> Så EPA skriver, og beskriver nu
offentligt, en sofistikeret software

28
00:01:26,530 --> 00:01:29,390
algoritme på visse
Volkswagen biler registrerer

29
00:01:29,390 --> 00:01:32,630
når bilen er under
test officielle emissioner

30
00:01:32,630 --> 00:01:36,505
og fik fuld emissioner
styrer kun på under testen.

31
00:01:36,505 --> 00:01:38,380
Effektiviteten af
disse køretøjer forurening

32
00:01:38,380 --> 00:01:43,260
kontrol emissioner enheder er i høj grad
reduceret i alle normal kørsel

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

34
00:01:44,320 --> 00:01:48,190
Dette resulterer i biler, der opfylder
standarder i laboratoriet eller afprøvning

35
00:01:48,190 --> 00:01:52,790
station, men under normal drift
udsender kvælstof oxides-- eller NOx--

36
00:01:52,790 --> 00:01:54,950
ved op til 40 gange den standard.

37
00:01:54,950 --> 00:01:58,220
Den software produceret af Volkswagen
er et citat citat slut, manipulationsanordning,

38
00:01:58,220 --> 00:02:00,650
som defineret af Clean
Air Act i USA.

39
00:02:00,650 --> 00:02:03,410
>> De går på at sige, at
EPA og andet agentur

40
00:02:03,410 --> 00:02:07,020
afdækket nederlaget enhed
softwaren efter selvstændig analyse

41
00:02:07,020 --> 00:02:09,660
af forskere ved West
Virginia University.

42
00:02:09,660 --> 00:02:14,160
NOx forurening bidrager til
nitrogendioxid, jordnær ozon,

43
00:02:14,160 --> 00:02:15,700
og fine partikler.

44
00:02:15,700 --> 00:02:18,090
Udsættelse for disse
forurenende stoffer er blevet forbundet

45
00:02:18,090 --> 00:02:20,870
med en bred vifte af
alvorlige sundhedsmæssige effekter,

46
00:02:20,870 --> 00:02:23,637
herunder øget astma
angreb og andre respiratoriske

47
00:02:23,637 --> 00:02:26,470
sygdomme, der kan være nok alvorlige
at sende folk til hospitalet.

48
00:02:26,470 --> 00:02:28,660
Udsættelse for ozon og
partikler har også

49
00:02:28,660 --> 00:02:31,960
blevet associeret med tidlig
dødsfald som følge af respiratoriske relaterede

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

51
00:02:35,690 --> 00:02:38,940
Børn, ældre, personer med
allerede eksisterende luftvejssygdom

52
00:02:38,940 --> 00:02:42,840
er særligt udsatte for
sundhedsmæssige virkninger af disse forurenende stoffer.

53
00:02:42,840 --> 00:02:45,056
>> Tilstrækkeligt det vil sige, det er ganske alvorligt.

54
00:02:45,056 --> 00:02:46,930
Og lad os gå videre til at læse
blot endnu uddrag

55
00:02:46,930 --> 00:02:49,370
og så vil vi tage et kig på
de underliggende konsekvenser

56
00:02:49,370 --> 00:02:50,920
af denne i forbindelse med en bil.

57
00:02:50,920 --> 00:02:53,730
Specifikt Volkswagen
fremstillet og installeret

58
00:02:53,730 --> 00:02:56,210
software i det såkaldte
elektronisk styring

59
00:02:56,210 --> 00:02:59,320
module-- eller ECM-- af
disse køretøjer, der fornemmede

60
00:02:59,320 --> 00:03:03,580
når køretøjet blev testet for
overholdelse af EPA emissionsnormer.

61
00:03:03,580 --> 00:03:07,510
Baseret på forskellige input, herunder
stilling af rattet, køretøj

62
00:03:07,510 --> 00:03:11,280
hastighed, varighed af motorens
drift og barometertryk,

63
00:03:11,280 --> 00:03:13,720
disse indgange præcist
spores parametrene

64
00:03:13,720 --> 00:03:17,600
af den føderale testprocedure, der anvendes til
emission test for EPA certificering

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

66
00:03:18,400 --> 00:03:21,850
>> Under Miljøstyrelsens emission test,
den køretøjer ECM-software

67
00:03:21,850 --> 00:03:25,060
løb software, som er fremstillet
emissioner overensstemmende resultater.

68
00:03:25,060 --> 00:03:28,340
På alle andre tidspunkter, den
køretøj ECM-software

69
00:03:28,340 --> 00:03:31,090
løb en separat vej
kalibrering som reducerede

70
00:03:31,090 --> 00:03:34,360
effektiviteten af
samlede emission styresystem,

71
00:03:34,360 --> 00:03:37,864
specifikt selektiv katalytisk
reduktion af Lean NOx trap--

72
00:03:37,864 --> 00:03:39,280
som vi vil se om et øjeblik.

73
00:03:39,280 --> 00:03:43,040
Som et resultat, emissioner af NOx
øges med en faktor på 10 til 40 gange

74
00:03:43,040 --> 00:03:47,450
over de økonomiske partnerskabsaftaler kompatible niveauer
afhængigt af typen af ​​drevet cyklus.

75
00:03:47,450 --> 00:03:50,800
>> Så hvad det egentlig betyder, og
kildekoden til softwaren kører

76
00:03:50,800 --> 00:03:53,190
på Volkswagens har ikke
endnu ikke blevet offentliggjort,

77
00:03:53,190 --> 00:03:56,460
er, at en effektiv, dette
tilsvarende er et sted der inde

78
00:03:56,460 --> 00:03:57,830
af Volkswagens kode.

79
00:03:57,830 --> 00:04:02,200
Hvis du er ved at blive testet, og hvis bilen
registrerer visse miljømæssige faktorer

80
00:04:02,200 --> 00:04:04,330
ligesom rattet
position eller bevægelse

81
00:04:04,330 --> 00:04:06,710
eller mangel på samme af bilen eller
en række andre faktorer

82
00:04:06,710 --> 00:04:09,940
der i øjeblikket hypotese
at være en del af denne formel,

83
00:04:09,940 --> 00:04:12,370
de simpelthen tænder
fuld emissioner kontrol.

84
00:04:12,370 --> 00:04:15,670
Med andre ord, de begynder
udsender mindre af de forurenende stoffer.

85
00:04:15,670 --> 00:04:18,769
>> Else, i enhver anden situation,
når det ikke er påvist som værende

86
00:04:18,769 --> 00:04:20,790
i laboratoriet, de gør bare ikke.

87
00:04:20,790 --> 00:04:24,320
Og så du kan forenkle denne til mere
beton pseudokode med noget

88
00:04:24,320 --> 00:04:24,820
sådan her.

89
00:04:24,820 --> 00:04:27,810
Hvis hjulene vender men
rattet er ikke, suggestivt

90
00:04:27,810 --> 00:04:30,060
at bilen er på nogle
slags roterende cylinder

91
00:04:30,060 --> 00:04:32,550
men i en slags
lageret, der testes,

92
00:04:32,550 --> 00:04:36,070
derefter opføre sig som den
EPA vil gerne have dig til.

93
00:04:36,070 --> 00:04:37,960
Ellers ikke.

94
00:04:37,960 --> 00:04:40,420
Så lad os tage et kig
på en kort video, der

95
00:04:40,420 --> 00:04:45,391
tager et kig på, hvad konsekvenserne
er af denne faktisk mekanisk.

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

97
00:04:48,620 --> 00:04:52,800
>> -Sidste Fredag ​​EPA meddelt, at nogle
Volkswagen Audi biler lavet mellem 2009

98
00:04:52,800 --> 00:04:55,840
og i år brugte
en såkaldt manipulationsanordning

99
00:04:55,840 --> 00:04:59,060
at komme rundt emissioner love
designet til at holde luften ren.

100
00:04:59,060 --> 00:05:01,700
Men hvad betyder det præcist?

101
00:05:01,700 --> 00:05:04,666
>> Nå, moderne biler har snesevis
computere inde i dem.

102
00:05:04,666 --> 00:05:07,040
Og nogle af disse computere
hjælpe med at koordinere funktionerne

103
00:05:07,040 --> 00:05:09,590
af motoren til optimal
ydeevne samtidig med at sikre

104
00:05:09,590 --> 00:05:12,340
at der ikke er for meget skrald
kommer ud af udstødningsrøret.

105
00:05:12,340 --> 00:05:15,170
De har faktisk arbejdet
på denne måde i flere årtier nu.

106
00:05:15,170 --> 00:05:17,380
Dybest set, hver en del
af en moderne bils motor

107
00:05:17,380 --> 00:05:20,080
har en sensor eller controller
på det, og disse computere

108
00:05:20,080 --> 00:05:23,460
læser i data tusindvis af
gange i sekundet justeringer gør

109
00:05:23,460 --> 00:05:26,220
ligesom forholdet mellem brændstof og den luft
der kommer ind i cylindrene.

110
00:05:26,220 --> 00:05:28,730
>> Disse snyd Volkswagen
og Audi modeller er dieselmotorer,

111
00:05:28,730 --> 00:05:30,890
og dieselmotorer har en mere
virkelig vigtigt computer

112
00:05:30,890 --> 00:05:34,030
styrede parametre, som er
mængden af ​​uforbrændt brændstof kommer

113
00:05:34,030 --> 00:05:35,200
i udstødningen.

114
00:05:35,200 --> 00:05:36,310
Nu, lyder slemt.

115
00:05:36,310 --> 00:05:39,642
Lyder ikke som du ønsker
uforbrændt brændstof kommer ind i udstødningen.

116
00:05:39,642 --> 00:05:41,600
Men i tilfælde af en
diesel, du har noget

117
00:05:41,600 --> 00:05:46,110
kaldes en NOx-fælde, som er en enhed,
absorberer og fælder for nitrogenoxider

118
00:05:46,110 --> 00:05:48,880
der er forurenende stoffer, der ville
ellers gå i atmosfæren.

119
00:05:48,880 --> 00:05:53,040
Og effekten af ​​denne NOx fælde
er forbedret med uforbrændt brændstof.

120
00:05:53,040 --> 00:05:56,650
Så en manipulationsanordning er et særligt program
inde i disse computere, der kan gøre det

121
00:05:56,650 --> 00:05:59,527
ligne bilen opfylder emission
standarder, selv når det ikke gør.

122
00:05:59,527 --> 00:06:01,110
Volkswagen havde et problem på sine hænder.

123
00:06:01,110 --> 00:06:04,050
Dens dieselmotorer var kendt
for at få store brændstoføkonomi,

124
00:06:04,050 --> 00:06:07,510
men NOx fælden fungerer kun godt
når der anvendes mere brændstof.

125
00:06:07,510 --> 00:06:10,460
Så bilen ville afsløre,
ved hjælp af denne manipulationsanordning,

126
00:06:10,460 --> 00:06:13,870
da det fik en emission
test, ville den bruge mere brændstof,

127
00:06:13,870 --> 00:06:16,830
gøre NOx fælden arbejde godt,
emissioner ville være fint.

128
00:06:16,830 --> 00:06:21,130
Men så får du på vejen, enheden
slukker, du brænder mindre brændstof

129
00:06:21,130 --> 00:06:24,256
men du lægger så meget som 40 gange
flere forurenende stoffer i atmosfæren.

130
00:06:24,256 --> 00:06:26,130
Men hvordan dælen gjorde
bilen ved, at det var

131
00:06:26,130 --> 00:06:27,720
bliver testet for overholdelse emissioner?

132
00:06:27,720 --> 00:06:30,590
EPA siger, at det var en sofistikeret
system, der kontrolleres ting

133
00:06:30,590 --> 00:06:34,090
ligesom rattet,
hastighed, hvor længe motoren var på,

134
00:06:34,090 --> 00:06:35,507
og selv det atmosfæriske tryk.

135
00:06:35,507 --> 00:06:37,673
Med andre ord var der
ingen måde var dette et uheld

136
00:06:37,673 --> 00:06:40,260
fordi softwaren var
designet meget omhyggeligt for at opdage

137
00:06:40,260 --> 00:06:41,630
en officiel test emissioner.

138
00:06:41,630 --> 00:06:43,588
Det er nogle ret alvorlige
bedrag, og det er

139
00:06:43,588 --> 00:06:45,420
hvorfor Volkswagen er i
sådan alvorlige problemer.

140
00:06:45,420 --> 00:06:48,600
Faktisk deres CEO, Martin
Winterkorn, bare trådte tilbage.

141
00:06:48,600 --> 00:06:49,820
>> Så hvad sker der nu?

142
00:06:49,820 --> 00:06:53,900
Tja, hvis du er en af ​​den halve million
diesel jettas, Beatles, Golfs, Passat,

143
00:06:53,900 --> 00:06:56,220
eller Audi A3S gennemført,
den gode nyhed er, er

144
00:06:56,220 --> 00:06:57,886
at din bil er stadig sikkert at køre.

145
00:06:57,886 --> 00:07:00,510
Du behøver ikke at sætte det væk
indtil Volkswagen udsteder en tilbagekaldelse.

146
00:07:00,510 --> 00:07:02,509
Men på et tidspunkt, de er
sandsynligvis vil have

147
00:07:02,509 --> 00:07:04,230
at opdatere softwaren i din bil.

148
00:07:04,230 --> 00:07:06,927
Når det sker du måske
få færre miles pr tank.

149
00:07:06,927 --> 00:07:09,260
Advokater er allerede geare
op til kollektive søgsmål

150
00:07:09,260 --> 00:07:12,500
så ejere kan få kompenseret
på et tidspunkt i fremtiden.

151
00:07:12,500 --> 00:07:15,832
Men det kommer ikke til at
ske enhver tid snart.

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

153
00:07:16,711 --> 00:07:19,960
DAVID J. MALAN: Så det faktisk rejser
et interessant større billede spørgsmål

154
00:07:19,960 --> 00:07:20,660
som at stole på.

155
00:07:20,660 --> 00:07:21,160
Højre?

156
00:07:21,160 --> 00:07:24,300
Vi har alle iPhones eller Androids eller
noget i vores lommer sandsynligvis

157
00:07:24,300 --> 00:07:26,500
disse dage, eller bærbare computere
på vores omgange, der er

158
00:07:26,500 --> 00:07:28,510
kører software lavet
af Apple og Microsoft

159
00:07:28,510 --> 00:07:30,710
og bundter af andre selskaber.

160
00:07:30,710 --> 00:07:34,240
Men hvordan kan vi vide, at hvad
disse software produkter gør

161
00:07:34,240 --> 00:07:37,680
er faktisk, hvad disse
virksomheder siger, at de gør?

162
00:07:37,680 --> 00:07:39,610
>> For eksempel, der er til
sige, at hver gang du

163
00:07:39,610 --> 00:07:42,200
foretage et telefonopkald på din iPhone
eller Android-telefon eller lignende,

164
00:07:42,200 --> 00:07:45,650
at dette telefonnummer er heller ikke
bliver uploadet til nogle virksomhedens server

165
00:07:45,650 --> 00:07:48,399
på grund af nogle program, du har
skrevet, uanset om det er operativsystemet

166
00:07:48,399 --> 00:07:51,070
selve systemet ligesom iOS eller Android,
eller fordi du har downloadet

167
00:07:51,070 --> 00:07:53,880
nogle tredjeparts app
at en eller anden måde er at lytte

168
00:07:53,880 --> 00:07:57,120
til alt, hvad du skriver i eller
alt, hvad du rent faktisk siger.

169
00:07:57,120 --> 00:07:59,500
Hvordan ved du, at når
du fyre kører Dunk

170
00:07:59,500 --> 00:08:02,590
Eller Kom med til at oversætte din
egen software i CS50, hvordan

171
00:08:02,590 --> 00:08:06,080
gør dig, at CS50 eget personale,
i form af CS50 bibliotek,

172
00:08:06,080 --> 00:08:08,690
har ikke været logge alle
streng, du nogensinde har fået

173
00:08:08,690 --> 00:08:10,276
eller hver tomme, du nogensinde har fået?

174
00:08:10,276 --> 00:08:12,900
Nå, kunne du sikkert se
på kildekoden til noget

175
00:08:12,900 --> 00:08:15,233
ligesom CS50 bibliotek, du
kunne se på kildekoden

176
00:08:15,233 --> 00:08:18,170
til Linux-operativsystem
kører på CS50 IDE.

177
00:08:18,170 --> 00:08:23,090
Men en fantastisk præsentation
blev givet tilbage i 1984

178
00:08:23,090 --> 00:08:26,730
i modtagelse af Turing Award af en
meget berømt datalog kendt

179
00:08:26,730 --> 00:08:29,750
as-- navngivet Ken Thompson, der
modtaget Turing Award, som

180
00:08:29,750 --> 00:08:33,500
er en slags datalogi s
Nobelprisen, hvis du vil,

181
00:08:33,500 --> 00:08:35,309
for hans arbejde med en
operativsystem kaldet

182
00:08:35,309 --> 00:08:39,039
Unix, som er meget ens i
ånd til hvad vi bruger som er Linux.

183
00:08:39,039 --> 00:08:41,960
Og det spørgsmål, han stillede i sin
takketale, hovedsagelig

184
00:08:41,960 --> 00:08:44,910
om rammerne for
år og års drøftelser

185
00:08:44,910 --> 00:08:46,970
om tillid og sikkerhed, var dette.

186
00:08:46,970 --> 00:08:50,410
I hvilket omfang bør man tillid et
erklæring om, at en program-- et stykke

187
00:08:50,410 --> 00:08:53,010
af software-- er fri for trojanske heste?

188
00:08:53,010 --> 00:08:56,500
Måske er det mere vigtigt at have tillid
de mennesker, der skrev softwaren.

189
00:08:56,500 --> 00:08:58,650
>> Og i virkeligheden, har vi knyttet
til snak om, at han

190
00:08:58,650 --> 00:09:02,400
gav ved tiltrædelsen af ​​denne pris
i 80'erne på CS50 hjemmeside

191
00:09:02,400 --> 00:09:04,030
under Forelæsninger siden for i dag.

192
00:09:04,030 --> 00:09:06,071
Fordi det, du vil se
er, at han faktisk giver

193
00:09:06,071 --> 00:09:09,430
en forholdsvis simpelt eksempel på, hvordan selv
en compiler som Dunk eller hvad

194
00:09:09,430 --> 00:09:13,950
compilere andre har brugt i fortiden,
hvad nu hvis indlejret i compiler vi

195
00:09:13,950 --> 00:09:18,190
selv bruger, er lidt, hvis
forudsat at hovedsagelig siger,

196
00:09:18,190 --> 00:09:22,360
hvis du bemærker, at denne kode er at bruge
den getString funktionen eller GetInt

197
00:09:22,360 --> 00:09:26,600
funktion, gå videre og indsætte
en bagdør eller en trojansk hest

198
00:09:26,600 --> 00:09:29,340
således at dette program
nu har nogle nuller

199
00:09:29,340 --> 00:09:30,930
og dem, der gør noget ondsindet.

200
00:09:30,930 --> 00:09:33,080
Logning alle dine
tastetryk, uploade, at data

201
00:09:33,080 --> 00:09:35,100
til nogle server, eller virkelig noget.

202
00:09:35,100 --> 00:09:37,290
>> Og hvad Ken Thompson
går på at gøre i sin tale

203
00:09:37,290 --> 00:09:40,580
er at vise, at selv om
du har adgang til kilden

204
00:09:40,580 --> 00:09:43,794
koden for en compiler, der
skadeligt kunne gøre dette,

205
00:09:43,794 --> 00:09:46,210
det gør ikke noget, fordi
der er denne hønen og ægget

206
00:09:46,210 --> 00:09:49,500
virkelighed af fortiden mange
år hvorved compilere

207
00:09:49,500 --> 00:09:51,960
bruges til at kompilere selv.

208
00:09:51,960 --> 00:09:55,440
Med andre ord vej tilbage, når en person
havde at have skrevet den første compiler.

209
00:09:55,440 --> 00:09:59,060
Og derefter, når som helst de har opdateret
en compiler ved at ændre dens kildekode,

210
00:09:59,060 --> 00:10:02,020
tilføje funktioner og omkompilering det
for folk som os at bruge, godt,

211
00:10:02,020 --> 00:10:04,270
de bruger den gamle
version af compileren

212
00:10:04,270 --> 00:10:06,370
at kompilere den nye
version af compileren.

213
00:10:06,370 --> 00:10:08,370
Og hvis du tager et kig
ved snak om, at han gav,

214
00:10:08,370 --> 00:10:10,970
vil du se, at fordi
af denne cirkularitet,

215
00:10:10,970 --> 00:10:14,330
du kan faktisk har fejl eller
Trojanske heste indlejret i software

216
00:10:14,330 --> 00:10:14,990
vi bruger.

217
00:10:14,990 --> 00:10:18,010
Og selv hvis man ser på den
kildekoden til disse programmer,

218
00:10:18,010 --> 00:10:21,550
det måske ikke engang være indlysende
fordi svindel er faktisk

219
00:10:21,550 --> 00:10:24,710
i nogle ældre version af en
compiler, lige siden har været

220
00:10:24,710 --> 00:10:27,340
injektion truslen i vores software.

221
00:10:27,340 --> 00:10:29,740
>> Hvilket er kun at sige, vi
virkelig kan ikke bør og ikke

222
00:10:29,740 --> 00:10:32,939
tillid software, der kører på vores bærbare pc'er
eller telefoner eller et vilkårligt antal steder.

223
00:10:32,939 --> 00:10:36,230
Og i virkeligheden, senere i dette semester, når
vi begynder at tale om webprogrammering

224
00:10:36,230 --> 00:10:38,521
og faktisk begynde at bygge
webapplikationer os selv,

225
00:10:38,521 --> 00:10:40,285
Vi vil tale om disse
trusler og andre.

226
00:10:40,285 --> 00:10:43,410
Nu har du måske undret og bemærket
at der var en lille smule Darth

227
00:10:43,410 --> 00:10:45,842
Vader i de klip,
Den Verge var viser der

228
00:10:45,842 --> 00:10:47,550
om Volkswagen. Hvis
du aldrig har set, jeg

229
00:10:47,550 --> 00:10:49,190
troede, vi skulle lette
stemningen, fordi det er alt

230
00:10:49,190 --> 00:10:50,780
meget deprimerende og skræmmende.

231
00:10:50,780 --> 00:10:52,910
Jeg har tænkt mig at se tilbage
Super Bowl 2011

232
00:10:52,910 --> 00:10:55,300
når en kommerciel ved
Volkswagen-- og dette

233
00:10:55,300 --> 00:10:59,620
næsten gør dem vellidte igen--
luftet for første gang på TV.

234
00:10:59,620 --> 00:11:04,039
Det er de 60 andet klip
at jeg tror, ​​du vil nyde.

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

236
00:11:04,705 --> 00:11:08,198
[MUSIC - temaet fra "Star Wars"]

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

238
00:11:35,643 --> 00:11:38,138
[Hund gør]

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

240
00:11:50,114 --> 00:11:53,607
[Bilen begynder]

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

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

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

244
00:12:06,830 --> 00:12:07,663
Jeg var bare kontrol.

245
00:12:07,663 --> 00:12:11,360
At bilen er på listen over overtrædelser.

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

247
00:12:12,000 --> 00:12:14,040
Så vi ser på nogle
pseudokode for et øjeblik siden.

248
00:12:14,040 --> 00:12:15,380
Og her er en større
uddrag af pseudokode kode

249
00:12:15,380 --> 00:12:16,921
at vi har set et par gange hidtil.

250
00:12:16,921 --> 00:12:19,970
Og lad os bruge denne er en mulighed
nu at indføre en ny programmering

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

252
00:12:23,776 --> 00:12:25,400
sidste uge, da vi kiggede på mergesort.

253
00:12:25,400 --> 00:12:28,270
Men lad os formalisere det og se, hvordan
vi måske bruge det i konkrete kode,

254
00:12:28,270 --> 00:12:30,350
og så vil vi bruge denne
teknik ned ad vejen mest

255
00:12:30,350 --> 00:12:32,000
sandsynligvis løse en række andre problemer.

256
00:12:32,000 --> 00:12:35,790
>> Så det var et af de første programmer, vi
nogensinde skrev, omend i pseudokode kode.

257
00:12:35,790 --> 00:12:37,790
Og hvad dette program
tilladt os at gøre kurset

258
00:12:37,790 --> 00:12:41,510
var at finde Mike Smith i en telefonbog.

259
00:12:41,510 --> 00:12:46,216
Og bemærk især linjer otte
og 11, som havde denne Gå til erklæring.

260
00:12:46,216 --> 00:12:48,090
Og faktisk visse
sprog, C blandt dem,

261
00:12:48,090 --> 00:12:50,006
faktisk har en
erklæring om, at er bogstaveligt talt

262
00:12:50,006 --> 00:12:52,710
gå til, hvor du kan
springe til en bestemt linje.

263
00:12:52,710 --> 00:12:55,470
Det er generelt ildeset, fordi
Det kan meget nemt misbruges

264
00:12:55,470 --> 00:12:58,490
og du kan begynde at hoppe din
program over det hele i modsætning

265
00:12:58,490 --> 00:13:00,690
at bruge den slags
logik og reguleringsflowet

266
00:13:00,690 --> 00:13:04,000
at vi har brugt hidtil med blot
loops og betingelser og lignende.

267
00:13:04,000 --> 00:13:08,660
>> Men vi kan forenkle denne algoritme
i pseudokode kode som følger.

268
00:13:08,660 --> 00:13:11,250
I stedet for denne iterative
eller looping tilgang

269
00:13:11,250 --> 00:13:14,160
hvor vi holde gå tilbage og
tilbage og tilbage til linje tre,

270
00:13:14,160 --> 00:13:18,300
hvorfor vi ikke bare slags punt og mere
generelt siger på linje syv og 10,

271
00:13:18,300 --> 00:13:20,570
bare erstatte dem to
par linjer med,

272
00:13:20,570 --> 00:13:22,810
ellers hvis Smith er tidligere
i bogen vi får

273
00:13:22,810 --> 00:13:25,110
søge efter Mike i
venstre halvdel af bogen.

274
00:13:25,110 --> 00:13:28,560
Ellers hvis Smith er senere i
bog, søge efter Mike i den rigtige

275
00:13:28,560 --> 00:13:29,540
halvdelen af ​​bogen.

276
00:13:29,540 --> 00:13:31,180
Og mærke allerede cirkularitet.

277
00:13:31,180 --> 00:13:31,680
Højre?

278
00:13:31,680 --> 00:13:34,250
Jeg søger efter Mike i
telefonbogen og derefter

279
00:13:34,250 --> 00:13:37,090
Jeg til sidst ramte måske
line syv eller måske linie 10

280
00:13:37,090 --> 00:13:41,089
og min instruktion til mig selv er at søge
til Mike i halvdelen af ​​telefonbogen.

281
00:13:41,089 --> 00:13:42,380
Nå, hvordan søger jeg efter Mike?

282
00:13:42,380 --> 00:13:44,213
Jeg er midt i
søger efter Mike, hvorfor

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

284
00:13:45,860 --> 00:13:49,590
Men det er OK, fordi det, der er
sker med størrelsen af ​​problemet,

285
00:13:49,590 --> 00:13:52,630
som skrevet i linje 7 og 10?

286
00:13:52,630 --> 00:13:54,989
Vi er ikke bare at sige søgning
til Mike, søge efter Mike.

287
00:13:54,989 --> 00:13:56,280
Vi specifikt sige, hvad?

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

289
00:13:58,694 --> 00:14:01,610
Søg efter ham i den venstre halvdel af
den højre halvdel, som er effektivt

290
00:14:01,610 --> 00:14:03,440
halv størrelse af problemet.

291
00:14:03,440 --> 00:14:07,170
Så det er OK, at vi er sådan
engagere sig i denne cirkularitet,

292
00:14:07,170 --> 00:14:09,180
dette cirkulære argument,
fordi der i mindst vi er

293
00:14:09,180 --> 00:14:11,090
at gøre problemet mindre og mindre.

294
00:14:11,090 --> 00:14:14,220
Og til sidst vil vi nå
at den såkaldte base case, hvor

295
00:14:14,220 --> 00:14:16,780
Vi har kun én side left--
som vores frivillige i sidste uge

296
00:14:16,780 --> 00:14:18,684
did-- vi havde en side
til venstre og derefter gør vi ikke

297
00:14:18,684 --> 00:14:21,600
nødt til at holde søger efter Mike Smith
fordi han er enten på den pågældende side

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

299
00:14:23,080 --> 00:14:27,480
>> Så hvordan kan vi gennemføre denne idé, dette
slags cirkularitet i konkrete kode?

300
00:14:27,480 --> 00:14:31,030
Nå, kan vi udnytte en teknik
der er almindeligt kendt som rekursion.

301
00:14:31,030 --> 00:14:33,960
Og vi har set det i
pseudokode for mergesort sidste uge.

302
00:14:33,960 --> 00:14:37,190
Husk på, at dette var den
pseudokode til mergesort.

303
00:14:37,190 --> 00:14:40,560
Det er velsagtens endnu enklere end
boble eller valg eller indsættelse sortere

304
00:14:40,560 --> 00:14:43,310
kun med hensyn til enkelhed
som du kan udtrykke det.

305
00:14:43,310 --> 00:14:46,750
>> Men det er fordi
vi er slags cirkulært

306
00:14:46,750 --> 00:14:51,350
siger, søge efter noget
ved at søge efter det igen.

307
00:14:51,350 --> 00:14:53,960
Men vi søger enten på
den venstre halvdel eller den højre halvdel

308
00:14:53,960 --> 00:14:56,070
og så til sidst er vi
sammenlægning i dette tilfælde.

309
00:14:56,070 --> 00:14:58,520
Men også her med
disse to sortere linjer,

310
00:14:58,520 --> 00:15:01,320
vi igen har denne
tanken om rekursion.

311
00:15:01,320 --> 00:15:05,350
Og konkret, hvad det betyder,
i forbindelse med en algoritme,

312
00:15:05,350 --> 00:15:10,880
er, at en algoritme er rekursiv
hvis den bruger eller kalder sig.

313
00:15:10,880 --> 00:15:14,330
>> Eller i form af C, en funktion
recursive-- en funktion kaldet

314
00:15:14,330 --> 00:15:18,510
foo er rekursiv, hvis foo,
et eller andet sted i sin kildekode,

315
00:15:18,510 --> 00:15:21,250
kalder funktionen foo selv.

316
00:15:21,250 --> 00:15:25,790
Og det er slemt, hvis alle foo nogensinde gør
er kalde sig igen og igen.

317
00:15:25,790 --> 00:15:30,600
Det er OK, hvis foo sidst stopper, som gør
mergesort, ved at sige, vent et minut,

318
00:15:30,600 --> 00:15:32,980
Hvis problemet er super
lille, for eksempel,

319
00:15:32,980 --> 00:15:35,840
eller jeg fandt ham, hvem jeg er
leder efter, bare vende tilbage.

320
00:15:35,840 --> 00:15:41,000
Må ikke rekursivt, ikke
cyklisk kalde mig selv igen.

321
00:15:41,000 --> 00:15:44,200
>> Og så lad os tage et kig på
hvordan dette kan faktisk fungere.

322
00:15:44,200 --> 00:15:48,430
Så jeg har tænkt mig at gå videre og åbne
op to source kode eksempler her.

323
00:15:48,430 --> 00:15:50,321
Hvoraf den ene kaldes sigma 0.

324
00:15:50,321 --> 00:15:52,320
Og det er ikke på alle
rekursive, men lad os tage

325
00:15:52,320 --> 00:15:53,694
et kig på, hvad dette program gør.

326
00:15:53,694 --> 00:15:55,737
Jeg har strippet ud af alt
kommentarer fra det, men alle

327
00:15:55,737 --> 00:15:58,070
af kildekoden på CS50 s
hjemmeside har kommentarer, hvis du

328
00:15:58,070 --> 00:15:59,570
ønsker at læse den igen senere.

329
00:15:59,570 --> 00:16:02,010
Og lad os gøre et par
af tilregnelighed kontrollerer her.

330
00:16:02,010 --> 00:16:06,640
>> Så i toppen af ​​denne kode,
vi har inkludere CS50.h.

331
00:16:06,640 --> 00:16:07,650
Hvad betyder dette gøre?

332
00:16:07,650 --> 00:16:08,990
Hvorfor er det her?

333
00:16:08,990 --> 00:16:11,740
I rimelig lægmandssprog.

334
00:16:11,740 --> 00:16:12,424
Hvad gør den?

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

336
00:16:12,858 --> 00:16:14,160
>> PUBLIKUM: Så GetInt funktion virker.

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

338
00:16:16,243 --> 00:16:18,115
Fordi indersiden af ​​denne
fil, CS50.h, som

339
00:16:18,115 --> 00:16:20,950
vi vil se inden længe i
form af sin kildekode,

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

341
00:16:23,270 --> 00:16:26,950
og en flok others-- og medmindre
vi faktisk har at Medtag linje,

342
00:16:26,950 --> 00:16:29,320
compileren Dunk ikke
kommer til at vide, at det eksisterer.

343
00:16:29,320 --> 00:16:32,400
Og samme gælder for linje
to hvor int defineres

344
00:16:32,400 --> 00:16:35,101
printf, som er en funktion
vi fortsætte med at bruge ganske lidt.

345
00:16:35,101 --> 00:16:37,850
Nu linje fire virker lidt funky
fordi det er bare en one liner.

346
00:16:37,850 --> 00:16:41,570
Det har fået et semikolon, ingen krøllede
seler, ingen kode inde i den.

347
00:16:41,570 --> 00:16:44,640
Men hvad gjorde vi kalder
denne ting i uger tidligere?

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

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

350
00:16:46,060 --> 00:16:48,390
Og hvorfor har vi en
prototype som synes

351
00:16:48,390 --> 00:16:51,050
at være lidt overflødigt
typisk fordi vi normalt

352
00:16:51,050 --> 00:16:53,474
se funktionen igen
senere i filen, ikke?

353
00:16:53,474 --> 00:16:56,390
Så hvorfor skal vi have-- du bare
skrabe dit hoved, men jeg tager det.

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

355
00:16:57,302 --> 00:17:00,000
>> PUBLIKUM: [uhørligt]
funktion efter den vigtigste.

356
00:17:00,000 --> 00:17:01,000
DAVID J. MALAN: Præcis.

357
00:17:01,000 --> 00:17:04,089
Således at compileren kender dig
i sidste ende vil definere eller gennemføre

358
00:17:04,089 --> 00:17:06,579
denne funktion efter vigtigste, formentlig.

359
00:17:06,579 --> 00:17:08,462
Så Dunk og mest
compilere er lidt dum

360
00:17:08,462 --> 00:17:10,510
og de vil kun kender
hvad du fortæller dem.

361
00:17:10,510 --> 00:17:12,569
Og hvis du ønsker at bruge
en funktion kaldet sigma,

362
00:17:12,569 --> 00:17:15,710
du bedre lære compileren
at det eksisterer i forvejen.

363
00:17:15,710 --> 00:17:17,970
>> Nu main sig selv, selv
selvom det er en flok af linjer,

364
00:17:17,970 --> 00:17:19,839
er temmelig velkendt forhåbentlig ved nu.

365
00:17:19,839 --> 00:17:21,942
Det har fået en gør while-løkke
hvis formål i livet

366
00:17:21,942 --> 00:17:24,400
her åbenbart er at få en
positivt heltal fra brugeren.

367
00:17:24,400 --> 00:17:27,349
Og bare holde plage ham
eller hende, indtil de samarbejder.

368
00:17:27,349 --> 00:17:30,670
Så på linje 16 Jeg har
en interessant opkald.

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

370
00:17:31,570 --> 00:17:33,710
Hvilket på venstre
side giver mig en Int

371
00:17:33,710 --> 00:17:36,650
som kan store-- kaldes Answer--
der skal opbevares, tilsyneladende,

372
00:17:36,650 --> 00:17:39,090
returværdien af ​​sigma.

373
00:17:39,090 --> 00:17:41,840
Så sigma er blot en
vilkårlig men meningsfyldt navn

374
00:17:41,840 --> 00:17:44,500
at jeg har givet til en funktion
hvis formål i livet

375
00:17:44,500 --> 00:17:47,680
er at tage en argument--
vi vil kalde det N i denne case--

376
00:17:47,680 --> 00:17:52,280
og bare for at tage summen af ​​dette nummer
plus ethvert positivt tal, der er

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

378
00:17:53,200 --> 00:17:58,140
>> Så hvis jeg passere i nummer 2 til
sigma, jeg ønsker at tilføje 2 plus 1

379
00:17:58,140 --> 00:18:00,240
plus 0-- ikke 0-- så mig 3 giver.

380
00:18:00,240 --> 00:18:05,320
Hvis jeg går i 3 til sigma, jeg ønsker at
har 3 plus 2 plus 1, som giver mig 6.

381
00:18:05,320 --> 00:18:05,900
Og så videre.

382
00:18:05,900 --> 00:18:09,750
Så det bare tilføjer op alle
tal mindre end eller lig med det.

383
00:18:09,750 --> 00:18:12,040
>> Nu herned jeg bare
at udskrive svaret.

384
00:18:12,040 --> 00:18:17,330
Så som en hurtig tilregnelighed check, lad os
gøre sigma 0-- dot skråstreg sigma 0--

385
00:18:17,330 --> 00:18:18,690
og lad mig skrive i 2.

386
00:18:18,690 --> 00:18:19,960
Og jeg faktisk får 3.

387
00:18:19,960 --> 00:18:21,240
Lad mig skrive i 3.

388
00:18:21,240 --> 00:18:22,860
I faktisk får 6.

389
00:18:22,860 --> 00:18:27,636
Og hvis nogen kan gøre det math hurtigt,
hvis jeg gør 50 hvad skal jeg få?

390
00:18:27,636 --> 00:18:29,839
>> PUBLIKUM: [uhørligt].

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

392
00:18:30,880 --> 00:18:33,340
Men 1.275 som er temmelig tæt på.

393
00:18:33,340 --> 00:18:38,850
Så dette er et resultat af at gøre 50
plus 49 plus 48 plus 47 plus 46

394
00:18:38,850 --> 00:18:40,349
hele vejen ned til 1.

395
00:18:40,349 --> 00:18:41,390
Så det er alt sigma gør.

396
00:18:41,390 --> 00:18:43,350
Men lad os se, hvordan vi har
gennemført det nu.

397
00:18:43,350 --> 00:18:45,790
Så hernede er funktionen selv.

398
00:18:45,790 --> 00:18:49,000
Og det ser ikke ud til at have
noget at gøre med rekursion endnu.

399
00:18:49,000 --> 00:18:51,070
Faktisk er vi ved hjælp af en
gamle skole teknik.

400
00:18:51,070 --> 00:18:56,680
Jeg initialisering en variabel kaldet sum
til nul, så har jeg en foreloop her,

401
00:18:56,680 --> 00:19:00,790
og jeg erklærer en Int kaldet
Jeg, sætte den lig med 1--

402
00:19:00,790 --> 00:19:04,080
selvom jeg kunne sætte det lig med
nul, men da jeg gør kommer,

403
00:19:04,080 --> 00:19:05,340
Hvem bekymrer sig om det er nul eller én.

404
00:19:05,340 --> 00:19:06,660
Det kommer til at have nogen effekt.

405
00:19:06,660 --> 00:19:10,110
>> Så jeg iteration, så længe jeg er
mindre end eller lig med m, hvilket

406
00:19:10,110 --> 00:19:11,671
er det argument, der blev vedtaget i.

407
00:19:11,671 --> 00:19:13,670
Og så er jeg bare holde
forøgelse I. og indsigt

408
00:19:13,670 --> 00:19:20,010
af løkken alt jeg gør gør sum
plus lig I. Og det er bevidst.

409
00:19:20,010 --> 00:19:22,326
Jeg ønsker ikke at gøre, i denne
tilfælde som summen plus plus.

410
00:19:22,326 --> 00:19:24,790
Jeg ønsker at faktisk tilføje
den aktuelle værdi af I

411
00:19:24,790 --> 00:19:28,190
der holder bliver større og større
og større til driften tally.

412
00:19:28,190 --> 00:19:30,210
>> Og så er jeg tilbage sum.

413
00:19:30,210 --> 00:19:33,850
Og så svar får værdien sum.

414
00:19:33,850 --> 00:19:35,282
Og så er jeg printe det ud.

415
00:19:35,282 --> 00:19:37,740
Så der er en mulighed her,
dog slags at forenkle

416
00:19:37,740 --> 00:19:41,260
denne kode begrebsmæssigt
og den slags pudse sin

417
00:19:41,260 --> 00:19:43,250
huske i form af
enkelhed selvom det

418
00:19:43,250 --> 00:19:45,700
tager et stykke tid at sortere
af forstå, hvorfor denne

419
00:19:45,700 --> 00:19:47,330
er stærk i disse små eksempler.

420
00:19:47,330 --> 00:19:50,380
Her er sigma en-- så
anden version af denne kode.

421
00:19:50,380 --> 00:19:55,290
Alt op øverst er identisk, så
at samme historie gælder som før.

422
00:19:55,290 --> 00:19:59,220
Men lad os nu se på den
gennemførelse af sigma som

423
00:19:59,220 --> 00:20:05,040
Jeg har skåret ned til bare disse
lines-- fire linjer kode, virkelig,

424
00:20:05,040 --> 00:20:06,980
plus nogle krøllede parenteser og hvide rum.

425
00:20:06,980 --> 00:20:07,930
>> Men hvad gør jeg?

426
00:20:07,930 --> 00:20:11,050
Hvis m er mindre end eller lig med
nul, jeg har brug for at slags håndtere

427
00:20:11,050 --> 00:20:12,490
at super enkel sag.

428
00:20:12,490 --> 00:20:15,450
Og hvis du afleverer mig nul eller noget
negativ som er lige underligt,

429
00:20:15,450 --> 00:20:17,909
Jeg vil blot vilkårligt
men konsekvent vende tilbage til nul.

430
00:20:17,909 --> 00:20:20,200
Jeg ønsker ikke denne ting til
komme ind i nogle underlige uendelige

431
00:20:20,200 --> 00:20:21,810
loop på grund af en negativ værdi.

432
00:20:21,810 --> 00:20:25,070
Så jeg siger bare, hvis du giver mig
nul eller mindre, jeg vender tilbage nul.

433
00:20:25,070 --> 00:20:28,220
>> Men det er godt, fordi det er
at enkelt side af telefonbogen

434
00:20:28,220 --> 00:20:28,790
der er tilbage.

435
00:20:28,790 --> 00:20:32,660
Jeg bide et meget specifikt problem
og ikke kalde noget rekursivt.

436
00:20:32,660 --> 00:20:36,580
Men i ledningen 31, hvilket
skal jeg synes at gøre?

437
00:20:36,580 --> 00:20:39,780
De parentes er bare holder
ting forhåbentlig lidt klarere.

438
00:20:39,780 --> 00:20:42,110
Men alt jeg gør er jeg
returnering m-- uanset

439
00:20:42,110 --> 00:20:45,790
du aflevere mig-- plus
værdien af ​​m-- sorry,

440
00:20:45,790 --> 00:20:49,052
plus værdien af ​​sigma m minus 1.

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

442
00:20:50,010 --> 00:20:53,965
Hvis du giver mig det nummer 3 som input,
det svar, jeg ønsker at få i sidste ende

443
00:20:53,965 --> 00:20:57,307
er 6, fordi 3 plus 2 plus 1 giver mig 6.

444
00:20:57,307 --> 00:20:59,390
Men hvordan kan jeg tænke over
hvordan denne kode kører?

445
00:20:59,390 --> 00:21:03,070
Første gang jeg kalder sigma
og jeg passerer i værdien 3,

446
00:21:03,070 --> 00:21:07,960
det er ligesom at sige på et stykke
papir, her er værdien 3

447
00:21:07,960 --> 00:21:09,920
og jeg har bestået dette som sigma.

448
00:21:09,920 --> 00:21:13,090
3 er naturligvis ikke mindre end 0, så
IF betingelse gælder ikke.

449
00:21:13,090 --> 00:21:14,020
Den andre gør.

450
00:21:14,020 --> 00:21:14,990
Så hvad skal jeg gøre?

451
00:21:14,990 --> 00:21:19,902
Jeg ønsker at vende tilbage m, hvilket er
3, plus sigma m minus 1.

452
00:21:19,902 --> 00:21:21,110
Så lad mig holde styr på dette.

453
00:21:21,110 --> 00:21:22,710
Jeg har tænkt mig at sætte dette
stykke papir ned.

454
00:21:22,710 --> 00:21:24,668
Og hvilken værdi, at være
klar, vil jeg videregive

455
00:21:24,668 --> 00:21:26,540
ind sigma på dette tidspunkt i historien?

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

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

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

459
00:21:29,670 --> 00:21:32,000
Så jeg har bare brug for lidt
skrot af papir her.

460
00:21:32,000 --> 00:21:33,931
Så nu sigma er at få kaldt igen.

461
00:21:33,931 --> 00:21:35,930
Og jeg har med vilje lagt
dette ned, fordi det er

462
00:21:35,930 --> 00:21:38,070
lidt ligesom pause
denne version af historien

463
00:21:38,070 --> 00:21:40,720
fordi nu er jeg fokuseret
på signalet af m minus 1.

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

465
00:21:42,660 --> 00:21:45,110
Så her er 2 at jeg har bestået.

466
00:21:45,110 --> 00:21:48,510
2 er naturligvis ikke mindre end
0 således at sagen ikke finder anvendelse.

467
00:21:48,510 --> 00:21:53,445
Else Jeg vender tilbage m, hvilket er det
ting, plus sigma af hvilken værdi?

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

469
00:21:56,160 --> 00:21:59,650
Så hvis sigma af 1-- fordi m er
lige nu 2 så 2 minus 1 er 1.

470
00:21:59,650 --> 00:22:01,950
Så nu har jeg bare værdien 1.

471
00:22:01,950 --> 00:22:04,810
Jeg passerer lige antal
1 til funktionen sigma--

472
00:22:04,810 --> 00:22:09,120
eller mig selv her-- så 1 er naturligvis ikke
mindre end nul, stadig ikke gælder.

473
00:22:09,120 --> 00:22:12,970
>> Else afkast 1 plus sigma af hvad?

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

475
00:22:13,470 --> 00:22:14,678
Så lad mig bare huske, at.

476
00:22:14,678 --> 00:22:15,920
Jeg vil vende tilbage til senere.

477
00:22:15,920 --> 00:22:18,060
Nu vil jeg gå videre og tøddel
ned på antallet 0, fordi det er

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

479
00:22:19,470 --> 00:22:22,400
Jeg bestået nummer 0
og endelig denne proces

480
00:22:22,400 --> 00:22:25,760
for bare at gentage mig selv annonce
nauseum betyder ophører, fordi det,

481
00:22:25,760 --> 00:22:28,820
gør jeg straks gøre, når jeg ser dette 0?

482
00:22:28,820 --> 00:22:29,790
Jeg vender tilbage nul.

483
00:22:29,790 --> 00:22:31,790
Så nu er du nødt til at spole tilbage historien.

484
00:22:31,790 --> 00:22:34,430
>> Hvis jeg nu gå baglæns i tid,
hvad var den seneste ting

485
00:22:34,430 --> 00:22:36,670
Jeg gjorde, hvis du var bogstaveligt
tilbagespoling en video?

486
00:22:36,670 --> 00:22:41,630
Jeg har tænkt mig at afhente den seneste
1 og det giver mig 1 plus 0 er 1..

487
00:22:41,630 --> 00:22:44,100
Hvis jeg holder tilbagespoling af
historie, der kommer til at give mig

488
00:22:44,100 --> 00:22:46,880
2 plus det kører værdi, som er 1.

489
00:22:46,880 --> 00:22:47,789
Så det er 3.

490
00:22:47,789 --> 00:22:49,330
Og så jeg har tænkt mig at holde tilbagespoling.

491
00:22:49,330 --> 00:22:54,220
Da jeg først satte antallet
3-- så 3 plus 3 giver mig 6.

492
00:22:54,220 --> 00:22:57,272
>> Og nu, hvis du har spolet tilbage
videoen indtil dette punkt,

493
00:22:57,272 --> 00:22:58,980
dette var meget
første spørgsmål spurgte jeg.

494
00:22:58,980 --> 00:23:01,450
Når passeret 3, hvad der er sigma 3?

495
00:23:01,450 --> 00:23:04,204
Det er faktisk 6, summen af
alle disse stykker papir.

496
00:23:04,204 --> 00:23:07,120
Så hvis der tager lidt tid at
wrap dit sind omkring, det er fint.

497
00:23:07,120 --> 00:23:10,700
Men overveje det var en little-- det
var meget bevidst, at jeg stablet

498
00:23:10,700 --> 00:23:12,990
disse numre oven på hinanden.

499
00:23:12,990 --> 00:23:17,440
Det er lidt som at have en
memory-- en rekord i tiden,

500
00:23:17,440 --> 00:23:19,940
som en skrubber i en video,
at jeg faktisk kan spole tilbage i.

501
00:23:19,940 --> 00:23:24,350
Og vi vil komme tilbage til
at metafor i bare en lille smule.

502
00:23:24,350 --> 00:23:28,240
>> Men først, det viser sig, at der er
en masse nørder og sjove mennesker,

503
00:23:28,240 --> 00:23:29,614
Jeg gætter på Google.

504
00:23:29,614 --> 00:23:31,530
Ville en person, der er meget
god til Googling sind

505
00:23:31,530 --> 00:23:34,270
kommer op for bare et øjeblik og
hjælp mig søge efter noget?

506
00:23:34,270 --> 00:23:35,650
Meget, meget lav nøgle.

507
00:23:35,650 --> 00:23:37,870
Nogen, der er aldrig
kommer op før, måske.

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

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

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

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

512
00:23:41,410 --> 00:23:42,183
Hvad er dit navn?

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

515
00:23:44,290 --> 00:23:45,320
Dette er den samme.

516
00:23:45,320 --> 00:23:46,280
Dejligt at møde dig.

517
00:23:46,280 --> 00:23:46,780
Hey.

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

519
00:23:47,580 --> 00:23:51,290
Så alt jeg har brug for dig til at gøre, hvis
du kunne, Sam, her er Google.

520
00:23:51,290 --> 00:23:53,240
Kan du søge efter ordet rekursion?

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

522
00:23:55,770 --> 00:23:56,270
Må ikke ødelægge.

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

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

525
00:24:00,970 --> 00:24:03,380
OK Klik det.

526
00:24:03,380 --> 00:24:04,315
Bedre klikke det.

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å lad os gøre et par andre.

532
00:24:10,430 --> 00:24:12,830
Ikke så meget relateret
fagligt her, men har du

533
00:24:12,830 --> 00:24:14,520
nogensinde søgte på Google efter 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øg efter anagram stedet for rekursion.

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

538
00:24:22,540 --> 00:24:23,790
Hvordan omkring skævt.

539
00:24:23,790 --> 00:24:25,515
Har du nogensinde søgt efter skævt?

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

541
00:24:29,260 --> 00:24:32,692
Nu, dette ene er lidt svært at
se, men forhåbentlig everything's-- OK.

542
00:24:32,692 --> 00:24:34,150
Det er bare dig og mig nyder dette.

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

544
00:24:34,690 --> 00:24:38,950
>> Så til sidst, denne one's--
det er lidt skævt.

545
00:24:38,950 --> 00:24:40,810
Nu gør en tønde roll.

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

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

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

549
00:24:45,910 --> 00:24:47,110
Stor tak til Sam.

550
00:24:47,110 --> 00:24:49,416
Vær så god.

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

552
00:24:50,400 --> 00:24:52,807
>> Så hvad der foregår i alle
af disse tåbelige eksempler?

553
00:24:52,807 --> 00:24:55,640
Så virkelig, under kølerhjelmen af
Googles millioner af linjer kode

554
00:24:55,640 --> 00:24:58,860
tilsyneladende er et par fjollet IF
forhold, der er væsentlige

555
00:24:58,860 --> 00:25:01,160
kontrollere, om brugeren har
skrevet i denne sætning,

556
00:25:01,160 --> 00:25:03,760
gøre noget, der formentlig fandt
en nontrivial mængde tid

557
00:25:03,760 --> 00:25:06,080
at gennemføre blot at
være morsom på denne måde.

558
00:25:06,080 --> 00:25:08,430
Men det er alt det koger
ned til under motorhjelmen.

559
00:25:08,430 --> 00:25:11,570
Men naturligvis rekursion
er mere af geekier

560
00:25:11,570 --> 00:25:13,880
eksempel blandt de særlige tricks.

561
00:25:13,880 --> 00:25:16,880
Og mon der ikke er andre derude
så godt, at vi måske har ikke engang

562
00:25:16,880 --> 00:25:18,230
opdaget endnu.

563
00:25:18,230 --> 00:25:22,830
>> Så tag et kig, eller overveje
nu følgende program,

564
00:25:22,830 --> 00:25:24,830
og helt sikkert få fat i nogen
af disse på din vej ud.

565
00:25:24,830 --> 00:25:28,820
Jeg har tænkt mig at gå videre og
åbne op for et program, der er

566
00:25:28,820 --> 00:25:30,920
vil forsøge at bytte to værdier.

567
00:25:30,920 --> 00:25:33,210
Men før vi går der, lad os gøre det.

568
00:25:33,210 --> 00:25:38,500
Kunne vi få en mere
frivillig, jeg tror?

569
00:25:38,500 --> 00:25:40,480
Kunne du tænke dig at arbejde frivilligt?

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

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

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

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

574
00:25:42,890 --> 00:25:44,136
Så dit navn er hvad?

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 op, Lauren.

578
00:25:46,890 --> 00:25:50,140
Så Lauren er ved at blive
Her udfordres som følger.

579
00:25:50,140 --> 00:25:52,310
Dejligt at møde dig.

580
00:25:52,310 --> 00:25:55,730
Så Lauren her har foran
af hendes to tomme kopper.

581
00:25:55,730 --> 00:25:57,570
Og vi har nogle orange
saft og nogle mælk

582
00:25:57,570 --> 00:26:00,301
og vi kommer til at gå
videre og gøre følgende.

583
00:26:00,301 --> 00:26:01,550
Vi er lige kommer til at fylde dette.

584
00:26:01,550 --> 00:26:07,840
Et par ounces mælk herover og lad os
fylde lidt appelsinjuice herovre.

585
00:26:07,840 --> 00:26:11,475
>> Og foran alle
disse tilhørerne,

586
00:26:11,475 --> 00:26:13,550
bytte de to værdier for disse kopper.

587
00:26:13,550 --> 00:26:16,970
Sæt appelsinjuice i mælken koppen
og mælken i appelsinsaft cup.

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

589
00:26:22,380 --> 00:26:26,150
Hvordan ville du gøre det, hvis du var på
hjem og havde adgang til andre forsyninger?

590
00:26:26,150 --> 00:26:27,400
LAUREN: Put det i en anden kop.

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

592
00:26:28,191 --> 00:26:31,940
Så lad os få en midlertidig
variabel, hvis vi vil.

593
00:26:31,940 --> 00:26:35,871
Og gå videre nu og implementere
samme swapping procedure.

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

595
00:26:36,370 --> 00:26:41,490
Vi har lagt OJ i den midlertidige
variabel, mælk i EFT variabel,

596
00:26:41,490 --> 00:26:44,481
og nu midlertidig variabel
i mælkevariablen.

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

598
00:26:44,980 --> 00:26:48,740
Så meget godt gjort hidtil.

599
00:26:48,740 --> 00:26:50,990
Så det viser out-- fastslå, at
tænkte for bare et øjeblik.

600
00:26:50,990 --> 00:26:54,479
Her, bare til Geek det lidt op, det
ville være den tilsvarende C-kode

601
00:26:54,479 --> 00:26:55,520
at vi implementeret bare.

602
00:26:55,520 --> 00:26:58,650
Vi havde to indgange, a og b, der begge
som vi vil bare sige til enkelhed er

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

604
00:26:59,260 --> 00:27:02,780
Og mærke her, hvis jeg ønsker at bytte
værdierne af to variabler, a og b,

605
00:27:02,780 --> 00:27:06,890
vi faktisk har brug for en mellemmand, en
midlertidig variabel, en midlertidig kop,

606
00:27:06,890 --> 00:27:10,830
i hvilken hældes en af ​​værdierne
således at vi har en pladsholder for det.

607
00:27:10,830 --> 00:27:13,480
Men så koden er præcis
som Lauren her implementeret.

608
00:27:13,480 --> 00:27:15,500
>> Nu, bare for at få en
lidt mere skørt, viser sig

609
00:27:15,500 --> 00:27:20,930
at du kan gøre dette uden
en midlertidig variabel.

610
00:27:20,930 --> 00:27:24,870
For at gøre dette korrekt, men vi vil
nødt til at snyde med nogle kemi.

611
00:27:24,870 --> 00:27:26,380
Vi har nogle ekstra kopper her.

612
00:27:26,380 --> 00:27:29,600
Så det tætteste, der ser
ligesom mælk og vand perhaps--

613
00:27:29,600 --> 00:27:34,090
eller mælk og OJ-- er vi har nogle
vand, så vi vil udfylde dette en op

614
00:27:34,090 --> 00:27:36,486
med et par ounces klart vand.

615
00:27:36,486 --> 00:27:38,332
Det er nok for meget.

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

617
00:27:38,832 --> 00:27:39,934
Det er helt sikkert for meget.

618
00:27:39,934 --> 00:27:40,600
Hold på én sek.

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

620
00:27:43,520 --> 00:27:48,420
>> Og nu har vi olie, som, så vidt jeg husker
fra midten skole kemi klasse,

621
00:27:48,420 --> 00:27:49,990
forhåbentlig er det ikke blandes med vand.

622
00:27:49,990 --> 00:27:53,650
Men den slags slags
ligner mælk og EFT.

623
00:27:53,650 --> 00:27:55,760
Så nu, uden at bruge
en midlertidig variabel,

624
00:27:55,760 --> 00:27:59,260
kan du bytte disse to værdier?

625
00:27:59,260 --> 00:28:03,884
Så olier går i vandet kop,
vand går ind i olie koppen.

626
00:28:03,884 --> 00:28:04,800
LAUREN: Ingen andre kopper?

627
00:28:04,800 --> 00:28:05,940
DAVID J. MALAN: Ingen andre kopper.

628
00:28:05,940 --> 00:28:07,860
Og jeg har faktisk ikke
testet dette før dette år

629
00:28:07,860 --> 00:28:10,110
så jeg ved ikke, om dette vil
rent faktisk arbejder kemisk.

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

631
00:28:16,130 --> 00:28:18,650
Det var ikke meningen at ske.

632
00:28:18,650 --> 00:28:19,761
Er det til at virke?

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

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

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

636
00:28:21,490 --> 00:28:24,714
Nu fik vi at få den
vand i det andet bæger.

637
00:28:24,714 --> 00:28:27,630
Smartere kemi koncentratorer kunne
sandsynligvis gøre det bedre end mig.

638
00:28:27,630 --> 00:28:28,510
>> LAUREN: Vandet er på bunden.

639
00:28:28,510 --> 00:28:31,910
>> DAVID J. MALAN: Det water--, der var
hvad der er nøglen sidste gang vi gjorde dette.

640
00:28:31,910 --> 00:28:33,950
Du er nødt til at gøre det i den rigtige rækkefølge.

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

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

643
00:28:35,270 --> 00:28:37,290
Så nu har vi to kopper olie.

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

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

646
00:28:38,510 --> 00:28:40,110
Men kemisk hvis dette arbejdede end jeg--

647
00:28:40,110 --> 00:28:41,200
>> LAUREN: Dette er vand.

648
00:28:41,200 --> 00:28:41,930
>> DAVID J. MALAN: Det er for det meste vand.

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

650
00:28:42,430 --> 00:28:44,210
Men det er stadig den samme kop som før.

651
00:28:44,210 --> 00:28:47,570
Så hæld det-- prøve det derovre.

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

653
00:28:49,300 --> 00:28:51,010
Det er en god brug af klassen tid i dag.

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

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

656
00:28:53,890 --> 00:28:55,460
Slags.

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

658
00:28:55,960 --> 00:28:56,690
Så meget godt.

659
00:28:56,690 --> 00:29:00,006
Tak til Lauren.

660
00:29:00,006 --> 00:29:01,950
Meget godt klaret.

661
00:29:01,950 --> 00:29:04,570
>> Så bare at blæse jeres sind,
og det er måske noget

662
00:29:04,570 --> 00:29:08,660
at lege med, hvis du gerne i CS50-id,
du kan faktisk bytte to variabler

663
00:29:08,660 --> 00:29:11,470
uden brug af en midlertidig heltal.

664
00:29:11,470 --> 00:29:13,060
Og dette er den tilsvarende C-kode.

665
00:29:13,060 --> 00:29:16,110
Og hvis du husker fra sidste
Onsdag introducerede vi, hvis kort,

666
00:29:16,110 --> 00:29:19,720
nogle nye operatører i C. Og gør
nogen huske, hvad den lille gulerod

667
00:29:19,720 --> 00:29:23,660
symbolet er, at lille trekantede
symbol fra tastaturet repræsenterer?

668
00:29:23,660 --> 00:29:26,003
Hvad bitvis operatør?

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

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

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

672
00:29:28,560 --> 00:29:32,920
Så hvis du ønsker, bare for sjov på
hjem, til opnåelse a og b to vilkårlige

673
00:29:32,920 --> 00:29:36,072
værdier som helst eight-- og jeg
ville vælge en otte bit værdi.

674
00:29:36,072 --> 00:29:38,530
Hvis du gør dette med 32 bits,
vil du meget hurtigt kede sig.

675
00:29:38,530 --> 00:29:42,150
Men bare give en en otte bit
værdi, der er hvad, en eller to,

676
00:29:42,150 --> 00:29:43,790
og give b samme værdi.

677
00:29:43,790 --> 00:29:46,810
Og derefter bruge definitionen
af XOR fra sidste onsdag,

678
00:29:46,810 --> 00:29:52,560
anvende denne lidt efter lidt, idet hver af
disse otte bit i hver af a og b,

679
00:29:52,560 --> 00:29:54,980
og derefter gøre det nøjagtigt pr denne kode.

680
00:29:54,980 --> 00:29:58,170
Og det er ikke forkert, hvad
du ser her på skærmen.

681
00:29:58,170 --> 00:30:02,100
Det faktisk koges ned
til tre XOR operationer

682
00:30:02,100 --> 00:30:05,910
og på en måde magisk a og
b vil udveksle holdninger

683
00:30:05,910 --> 00:30:08,010
uden at miste nogen oplysninger.

684
00:30:08,010 --> 00:30:11,580
>> Så olien og vandet trick er
tættest virkelige verden inkarnation

685
00:30:11,580 --> 00:30:12,980
Jeg kunne tænke på at efterligne det.

686
00:30:12,980 --> 00:30:15,950
Men det er helt sikkert nemmere at
bruge en midlertidig variabel,

687
00:30:15,950 --> 00:30:16,920
som i dette tilfælde her.

688
00:30:16,920 --> 00:30:21,190
Og også dette er en mulighed sige,
Også denne form for mikro optimering,

689
00:30:21,190 --> 00:30:23,590
som en datalog
ville sige, mens slags sjov

690
00:30:23,590 --> 00:30:27,060
at prale om, hvordan du gjorde det uden
ligesom at bytte med en ekstra variabel,

691
00:30:27,060 --> 00:30:28,640
det er ikke alt, overbevisende.

692
00:30:28,640 --> 00:30:31,619
Fordi at spare 32 bit, som
i tilfælde af en faktisk int,

693
00:30:31,619 --> 00:30:33,410
er ikke alt, overbevisende
på et system, hvor

694
00:30:33,410 --> 00:30:36,722
du bruger måske snesevis af megabytes
eller endnu mere sådan hukommelse disse dage.

695
00:30:36,722 --> 00:30:38,680
Og i virkeligheden, når vi får
til et senere problem sæt

696
00:30:38,680 --> 00:30:41,010
og du implementere magi
brik og du vil

697
00:30:41,010 --> 00:30:43,550
blive udfordret til at gøre det med
dette så lidt RAM og så lidt

698
00:30:43,550 --> 00:30:46,820
tid som muligt på
computer-- du stadig

699
00:30:46,820 --> 00:30:50,160
har en uge til at gennemføre
det-- du vil have-- du vil være

700
00:30:50,160 --> 00:30:51,799
udfordret til at minimere disse ressourcer.

701
00:30:51,799 --> 00:30:53,840
Og det er virkelig den eneste
anledning dette semester

702
00:30:53,840 --> 00:30:57,940
hvor du vil blive opfordret til at barbere
off selv de fineste resultater

703
00:30:57,940 --> 00:30:59,340
koster andet.

704
00:30:59,340 --> 00:31:02,200
>> Så Hvad-- hvordan kan vi
se dette i konkrete kode?

705
00:31:02,200 --> 00:31:04,530
Lad mig gå videre nu
og åbne op et eksempel

706
00:31:04,530 --> 00:31:07,700
der bevidst hedder
Ingen Swap fordi det ikke

707
00:31:07,700 --> 00:31:10,670
faktisk bytte variablerne
som du faktisk kunne forvente.

708
00:31:10,670 --> 00:31:12,260
Så lad os tage et kig.

709
00:31:12,260 --> 00:31:17,050
Her er et program, der ikke har nogen CS50
bibliotek foregår, bare standard I / O.

710
00:31:17,050 --> 00:31:19,560
Nu har vi en prototype
til swap op øverst, som netop

711
00:31:19,560 --> 00:31:21,540
betyder, at det er nødt til at være defineret senere.

712
00:31:21,540 --> 00:31:22,550
Og her er vigtigste.

713
00:31:22,550 --> 00:31:26,000
>> Jeg vilkårligt tildelt x og y,
henholdsvis værdier et og to

714
00:31:26,000 --> 00:31:28,590
bare fordi de er små
og let at tænke over.

715
00:31:28,590 --> 00:31:32,280
Og så er jeg bare har en masse printfs
hvor jeg har en tilregnelighed check. x er 1

716
00:31:32,280 --> 00:31:35,110
og y er 2, er formentlig
hvad disse printfs vil sige.

717
00:31:35,110 --> 00:31:36,530
Så ingen magisk hidtil.

718
00:31:36,530 --> 00:31:40,100
>> Så jeg har tænkt mig at hævde med
udskrive def, bytte dot dot dot.

719
00:31:40,100 --> 00:31:43,730
Jeg har tænkt mig at ringe til swap
funktion, der passerer i x og y.

720
00:31:43,730 --> 00:31:47,350
Og lad os antage, for nu at
swap gennemføres nøjagtigt

721
00:31:47,350 --> 00:31:49,930
som det var for et øjeblik siden
med en midlertidig variabel.

722
00:31:49,930 --> 00:31:52,670
Og så jeg hævder dristigt, byttes.

723
00:31:52,670 --> 00:31:55,429
X er nu dette, og y er nu, at.

724
00:31:55,429 --> 00:31:57,220
Men filen, selvfølgelig,
kaldes Ingen Swap.

725
00:31:57,220 --> 00:31:58,678
Så lad os faktisk se hvad der sker.

726
00:31:58,678 --> 00:32:04,450
Hvis jeg kompilere ikke bytte, og derefter
gør ./noswap, x er 1, y er 2.

727
00:32:04,450 --> 00:32:05,770
Bytte byttes.

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

729
00:32:07,200 --> 00:32:11,980
Så det faktisk ser ud til at være behæftet med fejl, selv
selvom swap-- lad os rulle ned nu--

730
00:32:11,980 --> 00:32:16,542
gennemføres nøjagtigt pr
kode Jeg foreslog for et øjeblik siden.

731
00:32:16,542 --> 00:32:19,000
Så vi kommer ikke til at få lyst
med XOR ting for nu.

732
00:32:19,000 --> 00:32:21,890
Også dette bør arbejde bare
gerne med mælk og EFT,

733
00:32:21,890 --> 00:32:25,820
men det ser ikke ud til at virke.

734
00:32:25,820 --> 00:32:27,180
>> Så lad os gøre det igen.

735
00:32:27,180 --> 00:32:29,310
Måske jeg bare var ikke kører det rigtigt.

736
00:32:29,310 --> 00:32:32,010
Så lad os løbe Ingen Swap igen.

737
00:32:32,010 --> 00:32:32,900
Måske jeg-- nej.

738
00:32:32,900 --> 00:32:34,400
Så det er bare ikke i orden.

739
00:32:34,400 --> 00:32:36,060
Så lad os gøre en lille tilregnelighed check.

740
00:32:36,060 --> 00:32:39,690
Lad mig gå videre her i Swap
og blot tilføje, vent et minut,

741
00:32:39,690 --> 00:32:43,856
a er% i / n og lad os
plug-in værdien af ​​en.

742
00:32:43,856 --> 00:32:45,730
Fordi jeg virkelig ønsker
for at se, hvad der foregår.

743
00:32:45,730 --> 00:32:47,570
Og ja, det er
en debugging teknik

744
00:32:47,570 --> 00:32:50,028
at du bruger måske i
kontortid eller derhjemme allerede,

745
00:32:50,028 --> 00:32:53,560
beslægtet med den første halvdel af Dan
Armendariz video i PSET3

746
00:32:53,560 --> 00:32:56,870
hvor vi introducerede print def som
en anbefalet teknik, i det mindste

747
00:32:56,870 --> 00:32:58,080
for simple sager.

748
00:32:58,080 --> 00:33:01,720
Lad mig gå videre og køre gøre
ingen swap igen, ./noswap.

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

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

751
00:33:05,840 --> 00:33:11,670
Så mærke til, hvad der synes at være sandt. x
er 1, y er 2, men er 2 når b er 1.

752
00:33:11,670 --> 00:33:16,790
Så dem to en eller anden måde fik byttet
men x og y er ikke at få byttet.

753
00:33:16,790 --> 00:33:21,090
Så for at være klar, hvad der sker
er, heroppe har jeg x og y

754
00:33:21,090 --> 00:33:25,380
og dem er variable lokale i
omfanget af vigtigste, jeg passerer i x og y

755
00:33:25,380 --> 00:33:26,170
at bytte.

756
00:33:26,170 --> 00:33:29,080
Nu swap, som en separat funktion,
er velkommen til at ringe sine argumenter

757
00:33:29,080 --> 00:33:30,590
eller dens parametre noget den ønsker.

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
Blot for at gøre det klart, at de er
ikke er identisk med x og y per se,

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

761
00:33:38,020 --> 00:33:40,040
Men vi kunne kalde dem noget, vi ønsker.

762
00:33:40,040 --> 00:33:43,960
>> Og så det ligner
swap bliver passeret

763
00:33:43,960 --> 00:33:48,980
x-- AKA en-- og det er
forbikøres y-- AKA b.

764
00:33:48,980 --> 00:33:51,900
På en måde disse tre linjer er
bytte disse værdier nøjagtigt

765
00:33:51,900 --> 00:33:53,510
som Lauren gjorde med mælk og EFT.

766
00:33:53,510 --> 00:33:56,010
Men når vi udskriver
værdierne, a og b

767
00:33:56,010 --> 00:34:01,340
er faktisk bytte, men X og
Y har ingen ændring til dem.

768
00:34:01,340 --> 00:34:03,150
Husk på, at x og y er heroppe.

769
00:34:03,150 --> 00:34:05,320
>> Så vi kan se det via
en anden teknik samt.

770
00:34:05,320 --> 00:34:08,110
Og også dette er en teknik
indlejret i problemet sæt tre.

771
00:34:08,110 --> 00:34:10,780
Lad os gå videre og gøre dette i
CS50-id, hvis du ikke allerede har.

772
00:34:10,780 --> 00:34:13,730
På højre side, vi
har denne fane Debugger.

773
00:34:13,730 --> 00:34:16,159
Og hvis du åbner dette op,
der er nogle mystiske oplysninger

774
00:34:16,159 --> 00:34:17,530
der er kastet på dig i første omgang.

775
00:34:17,530 --> 00:34:19,310
Men lad os drille det fra hinanden rigtig hurtigt.

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

777
00:34:21,620 --> 00:34:26,230
Viser sig, at bygge ind i CS50 IDE, og
en masse programmering miljøer mere

778
00:34:26,230 --> 00:34:28,060
generelt, er en debugger.

779
00:34:28,060 --> 00:34:31,340
Et værktøj, der giver dig mulighed for visuelt at se
hvad der foregår inde i dit program

780
00:34:31,340 --> 00:34:34,380
uden at skulle ty til at tilsætte
printfs og kompilering og kører

781
00:34:34,380 --> 00:34:37,588
og tilføje printf-og kompilering og
løb, som allerede i kontortiden

782
00:34:37,588 --> 00:34:40,070
eller hjemme, er sandsynligvis
at få temmelig trættende.

783
00:34:40,070 --> 00:34:43,090
>> Så her, på bare et øjeblik, vi er
kommer til at se i realtid

784
00:34:43,090 --> 00:34:44,760
værdierne i vores lokale variable.

785
00:34:44,760 --> 00:34:47,880
Vi er også vil være i stand til at sætte
hvad der kaldes breakpoints, som

786
00:34:47,880 --> 00:34:52,570
er muligheder i mit program til at holde pause
bearbejdning fra et bestemt linje kode

787
00:34:52,570 --> 00:34:53,710
at jeg er nysgerrig.

788
00:34:53,710 --> 00:34:54,210
Højre?

789
00:34:54,210 --> 00:34:55,969
Disse programmer kører i et splitsekund.

790
00:34:55,969 --> 00:35:00,450
Det er slags rart for os langsommere mennesker
at være i stand til at holde pause, tage et øjeblik, se

791
00:35:00,450 --> 00:35:02,380
hvad der foregår omkring
en vis linje kode

792
00:35:02,380 --> 00:35:05,050
uden programmet pløjning
gennem det og efterbehandling helt.

793
00:35:05,050 --> 00:35:08,510
Så en breakpoints kommer til at tillade os at
bryde og pause på et bestemt tidspunkt.

794
00:35:08,510 --> 00:35:12,990
>> Kaldstakkens er en fancy måde
sige, hvad funktioner er i øjeblikket

795
00:35:12,990 --> 00:35:14,140
bliver kaldt i øjeblikket.

796
00:35:14,140 --> 00:35:15,370
Vigtigste altid kaldes først.

797
00:35:15,370 --> 00:35:17,230
Men hvis Main kalder en
funktion kaldet Swap,

798
00:35:17,230 --> 00:35:20,470
vi faktisk kommer til at se denne
tårn af funktioner, der har været

799
00:35:20,470 --> 00:35:22,400
kaldte i omvendt kronologisk rækkefølge.

800
00:35:22,400 --> 00:35:23,310
Så lad os se det.

801
00:35:23,310 --> 00:35:24,327
>> Jeg har tænkt mig at zoome ud.

802
00:35:24,327 --> 00:35:25,660
Jeg har tænkt mig at gå tilbage til min kode.

803
00:35:25,660 --> 00:35:27,540
Og bare fordi jeg ønsker
at være pedantisk her,

804
00:35:27,540 --> 00:35:31,100
Jeg har tænkt mig at gå videre og klik
lige til venstre for linjen fem.

805
00:35:31,100 --> 00:35:32,830
Og det skaber en rød prik.

806
00:35:32,830 --> 00:35:36,200
Og bemærk på højre side
at debugger kender, hey,

807
00:35:36,200 --> 00:35:41,020
Jeg sagde bare et breakpoint på
noswap.c linje fem, specielt

808
00:35:41,020 --> 00:35:42,480
på dette linje kode.

809
00:35:42,480 --> 00:35:45,090
Så debugger ved, at jeg
har anmodet om, at næste gang

810
00:35:45,090 --> 00:35:48,530
Jeg køre mit program det pause
udførelse der snarere end blot

811
00:35:48,530 --> 00:35:50,390
kører det hele super hurtigt.

812
00:35:50,390 --> 00:35:53,889
>> Så nu vil jeg til at klikke på Debug
knappen på toppen af ​​IDE

813
00:35:53,889 --> 00:35:55,430
og det kommer til at gøre følgende.

814
00:35:55,430 --> 00:36:00,680
Det kommer til at åbne en oprindeligt noget
skræmmende leder anden terminal window--

815
00:36:00,680 --> 00:36:02,679
remote debugging fra
vært sådan og such--

816
00:36:02,679 --> 00:36:04,970
og vi vil komme tilbage til det,
alt, betyder inden længe.

817
00:36:04,970 --> 00:36:09,020
Men hvad der er vigtigt for nu
er, at der red dot blev ramt,

818
00:36:09,020 --> 00:36:11,735
debugger har bevidst
standsede execution--

819
00:36:11,735 --> 00:36:15,560
på denne linje sådan, men på den første
linje faktiske kode i denne funktion.

820
00:36:15,560 --> 00:36:18,040
Og det er derfor linie syv er
nu markeret med gult.

821
00:36:18,040 --> 00:36:20,550
>> Og lad os nu tage et kig
på højre side.

822
00:36:20,550 --> 00:36:27,300
Det ligner, som standard,
pænt nok, x har hvilken værdi?

823
00:36:27,300 --> 00:36:27,860
0.

824
00:36:27,860 --> 00:36:29,750
Og y har hvad værdi?

825
00:36:29,750 --> 00:36:30,410
Zero.

826
00:36:30,410 --> 00:36:35,540
Og det er der kan forventes i den forstand,
at x og y-- at gul line-- har

827
00:36:35,540 --> 00:36:36,770
udføres ikke endnu.

828
00:36:36,770 --> 00:36:38,510
SOx bør ikke have værdien 1.

829
00:36:38,510 --> 00:36:41,470
Det kunne have en anden værdi,
en såkaldt garbage værdi.

830
00:36:41,470 --> 00:36:44,320
Og vi fik heldig i, at det er
nul på dette tidspunkt i det væsentlige.

831
00:36:44,320 --> 00:36:46,400
>> Så nu er der kun få
knapper, vi har brug for at pleje

832
00:36:46,400 --> 00:36:48,100
om, når debugging på denne måde.

833
00:36:48,100 --> 00:36:49,970
Bemærk her, har vi en knappen Afspil.

834
00:36:49,970 --> 00:36:51,877
Og hvis vi spiller eller hit
genoptage, det er bare

835
00:36:51,877 --> 00:36:53,710
kommer til at løbe gennem
resten af ​​programmet

836
00:36:53,710 --> 00:36:55,300
eller indtil den rammer en anden breakpoint.

837
00:36:55,300 --> 00:36:56,910
Men jeg har ikke sat nogen anden
breakpoints så det er bare

838
00:36:56,910 --> 00:36:58,118
kommer til at køre gennem enden.

839
00:36:58,118 --> 00:37:00,280
Den slags nederlag de
Formålet med rode rundt.

840
00:37:00,280 --> 00:37:03,290
>> Så i stedet, jeg holder
disse ikoner til højre.

841
00:37:03,290 --> 00:37:05,360
Og hvis jeg svæve over
dem, som du bør også,

842
00:37:05,360 --> 00:37:07,450
vil du se lidt tips-- værktøjstip.

843
00:37:07,450 --> 00:37:09,020
Denne ene er trin over.

844
00:37:09,020 --> 00:37:11,290
Nu betyder det ikke, skip
følgende linje kode.

845
00:37:11,290 --> 00:37:14,840
Det betyder blot udføre det og
flytte til den næste, flytte til den næste,

846
00:37:14,840 --> 00:37:15,580
flytte til det næste.

847
00:37:15,580 --> 00:37:17,610
Med andre ord, via
denne knap, kan jeg gå

848
00:37:17,610 --> 00:37:20,390
gennem min kode et skridt ad gangen.

849
00:37:20,390 --> 00:37:21,914
Linje for linje, bogstaveligt talt.

850
00:37:21,914 --> 00:37:23,830
Nu til højre for
det, er der en anden

851
00:37:23,830 --> 00:37:25,163
at vi vil se på bare et øjeblik.

852
00:37:25,163 --> 00:37:27,820
Dette er den såkaldte
Step Into ikon, der er

853
00:37:27,820 --> 00:37:30,300
vil tillade mig dykke
i en anden funktion.

854
00:37:30,300 --> 00:37:31,800
Men lad os se det i bare et øjeblik.

855
00:37:31,800 --> 00:37:33,280
Så jeg har tænkt mig at klikke på trin over.

856
00:37:33,280 --> 00:37:35,820
Og nu mærke til, da jeg klikker
denne knap øverst til højre,

857
00:37:35,820 --> 00:37:41,260
holde dine øjne nogenlunde under Local
Variabler og se hvad der sker til x.

858
00:37:41,260 --> 00:37:44,115
X er nu 1 fordi
gule linje er nu udført

859
00:37:44,115 --> 00:37:45,840
og vi har flyttet til linje 8.

860
00:37:45,840 --> 00:37:49,840
Og på bare et øjeblik y
skulle forhåbentlig blive 2.

861
00:37:49,840 --> 00:37:52,330
>> Nu intet, interessant
sker for lidt.

862
00:37:52,330 --> 00:37:53,390
Alt dette er er printf.

863
00:37:53,390 --> 00:37:58,010
Og bemærk, i min sekundære terminal
vindue, ser jeg produktionen af ​​print def.

864
00:37:58,010 --> 00:38:01,080
Og nu er jeg nødt til at gøre en
afgørelse som programmøren.

865
00:38:01,080 --> 00:38:04,360
Jeg kan træde over denne linje af
kode, udfører det, men ikke

866
00:38:04,360 --> 00:38:06,220
få nysgerrig efter, hvad der er indeni.

867
00:38:06,220 --> 00:38:11,130
Eller jeg kan faktisk træde ind i det
og gå inde i Swap selv.

868
00:38:11,130 --> 00:38:12,340
Så lad os gøre det sidste.

869
00:38:12,340 --> 00:38:15,550
>> Lad mig gå videre og klik
ikke træde over men Step Into.

870
00:38:15,550 --> 00:38:17,300
Varsel, pludselig
vinduet ændringer

871
00:38:17,300 --> 00:38:19,330
at fremhæve det første
linje kode i Swap.

872
00:38:19,330 --> 00:38:20,710
Det er linje 21.

873
00:38:20,710 --> 00:38:25,220
Og nu, hvad er slags funky er,
hvis man ser herovre, som forventet,

874
00:38:25,220 --> 00:38:29,720
et komma b er 1, og 2, henholdsvis.

875
00:38:29,720 --> 00:38:33,840
Hvorfor er temp 32.767?

876
00:38:33,840 --> 00:38:36,560
Erindrer om, at temp, ligesom
den tomme kop for et øjeblik siden,

877
00:38:36,560 --> 00:38:38,980
erklæres her på linie 21.

878
00:38:38,980 --> 00:38:43,390
Hvorfor 32,000- Jeg mener, hvorfor er
det bare nogle underlige værdi?

879
00:38:43,390 --> 00:38:43,890
Ja?

880
00:38:43,890 --> 00:38:45,190
>> PUBLIKUM: Det er ikke initialiseret.

881
00:38:45,190 --> 00:38:46,940
>> DAVID J. MALAN: Det er
ikke blevet initialiseret.

882
00:38:46,940 --> 00:38:49,370
Så vores computer altid
har fysisk hukommelse.

883
00:38:49,370 --> 00:38:50,544
Det har altid fysisk RAM.

884
00:38:50,544 --> 00:38:52,710
Og der er altid nul s
og man er derinde, ikke?

885
00:38:52,710 --> 00:38:54,626
Fordi vi bruger vores
computer hele dagen lang,

886
00:38:54,626 --> 00:38:57,210
du bruger CS50 IDE
eller serverne hele dagen lang.

887
00:38:57,210 --> 00:39:01,159
Således at RAM enten har nogle nuller eller
nogle ens eller nogle nuller og ettaller.

888
00:39:01,159 --> 00:39:02,950
Uanset om eller
ikke du bruger dem.

889
00:39:02,950 --> 00:39:05,270
Du kan ikke bare have tom
rum, hvor du vil have bits.

890
00:39:05,270 --> 00:39:06,850
De er enten nuller og ettaller.

891
00:39:06,850 --> 00:39:09,610
>> Så det viser sig, at temp, fordi
vi har ikke initialiseret det endnu,

892
00:39:09,610 --> 00:39:14,580
vi har de 32 bit, men de er ikke har
blevet initialiseret til alle kendte værdier.

893
00:39:14,580 --> 00:39:18,110
Så uanset hvad de var mest
nylig brugt for-- dem 32 bits--

894
00:39:18,110 --> 00:39:23,000
vi bare se artefakter af nogle
tidligere brug af dem bestemt 32

895
00:39:23,000 --> 00:39:23,500
bit.

896
00:39:23,500 --> 00:39:27,780
Så snart jeg klikker Step Over selv,
phew, er temp vil få værdien 1.

897
00:39:27,780 --> 00:39:31,600
Og hvis jeg gør det igen, en er
vil blive givet værdien 2

898
00:39:31,600 --> 00:39:33,830
og derefter b kommer til at
gives værdien 1.

899
00:39:33,830 --> 00:39:36,390
>> Og så hvad er rart nu på
dette tidspunkt i historien

900
00:39:36,390 --> 00:39:39,750
er, at debugger er
viser mig, super langsomt

901
00:39:39,750 --> 00:39:42,640
i mit eget tempo, hvad
tilstanden af ​​Swap er.

902
00:39:42,640 --> 00:39:47,490
Men bemærk i toppen her, varsel
at opkaldet stak faktisk

903
00:39:47,490 --> 00:39:49,180
har to lag til det.

904
00:39:49,180 --> 00:39:53,240
Nu en, der er fremhævet som
Swap, hvis jeg klikker på Main stedet,

905
00:39:53,240 --> 00:39:57,100
mærke til, hvordan de lokale variabler ændrer
fordi udvikleren kan bare hoppe

906
00:39:57,100 --> 00:39:59,740
rundt og gå ind i en hvilken som helst anden rækkevidde.

907
00:39:59,740 --> 00:40:04,070
Så selv om vi gør alt dette
arbejde og korrekt swapping a og b,

908
00:40:04,070 --> 00:40:09,080
hvis jeg går frem og tilbage mellem Swap
hvor a er 2, og b er 1, og Main,

909
00:40:09,080 --> 00:40:11,851
har Main blevet påvirket på alle?

910
00:40:11,851 --> 00:40:12,350
Nej.

911
00:40:12,350 --> 00:40:13,930
Så hvad er takeaway her?

912
00:40:13,930 --> 00:40:18,200
Tja, det viser sig, at hver gang
du kalder en funktion som Swap,

913
00:40:18,200 --> 00:40:21,600
og du passerer det argumenter, hvad
du passerer til Swap-funktionen

914
00:40:21,600 --> 00:40:24,730
i dette tilfælde er en kopi
af disse argumenter.

915
00:40:24,730 --> 00:40:28,620
Så hvis x og y er hver henholdsvis
32 bit, hvad Swap bliver

916
00:40:28,620 --> 00:40:30,760
er to nye lokale
variabler, eller argumenter,

917
00:40:30,760 --> 00:40:34,380
kaldes en og B-- men de er vilkårlige
names-- men mønstret af nuller

918
00:40:34,380 --> 00:40:39,520
og dem inde i a og b er
linet op at være identisk med x og y

919
00:40:39,520 --> 00:40:42,610
men de er ikke de er
samme som x og y.

920
00:40:42,610 --> 00:40:46,880
>> Det er som om Main har på sin stykke
papir nummer 1 og 2 for x og y,

921
00:40:46,880 --> 00:40:49,260
og så når det hænder, at
stykke papir til Swap,

922
00:40:49,260 --> 00:40:51,970
Swap meget hurtigt får
sin egen pen, skriver ned

923
00:40:51,970 --> 00:40:56,240
1 og 2 på eget ark papir,
hænder tilbage til den originale xy til Main

924
00:40:56,240 --> 00:40:58,790
og derefter gør sit eget
ting med a og b.

925
00:40:58,790 --> 00:41:01,940
Og det er nu super vigtigt, fordi
dette har nontrivial konsekvenser

926
00:41:01,940 --> 00:41:06,260
for faktisk skriver korrekte kode
fordi det synes vi ikke kan bytte

927
00:41:06,260 --> 00:41:07,500
to variabler.

928
00:41:07,500 --> 00:41:09,150
>> Jeg har skrevet en korrekt Swap funktion.

929
00:41:09,150 --> 00:41:12,770
Vi har implementeret det med Lauren som
en korrekt swap funktion i virkeligheden

930
00:41:12,770 --> 00:41:16,700
men tilsyneladende ingen af ​​der
spørgsmål, hvis du kan faktisk ikke

931
00:41:16,700 --> 00:41:19,530
bytte to værdier permanent.

932
00:41:19,530 --> 00:41:21,970
Så vi har brug for en anden måde
til rent faktisk at komme på dette,

933
00:41:21,970 --> 00:41:24,472
og vi skal være i stand til
faktisk løse dette problem.

934
00:41:24,472 --> 00:41:27,180
Og det viser out-- og vi vil komme
tilbage til denne særlige billede

935
00:41:27,180 --> 00:41:30,500
før long-- dette er en måde at
du måske tegne computerens hukommelse.

936
00:41:30,500 --> 00:41:31,460
Det er bare et rektangel.

937
00:41:31,460 --> 00:41:32,960
Du kunne tegne det noget
række måder, men det er

938
00:41:32,960 --> 00:41:35,740
bekvemt at tegne den som en
rektangel af følgende grund.

939
00:41:35,740 --> 00:41:40,040
>> Vi kommer til at starte i dag og videre
taler om den såkaldte stak.

940
00:41:40,040 --> 00:41:43,870
Og stakken er blot en luns
af RAM-- en luns af memory--

941
00:41:43,870 --> 00:41:47,100
der fungerer har adgang
til, når de kaldes.

942
00:41:47,100 --> 00:41:49,800
Og så viser det sig, at der på
den meget bunden af ​​denne stak

943
00:41:49,800 --> 00:41:53,590
er hvor alle Mains lokale variable
og org C og org V og alt det der

944
00:41:53,590 --> 00:41:56,950
kommer til at gå som standard. Og hvis Main
kalder nogle andre funktion som Swap,

945
00:41:56,950 --> 00:42:00,330
godt, er Swap kommer til at få en anden
lag af hukommelsen op over det.

946
00:42:00,330 --> 00:42:04,490
>> Og så bare for at give dig en hurtig overfladisk
billede af dette, hvis jeg gå over her--

947
00:42:04,490 --> 00:42:09,450
og lad mig afspejle dette på
overliggende som well-- hvad der virkelig har jeg,

948
00:42:09,450 --> 00:42:12,100
hvis vi interesserer kun om
bunden af ​​dette billede for nu,

949
00:42:12,100 --> 00:42:15,070
er, at når jeg kører et program
og Main bliver kaldt,

950
00:42:15,070 --> 00:42:18,330
Main gives et stykke
RAM i min computer, der er

951
00:42:18,330 --> 00:42:20,060
i bunden af ​​denne såkaldte stak.

952
00:42:20,060 --> 00:42:22,143
Og jeg har tænkt mig at tegne det
bevidst som en firkant.

953
00:42:22,143 --> 00:42:24,540
Så det er ligesom 32 bit eller fire bytes.

954
00:42:24,540 --> 00:42:28,790
Og hvis dette hovedfunktion har en
variabel kaldet X med en værdi på 1

955
00:42:28,790 --> 00:42:32,626
og det har en variabel kaldet
y med værdien 2, der er

956
00:42:32,626 --> 00:42:35,750
som at tage denne splint af hukommelse,
Vigtigste er blevet givet af operativsystemet

957
00:42:35,750 --> 00:42:38,850
systemet og dividere det op, så
den første lokal variabel går her,

958
00:42:38,850 --> 00:42:40,930
den anden går her, og det er det.

959
00:42:40,930 --> 00:42:45,590
>> Når Main kalder swap, swap
får sin egen skive hukommelse

960
00:42:45,590 --> 00:42:48,280
at vi vil trække på denne måde
fra operativsystemet,

961
00:42:48,280 --> 00:42:50,820
og det kommer til at have sin
egne lokale variabler baseret

962
00:42:50,820 --> 00:42:53,825
på vores implementering tidligere
med lokale variable en

963
00:42:53,825 --> 00:42:58,010
og b, der oprindeligt
få værdierne 1 og 2.

964
00:42:58,010 --> 00:43:00,450
Men så, så snart
Swap-koden henretter,

965
00:43:00,450 --> 00:43:03,760
og Lauren faktisk swaps den
EFT og mælk, hvad sker der?

966
00:43:03,760 --> 00:43:09,030
Nå, denne 2 bliver en 1, denne
1 er ved at blive en 2, og ved den måde,

967
00:43:09,030 --> 00:43:13,360
der er en temp variabel, der er at være
brugte det hele tiden, som til sidst

968
00:43:13,360 --> 00:43:14,470
går væk.

969
00:43:14,470 --> 00:43:16,720
Men det gør ikke noget
hvor meget arbejde du gør

970
00:43:16,720 --> 00:43:22,160
i denne linje of-- i denne hukommelsesplads,
x og y er helt uberørt.

971
00:43:22,160 --> 00:43:26,320
>> Så vi har brug for nogle måde at give
Swap og funktioner som det

972
00:43:26,320 --> 00:43:32,640
hemmelig adgang, hvis du vil, til
funktioner like-- til hukommelse som x og y.

973
00:43:32,640 --> 00:43:35,110
Så lad os tage et kig på
et eksempel, der hjælper

974
00:43:35,110 --> 00:43:38,220
os se præcis, hvad har været
foregår hele denne gang.

975
00:43:38,220 --> 00:43:40,284
Jeg har tænkt mig at gå videre
og åbne op sammenligne Zero.

976
00:43:40,284 --> 00:43:42,200
Og jeg har tænkt mig at lukke
vores debugger, jeg har tænkt mig

977
00:43:42,200 --> 00:43:44,360
at lukke denne skræmmende leder besked
det bare siger, vent et minut,

978
00:43:44,360 --> 00:43:45,800
du er midt debugging.

979
00:43:45,800 --> 00:43:48,383
Jeg har tænkt mig at skjule denne fane her
bare at gå tilbage til enkelhed.

980
00:43:48,383 --> 00:43:50,160
Så du skal ikke bekymre dig, hvis GDB bliver dræbt.

981
00:43:50,160 --> 00:43:53,910
Det betyder blot, at programmet har
blevet quit, bevidst i denne sag,

982
00:43:53,910 --> 00:43:54,820
af mig.

983
00:43:54,820 --> 00:43:57,700
>> Og nu sammenligne Zero gør dette.

984
00:43:57,700 --> 00:44:00,110
Jeg bruger CS50
bibliotek i standard I / O.

985
00:44:00,110 --> 00:44:04,319
Jeg har en hovedfunktion, der først
siger, sige noget, og får en streng.

986
00:44:04,319 --> 00:44:06,110
Så siger det igen og
får en anden streng.

987
00:44:06,110 --> 00:44:09,910
Og bemærk, at disse to strenge
kaldes s og t hhv.

988
00:44:09,910 --> 00:44:12,910
Og nu dette program, sammenligne
Zero, dens formål i livet,

989
00:44:12,910 --> 00:44:15,470
det er meningen at fortælle mig,
jeg skriver det samme?

990
00:44:15,470 --> 00:44:16,910
Og så jeg vil tilbage til uge et.

991
00:44:16,910 --> 00:44:19,950
Jeg bruger min lige lige operatør
som er kvaliteten operatør.

992
00:44:19,950 --> 00:44:22,220
Ikke tildelingsoperatoren,
operatøren lighed.

993
00:44:22,220 --> 00:44:23,890
Jeg er bare sammenligne s og t.

994
00:44:23,890 --> 00:44:27,470
>> Så lad os faktisk gå videre og gøre dette.

995
00:44:27,470 --> 00:44:32,680
Og jeg har tænkt mig at gå videre
og gøre Sammenlign Zero.

996
00:44:32,680 --> 00:44:35,110
Jeg har tænkt mig at gøre ./comparezero.

997
00:44:35,110 --> 00:44:37,150
Og jeg har tænkt mig at gå
videre og sige noget

998
00:44:37,150 --> 00:44:43,450
lignende, lad os gøre mor med små bogstaver
og hvad med mor med store bogstaver.

999
00:44:43,450 --> 00:44:45,034
Og selvfølgelig jeg skriver forskellige ting.

1000
00:44:45,034 --> 00:44:45,533
Okay.

1001
00:44:45,533 --> 00:44:46,570
Det kan forventes.

1002
00:44:46,570 --> 00:44:47,640
>> Lad os køre den igen.

1003
00:44:47,640 --> 00:44:49,740
Begge gange gør små bogstaver, små bogstaver.

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
Måske er det bare underligt, fordi
det er ikke lide min grammatik.

1008
00:44:55,804 --> 00:44:59,930
Så lad os gøre en hovedstad MOM,
hovedstad MOM, identiske.

1009
00:44:59,930 --> 00:45:01,490
Forskellige ting.

1010
00:45:01,490 --> 00:45:03,907
>> Så hvorfor er det?

1011
00:45:03,907 --> 00:45:06,240
Nå, hvad er faktisk at gå
på under kølerhjelmen her?

1012
00:45:06,240 --> 00:45:08,180
Så lad os gå tilbage over
her for blot et øjeblik

1013
00:45:08,180 --> 00:45:10,910
og overveje, hvad getString
er faktisk gør.

1014
00:45:10,910 --> 00:45:13,385
Når du ringer getString,
det er en funktion, vi

1015
00:45:13,385 --> 00:45:16,510
selv skrev og det på en måde får en
sekvens af tegn fra brugeren.

1016
00:45:16,510 --> 00:45:20,280
Og lad os antage, at den første
gang jeg kalder getString, der giver mig

1017
00:45:20,280 --> 00:45:21,930
en luns af hukommelse, der ser sådan ud.

1018
00:45:21,930 --> 00:45:26,990
Og hvis jeg har skrevet i alle små bogstaver
m-o-m-- og hvad der går efter det?

1019
00:45:26,990 --> 00:45:28,840
Bare en hurtig tilregnelighed check.

1020
00:45:28,840 --> 00:45:29,780
>> Backslash nul.

1021
00:45:29,780 --> 00:45:30,510
Vi ved, at.

1022
00:45:30,510 --> 00:45:32,784
Og huske, at vi spillede
rundt med Zamila navn

1023
00:45:32,784 --> 00:45:34,950
og en masse andre navne
da Rob var her søger

1024
00:45:34,950 --> 00:45:36,280
ved, hvad der foregår inde i hukommelsen.

1025
00:45:36,280 --> 00:45:37,780
Så den historie er præcis det samme.

1026
00:45:37,780 --> 00:45:40,160
Dette er, hvad getString
vender tilbage til mig.

1027
00:45:40,160 --> 00:45:44,780
Nu er min kode for et øjeblik siden gemt
returværdien af ​​getString

1028
00:45:44,780 --> 00:45:47,510
i en variabel kaldet s.

1029
00:45:47,510 --> 00:45:51,390
Og så anden gang, jeg kaldte det,
Det opbevares det i en variabel kaldet t.

1030
00:45:51,390 --> 00:45:55,070
>> Så hvis jeg går herovre, jeg har brug for
at tegne denne lokale variable--

1031
00:45:55,070 --> 00:45:59,610
og jeg generelt vil
tegne en streng som bare-- vi får

1032
00:45:59,610 --> 00:46:02,360
kalder det S-- som en lille firkant her.

1033
00:46:02,360 --> 00:46:09,760
Og nu, somehow-- hvordan gør mor
gå inde i denne variabel s?

1034
00:46:09,760 --> 00:46:12,010
Nå, er vi nødt til at gå tilbage
til første principper her.

1035
00:46:12,010 --> 00:46:15,660
Hvad der er getString egentlig tilbage?

1036
00:46:15,660 --> 00:46:19,030
>> Så det viser sig, at M-O-M
backslash nul, og et antal

1037
00:46:19,030 --> 00:46:22,364
af andre strenge i hukommelse som
Zamila og Rob eller Andy eller nogen andre,

1038
00:46:22,364 --> 00:46:24,280
er naturligvis i vores
computerens RAM eller hukommelse.

1039
00:46:24,280 --> 00:46:27,760
Og din RAM har like-- du har
en koncert RAM, to koncerter RAM,

1040
00:46:27,760 --> 00:46:30,860
eller en milliard eller to milliarder bytes,
eller måske endnu flere i disse dage.

1041
00:46:30,860 --> 00:46:34,070
Så lad os antage, for nutidens formål,
at det er ligegyldigt, hvordan vi nummer

1042
00:46:34,070 --> 00:46:36,640
dem, men vi kan nummerere hver
af disse milliarder eller to milliarder

1043
00:46:36,640 --> 00:46:37,880
eller fire milliarder byte.

1044
00:46:37,880 --> 00:46:42,240
>> Og lad os bare vilkårligt sige, at
dette er den første bid, andet bid,

1045
00:46:42,240 --> 00:46:43,380
tredje, fjerde.

1046
00:46:43,380 --> 00:46:46,570
Jeg bevidst ikke bruger nul for
i dag, men vi vil vende tilbage til.

1047
00:46:46,570 --> 00:46:49,570
Så med andre ord, hvis dette er
allerførste gang jeg bruger programmet

1048
00:46:49,570 --> 00:46:52,715
Jeg er lige ved at komme heldig og den første
bid er på placering en så to

1049
00:46:52,715 --> 00:46:53,590
derefter tre end fire.

1050
00:46:53,590 --> 00:46:57,430
Og hvis jeg holdt tegning, kasse nummer
to milliarder ville være vejen herovre.

1051
00:46:57,430 --> 00:47:02,200
>> Så hvad tror du da,
GetString faktisk vender tilbage?

1052
00:47:02,200 --> 00:47:06,010
Det er ikke returnere M-O-M backslash
nul i sig selv, fordi det klart

1053
00:47:06,010 --> 00:47:08,180
vil ikke passe i boksen, som jeg har tegnet.

1054
00:47:08,180 --> 00:47:11,210
Så hvad der ellers måtte getString faktisk
tilbage alle disse uger?

1055
00:47:11,210 --> 00:47:14,410

1056
00:47:14,410 --> 00:47:16,820
Svaret er på
bord her et sted.

1057
00:47:16,820 --> 00:47:20,390
Du kan ikke passe M-O-M omvendt skråstreg nul,
så hvad kan give mening i stedet?

1058
00:47:20,390 --> 00:47:23,424
Hvis du skulle være super dygtig, at sætte
på den såkaldte engineering hat,

1059
00:47:23,424 --> 00:47:24,340
hvad kunne du vender tilbage?

1060
00:47:24,340 --> 00:47:27,340
Hvad er den mindste mængde af information
du kunne vende tilbage, der ville stadig

1061
00:47:27,340 --> 00:47:30,610
lade dig finde M-O-M i hukommelsen?

1062
00:47:30,610 --> 00:47:31,270
Ja?

1063
00:47:31,270 --> 00:47:31,950
>> PUBLIKUM: One.

1064
00:47:31,950 --> 00:47:32,200
>> DAVID J. MALAN: One.

1065
00:47:32,200 --> 00:47:33,021
Og hvorfor en?

1066
00:47:33,021 --> 00:47:35,520
PUBLIKUM: Fordi det ville fortælle
dig, hvor at gå [uhørligt].

1067
00:47:35,520 --> 00:47:38,391

1068
00:47:38,391 --> 00:47:39,390
DAVID J. MALAN: Præcis.

1069
00:47:39,390 --> 00:47:44,300
Jeg vil blot returnere adressen
af strengen, som jeg har fået.

1070
00:47:44,300 --> 00:47:46,570
Adressen i dette
tilfælde er placering én.

1071
00:47:46,570 --> 00:47:51,280
Så hvad der virkelig bliver gemt i S--
og hver strengvariablen således far--

1072
00:47:51,280 --> 00:47:53,430
har netop været
adresse på den pågældende streng.

1073
00:47:53,430 --> 00:47:57,840
>> I mellemtiden, hvis jeg kalder
GetString en anden gang og jeg

1074
00:47:57,840 --> 00:48:03,300
skrive i bogstaveligt samme thing--
M-O-M med lowercase-- M-O-M

1075
00:48:03,300 --> 00:48:06,200
og en anden skråstreg nul,
og nu måske min programmets

1076
00:48:06,200 --> 00:48:09,820
kørt i et stykke tid, så måske dette
er 10, er det i lokation 11, er 12,

1077
00:48:09,820 --> 00:48:10,700
dette er 13.

1078
00:48:10,700 --> 00:48:13,590
De computere, der bruger nogle andre
hukommelse uanset årsagen.

1079
00:48:13,590 --> 00:48:18,172
Hvad nu går i mit andet
variabel i mit program t?

1080
00:48:18,172 --> 00:48:19,390
10.

1081
00:48:19,390 --> 00:48:20,050
Præcis.

1082
00:48:20,050 --> 00:48:23,910
>> Og så når vi ser på
kildekode af dette program

1083
00:48:23,910 --> 00:48:26,550
hvor jeg blot forsøger
at sammenligne de to værdier,

1084
00:48:26,550 --> 00:48:32,180
er S lig lig t, hvad er
det indlysende menneskelige svar?

1085
00:48:32,180 --> 00:48:34,890
Bare nej, fordi 1 ikke er lig 10.

1086
00:48:34,890 --> 00:48:36,861
Og så heri ligger en
mulighed for os virkelig

1087
00:48:36,861 --> 00:48:39,610
at bare gå tilbage til, igen, først
principper og tænke over, godt,

1088
00:48:39,610 --> 00:48:41,110
hvad der foregår under kølerhjelmen?

1089
00:48:41,110 --> 00:48:43,240
Vi har talt om
bits og bytes og hukommelse,

1090
00:48:43,240 --> 00:48:46,820
men det er faktisk nyttigt at forstå
fordi når du kalder getString,

1091
00:48:46,820 --> 00:48:50,280
selv om vi tænker på det er
tilbage M-O-M eller snor mor

1092
00:48:50,280 --> 00:48:53,120
eller Andy eller Zamila eller
lignende, teknisk

1093
00:48:53,120 --> 00:48:55,510
det er bare at returnere adressen
af denne chunk hukommelse.

1094
00:48:55,510 --> 00:48:56,910
>> Men det er OK.

1095
00:48:56,910 --> 00:49:00,570
Fordi hvordan kan jeg vide
hvor streng ender?

1096
00:49:00,570 --> 00:49:03,840
Hvis jeg kun har tænkt givet begyndelsen?

1097
00:49:03,840 --> 00:49:05,380
Nå, backslash nul, ikke?

1098
00:49:05,380 --> 00:49:08,800
Bare i lineær tid, jeg kan
udskrive med print def M-O-M.

1099
00:49:08,800 --> 00:49:11,820
Og så snart jeg ser omvendt skråstreg
nul, jeg er ligeglad, hvor jeg startede,

1100
00:49:11,820 --> 00:49:14,950
Jeg ved allerede implicit
hvor jeg skal ende.

1101
00:49:14,950 --> 00:49:18,700
>> Og så i dag markerer beginning-- og
lad mig gøre det dramatisk, fordi vi

1102
00:49:18,700 --> 00:49:21,800
gik igennem en masse problemer til
få disse her uddannelse wheels--

1103
00:49:21,800 --> 00:49:29,840
så i dag de støttehjul starter
at komme ud, og vi afslører på least--

1104
00:49:29,840 --> 00:49:31,373
>> [Applaus]

1105
00:49:31,373 --> 00:49:33,220

1106
00:49:33,220 --> 00:49:36,160
>> Det var værd at rejse
til Target morges, ja?

1107
00:49:36,160 --> 00:49:39,600
Så nu-- der er, viser det sig
ud, ikke sådan noget som streng.

1108
00:49:39,600 --> 00:49:41,140
String findes ikke.

1109
00:49:41,140 --> 00:49:43,760
Det er et synonym, som vi har haft
indersiden af ​​CS50 biblioteket.

1110
00:49:43,760 --> 00:49:48,660
Fremover vil vi begynde at kalde
s og t ikke strygere men char stjerner.

1111
00:49:48,660 --> 00:49:51,180
Og char stjerne vi får
drille hinanden inden længe.

1112
00:49:51,180 --> 00:49:53,510
Men det vil sige,
at selv hvis vi fortsætter

1113
00:49:53,510 --> 00:49:56,180
hjælp getString for nu,
teknisk jeg skulle

1114
00:49:56,180 --> 00:49:59,010
være at sige char stjerne og char stjerne.

1115
00:49:59,010 --> 00:50:01,720
>> Og det viser sig, hvad det stjerne
kommer til at betegne er noget

1116
00:50:01,720 --> 00:50:04,340
kaldes en pegepind eller en adresse.

1117
00:50:04,340 --> 00:50:06,110
Og i virkeligheden, en teaser
for, hvad der ligger forude

1118
00:50:06,110 --> 00:50:09,760
er denne 20 andet klip fra vores
ven Nick Parlante på Stanford

1119
00:50:09,760 --> 00:50:12,927
der, et godt stykke tid siden, tilbringer
et latterligt beløb af tid,

1120
00:50:12,927 --> 00:50:15,010
så godt jeg kan fortælle i hans
køkken eller hans kælder,

1121
00:50:15,010 --> 00:50:17,140
gør claymation
indføre til verden

1122
00:50:17,140 --> 00:50:20,010
en figur ved navn
Binky med hvem vi vil

1123
00:50:20,010 --> 00:50:22,010
indføres næste gang pointere.

1124
00:50:22,010 --> 00:50:24,588
Så her er et eksempel på, hvad der er at komme.

1125
00:50:24,588 --> 00:50:26,370
>> [VIDEO PLAYBACK]

1126
00:50:26,370 --> 00:50:27,510
>> -Hey, Binky.

1127
00:50:27,510 --> 00:50:28,260
Vågn op.

1128
00:50:28,260 --> 00:50:30,672
Det er tid til pointer sjov.

1129
00:50:30,672 --> 00:50:31,616
>> -Hvad er det?

1130
00:50:31,616 --> 00:50:33,032
Lær om pointers?

1131
00:50:33,032 --> 00:50:34,450
Åh, goody.

1132
00:50:34,450 --> 00:50:35,431
>> [END AFSPIL]

1133
00:50:35,431 --> 00:50:38,055
DAVID J. MALAN: Og på dette notat,
vi vil se dig på onsdag.

1134
00:50:38,055 --> 00:50:47,590

1135
00:50:47,590 --> 00:50:48,090
Okay.

1136
00:50:48,090 --> 00:50:48,740
Hvem er dans?

1137
00:50:48,740 --> 00:50:49,240
Kom nu.

1138
00:50:49,240 --> 00:50:50,330
Hvem er dans?

1139
00:50:50,330 --> 00:50:51,820
Skal jeg få det i gang?

1140
00:50:51,820 --> 00:50:53,770
Jeg vil få det i gang.

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øde fancy Moses.