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

2
00:00:09,572 --> 00:00:12,030
ROB BOWDEN: Hej, jag är Rob Bowden,
och låt oss tala om quiz0.

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

4
00:00:13,280 --> 00:00:14,545
>> Så första frågan.

5
00:00:14,545 --> 00:00:17,750
Detta är den fråga där
du behövs för att koda numret

6
00:00:17,750 --> 00:00:21,270
127 i de binära glödlampor.

7
00:00:21,270 --> 00:00:23,550
Om du ville, du kunde
gör den vanliga konvertering

8
00:00:23,550 --> 00:00:25,950
från bi-- eller från decimal till binär.

9
00:00:25,950 --> 00:00:28,300
Men det är förmodligen kommer
att ta en hel del tid.

10
00:00:28,300 --> 00:00:31,750
Jag menar, du kan räkna ut det,
OK, 1 är det, 2 är där,

11
00:00:31,750 --> 00:00:33,650
4 är där, är där 8.

12
00:00:33,650 --> 00:00:39,280
Enklare sätt är 127 128 minus ett.

13
00:00:39,280 --> 00:00:42,013
Den längst till vänster glödlampa är den 128-bit.

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

15
00:00:43,490 --> 00:00:47,860
Så 127 är egentligen bara alla
andra glödlampor,

16
00:00:47,860 --> 00:00:51,420
eftersom det är längst till vänster
glödlampa minus ett.

17
00:00:51,420 --> 00:00:52,800
Det var allt för denna fråga.

18
00:00:52,800 --> 00:00:54,060
>> Fråga ett.

19
00:00:54,060 --> 00:00:56,710
Så med 3 bitar som du kan
representerar 8 olika värden.

20
00:00:56,710 --> 00:01:01,000
Varför är då 7 den största icke-negativ
decimalt heltal du kan representera?

21
00:01:01,000 --> 00:01:04,050
Tja, om vi bara kan
representerar 8 olika värden,

22
00:01:04,050 --> 00:01:07,430
vad vi ska bli
representerar är 0 till 7.

23
00:01:07,430 --> 00:01:08,745
0 tar upp ett av värdena.

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

25
00:01:09,980 --> 00:01:11,190
>> Fråga två.

26
00:01:11,190 --> 00:01:14,610
Med n bitar, hur många distinkta
värden kan du representerar?

27
00:01:14,610 --> 00:01:19,080
Så, med n bitar, har du 2
möjliga värden för varje bit.

28
00:01:19,080 --> 00:01:22,300
Så vi har två möjliga värden för
den första biten, två möjliga värden

29
00:01:22,300 --> 00:01:24,450
för det andra, två
möjligt för den tredje.

30
00:01:24,450 --> 00:01:28,730
Och så det finns 2 gånger 2 gånger 2, och
slutligen svaret är 2 till n.

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

32
00:01:30,010 --> 00:01:31,100
>> Fråga tre.

33
00:01:31,100 --> 00:01:33,450
Vad finns 0x50 i binär?

34
00:01:33,450 --> 00:01:39,490
Så kom ihåg att hexadecimal har en mycket
enkel konvertering till binär.

35
00:01:39,490 --> 00:01:43,180
Så här behöver vi bara titta på
den 5 och 0 oberoende av varandra.

36
00:01:43,180 --> 00:01:45,110
Så vad är 5 i binär?

37
00:01:45,110 --> 00:01:48,400
0101, det är 1 bit och 4 bit.

38
00:01:48,400 --> 00:01:49,900
Vad är 0 i binär?

39
00:01:49,900 --> 00:01:50,520
Inte knepigt.

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

41
00:01:52,180 --> 00:01:54,970
Så bara sätta ihop dem, och
som är fulla antalet i binär.

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

43
00:01:57,640 --> 00:02:00,439
Och om du ville du kunde
ta av det längst till vänster noll.

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

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

46
00:02:02,920 --> 00:02:05,733
>> Så då alternativt
vad som är 0x50 i decimal?

47
00:02:05,733 --> 00:02:08,649
Om du ville, could-- dig om du är
mer bekväm med det binära,

48
00:02:08,649 --> 00:02:11,340
du kan ta det binära svar
och omvandla det till decimal.

49
00:02:11,340 --> 00:02:13,870
Eller vi kan bara minnas
som hexadecimalt.

50
00:02:13,870 --> 00:02:21,140
Så att 0 är i 0-e plats, och
den 5 är i det 16 till den första platsen.

51
00:02:21,140 --> 00:02:25,990
Så här har vi 5 gånger 16 till
först, plus 0 gånger 16 till noll,

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

53
00:02:27,520 --> 00:02:29,710
Och om du tittat på
Titeln på frågan,

54
00:02:29,710 --> 00:02:32,920
Det var CS 80, som var typ av en
ledtråd till svaret på detta problem.

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

56
00:02:34,460 --> 00:02:35,420
>> Fråga fem.

57
00:02:35,420 --> 00:02:40,320
Vi har denna Scratch manus, vilket är
upprepa 4 gånger jordnötssmör gelé.

58
00:02:40,320 --> 00:02:42,800
Så hur gör vi nu kod som i C?

59
00:02:42,800 --> 00:02:47,730
Tja, vi har här-- delen i fetstil
är den enda del som du var tvungen att genomföra.

60
00:02:47,730 --> 00:02:51,950
Så vi har en 4 slinga som är kretsa 4
gånger, printf-ing jordnötssmör gelé,

61
00:02:51,950 --> 00:02:53,910
med ny linje som problemet frågar efter.

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

63
00:02:55,250 --> 00:02:57,490
>> Fråga sex, en annan Scratch problem.

64
00:02:57,490 --> 00:03:00,210
Vi ser att vi är i ett evigt loop.

