1
00:00:00,000 --> 00:00:09,572

2
00:00:09,572 --> 00:00:12,030
ROB BOWDEN: Hej, jeg hedder Rob Bowden,
og lad os tale om quiz0.

3
00:00:12,030 --> 00:00:13,280

4
00:00:13,280 --> 00:00:14,545
>> Så første spørgsmål.

5
00:00:14,545 --> 00:00:17,750
Det er spørgsmålet om, hvor
du behov for at kode nummeret

6
00:00:17,750 --> 00:00:21,270
127 i de binære pærer.

7
00:00:21,270 --> 00:00:23,550
Hvis du ville, kunne du
gøre regelmæssig konvertering

8
00:00:23,550 --> 00:00:25,950
fra bi-- eller fra decimal til binær.

9
00:00:25,950 --> 00:00:28,300
Men det er sandsynligvis vil
til at tage en masse tid.

10
00:00:28,300 --> 00:00:31,750
Jeg mener, du kunne regne ud, at,
OK, 1 er i der, 2 er i der,

11
00:00:31,750 --> 00:00:33,650
4 er der, 8 er derinde.

12
00:00:33,650 --> 00:00:39,280
Nemmere måde, 127 er 128 minus én.

13
00:00:39,280 --> 00:00:42,013
Det længst til venstre pære er 128-bit.

14
00:00:42,013 --> 00:00:43,490

15
00:00:43,490 --> 00:00:47,860
Så 127 er virkelig bare alt
af de andre pærer,

16
00:00:47,860 --> 00:00:51,420
da det er den længst til venstre
pære minus 1.

17
00:00:51,420 --> 00:00:52,800
Det er det for det spørgsmål.

18
00:00:52,800 --> 00:00:54,060
>> Spørgsmål én.

19
00:00:54,060 --> 00:00:56,710
Så med 3 bit du kan
repræsenterer 8 forskellige værdier.

20
00:00:56,710 --> 00:01:01,000
Hvorfor er 7 den største ikke-negative
decimal heltal du kan repræsentere?

21
00:01:01,000 --> 00:01:04,050
Tja, hvis vi kun kan
repræsenterer 8 forskellige værdier,

22
00:01:04,050 --> 00:01:07,430
så hvad vi kommer til at være
repræsenterer er 0 til 7.

23
00:01:07,430 --> 00:01:08,745
0 fylder en af ​​værdierne.

24
00:01:08,745 --> 00:01:09,980

25
00:01:09,980 --> 00:01:11,190
>> Spørgsmål to.

26
00:01:11,190 --> 00:01:14,610
Med n bits, hvor mange særskilte
Værdierne kan du repræsenterer?

27
00:01:14,610 --> 00:01:19,080
Så med n bits, har du 2
mulige værdier for hver bit.

28
00:01:19,080 --> 00:01:22,300
Så vi har 2 mulige værdier for
den første bit, 2 mulige værdier

29
00:01:22,300 --> 00:01:24,450
for det andet, 2
muligt for den tredje.

30
00:01:24,450 --> 00:01:28,730
Og så er der 2 gange 2 gange 2, og
sidste ende svaret er 2 til n.

31
00:01:28,730 --> 00:01:30,010

32
00:01:30,010 --> 00:01:31,100
>> Spørgsmål tre.

33
00:01:31,100 --> 00:01:33,450
Hvad er 0x50 i binær?

34
00:01:33,450 --> 00:01:39,490
Så husk at hexadecimal har en meget
ligetil omdannelse til binær.

35
00:01:39,490 --> 00:01:43,180
Så her er vi bare nødt til at se på
5 og 0 uafhængigt.

36
00:01:43,180 --> 00:01:45,110
Så hvad er 5 i binær?

37
00:01:45,110 --> 00:01:48,400
0101, det er 1 bit og 4 bit.

38
00:01:48,400 --> 00:01:49,900
Hvad er 0 i binær?

39
00:01:49,900 --> 00:01:50,520
Ikke tricky.

40
00:01:50,520 --> 00:01:52,180
0000.

41
00:01:52,180 --> 00:01:54,970
Så bare sætte dem sammen, og
det er det fulde antal i binær.

42
00:01:54,970 --> 00:01:57,640
01010000.

43
00:01:57,640 --> 00:02:00,439
Og hvis du ønskede du kunne
tage det længst til venstre nul.

44
00:02:00,439 --> 00:02:01,105
Det er irrelevant.

45
00:02:01,105 --> 00:02:02,920

46
00:02:02,920 --> 00:02:05,733
>> Så alternativt
hvad er 0x50 i decimal?

47
00:02:05,733 --> 00:02:08,649
Hvis du ønskede, du could--, hvis du er
mere komfortabel med den binære,

48
00:02:08,649 --> 00:02:11,340
du kunne tage det binære svar
og konvertere det til decimal.

49
00:02:11,340 --> 00:02:13,870
Eller vi kunne bare huske
at hexadecimal.

50
00:02:13,870 --> 00:02:21,140
Således at 0 er i 0-th sted, og
5 er i 16 til det første sted.

51
00:02:21,140 --> 00:02:25,990
Så her har vi 5 gange 16 til
første plus 0 gange 16 til nul,

52
00:02:25,990 --> 00:02:27,520
er 80.

53
00:02:27,520 --> 00:02:29,710
Og hvis man så på
titel til spørgsmålet,

54
00:02:29,710 --> 00:02:32,920
det var CS 80, som var lidt af en
vink til svaret på dette problem.

55
00:02:32,920 --> 00:02:34,460

56
00:02:34,460 --> 00:02:35,420
>> Spørgsmål fem.

57
00:02:35,420 --> 00:02:40,320
Vi har denne Scratch script, som er
gentage 4 gange jordnøddesmør gelé.

58
00:02:40,320 --> 00:02:42,800
Så hvordan gør vi nu kode, der i C?

59
00:02:42,800 --> 00:02:47,730
Tja, vi har her-- den del med fed
er den eneste del, du var nødt til at gennemføre.

60
00:02:47,730 --> 00:02:51,950
Så vi har en 4 løkke, der er looping 4
gange, printf-ing jordnøddesmør gelé,

61
00:02:51,950 --> 00:02:53,910
med ny linje som problemet beder om.

62
00:02:53,910 --> 00:02:55,250

63
00:02:55,250 --> 00:02:57,490
>> Spørgsmål seks, en anden Scratch problem.