65
00:03:00,210 --> 00:03:05,000
Vi säger variabeln i
och sedan stega i med 1.

66
00:03:05,000 --> 00:03:09,580
Nu vill vi göra det i C. Det finns
flera sätt som vi kunde ha gjort det här.

67
00:03:09,580 --> 00:03:12,840
Här råkade vi koda
forever loop som ett tag (sant).

68
00:03:12,840 --> 00:03:16,600
Så vi deklarerar variabeln i, bara
som vi hade variabeln i i Scratch.

69
00:03:16,600 --> 00:03:21,950
Deklarera variabeln i, och för evigt
while (true), säger vi variabeln i.

70
00:03:21,950 --> 00:03:25,260
Så printf% Jag-- eller du kan har använt% d.

71
00:03:25,260 --> 00:03:27,985
Vi säger att variabeln, och
sedan höja detta, i ++.

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

73
00:03:29,560 --> 00:03:30,830
>> Fråga sju.

74
00:03:30,830 --> 00:03:35,560
Nu vill vi göra något mycket liknande
Mario dot c från problembild en.

75
00:03:35,560 --> 00:03:39,110
Vi vill skriva ut dessa hashtags,
Vi vill skriva ut en fem

76
00:03:39,110 --> 00:03:40,700
med tre rektangel av dessa hashar.

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

78
00:03:41,770 --> 00:03:43,162
Så hur ska vi göra det?

79
00:03:43,162 --> 00:03:45,370
Nåväl, vi ger dig en hel
gäng kod, och du bara

80
00:03:45,370 --> 00:03:47,560
måste fylla i tryck rutnät funktionen.

81
00:03:47,560 --> 00:03:49,540
>> Så vad gör PrintGrid ut?

82
00:03:49,540 --> 00:03:51,480
Jo du är förbi
bredd och höjd.

83
00:03:51,480 --> 00:03:53,520
Så vi har ett yttre 4
loop, som är looping

84
00:03:53,520 --> 00:03:57,650
över alla rader i denna
rutnät som vi vill skriva ut.

85
00:03:57,650 --> 00:04:01,250
Sedan har vi den inter kapslade 4 slinga,
det är att skriva ut över varje kolumn.

86
00:04:01,250 --> 00:04:06,210
Så för varje rad, vi trycker på
varje kolumn, en enda hash.

87
00:04:06,210 --> 00:04:10,045
Sedan i slutet av raden som vi skriver ut ett
enda ny rad för att gå till nästa rad.

88
00:04:10,045 --> 00:04:11,420
Och det är det för hela nätet.

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

90
00:04:12,810 --> 00:04:13,675
>> Fråga åtta.

91
00:04:13,675 --> 00:04:17,170
En funktion som PrintGrid sägs
har en sidoeffekt, men inte en återgång

92
00:04:17,170 --> 00:04:17,670
värde.

93
00:04:17,670 --> 00:04:19,209
Förklara skillnaden.

94
00:04:19,209 --> 00:04:23,080
Så detta är beroende av dig minnas
vad en biverkning är.

95
00:04:23,080 --> 00:04:25,180
Tja, en återgång value--
vi vet PrintGrid inte

96
00:04:25,180 --> 00:04:28,180
har returvärde, eftersom
här står det ogiltigt.

97
00:04:28,180 --> 00:04:31,150
Så allt som returnerar void
egentligen inte tillbaka någonting.

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

99
00:04:32,200 --> 00:04:33,620
Så vad är det bieffekt?

100
00:04:33,620 --> 00:04:36,620
Tja, är en bieffekt
något som slags kvarstår

101
00:04:36,620 --> 00:04:39,500
efter funktions slutar
Det var inte bara tillbaka,

102
00:04:39,500 --> 00:04:41,340
och det var inte bara från ingångarna.

103
00:04:41,340 --> 00:04:44,970
>> Så, till exempel, vi kanske
ändra en global variabel.

104
00:04:44,970 --> 00:04:46,590
Det skulle vara en bieffekt.

105
00:04:46,590 --> 00:04:49,000
I just detta fall, en
mycket viktig sidoeffekt

106
00:04:49,000 --> 00:04:51,070
skriver ut på skärmen.

107
00:04:51,070 --> 00:04:53,110
Så det är en bieffekt
att PrintGrid har.

108
00:04:53,110 --> 00:04:54,980
Vi trycker dessa saker på skärmen.

109
00:04:54,980 --> 00:04:56,370
Och du kan tänka dig
att som en sidoeffekt,

110
00:04:56,370 --> 00:04:58,690
eftersom det är något som
kvarstår efter den här funktionen avslutas.

111
00:04:58,690 --> 00:05:01,481
Det är något utanför
av denna funktion som slutligen

112
00:05:01,481 --> 00:05:03,380
håller på att ändras,
innehållet på skärmen.

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

114
00:05:05,200 --> 00:05:05,839
>> Fråga nio.

115
00:05:05,839 --> 00:05:07,880
Betrakta programmet nedan,
till vilket radnummer

116
00:05:07,880 --> 00:05:09,740
har lagts till för
diskussionens skull.

117
00:05:09,740 --> 00:05:13,480
Så i det här programmet är vi bara
ringer getString, lagra det

118
00:05:13,480 --> 00:05:16,220
i denna variabel s, och sedan
skriver ut variabeln s.

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

120
00:05:16,720 --> 00:05:19,090
Så förklara varför linje man är närvarande.

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

122
00:05:20,920 --> 00:05:23,820
Varför behöver vi #include CS50 dot h?

123
00:05:23,820 --> 00:05:26,180
Jo vi kallar det
GetString funktion,

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

125
00:05:28,840 --> 00:05:31,600
Så om vi inte hade
#include CS50 dot h,

126
00:05:31,600 --> 00:05:35,760
vi skulle få det implicit deklaration
av getString funktionsfel

127
00:05:35,760 --> 00:05:36,840
från kompilatorn.

128
00:05:36,840 --> 00:05:40,110
Så vi måste inkludera library--
Vi måste inkludera header-filen,

129
00:05:40,110 --> 00:05:42,870
annars kompilatorn kommer inte
inse att getString existerar.

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

131
00:05:44,380 --> 00:05:46,140
>> Förklara varför linje två är närvarande.

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

133
00:05:47,890 --> 00:05:50,430
Det är exakt samma
som det föregående problemet,

134
00:05:50,430 --> 00:05:53,310
utom i stället för att hantera
GetString, vi pratar om printf.

135
00:05:53,310 --> 00:05:56,654
Så om vi inte säga att vi behöver
att inkludera standard io dot h,

136
00:05:56,654 --> 00:05:58,820
då skulle vi inte kunna
att använda printf funktion,

137
00:05:58,820 --> 00:06:00,653
eftersom kompilatorn
skulle inte veta om det.

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

139
00:06:01,750 --> 00:06:05,260
>> Why-- vilken betydelse
av ogiltig i linje fyra?

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

141
00:06:08,010 --> 00:06:10,600
Det är bara att säga att vi
blir inte kommandoraden

142
00:06:10,600 --> 00:06:12,280
argument till main.

143
00:06:12,280 --> 00:06:17,390
Kom ihåg att vi kunde säga int
huvud int argc sträng argv parentes.

144
00:06:17,390 --> 00:06:20,400
Så här säger vi bara tomrum att säga att vi
ignorerar kommandoradsargument.

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

146
00:06:21,840 --> 00:06:25,225
>> Förklara, med avseende på minne, exakt
vad getString i linje sex returer.

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

148
00:06:27,040 --> 00:06:31,640
GetString återvänder ett block av
minne, en array av tecken.

149
00:06:31,640 --> 00:06:34,870
Det är verkligen returnera en
pekare till det första tecknet.

150
00:06:34,870 --> 00:06:37,170
Tänk på att en sträng är en röding stjärna.

151
00:06:37,170 --> 00:06:41,360
Så ar är en pekare till den första
tecken oavsett i vilken strängen är

152
00:06:41,360 --> 00:06:43,510
att användaren anger på tangentbordet.

153
00:06:43,510 --> 00:06:47,070
Och att minnet råkar vara malloced,
så att minnet är i högen.

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

155
00:06:49,080 --> 00:06:50,450
>> Fråga 13.

156
00:06:50,450 --> 00:06:51,960
Betrakta programmet nedan.

157
00:06:51,960 --> 00:06:55,579
Så allt det här programmet gör
är printf-ing 1 dividerat med 10.

158
00:06:55,579 --> 00:06:57,370
Så när de sammanställs och
avrättades, det här programmet

159
00:06:57,370 --> 00:07:01,170
utgångar 0.0, även om
1 dividerat med 10 är 0,1.

160
00:07:01,170 --> 00:07:02,970
Så varför är det 0,0?

161
00:07:02,970 --> 00:07:05,510
Nåväl, detta är därför att
av heltalsdivision.

162
00:07:05,510 --> 00:07:08,580
Så en är ett heltal, 10 är ett heltal.

163
00:07:08,580 --> 00:07:11,980
Så 1 dividerat med 10, allt
behandlas som heltal,

164
00:07:11,980 --> 00:07:16,380
och i C, när vi gör heltalsdivision,
Vi trunkera något decimalkomma.

165
00:07:16,380 --> 00:07:19,590
Så 1 dividerat med 10
0, och då vi försöker

166
00:07:19,590 --> 00:07:24,410
för att skriva ut det som ett flyttal, så
noll ut som en flottör är 0,0.

167
00:07:24,410 --> 00:07:27,400
Och det är därför vi får 0.0.

168
00:07:27,400 --> 00:07:28,940
>> Betrakta programmet nedan.

169
00:07:28,940 --> 00:07:31,280
Nu är vi skriver ut 0,1.

170
00:07:31,280 --> 00:07:34,280
Så ingen heltalsdivision,
vi bara skriva ut 0.1,

171
00:07:34,280 --> 00:07:37,100
men vi skriver ut det
till 28 decimaler.

172
00:07:37,100 --> 00:07:41,810
Och vi får denna 0.1000, ett helt gäng
av nollor, 5 5 5, bla bla bla.

173
00:07:41,810 --> 00:07:45,495
Så frågan här är varför gör det
skriva att, i stället för att exakt 0,1?

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

175
00:07:46,620 --> 00:07:49,640
>> Så anledningen här är nu
flyttal vaghet.

176
00:07:49,640 --> 00:07:53,410
Tänk på att en flottör är bara 32 bitar.

177
00:07:53,410 --> 00:07:57,540
Så vi kan bara representera ett begränsat antal
av flyttalsvärden med dem 32

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

179
00:07:58,560 --> 00:08:01,760
Jo det finns slutligen oändligt
många flyttalsvärden,

180
00:08:01,760 --> 00:08:04,940
och det finns oändligt många flytande
punkt värden i mellan 0 och 1,

181
00:08:04,940 --> 00:08:07,860
och vi är självklart kunna
representerar ännu fler värden än så.

182
00:08:07,860 --> 00:08:13,230
Så vi måste göra uppoffringar för att
kunna representera de flesta värden.

183
00:08:13,230 --> 00:08:16,960
>> Så ett värde som 0,1, tydligen
Vi kan inte representera det exakt.

184
00:08:16,960 --> 00:08:22,500
Så istället för att representera 0,1 vi gör
bästa vi kan representera denna 0.100000 5 5

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

186
00:08:23,260 --> 00:08:26,306
Och det är ganska nära, men
för många tillämpningar

187
00:08:26,306 --> 00:08:28,430
du behöver oroa dig
flyttal vaghet,