64
00:02:57,490 --> 00:03:00,210
Vi ser, at vi er i en evig løkke.

65
00:03:00,210 --> 00:03:05,000
Vi siger variablen i
og derefter inkrementering jeg med 1.

66
00:03:05,000 --> 00:03:09,580
Nu ønsker vi at gøre det i C. Der er
flere måder, vi kunne have gjort det.

67
00:03:09,580 --> 00:03:12,840
Her skete vi at kode
evigt loop som en while (sand).

68
00:03:12,840 --> 00:03:16,600
Så vi erklærer variablen i, bare
ligesom vi havde variabel jeg i Scratch.

69
00:03:16,600 --> 00:03:21,950
Erklære variablen i, og for evigt
while (true), siger vi variablen i.

70
00:03:21,950 --> 00:03:25,260
Så printf% I-- eller du kunne have brugt% d.

71
00:03:25,260 --> 00:03:27,985
Vi siger, at variable, og
så øg det, jeg ++.

72
00:03:27,985 --> 00:03:29,560

73
00:03:29,560 --> 00:03:30,830
>> Spørgsmål syv.

74
00:03:30,830 --> 00:03:35,560
Nu ønsker vi at gøre noget meget lignende
til Mario dot c fra problem angive én.

75
00:03:35,560 --> 00:03:39,110
Vi ønsker at udskrive disse hashtags,
vi ønsker at udskrive et fem

76
00:03:39,110 --> 00:03:40,700
med tre rektangel af disse hashes.

77
00:03:40,700 --> 00:03:41,770

78
00:03:41,770 --> 00:03:43,162
Så hvordan skal vi gøre det?

79
00:03:43,162 --> 00:03:45,370
Nå, vi giver dig en hel
bundt af kode, og du bare

80
00:03:45,370 --> 00:03:47,560
skal udfylde print grid-funktionen.

81
00:03:47,560 --> 00:03:49,540
>> Så hvad betyder PrintGrid se ud?

82
00:03:49,540 --> 00:03:51,480
Nå du er forbi
bredde og højde.

83
00:03:51,480 --> 00:03:53,520
Så vi har en ydre 4
loop, der er looping

84
00:03:53,520 --> 00:03:57,650
i alle rækkerne i denne
grid, at vi ønsker at udskrive.

85
00:03:57,650 --> 00:04:01,250
Så har vi den inter-indlejrede 4 loop,
det er udskrivning over hver kolonne.

86
00:04:01,250 --> 00:04:06,210
Så for hver række, vi udskriver for
hver søjle en enkelt hash.

87
00:04:06,210 --> 00:04:10,045
Så i slutningen af ​​rækken, vi udskriver en
enkelt ny linje til at gå til den næste række.

88
00:04:10,045 --> 00:04:11,420
Og det er det for hele nettet.

89
00:04:11,420 --> 00:04:12,810

90
00:04:12,810 --> 00:04:13,675
>> Spørgsmål otte.

91
00:04:13,675 --> 00:04:17,170
En funktion som PrintGrid siges at
har en bivirkning, men ikke en tilbagevenden

92
00:04:17,170 --> 00:04:17,670
værdi.

93
00:04:17,670 --> 00:04:19,209
Forklarer sondringen.

94
00:04:19,209 --> 00:04:23,080
Så dette er afhængig af dig at huske
hvad en bivirkning er.

95
00:04:23,080 --> 00:04:25,180
Tja, en tilbagevenden value--
vi kender PrintGrid ikke

96
00:04:25,180 --> 00:04:28,180
har returværdi, eftersom
lige her det siger ugyldig.

97
00:04:28,180 --> 00:04:31,150
Så noget, der returnerer void
ikke rigtig returnere noget.

98
00:04:31,150 --> 00:04:32,200

99
00:04:32,200 --> 00:04:33,620
Så hvad er den bivirkning?

100
00:04:33,620 --> 00:04:36,620
Tja, en bivirkning er
noget den slags fortsætter

101
00:04:36,620 --> 00:04:39,500
efter at funktionen ender
det var ikke lige vendt tilbage,

102
00:04:39,500 --> 00:04:41,340
og det var ikke bare fra indgangene.

103
00:04:41,340 --> 00:04:44,970
>> Så, for eksempel, kan vi
ændre en global variabel.

104
00:04:44,970 --> 00:04:46,590
Det ville være en bivirkning.

105
00:04:46,590 --> 00:04:49,000
I dette særlige tilfælde, en
meget vigtig bivirkning

106
00:04:49,000 --> 00:04:51,070
udskriver til skærmen.

107
00:04:51,070 --> 00:04:53,110
Så der er en bivirkning
at PrintGrid har.

108
00:04:53,110 --> 00:04:54,980
Vi udskriver disse ting på skærmen.

109
00:04:54,980 --> 00:04:56,370
Og du kan tænke på
at som en bivirkning,

110
00:04:56,370 --> 00:04:58,690
da det er noget,
fortsætter efter denne funktion slutter.

111
00:04:58,690 --> 00:05:01,481
Det er noget, der ikke er omfattet
af denne funktion, der i sidste ende

112
00:05:01,481 --> 00:05:03,380
bliver ændret,
indholdet af skærmen.

113
00:05:03,380 --> 00:05:05,200

114
00:05:05,200 --> 00:05:05,839
>> Spørgsmål ni.

115
00:05:05,839 --> 00:05:07,880
Overvej program nedenfor
hvortil linjenumre

116
00:05:07,880 --> 00:05:09,740
er blevet tilføjet for
skyld diskussion.

117
00:05:09,740 --> 00:05:13,480
Så i dette program, vi er lige
ringer getString, oplagring

118
00:05:13,480 --> 00:05:16,220
Denne variabel s, og derefter
udskriver variable s.

119
00:05:16,220 --> 00:05:16,720
OK.

120
00:05:16,720 --> 00:05:19,090
Så forklare, hvorfor line man er til stede.

121
00:05:19,090 --> 00:05:20,920
#include CS50 dot h.

122
00:05:20,920 --> 00:05:23,820
Hvorfor har vi brug for at # include CS50 dot h?

123
00:05:23,820 --> 00:05:26,180
Godt vi kalder den
GetString funktion,

124
00:05:26,180 --> 00:05:28,840
og getString defineres
i CS50 biblioteket.

125
00:05:28,840 --> 00:05:31,600
Så hvis vi ikke havde
#include CS50 dot h,