188
00:08:28,430 --> 00:08:30,930
eftersom vi bara inte kan representera
alla flytande punkter exakt.

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

190
00:08:32,500 --> 00:08:33,380
>> Fråga 15.

191
00:08:33,380 --> 00:08:34,679
Tänk koden nedan.

192
00:08:34,679 --> 00:08:36,630
Vi är bara att skriva ut 1 plus 1.

193
00:08:36,630 --> 00:08:38,289
Så det finns ingen konst här.

194
00:08:38,289 --> 00:08:41,780
1 plus 1 beräknas till 2, och
då vi skriver ut det.

195
00:08:41,780 --> 00:08:42,789
Detta skriver bara 2.

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

197
00:08:43,850 --> 00:08:44,700
>> Fråga 16.

198
00:08:44,700 --> 00:08:49,450
Nu ska vi skriva ut tecknet
1 plus tecknet 1.

199
00:08:49,450 --> 00:08:52,110
Så varför gör detta inte
skriva ut samma sak?

200
00:08:52,110 --> 00:08:57,680
Tja tecknet 1 plus tecknet
1, karaktären 1 har ASCII-värdet 49.

201
00:08:57,680 --> 00:09:04,840
Så det här är verkligen säger 49 plus 49, och
i slutändan kommer detta att skriva ut 98.

202
00:09:04,840 --> 00:09:06,130
Så det här inte ut 2.

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

204
00:09:08,070 --> 00:09:09,271
>> Fråga 17.

205
00:09:09,271 --> 00:09:11,520
Slutföra genomförandet
av udda nedan på ett sådant sätt

206
00:09:11,520 --> 00:09:14,615
att funktionen returnerar true om
n är udda och falskt om n är jämnt.

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

208
00:09:16,710 --> 00:09:19,330
Detta är en stor ändamål
för mod operatör.

209
00:09:19,330 --> 00:09:24,530
Så vi tar våra argument n,
om n mod 2 är lika med 1, väl

210
00:09:24,530 --> 00:09:28,030
det betyder att n uppdelat
av 2 hade en rest.

211
00:09:28,030 --> 00:09:33,270
Om n divideras med 2 hade en rest, som
betyder att n är udda, så vi return true.

212
00:09:33,270 --> 00:09:34,910
Else återvänder vi falskt.

213
00:09:34,910 --> 00:09:39,070
Du kunde också ha gjort n mod 2 jämlikar
noll, returnera false, annars return true.

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

215
00:09:41,600 --> 00:09:43,640
>> Betrakta den rekursiva funktionen nedan.

216
00:09:43,640 --> 00:09:46,920
Så om n är mindre än eller
lika med 1, avkastning 1,

217
00:09:46,920 --> 00:09:50,430
annars retur n gånger f n minus ett.

218
00:09:50,430 --> 00:09:52,556
Så vad är denna funktion?

219
00:09:52,556 --> 00:09:54,305
Nåväl, detta är bara
fakulteten.

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

221
00:09:55,410 --> 00:09:57,405
Detta är fint representerad
såsom n faktoriell.

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

223
00:09:58,720 --> 00:10:02,310
>> Så fråga 19 nu, vill vi
ta detta rekursiv funktion.

224
00:10:02,310 --> 00:10:04,530
Vi vill göra det iterativ.

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

226
00:10:05,874 --> 00:10:07,790
Väl för personalen
lösning, och återigen finns det

227
00:10:07,790 --> 00:10:11,090
flera sätt som du skulle ha gjort
att börjar vi med denna int produkt

228
00:10:11,090 --> 00:10:11,812
är lika med ett.

229
00:10:11,812 --> 00:10:13,520
Och genom hela denna
för loop, vi kommer

230
00:10:13,520 --> 00:10:17,590
att multiplicera produkt att slutligen
sluta med fullständig faktor.

231
00:10:17,590 --> 00:10:21,870
Så för int jag är lika med 2, är i
mindre än eller lika med n, i ++.

232
00:10:21,870 --> 00:10:24,130
>> Du kanske undrar varför jag är lika med 2.

233
00:10:24,130 --> 00:10:28,380
Tja, kom ihåg att vi här har att
se till att vårt grundscenario är korrekt.

234
00:10:28,380 --> 00:10:32,180
Så om n är mindre än eller lika
till 1, vi bara åter 1.

235
00:10:32,180 --> 00:10:34,830
Så här borta, börjar vi på jag är lika med 2.

236
00:10:34,830 --> 00:10:39,090
Tja, om jag var 1, då the-- eller
om n var 1, sedan för loop

237
00:10:39,090 --> 00:10:40,600
skulle inte köra alls.

238
00:10:40,600 --> 00:10:43,190
Och så skulle vi bara
retur produkt som är ett.

239
00:10:43,190 --> 00:10:45,920
Likaså om n var
något mindre än 1--

240
00:10:45,920 --> 00:10:49,290
om det var 0, -1, whatever--
vi skulle ändå att återvända 1,

241
00:10:49,290 --> 00:10:52,260
vilket är precis vad
rekursiva versionen gör.

242
00:10:52,260 --> 00:10:54,660
>> Nu, om n är större
än 1, då ska vi

243
00:10:54,660 --> 00:10:56,550
att göra åtminstone en
variant av denna slinga.

244
00:10:56,550 --> 00:11:00,630
Så låt oss säga n är 5, då är vi
kommer att göra produkttider är lika med 2.

245
00:11:00,630 --> 00:11:02,165
Så nu produkt är 2.

246
00:11:02,165 --> 00:11:04,040
Nu ska vi göra
produkttider är lika med 3.

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

248
00:11:04,690 --> 00:11:07,500
Produkttider är lika med 4, nu är det 24.

249
00:11:07,500 --> 00:11:10,420
Produkttider lika med 5, nu är det 120.