126
00:05:31,600 --> 00:05:35,760
vi ville få det underforstået erklæring
af getString funktion fejl

127
00:05:35,760 --> 00:05:36,840
fra compiler.

128
00:05:36,840 --> 00:05:40,110
Så vi er nødt til også at omfatte library--
vi er nødt til også at omfatte header fil,

129
00:05:40,110 --> 00:05:42,870
ellers compileren vil ikke
erkende, at getString eksisterer.

130
00:05:42,870 --> 00:05:44,380

131
00:05:44,380 --> 00:05:46,140
>> Forklar hvorfor linje to er til stede.

132
00:05:46,140 --> 00:05:47,890
Så standard io dot h.

133
00:05:47,890 --> 00:05:50,430
Det er præcis den samme
som det tidligere problem,

134
00:05:50,430 --> 00:05:53,310
undtagen i stedet for at behandle
GetString, vi taler om printf.

135
00:05:53,310 --> 00:05:56,654
Så hvis vi ikke sige, at vi har brug for
omfatte standard io dot h,

136
00:05:56,654 --> 00:05:58,820
så ville vi ikke være i stand
at bruge printf funktion,

137
00:05:58,820 --> 00:06:00,653
fordi oversætteren
ville ikke vide det.

138
00:06:00,653 --> 00:06:01,750

139
00:06:01,750 --> 00:06:05,260
>> Why-- hvad er betydningen
af ugyldig linje fire?

140
00:06:05,260 --> 00:06:08,010
Så her har vi int main (void).

141
00:06:08,010 --> 00:06:10,600
Det er bare at sige, at vi
ikke får nogen kommandolinie

142
00:06:10,600 --> 00:06:12,280
argumenter til main.

143
00:06:12,280 --> 00:06:17,390
Husk, at vi kunne sige int
vigtigste int argc string argv parentes.

144
00:06:17,390 --> 00:06:20,400
Så her er vi bare sige tomrum at sige vi
ignorerer kommandolinjeargumenter.

145
00:06:20,400 --> 00:06:21,840

146
00:06:21,840 --> 00:06:25,225
>> Forklare med hensyn til hukommelse, præcis
hvad getString på linje seks afkast.

147
00:06:25,225 --> 00:06:27,040

148
00:06:27,040 --> 00:06:31,640
GetString returnerer en blok af
hukommelse, en række tegn.

149
00:06:31,640 --> 00:06:34,870
Det er virkelig at vende tilbage en
markøren til det første tegn.

150
00:06:34,870 --> 00:06:37,170
Husk, at en streng er en char stjerne.

151
00:06:37,170 --> 00:06:41,360
Så s er en pointer til den første
karakter uanset strengen er

152
00:06:41,360 --> 00:06:43,510
at brugeren har indtastet på tastaturet.

153
00:06:43,510 --> 00:06:47,070
Og at hukommelsen sker for at være malloced,
således at hukommelsen er i hoben.

154
00:06:47,070 --> 00:06:49,080

155
00:06:49,080 --> 00:06:50,450
>> Spørgsmål 13.

156
00:06:50,450 --> 00:06:51,960
Overveje programmet nedenfor.

157
00:06:51,960 --> 00:06:55,579
Så alt dette program er at gøre
er printf-ing 1 divideret med 10.

158
00:06:55,579 --> 00:06:57,370
Så når kompileret og
henrettet, dette program

159
00:06:57,370 --> 00:07:01,170
udgange 0.0, selvom
1 divideret med 10 er 0,1.

160
00:07:01,170 --> 00:07:02,970
Så hvorfor er det 0,0?

161
00:07:02,970 --> 00:07:05,510
Nå, det er fordi
af heltalsdivision.

162
00:07:05,510 --> 00:07:08,580
So 1 er et helt tal, 10 er et heltal.

163
00:07:08,580 --> 00:07:11,980
So 1 divideret med 10, alt
behandles som heltal,

164
00:07:11,980 --> 00:07:16,380
og i C, når vi gør heltalsdivisioner,
vi trunkere kommaet.

165
00:07:16,380 --> 00:07:19,590
Så 1 divideret med 10
0, og så vi prøver

166
00:07:19,590 --> 00:07:24,410
at printe som en svømmer, så
nul udskrives som en float er 0,0.

167
00:07:24,410 --> 00:07:27,400
Og det er derfor, vi får 0,0.

168
00:07:27,400 --> 00:07:28,940
>> Overveje programmet nedenfor.

169
00:07:28,940 --> 00:07:31,280
Nu er vi udskriver 0.1.

170
00:07:31,280 --> 00:07:34,280
Så ingen heltalsdivisioner,
vi bare udskriver 0,1,

171
00:07:34,280 --> 00:07:37,100
men vi udskriver det
til 28 decimaler.

172
00:07:37,100 --> 00:07:41,810
Og vi får denne 0.1000, en hel flok
af nuller, 5 5 5, bla bla bla.

173
00:07:41,810 --> 00:07:45,495
Så spørgsmålet her er, hvorfor gør det
udskrive, at i stedet for nøjagtigt 0,1?

174
00:07:45,495 --> 00:07:46,620

175
00:07:46,620 --> 00:07:49,640
>> Så grunden her er nu
floating point unøjagtighed.

176
00:07:49,640 --> 00:07:53,410
Husk, at en float er kun 32 bits.

177
00:07:53,410 --> 00:07:57,540
Så vi kan kun repræsentere et endeligt antal
af floating point-værdier med de 32

178
00:07:57,540 --> 00:07:58,560
bit.

179
00:07:58,560 --> 00:08:01,760
Nå der er i sidste ende uendeligt
mange kommeværdier,

180
00:08:01,760 --> 00:08:04,940
og der er uendeligt mange flydende
pointværdier i mellem 0 og 1,

181
00:08:04,940 --> 00:08:07,860
og vi er naturligvis i stand til at
repræsenterer endnu flere værdier end.

182
00:08:07,860 --> 00:08:13,230
Så vi er nødt til at ofre for at
være i stand til at repræsentere de fleste værdier.

183
00:08:13,230 --> 00:08:16,960
>> Så en værdi som 0,1, tilsyneladende
Vi kan ikke repræsentere det nøjagtigt.

184
00:08:16,960 --> 00:08:22,500
Så i stedet for at repræsentere 0,1 vi gør
bedste vi kan repræsentere denne 0.100000 5 5

185
00:08:22,500 --> 00:08:23,260
5.

186
00:08:23,260 --> 00:08:26,306
Og det er temmelig tæt, men
for en masse ansøgninger

187
00:08:26,306 --> 00:08:28,430
du skal bekymre dig om
floating point unøjagtighed,

188
00:08:28,430 --> 00:08:30,930
fordi vi kan bare ikke repræsentere
alt flydende punkter nøjagtigt.

189
00:08:30,930 --> 00:08:32,500

190
00:08:32,500 --> 00:08:33,380
>> Spørgsmål 15.

191
00:08:33,380 --> 00:08:34,679
Betragt koden nedenfor.

192
00:08:34,679 --> 00:08:36,630
Vi er lige udskrivning 1 plus 1.

193
00:08:36,630 --> 00:08:38,289
Så der er ingen trick her.

194
00:08:38,289 --> 00:08:41,780
1 plus 1 evalueres til 2, og
så vi udskriver det.

195
00:08:41,780 --> 00:08:42,789
Dette blot udskriver 2.

196
00:08:42,789 --> 00:08:43,850

197
00:08:43,850 --> 00:08:44,700
>> Spørgsmål 16.

198
00:08:44,700 --> 00:08:49,450
Nu er vi udskriver karakter
1 plus tegnet 1.

199
00:08:49,450 --> 00:08:52,110
Så hvorfor gør dette ikke
udskrive det samme ting?

200
00:08:52,110 --> 00:08:57,680
Godt tegn 1 plus tegnet
1, tegnet 1 har ASCII værdi 49.

201
00:08:57,680 --> 00:09:04,840
Så dette er virkelig siger 49 plus 49, og
i sidste ende det kommer til at udskrive 98.

202
00:09:04,840 --> 00:09:06,130
Så det ikke udskrives 2.

203
00:09:06,130 --> 00:09:08,070

204
00:09:08,070 --> 00:09:09,271
>> Spørgsmål 17.

205
00:09:09,271 --> 00:09:11,520
Afslutte gennemførelsen
ulige nedenfor på en sådan måde

206
00:09:11,520 --> 00:09:14,615
at funktionen returnerer true hvis
n er ulige og falsk, hvis n er lige.

207
00:09:14,615 --> 00:09:16,710

208
00:09:16,710 --> 00:09:19,330
Dette er en stor formål
til mod operatøren.

209
00:09:19,330 --> 00:09:24,530
Så vi tager vores argument n,
hvis n mod 2 er lig med 1, og

210
00:09:24,530 --> 00:09:28,030
det betyder, at n delt
med 2 havde en rest.

211
00:09:28,030 --> 00:09:33,270
Hvis n divideret med 2 havde en rest, der
betyder, at n er ulige, så vi vender tilbage sandt.

212
00:09:33,270 --> 00:09:34,910
Else vi return false.

213
00:09:34,910 --> 00:09:39,070
Du kunne også have gjort n mod 2 ligemænd
nul, return false, ellers returnere sandt.

214
00:09:39,070 --> 00:09:41,600

215
00:09:41,600 --> 00:09:43,640
>> Overvej rekursiv funktion nedenfor.

216
00:09:43,640 --> 00:09:46,920
Så hvis n er mindre end eller
lig med 1, afkast 1,

217
00:09:46,920 --> 00:09:50,430
ellers tilbagevenden n gange f n minus 1.

218
00:09:50,430 --> 00:09:52,556
Så hvad er denne funktion?

219
00:09:52,556 --> 00:09:54,305
Nå, det er bare den
faktoriel funktion.

220
00:09:54,305 --> 00:09:55,410

221
00:09:55,410 --> 00:09:57,405
Dette er pænt repræsenteret
n faktoriel.

222
00:09:57,405 --> 00:09:58,720

223
00:09:58,720 --> 00:10:02,310
>> Så Spørgsmål 19 nu, vi ønsker at
tage denne rekursiv funktion.

224
00:10:02,310 --> 00:10:04,530
Vi ønsker at gøre det iterativ.

225
00:10:04,530 --> 00:10:05,874
Så hvordan gør vi det?

226
00:10:05,874 --> 00:10:07,790
Godt for de ansatte
opløsning, og igen er der

227
00:10:07,790 --> 00:10:11,090
flere måder, du kunne have gjort
at vi starter med dette int produkt

228
00:10:11,090 --> 00:10:11,812
er lig med 1.

229
00:10:11,812 --> 00:10:13,520
Og i hele
for-løkke, vil vi

230
00:10:13,520 --> 00:10:17,590
at multiplicere produktet til sidst
ender med fuld fakultetsværdien.

231
00:10:17,590 --> 00:10:21,870
Så for int jeg lig med 2, i er
mindre end eller lig med n, i ++.

232
00:10:21,870 --> 00:10:24,130
>> Du kan være undrende, hvorfor jeg er lig med 2.

233
00:10:24,130 --> 00:10:28,380
Nå, så husk at her har vi at
at sikre vores base case er korrekt.

234
00:10:28,380 --> 00:10:32,180
Så hvis n er mindre end eller lig
til 1, vi bare returnere 1.

235
00:10:32,180 --> 00:10:34,830
Så her over, vi starter ved jeg lig med 2.

236
00:10:34,830 --> 00:10:39,090
Tja, hvis jeg var 1, så til-- eller
hvis n var 1, så for-løkken

237
00:10:39,090 --> 00:10:40,600
ville ikke udføre overhovedet.

238
00:10:40,600 --> 00:10:43,190
Og så ville vi bare
tilbagevenden produkt, som er 1.

239
00:10:43,190 --> 00:10:45,920
Tilsvarende, hvis n var
noget mindre end 1--

240
00:10:45,920 --> 00:10:49,290
hvis det var 0, negative 1, whatever--
vi ville stadig tilbage 1,

241
00:10:49,290 --> 00:10:52,260
som er det præcis
rekursiv version gør.

242
00:10:52,260 --> 00:10:54,660
>> Nu, hvis n er større
end 1, så vi vil

243
00:10:54,660 --> 00:10:56,550
at gøre mindst én
iteration af denne løkke.

244
00:10:56,550 --> 00:11:00,630
Så lad os sige n er 5, så er vi
vil gøre produktets gange lig med 2.

245
00:11:00,630 --> 00:11:02,165
Så nu vare er 2.