250
00:11:10,420 --> 00:11:16,730
Så sedan slutligen, vi återvänder
120, vilket är korrekt 5 faktoriell.

251
00:11:16,730 --> 00:11:17,510
>> Fråga 20.

252
00:11:17,510 --> 00:11:22,480
Detta är en där du måste fylla
i denna tabell med en given algoritm,

253
00:11:22,480 --> 00:11:25,735
något som vi har sett, att
passar dessa algoritmiska körningen

254
00:11:25,735 --> 00:11:28,060
gånger dessa asymptotiska körtider.

255
00:11:28,060 --> 00:11:33,270
Så vad är en algoritm som
är omega på 1, men stort o n?

256
00:11:33,270 --> 00:11:35,970
Så det skulle vara oändligt
många svar här.

257
00:11:35,970 --> 00:11:39,790
Det som vi har sett nog mest
ofta är bara linjär sökning.

258
00:11:39,790 --> 00:11:42,050
>> Så i bästa fall
scenario, objektet är vi

259
00:11:42,050 --> 00:11:44,050
söker är på
början av listan

260
00:11:44,050 --> 00:11:47,400
och så på omega 1 steg,
det första vi kontrollerar,

261
00:11:47,400 --> 00:11:49,740
vi bara omedelbart återvända
att vi hittat objektet.

262
00:11:49,740 --> 00:11:52,189
I det värsta scenariot,
objektet är i slutet,

263
00:11:52,189 --> 00:11:53,730
eller objektet inte finns i listan alls.

264
00:11:53,730 --> 00:11:56,700
Så vi måste söka
hela listan, alla n

265
00:11:56,700 --> 00:11:58,480
element, och det är därför det är o n.

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

267
00:11:59,670 --> 00:12:04,880
>> Så nu är det något som är både
omega n log n, och stora O n log n.

268
00:12:04,880 --> 00:12:08,650
Jo den mest relevanta sak
vi har sett här är Merge sort.

269
00:12:08,650 --> 00:12:12,950
Så sammanfoga sortera, kom ihåg,
är ytterst teta

270
00:12:12,950 --> 00:12:16,920
av n log n, där theta är definierad
om både omega och stora O är desamma.

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
>> Vad är något som är omega
N, och O i n kvadrat?

274
00:12:21,970 --> 00:12:23,990
Tja, återigen finns det
flera möjliga svar.

275
00:12:23,990 --> 00:12:26,440
Här råkar vi säga bubbla slag.

276
00:12:26,440 --> 00:12:28,840
Insättningssortering skulle också fungera här.

277
00:12:28,840 --> 00:12:31,400
Tänk på att bubbla sortera
har att optimering där,

278
00:12:31,400 --> 00:12:34,630
Om du har möjlighet att få
igenom hela listan

279
00:12:34,630 --> 00:12:37,402
utan att behöva göra
några swappar, då, ja,

280
00:12:37,402 --> 00:12:40,110
vi omedelbart kan återgå till att
listan sorterades till att börja med.

281
00:12:40,110 --> 00:12:43,185
Så i bästa fall,
det är bara omega n.

282
00:12:43,185 --> 00:12:45,960
Om det är inte bara ett fint
sorterade listan till att börja med,

283
00:12:45,960 --> 00:12:48,270
då har vi O n kvadrat swappar.

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

285
00:12:49,330 --> 00:12:55,610
Och slutligen har vi val Sortera
för n kvadrat, både omega och stora O.

286
00:12:55,610 --> 00:12:56,850
>> Fråga 21.

287
00:12:56,850 --> 00:12:58,870
Vad är heltalsspill?

288
00:12:58,870 --> 00:13:02,160
Tja igen, likt tidigare,
Vi har bara ändligt många bitar

289
00:13:02,160 --> 00:13:04,255
för att representera ett heltal,
så kanske 32 bitar.

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

291
00:13:06,300 --> 00:13:09,180
Låt oss säga att vi har ett heltal.

292
00:13:09,180 --> 00:13:12,800
Sedan slutligen den högsta
positivt tal vi kan representera

293
00:13:12,800 --> 00:13:15,910
är 2 till 31 minus ett.

294
00:13:15,910 --> 00:13:19,370
Så vad händer om vi försöker
då inkrementera som heltal?

295
00:13:19,370 --> 00:13:25,320
Nåväl, vi kommer att gå från 2 till 31
minus 1, ända ner till minus 2

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

297
00:13:26,490 --> 00:13:29,470
Så här heltalsspill är
när du håller uppräkning,

298
00:13:29,470 --> 00:13:32,330
och i slutändan kan du inte
bli högre och det bara

299
00:13:32,330 --> 00:13:34,520
sveper hela vägen tillbaka
runt till ett negativt värde.

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

301
00:13:35,850 --> 00:13:37,779
>> Vad sägs om en buffer overflow?

302
00:13:37,779 --> 00:13:39,820
Så en buffert overflow--
ihåg vad en buffert är.

303
00:13:39,820 --> 00:13:41,000
Det är bara en bit av minnet.

304
00:13:41,000 --> 00:13:43,350
Någonting liknande en array är en buffert.

305
00:13:43,350 --> 00:13:46,120
Så en buffer overflow är när
du försöker komma åt minnet

306
00:13:46,120 --> 00:13:47,880
längre än till slutet av den arrayen.

307
00:13:47,880 --> 00:13:50,410
Så om du har en
matris med storlek 5 och du

308
00:13:50,410 --> 00:13:53,700
försöker komma åt array fäste
5 eller konsol 6 eller bygel 7,

309
00:13:53,700 --> 00:13:56,610
eller något bortom
slutet, eller ens något

310
00:13:56,610 --> 00:14:00,790
below-- array bygel negativ 1--
alla dessa är buffertspill.