246
00:11:02,165 --> 00:11:04,040
Nu skal vi til at gøre
produkt- gange lig med 3.

247
00:11:04,040 --> 00:11:04,690
Nu er det 6.

248
00:11:04,690 --> 00:11:07,500
Produkt gange svarer til 4, nu er det 24.

249
00:11:07,500 --> 00:11:10,420
Produkt gange lig 5, nu er det 120.

250
00:11:10,420 --> 00:11:16,730
Så i sidste ende, vi vender tilbage
120, som er korrekt 5 factorial.

251
00:11:16,730 --> 00:11:17,510
>> Spørgsmål 20.

252
00:11:17,510 --> 00:11:22,480
Dette er den ene, hvor du nødt til at udfylde
i denne tabel med en given algoritme,

253
00:11:22,480 --> 00:11:25,735
noget, som vi har set, at
passer disse algoritmiske løb

254
00:11:25,735 --> 00:11:28,060
gange disse asymptotiske run Times.

255
00:11:28,060 --> 00:11:33,270
Så hvad er en algoritme,
er omega på 1, men store O n?

256
00:11:33,270 --> 00:11:35,970
Så der kan være uendeligt
mange svar her.

257
00:11:35,970 --> 00:11:39,790
Den ene, som vi har set nok mest
ofte er bare lineær søgning.

258
00:11:39,790 --> 00:11:42,050
>> Så i bedste fald
scenarie, elementet er vi

259
00:11:42,050 --> 00:11:44,050
efter på
begyndelsen af ​​listen

260
00:11:44,050 --> 00:11:47,400
og så i omega på 1 trin
den første ting, vi kontrollere,

261
00:11:47,400 --> 00:11:49,740
vi bare straks at vende tilbage
at vi fandt varen.

262
00:11:49,740 --> 00:11:52,189
I det værst tænkelige scenarie,
elementet er i slutningen,

263
00:11:52,189 --> 00:11:53,730
eller varen ikke er på listen overhovedet.

264
00:11:53,730 --> 00:11:56,700
Så vi nødt til at søge
hele listen, alle n

265
00:11:56,700 --> 00:11:58,480
elementer, og det er derfor, det er o n.

266
00:11:58,480 --> 00:11:59,670

267
00:11:59,670 --> 00:12:04,880
>> Så nu er det noget, der er både
omega n log n, og store O n log n.

268
00:12:04,880 --> 00:12:08,650
Nå de mest relevante ting
vi har set her er Mergesort.

269
00:12:08,650 --> 00:12:12,950
Så Mergesort husk,
er i sidste ende theta

270
00:12:12,950 --> 00:12:16,920
n log n, hvor theta er defineret
hvis begge omega og store O er de samme.

271
00:12:16,920 --> 00:12:17,580
Både n log n.

272
00:12:17,580 --> 00:12:18,690

273
00:12:18,690 --> 00:12:21,970
>> Hvad er noget, der er omega
n og O n kvadreret?

274
00:12:21,970 --> 00:12:23,990
Nå, igen er der
flere mulige svar.

275
00:12:23,990 --> 00:12:26,440
Her sker vi sige boble slags.

276
00:12:26,440 --> 00:12:28,840
Indsættelsessortering vil også arbejde her.

277
00:12:28,840 --> 00:12:31,400
Husk, at Boblesortering
har denne optimering, hvor

278
00:12:31,400 --> 00:12:34,630
hvis du er i stand til at få
gennem hele listen

279
00:12:34,630 --> 00:12:37,402
uden at gøre
eventuelle swaps, så godt,

280
00:12:37,402 --> 00:12:40,110
kan vi straks returnere det
listen blev sorteret til at begynde med.

281
00:12:40,110 --> 00:12:43,185
Så i bedste fald,
det er bare omega n.

282
00:12:43,185 --> 00:12:45,960
Hvis det er ikke bare et pænt
sorteret liste til at begynde med,

283
00:12:45,960 --> 00:12:48,270
så har vi O n kvadreret swaps.

284
00:12:48,270 --> 00:12:49,330

285
00:12:49,330 --> 00:12:55,610
Og endelig har vi valg Sorter
for n kvadreret, både omega og store O.

286
00:12:55,610 --> 00:12:56,850
>> Spørgsmål 21.

287
00:12:56,850 --> 00:12:58,870
Hvad er heltalsoverløb?

288
00:12:58,870 --> 00:13:02,160
Godt igen svarende til tidligere,
vi kun har endeligt mange bits

289
00:13:02,160 --> 00:13:04,255
at repræsentere et heltal,
Så måske 32 bits.

290
00:13:04,255 --> 00:13:06,300

291
00:13:06,300 --> 00:13:09,180
Lad os sige, at vi har en underskrevet heltal.

292
00:13:09,180 --> 00:13:12,800
Så i sidste ende den højeste
positivt tal, vi kan repræsentere

293
00:13:12,800 --> 00:13:15,910
er 2 til 31 minus 1.

294
00:13:15,910 --> 00:13:19,370
Så hvad sker der, hvis vi forsøger at
inkrementér derefter at heltal?

295
00:13:19,370 --> 00:13:25,320
Nå, vi kommer til at gå fra 2 til 31
minus 1, hele vejen ned til negativ 2

296
00:13:25,320 --> 00:13:26,490
til 31.

297
00:13:26,490 --> 00:13:29,470
Så dette heltalsoverløb er
når du holder forøgelse,

298
00:13:29,470 --> 00:13:32,330
og i sidste ende kan du ikke
få nogen højere, og det bare

299
00:13:32,330 --> 00:13:34,520
wraps hele vejen tilbage
rundt til en negativ værdi.

300
00:13:34,520 --> 00:13:35,850

301
00:13:35,850 --> 00:13:37,779
>> Hvad med en buffer overflow?

302
00:13:37,779 --> 00:13:39,820
Så en buffer overflow--
huske, hvad en buffer er.

303
00:13:39,820 --> 00:13:41,000
Det er bare en luns af hukommelse.

304
00:13:41,000 --> 00:13:43,350
Noget som et array er en buffer.

305
00:13:43,350 --> 00:13:46,120
Så en buffer overflow er, når
du forsøger at få adgang til hukommelse

306
00:13:46,120 --> 00:13:47,880
efter udgangen af ​​det array.

307
00:13:47,880 --> 00:13:50,410
Så hvis du har en
vifte af størrelse 5 og du

308
00:13:50,410 --> 00:13:53,700
forsøger at få adgang vifte beslag
5 eller beslag 6 eller beslag 7

309
00:13:53,700 --> 00:13:56,610
eller noget ud over det
ende, eller endog noget

310
00:13:56,610 --> 00:14:00,790
below-- række beslag negativ 1--
alle af dem er bufferoverløb.

311
00:14:00,790 --> 00:14:02,810
Du rører hukommelse i dårlige måder.

312
00:14:02,810 --> 00:14:04,090

313
00:14:04,090 --> 00:14:04,730
>> Spørgsmål 23.

314
00:14:04,730 --> 00:14:05,760

315
00:14:05,760 --> 00:14:09,100
Så i denne ene, du har brug for
at gennemføre strlen.

316
00:14:09,100 --> 00:14:11,630
Og vi fortælle dig, at du kan
antage s vil ikke være null,

317
00:14:11,630 --> 00:14:13,790
så du ikke behøver at
gøre enhver kontrol for null.

318
00:14:13,790 --> 00:14:16,190
Og der er flere måder
du kunne have gjort dette.

319
00:14:16,190 --> 00:14:18,440
Her er vi bare tage det ligetil.

320
00:14:18,440 --> 00:14:21,780
Vi starter med en tæller, n. n er
tælle hvor mange tegn der er.

321
00:14:21,780 --> 00:14:25,560
Så vi starter på 0, og så vi
gentage hele listen.

322
00:14:25,560 --> 00:14:29,092
>> Er s beslag 0 svarer til den
null terminator karakter?

323
00:14:29,092 --> 00:14:31,425
Husk, vi leder efter
null terminator karakter

324
00:14:31,425 --> 00:14:33,360
at bestemme hvor længe vores streng.

325
00:14:33,360 --> 00:14:35,890
Der vil afslutte
alle relevante streng.

326
00:14:35,890 --> 00:14:39,400
Så er s beslag 0 lig
til null terminator?

327
00:14:39,400 --> 00:14:42,850
Hvis det ikke er, så vi kommer til at
se på s beslag 1, s beslag 2.

328
00:14:42,850 --> 00:14:45,050
Vi holde gå, indtil vi
finde den null terminator.

329
00:14:45,050 --> 00:14:48,580
Når vi har fundet det, så n indeholder
den totale længde af strengen,

330
00:14:48,580 --> 00:14:49,942
og vi kan bare returnere det.

331
00:14:49,942 --> 00:14:51,180

332
00:14:51,180 --> 00:14:51,865
>> Spørgsmål 24.

333
00:14:51,865 --> 00:14:53,010

334
00:14:53,010 --> 00:14:56,050
Så dette er den ene, hvor du
nødt til at gøre afvejning.

335
00:14:56,050 --> 00:14:59,810
Så en ting er god i én
måde, men på hvilken måde er det dårligt?

336
00:14:59,810 --> 00:15:02,980
Så her, Mergesort tendens til
være hurtigere end boble slags.

337
00:15:02,980 --> 00:15:06,530
Når det er sagt at-- godt, der
er flere svar her.

338
00:15:06,530 --> 00:15:12,930
Men det vigtigste er, at Boblesortering
er omega n for en sorterede liste.

339
00:15:12,930 --> 00:15:14,950
>> Husk, at tabellen vi lige har set tidligere.

340
00:15:14,950 --> 00:15:17,600
Så boble sorterer omega
n, i bedste fald

341
00:15:17,600 --> 00:15:20,010
er det i stand til bare at gå over
listen gang, bestemme

342
00:15:20,010 --> 00:15:22,270
hey denne ting er allerede
sorteret, og vende tilbage.

343
00:15:22,270 --> 00:15:25,960
Mergesort, uanset hvad
du gør, er omega n log n.

344
00:15:25,960 --> 00:15:29,200
Så for sorterede liste, boble
sortere kommer til at være hurtigere.

345
00:15:29,200 --> 00:15:30,870

346
00:15:30,870 --> 00:15:32,430
>> Nu hvad hægtede lister?

347
00:15:32,430 --> 00:15:36,070
Så en sammenkædet liste kan vokse og krympe
til at passe så mange elementer efter behov.

348
00:15:36,070 --> 00:15:38,489
Når det er sagt at-- så
normalt direkte sammenligning

349
00:15:38,489 --> 00:15:40,280
vil være en sammenkædet
liste med et array.

350
00:15:40,280 --> 00:15:41,600

351
00:15:41,600 --> 00:15:44,050
Så selvom arrays kan
let vokse og skrumpe

352
00:15:44,050 --> 00:15:47,130
til at passe så mange elementer
efter behov, liste en sammenkædet

353
00:15:47,130 --> 00:15:49,600
sammenlignet med en array-- en
matrix har random access.

354
00:15:49,600 --> 00:15:52,960
Vi kan indekset i enhver
særlige element i arrayet.

355
00:15:52,960 --> 00:15:56,430
>> Så for en linket liste, kan vi ikke
bare gå til det femte element,

356
00:15:56,430 --> 00:16:00,260
Vi er nødt til at krydse fra begyndelsen
indtil vi kommer til det femte element.

357
00:16:00,260 --> 00:16:03,990
Og det kommer til at forhindre os
gør noget lignende binær søgning.

358
00:16:03,990 --> 00:16:08,150
Apropos binær søgning, binær søgning
tendens til at være hurtigere end lineær søgning.

359
00:16:08,150 --> 00:16:11,120
Sagt at--
så er en mulig ting

360
00:16:11,120 --> 00:16:13,380
er, at du ikke kan gøre binær
søge på hægtede lister,

361
00:16:13,380 --> 00:16:14,730
du kan kun gøre det på arrays.

362
00:16:14,730 --> 00:16:18,030
Men sandsynligvis endnu vigtigere,
du kan ikke gøre binær søgning

363
00:16:18,030 --> 00:16:20,690
på en matrix, der ikke er sorteret.

364
00:16:20,690 --> 00:16:23,990
Upfront du måske brug for at sortere
array, og først derefter kan

365
00:16:23,990 --> 00:16:25,370
du gør binær søgning.

366
00:16:25,370 --> 00:16:27,660
Så hvis dine ting er ikke
sorterede til at begynde med,

367
00:16:27,660 --> 00:16:29,250
så lineær søgning kunne være hurtigere.

368
00:16:29,250 --> 00:16:30,620