311
00:14:00,790 --> 00:14:02,810
Du vidrör minne på dåliga sätt.

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

313
00:14:04,090 --> 00:14:04,730
>> Fråga 23.

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

315
00:14:05,760 --> 00:14:09,100
Så i den här behöver du
att genomföra strlen.

316
00:14:09,100 --> 00:14:11,630
Och vi berätta att du kan
antar s kommer inte vara null,

317
00:14:11,630 --> 00:14:13,790
så du inte behöver
göra någon kontroll för null.

318
00:14:13,790 --> 00:14:16,190
Och det finns flera sätt
du kunde ha gjort det här.

319
00:14:16,190 --> 00:14:18,440
Här har vi bara ta det enkelt.

320
00:14:18,440 --> 00:14:21,780
Vi börjar med en räknare, n. n är
att räkna hur många tecken som finns.

321
00:14:21,780 --> 00:14:25,560
Så vi börjar på 0, och då är vi
iterera över hela listan.

322
00:14:25,560 --> 00:14:29,092
>> S är bygel 0 lika med den
null terminator karaktär?

323
00:14:29,092 --> 00:14:31,425
Kom ihåg att vi är ute efter
null terminator tecken

324
00:14:31,425 --> 00:14:33,360
att avgöra hur länge vår sträng är.

325
00:14:33,360 --> 00:14:35,890
Det kommer att upphöra
varje relevant sträng.

326
00:14:35,890 --> 00:14:39,400
Så är s fäste 0 lika
till noll terminator?

327
00:14:39,400 --> 00:14:42,850
Om det inte är, då vi kommer att
titta på s konsol 1, s konsol 2.

328
00:14:42,850 --> 00:14:45,050
Vi håller på tills vi
hitta null terminator.

329
00:14:45,050 --> 00:14:48,580
När vi har hittat den, då n innehåller
den totala längden på strängen,

330
00:14:48,580 --> 00:14:49,942
och vi kan bara tillbaka det.

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

332
00:14:51,180 --> 00:14:51,865
>> Fråga 24.

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

334
00:14:53,010 --> 00:14:56,050
Så det här är den där du
måste göra avvägning.

335
00:14:56,050 --> 00:14:59,810
Så en sak är bra i en
sätt, men på vilket sätt är det dåligt?

336
00:14:59,810 --> 00:15:02,980
Så här, Merge sort tenderar att
vara snabbare än bubbla slag.

337
00:15:02,980 --> 00:15:06,530
Med detta sagt that-- väl, det
är flera svar här.

338
00:15:06,530 --> 00:15:12,930
Men det viktigaste är att bubbla sortera
är omega n för en sorterad lista.

339
00:15:12,930 --> 00:15:14,950
>> Kom ihåg att bordet såg vi bara tidigare.

340
00:15:14,950 --> 00:15:17,600
Så bubbla sorterar omega av
n, det bästa scenariot

341
00:15:17,600 --> 00:15:20,010
är det ska kunna gå över
listan en gång, fastställa

342
00:15:20,010 --> 00:15:22,270
Hej det här är redan
sorteras och retur.

343
00:15:22,270 --> 00:15:25,960
Merge sort, oavsett vad
du gör, är omega n log n.

344
00:15:25,960 --> 00:15:29,200
Så för sorterad lista, bubbla
sortera kommer att bli snabbare.

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

346
00:15:30,870 --> 00:15:32,430
>> Nu vad om länkade listor?

347
00:15:32,430 --> 00:15:36,070
Så en länkad lista kan växa och krympa
för att passa så många element som behövs.

348
00:15:36,070 --> 00:15:38,489
Efter att ha sagt that-- så
vanligtvis direkt jämförelse

349
00:15:38,489 --> 00:15:40,280
kommer att bli en länkad
lista med en array.

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

351
00:15:41,600 --> 00:15:44,050
Så även om arrayer kan
lätt växa och krympa

352
00:15:44,050 --> 00:15:47,130
för att passa så många element
efter behov, lista en länkad

353
00:15:47,130 --> 00:15:49,600
jämfört med en array-- en
arrayen har slumpvis åtkomst.

354
00:15:49,600 --> 00:15:52,960
Vi kan indexera i någon
särskilt element i arrayen.

355
00:15:52,960 --> 00:15:56,430
>> Så för en länkad lista, kan vi inte
bara att gå till det femte elementet,

356
00:15:56,430 --> 00:16:00,260
vi har att passera från början
tills vi kommer till det femte elementet.

357
00:16:00,260 --> 00:16:03,990
Och det kommer att hindra oss från
gör något som binär sökning.

358
00:16:03,990 --> 00:16:08,150
På tal om binär sökning, binär sökning
tenderar att vara snabbare än linjär sökning.

359
00:16:08,150 --> 00:16:11,120
Efter att ha sagt that--
så, en möjlig sak

360
00:16:11,120 --> 00:16:13,380
är att du inte kan göra binär
Sök på länkade listor,

361
00:16:13,380 --> 00:16:14,730
Du kan bara göra det på matriser.

362
00:16:14,730 --> 00:16:18,030
Men förmodligen ännu viktigare,
du kan inte göra binär sökning

363
00:16:18,030 --> 00:16:20,690
på en samling som inte sorteras.

364
00:16:20,690 --> 00:16:23,990
Upfront kan du behöva sortera
arrayen, och endast då kan

365
00:16:23,990 --> 00:16:25,370
du gör binär sökning.

366
00:16:25,370 --> 00:16:27,660
Så om din sak är inte
sorterade till att börja med,

367
00:16:27,660 --> 00:16:29,250
då linjär sökning kan också gå fortare.

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

369
00:16:30,620 --> 00:16:31,740
>> Fråga 27.

370
00:16:31,740 --> 00:16:34,770
Så anser programmet nedan,
som kommer att vara i nästa bild.