369
00:16:30,620 --> 00:16:31,740
>> Spørgsmål 27.

370
00:16:31,740 --> 00:16:34,770
Så overveje programmet nedenfor,
som vil være i det næste lysbillede.

371
00:16:34,770 --> 00:16:37,790
Og dette er den ene, hvor vi er
lyst til at udtrykkeligt fremgår,

372
00:16:37,790 --> 00:16:39,980
værdierne for forskellige variable.

373
00:16:39,980 --> 00:16:41,990
Så lad os se på det.

374
00:16:41,990 --> 00:16:43,160
>> Så line den ene.

375
00:16:43,160 --> 00:16:45,457
Vi har int x er lig med 1.

376
00:16:45,457 --> 00:16:47,040
Det er den eneste ting, der er sket.

377
00:16:47,040 --> 00:16:50,440
Så på linje et, vi ser i vores
tabel, at y, a, b, og tmp er alle

378
00:16:50,440 --> 00:16:51,540
mørklagt.

379
00:16:51,540 --> 00:16:52,280
Så hvad er x?

380
00:16:52,280 --> 00:16:53,860
Nå vi bare sætte det lig med 1.

381
00:16:53,860 --> 00:16:55,020

382
00:16:55,020 --> 00:16:58,770
Og derefter linje to, ja,
ser vi, at y er sat til 2,

383
00:16:58,770 --> 00:17:00,550
og tabellen er allerede
udfyldes for os.

384
00:17:00,550 --> 00:17:03,040
Så x er 1 og y er 2.

385
00:17:03,040 --> 00:17:05,890
>> Nu linje tre, men vi er nu
inde i swap-funktion.

386
00:17:05,890 --> 00:17:07,560
Hvad gjorde vi passerer at bytte?

387
00:17:07,560 --> 00:17:11,609
Vi passerede tegnet x for
a, og tegnet y for f.

388
00:17:11,609 --> 00:17:15,160
Hvor problemet tidligere
erklærede, at adressen på x

389
00:17:15,160 --> 00:17:17,520
er 0x10, og adressen på y er 0x14.

390
00:17:17,520 --> 00:17:18,970

391
00:17:18,970 --> 00:17:21,909
Så a og b er lig med
0x10 og 0x14 hhv.

392
00:17:21,909 --> 00:17:23,670

393
00:17:23,670 --> 00:17:26,250
>> Nu ved linie tre, hvad er x og y?

394
00:17:26,250 --> 00:17:28,554
Nå, har intet ændret sig
om x og y på dette punkt.

395
00:17:28,554 --> 00:17:30,470
Selvom de er
inde i en main stakramme,

396
00:17:30,470 --> 00:17:32,469
de stadig har samme
værdier, som de gjorde før.

397
00:17:32,469 --> 00:17:34,030
Vi har ikke ændret noget hukommelse.

398
00:17:34,030 --> 00:17:35,710
Så x er 1, y er 2.

399
00:17:35,710 --> 00:17:36,550

400
00:17:36,550 --> 00:17:37,050
Ok.

401
00:17:37,050 --> 00:17:40,300
Så nu vi sagde int tmp lig stjerne en.

402
00:17:40,300 --> 00:17:44,410
Så på linje fire, alt
er den samme bortset tmp.

403
00:17:44,410 --> 00:17:47,130
Vi har ikke ændret nogle værdier
af noget bortset fra tmp.

404
00:17:47,130 --> 00:17:49,230
Vi sætter tmp lig stjerne en.

405
00:17:49,230 --> 00:17:50,620
Hvad er stjernen?

406
00:17:50,620 --> 00:17:56,240
Tja, en punkter til x, så stjerne en
vil lige x, som er 1.

407
00:17:56,240 --> 00:18:00,080
Så alt er kopieret
ned og tmp er sat til 1.

408
00:18:00,080 --> 00:18:01,110
>> Nu den næste linje.

409
00:18:01,110 --> 00:18:03,380
Stjerne a er lig stjernede b.

410
00:18:03,380 --> 00:18:10,000
Så ved linje five-- godt igen, alt
er den samme, bortset fra hvad stjernen er.

411
00:18:10,000 --> 00:18:10,830
Hvad er stjernen?

412
00:18:10,830 --> 00:18:13,720
Godt, vi lige sagt stjerne a er x.

413
00:18:13,720 --> 00:18:16,400
Så vi er ved at ændre x til lige stjernede b.

414
00:18:16,400 --> 00:18:18,960
Hvad er stjernede b? y. B peger på y.

415
00:18:18,960 --> 00:18:21,030
Så stjerne b er y.

416
00:18:21,030 --> 00:18:25,140
Så vi indstillingen x er lig med y,
og alt andet er det samme.

417
00:18:25,140 --> 00:18:29,130
Så vi ser i den næste række, at x er nu
2, og resten er bare kopieret ned.

418
00:18:29,130 --> 00:18:31,120
>> Nu i den næste linje, stjernede b lig tmp.

419
00:18:31,120 --> 00:18:34,740
Godt, vi lige sagt stjerne b er y,
så vi indstille y lig med tmp.

420
00:18:34,740 --> 00:18:37,450
Alt andet er det samme,
så alt bliver kopieret ned.

421
00:18:37,450 --> 00:18:42,050
Vi indstilling y lig med TMP, hvilket er
en, og alt andet er det samme.

422
00:18:42,050 --> 00:18:43,210
>> Nu endelig linje syv.

423
00:18:43,210 --> 00:18:44,700
Vi er tilbage i den vigtigste funktion.

424
00:18:44,700 --> 00:18:46,350
Vi er ude efter swap er færdig.

425
00:18:46,350 --> 00:18:48,972
Vi har mistet a, b, og
tmp, men i sidste ende vi

426
00:18:48,972 --> 00:18:51,180
ikke ændre nogen værdier
noget på dette punkt,

427
00:18:51,180 --> 00:18:52,800
vi bare kopiere x og y ned.

428
00:18:52,800 --> 00:18:56,490
Og vi ser, at x og y er
nu 2 og 1 i stedet for 1 og 2.

429
00:18:56,490 --> 00:18:58,160
Swappen har med succes udført.

430
00:18:58,160 --> 00:18:59,500

431
00:18:59,500 --> 00:19:00,105
>> Spørgsmål 28.

432
00:19:00,105 --> 00:19:01,226

433
00:19:01,226 --> 00:19:03,100
Antag, at du støder på
fejlmeddelelser

434
00:19:03,100 --> 00:19:06,790
nedenfor i kontortiden
næste år som en CA eller TF.

435
00:19:06,790 --> 00:19:08,930
Rådgive, hvordan du løser hver af disse fejl.

436
00:19:08,930 --> 00:19:11,160
Så udefineret reference til getString.

437
00:19:11,160 --> 00:19:12,540
Hvorfor kunne du se det?

438
00:19:12,540 --> 00:19:15,380
Tja, hvis en elev bruger
GetString i deres kode,

439
00:19:15,380 --> 00:19:20,310
de har ordentligt hash inkluderet CS50
dot h at omfatte CS50 biblioteket.

440
00:19:20,310 --> 00:19:22,380
>> Nå, hvad gør de
nødt til at rette fejlen?

441
00:19:22,380 --> 00:19:26,810
De har brug for at gøre en bindestreg lcs50 på
kommandolinjen når de kompilering.

442
00:19:26,810 --> 00:19:29,501
Så hvis de ikke kan passere
klang dash lcs50, de er

443
00:19:29,501 --> 00:19:32,000
ikke kommer til at have den faktiske
kode, der implementerer getString.

444
00:19:32,000 --> 00:19:33,190

445
00:19:33,190 --> 00:19:34,170
>> Spørgsmål 29.

446
00:19:34,170 --> 00:19:36,190
Implicit erklære
bibliotek funktion strlen.

447
00:19:36,190 --> 00:19:37,550

448
00:19:37,550 --> 00:19:40,360
Nå det nu, har de ikke
gjort korrekt hash omfatter.

449
00:19:40,360 --> 00:19:41,440

450
00:19:41,440 --> 00:19:45,410
I dette særlige tilfælde, headerfilen
de skal omfatte, er streng dot h

451
00:19:45,410 --> 00:19:48,710
og med streng dot h, nu
den student-- nu compiler

452
00:19:48,710 --> 00:19:51,750
har adgang til
erklæringer om strlen,

453
00:19:51,750 --> 00:19:54,120
og det ved, at din kode
bruger StrLen korrekt.

454
00:19:54,120 --> 00:19:55,380

455
00:19:55,380 --> 00:19:56,580
>> Spørgsmål 30.

456
00:19:56,580 --> 00:20:00,240
Flere procent konverteringer
end data argumenter.

457
00:20:00,240 --> 00:20:01,540
Så hvad er det?

458
00:20:01,540 --> 00:20:06,470
Nå huske, at disse procent
signs-- hvordan de er relevante for printf.

459
00:20:06,470 --> 00:20:08,890
Så i printf vi måske percent--
vi måske udskrive noget

460
00:20:08,890 --> 00:20:11,380
ligesom procent i backslash n.

461
00:20:11,380 --> 00:20:15,310
Eller vi kan printe ligesom procent i,
rum, procent i, plads, procent i.

462
00:20:15,310 --> 00:20:18,950
Så for hver af dem,
procenttegn, vi har brug for

463
00:20:18,950 --> 00:20:21,560
at passere en variabel i slutningen af ​​printf.

464
00:20:21,560 --> 00:20:26,980
>> Så hvis vi siger printf paren procent
Jeg backslash n nære paren,

465
00:20:26,980 --> 00:20:30,270
godt, siger vi, at vi er
vil udskrive et heltal,

466
00:20:30,270 --> 00:20:33,970
men så har vi ikke passere printf
et heltal til rent faktisk at udskrive.

467
00:20:33,970 --> 00:20:37,182
Så her mere procent
konverteringer end data argumenter?

468
00:20:37,182 --> 00:20:39,390
Det er at sige, at vi har
en hel bunke af procenter,

469
00:20:39,390 --> 00:20:42,445
og vi har ikke nok variabler
til faktisk at udfylde disse procenter.

470
00:20:42,445 --> 00:20:44,850

471
00:20:44,850 --> 00:20:50,010
>> Og så absolut, for spørgsmål 31,
helt tabt 40 bytes i en blokke.

472
00:20:50,010 --> 00:20:52,350
Så dette er en Valgrind fejl.

473
00:20:52,350 --> 00:20:54,720
Det siger, at
et eller andet sted i din kode,

474
00:20:54,720 --> 00:20:59,010
du har en fordeling, der er 40
bytes store, så du malloced 40 bytes,

475
00:20:59,010 --> 00:21:00,515
og du aldrig befriet det.

476
00:21:00,515 --> 00:21:02,480

477
00:21:02,480 --> 00:21:05,140
Mest sandsynligt, du bare har brug for
at finde nogle hukommelsesfejl,

478
00:21:05,140 --> 00:21:07,650
og finde, hvor du har brug for
frigøre denne blok af hukommelse.

479
00:21:07,650 --> 00:21:08,780

480
00:21:08,780 --> 00:21:11,910
>> Og spørgsmål 32,
ugyldig write af størrelse 4.

481
00:21:11,910 --> 00:21:13,250
Igen dette er en Valgrind fejl.

482
00:21:13,250 --> 00:21:15,440
Dette behøver ikke at gøre
med memory leaks nu.

483
00:21:15,440 --> 00:21:20,750
Dette er mest likely-- Jeg mener, det er
en slags ugyldige hukommelse rettigheder.

484
00:21:20,750 --> 00:21:23,270
Og sandsynligvis dette er nogle
slags buffer overflow.

485
00:21:23,270 --> 00:21:26,560
Hvor du har en array, måske
et heltal array, og lad os

486
00:21:26,560 --> 00:21:30,115
sige, det er af størrelse 5, og du
prøve at røre række beslag 5.

487
00:21:30,115 --> 00:21:34,150
Så hvis du prøver at skrive til denne
værdi, det er ikke et stykke af hukommelse

488
00:21:34,150 --> 00:21:37,440
at du rent faktisk har adgang til, og
så du kommer til at få denne fejl,

489
00:21:37,440 --> 00:21:39,272
siger ugyldig write størrelse 4.

490
00:21:39,272 --> 00:21:42,480
Valgrind kommer til at genkende dig er
forsøger at røre hukommelse uhensigtsmæssigt.

491
00:21:42,480 --> 00:21:43,980
>> Og det er det for quiz0.

492
00:21:43,980 --> 00:21:47,065
Jeg er Rob Bowden, og det er CS50.

493
00:21:47,065 --> 00:21:51,104