371
00:16:34,770 --> 00:16:37,790
Och det är det där vi är
kommer att vilja att uttryckligen ange

372
00:16:37,790 --> 00:16:39,980
värden för olika variabler.

373
00:16:39,980 --> 00:16:41,990
Så låt oss titta på det.

374
00:16:41,990 --> 00:16:43,160
>> Så linje ett.

375
00:16:43,160 --> 00:16:45,457
Vi har int x är lika med 1.

376
00:16:45,457 --> 00:16:47,040
Det är det enda som har hänt.

377
00:16:47,040 --> 00:16:50,440
Så vid linje ett, ser vi i vår
bord, att y, a, b, och TMP är alla

378
00:16:50,440 --> 00:16:51,540
blackout.

379
00:16:51,540 --> 00:16:52,280
Så vad är x?

380
00:16:52,280 --> 00:16:53,860
Jo vi bara satt det lika med 1.

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

382
00:16:55,020 --> 00:16:58,770
Och sedan linje två, ja,
ser vi att y är satt till 2,

383
00:16:58,770 --> 00:17:00,550
och tabellen är redan
fyllas i för oss.

384
00:17:00,550 --> 00:17:03,040
Så x är 1 och y är 2.

385
00:17:03,040 --> 00:17:05,890
>> Nu, linje tre, är vi nu
inuti växlingsfunktionen.

386
00:17:05,890 --> 00:17:07,560
Vad gjorde vi passerar byta?

387
00:17:07,560 --> 00:17:11,609
Vi passerade et-tecken x för
a, och et-y för miljarder.

388
00:17:11,609 --> 00:17:15,160
Där problemet tidigare
angav att adressen för x

389
00:17:15,160 --> 00:17:17,520
är 0x10, och adressen till y är 0x14.

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

391
00:17:18,970 --> 00:17:21,909
Så a och b är lika med
0x10 och 0x14, respektive.

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

393
00:17:23,670 --> 00:17:26,250
>> Nu på rad tre, vad är x och y?

394
00:17:26,250 --> 00:17:28,554
Tja, har ingenting förändrats
om x och y vid denna punkt.

395
00:17:28,554 --> 00:17:30,470
Även om de är
i en huvud stack ram,

396
00:17:30,470 --> 00:17:32,469
de fortfarande har samma
värden som de gjorde innan.

397
00:17:32,469 --> 00:17:34,030
Vi har inte ändrat något minne.

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

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

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

401
00:17:37,050 --> 00:17:40,300
Så nu vi sa int tmp lika med stjärna en.

402
00:17:40,300 --> 00:17:44,410
Så vid linje fyra, allt
är densamma med undantag för tmp.

403
00:17:44,410 --> 00:17:47,130
Vi har inte ändrat några värden
för något, utom för tmp.

404
00:17:47,130 --> 00:17:49,230
Vi sätter tmp lika med stjärna en.

405
00:17:49,230 --> 00:17:50,620
Vad är stjärnan a?

406
00:17:50,620 --> 00:17:56,240
Tja, en poäng till x, så stjärnan en
kommer att lika x, som är 1.

407
00:17:56,240 --> 00:18:00,080
Så allt kopieras
ner, och TMP är satt till ett.

408
00:18:00,080 --> 00:18:01,110
>> Nu nästa rad.

409
00:18:01,110 --> 00:18:03,380
Stjärn a är lika stjärn miljarder.

410
00:18:03,380 --> 00:18:10,000
Så genom linje five-- bra igen, allt
är samma förutom vad stjärn a är.

411
00:18:10,000 --> 00:18:10,830
Vad är stjärnan a?

412
00:18:10,830 --> 00:18:13,720
Jo, just sagt att vi stjärn a är x.

413
00:18:13,720 --> 00:18:16,400
Så vi ändra x till lika stjärnan f.

414
00:18:16,400 --> 00:18:18,960
Vad är stjärnan b? y. b pekar på y.

415
00:18:18,960 --> 00:18:21,030
Så stjärniga b är y.

416
00:18:21,030 --> 00:18:25,140
Så vi ställer x är lika med y,
och allt annat är lika.

417
00:18:25,140 --> 00:18:29,130
Så vi ser i nästa rad att x är nu
2, och resten är bara kopieras ned.

418
00:18:29,130 --> 00:18:31,120
>> Nu i nästa rad, stjärna B lika tmp.

419
00:18:31,120 --> 00:18:34,740
Jo, just sagt att vi stjärn b är y,
så vi ställer y lika med tmp.

420
00:18:34,740 --> 00:18:37,450
Allt annat är detsamma,
så allt blir kopierat ner.

421
00:18:37,450 --> 00:18:42,050
Vi ställer y lika med tmp, vilket är
en, och allt annat är lika.

422
00:18:42,050 --> 00:18:43,210
>> Nu äntligen, rad sju.

423
00:18:43,210 --> 00:18:44,700
Vi är tillbaka i huvudfunktionen.

424
00:18:44,700 --> 00:18:46,350
Vi är ute efter swap är klar.

425
00:18:46,350 --> 00:18:48,972
Vi har förlorat a, b, och
tmp, men i slutändan vi

426
00:18:48,972 --> 00:18:51,180
inte ändra några värden
av något på denna punkt,

427
00:18:51,180 --> 00:18:52,800
Vi kopierar bara x och y nedåt.

428
00:18:52,800 --> 00:18:56,490
Och vi ser att x och y är
nu 2 och 1 i stället för 1 och 2.

429
00:18:56,490 --> 00:18:58,160
Den swap har framgångsrikt genomfört.

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

431
00:18:59,500 --> 00:19:00,105
>> Fråga 28.

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

433
00:19:01,226 --> 00:19:03,100
Antag att du stöter
felmeddelandena

434
00:19:03,100 --> 00:19:06,790
nedan under kontorstid
nästa år som en CA eller TF.

435
00:19:06,790 --> 00:19:08,930
Råd hur man rättar till vart och ett av dessa fel.

436
00:19:08,930 --> 00:19:11,160
Så odefinierad referens till getString.

437
00:19:11,160 --> 00:19:12,540
Varför kan ni se det här?

438
00:19:12,540 --> 00:19:15,380
Tja, om en elev använder
GetString i sin kod,

439
00:19:15,380 --> 00:19:20,310
de har rätt hash inkluderat CS50
dot h att inkludera CS50 biblioteket.

440
00:19:20,310 --> 00:19:22,380
>> Tja, vad gör de
måste fixa detta fel?

441
00:19:22,380 --> 00:19:26,810
De måste göra ett streck lcs50 på
kommandoraden när de sammanställer.

442
00:19:26,810 --> 00:19:29,501
Så om de inte klarar
klang streck lcs50, de är

443
00:19:29,501 --> 00:19:32,000
kommer inte att ha den verkliga
kod som implementerar getString.

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

445
00:19:33,190 --> 00:19:34,170
>> Fråga 29.

446
00:19:34,170 --> 00:19:36,190
Underförstått att förklara
biblioteksfunktion strlen.

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

448
00:19:37,550 --> 00:19:40,360
Ja detta nu, de har inte
gjort korrekt hash inkludera.

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

450
00:19:41,440 --> 00:19:45,410
I detta särskilda fall var den header-fil
de behöver för att inkludera är sträng dot h,

451
00:19:45,410 --> 00:19:48,710
och inkluderande sträng dot h, nu
den student-- nu kompilatorn

452
00:19:48,710 --> 00:19:51,750
har tillgång till den
förklaringar strlen,

453
00:19:51,750 --> 00:19:54,120
och den vet att din kod
använder strlen fullständigt.

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

455
00:19:55,380 --> 00:19:56,580
>> Fråga 30.

456
00:19:56,580 --> 00:20:00,240
Fler procentuella omvandlingar
än uppgifter argument.

457
00:20:00,240 --> 00:20:01,540
Så vad är det här?

458
00:20:01,540 --> 00:20:06,470
Väl ihåg att dessa procent
signs-- hur de är relevanta för printf.

459
00:20:06,470 --> 00:20:08,890
Så i printf kan vi percent--
Vi kan skriva ut något

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

461
00:20:11,380 --> 00:20:15,310
Eller vi kan skriva ut som procent i,
utrymme, procent i, utrymme, procent i.

462
00:20:15,310 --> 00:20:18,950
Så för var och en av dem
procenttecken, vi behöver

463
00:20:18,950 --> 00:20:21,560
att passera en variabel vid slutet av printf.

464
00:20:21,560 --> 00:20:26,980
>> Så om vi säger printf Paren procent
I omvänt snedstreck n close Paren,

465
00:20:26,980 --> 00:20:30,270
ja, säger vi att vi är
kommer att skriva ut ett heltal,

466
00:20:30,270 --> 00:20:33,970
men då vi inte klarar printf
ett heltal att faktiskt skriva ut.

467
00:20:33,970 --> 00:20:37,182
Så här mer procent
omvandlingar än uppgifter argument?

468
00:20:37,182 --> 00:20:39,390
Det är att säga att vi måste
en hel massa procent,

469
00:20:39,390 --> 00:20:42,445
och vi har inte tillräckligt många variabler
att faktiskt fylla i dessa procenttal.

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

471
00:20:44,850 --> 00:20:50,010
>> Och då definitivt, för fråga 31,
definitivt förlorat 40 byte i ett block.

472
00:20:50,010 --> 00:20:52,350
Så detta är ett Valgrind fel.

473
00:20:52,350 --> 00:20:54,720
Detta är att säga att
någonstans i din kod,

474
00:20:54,720 --> 00:20:59,010
du har en fördelning som är 40
byte stort så du malloced 40 bytes,

475
00:20:59,010 --> 00:21:00,515
och du aldrig befriade den.

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

477
00:21:02,480 --> 00:21:05,140
Troligtvis behöver du bara
att hitta några minnesläcka,

478
00:21:05,140 --> 00:21:07,650
och hitta var du vill
befria denna minnesblock.

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

480
00:21:08,780 --> 00:21:11,910
>> Och fråga 32,
ogiltig skrivning av storlek 4.

481
00:21:11,910 --> 00:21:13,250
Återigen är detta en Valgrind fel.

482
00:21:13,250 --> 00:21:15,440
Detta behöver inte göra
med minnesläckor nu.

483
00:21:15,440 --> 00:21:20,750
Detta är, de flesta likely-- jag menar, det är
någon form av ogiltiga minnes rättigheter.

484
00:21:20,750 --> 00:21:23,270
Och troligtvis är detta en del
typ av buffertspill.

485
00:21:23,270 --> 00:21:26,560
Där du har en matris, kanske
ett heltal array, och låt oss

486
00:21:26,560 --> 00:21:30,115
säga att det är av storlek 5, och du
försöka röra array fäste 5.

487
00:21:30,115 --> 00:21:34,150
Så om du försöker skriva till den
värde, det är inte en bit av minne

488
00:21:34,150 --> 00:21:37,440
att du faktiskt har tillgång till, och
så du kommer att få detta fel,

489
00:21:37,440 --> 00:21:39,272
säger ogiltig skrivning av storlek 4.

490
00:21:39,272 --> 00:21:42,480
Valgrind kommer att känna igen dig är
försökte röra minnet olämpligt.

491
00:21:42,480 --> 00:21:43,980
>> Och det är det för quiz0.

492
00:21:43,980 --> 00:21:47,065
Jag är Rob Bowden, och detta är CS50.

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