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

2
00:00:09,572 --> 00:00:12,030
ROB BOWDEN: Hola, sóc Rob Bowden,
i parlarem de quiz0.

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

4
00:00:13,280 --> 00:00:14,545
>> Per tant, la primera pregunta.

5
00:00:14,545 --> 00:00:17,750
Aquesta és la pregunta on
que necessitaves per codificar el nombre

6
00:00:17,750 --> 00:00:21,270
127 en els bulbs binaris.

7
00:00:21,270 --> 00:00:23,550
Si volguessis, podries
fer la conversió normal

8
00:00:23,550 --> 00:00:25,950
des bi-- o, de decimal a binari.

9
00:00:25,950 --> 00:00:28,300
Però això probablement va
de prendre un munt de temps.

10
00:00:28,300 --> 00:00:31,750
Vull dir, vostè podria adonar-se que,
Acceptar, 1 és d'allà, 2 és allà,

11
00:00:31,750 --> 00:00:33,650
4 és aquí, 8 és en allà.

12
00:00:33,650 --> 00:00:39,280
Manera més fàcil, 127 és 128 menys un.

13
00:00:39,280 --> 00:00:42,013
Aquesta bombeta més a l'esquerra és la de 128 bits.

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

15
00:00:43,490 --> 00:00:47,860
Així que 127 és realment tot
de les altres bombetes,

16
00:00:47,860 --> 00:00:51,420
ja que és el més a l'esquerra
bombeta almenys 1.

17
00:00:51,420 --> 00:00:52,800
Això és tot per aquesta pregunta.

18
00:00:52,800 --> 00:00:54,060
>> Pregunta un.

19
00:00:54,060 --> 00:00:56,710
Així que amb 3 bits que pugui
representar 8 valors diferents.

20
00:00:56,710 --> 00:01:01,000
Per què, llavors, és la més gran de 7 no negatiu
sencer decimal es pot representar?

21
00:01:01,000 --> 00:01:04,050
Bé, si només podem
representar 8 valors diferents,

22
00:01:04,050 --> 00:01:07,430
llavors el que serem
que representa és de 0 a 7.

23
00:01:07,430 --> 00:01:08,745
0 ocupa un dels valors.

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

25
00:01:09,980 --> 00:01:11,190
>> Pregunta 2.

26
00:01:11,190 --> 00:01:14,610
Amb n bits, quants diferent
valors poden representar?

27
00:01:14,610 --> 00:01:19,080
Així, amb n bits, té 2
els valors possibles per a cada bit.

28
00:01:19,080 --> 00:01:22,300
Així que tenim dos valors possibles per
el primer bit, 2 valors possibles

29
00:01:22,300 --> 00:01:24,450
per al segon, 2
possible per a la tercera.

30
00:01:24,450 --> 00:01:28,730
I pel que és 2 vegades 2 cops 2, i
en última instància, la resposta és 2 a la n.

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

32
00:01:30,010 --> 00:01:31,100
>> Pregunta 3.

33
00:01:31,100 --> 00:01:33,450
Què és 0x50 en binari?

34
00:01:33,450 --> 00:01:39,490
Així que recordi que té una molt hexadecimal
conversió directa a binari.

35
00:01:39,490 --> 00:01:43,180
Així que aquí, només hem de mirar
el 5 i el 0 independent.

36
00:01:43,180 --> 00:01:45,110
Així que el que és 5 en binari?

37
00:01:45,110 --> 00:01:48,400
0101, que és el bit 1 i el 4 bits.

38
00:01:48,400 --> 00:01:49,900
El que és 0 en binari?

39
00:01:49,900 --> 00:01:50,520
No és complicat.

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

41
00:01:52,180 --> 00:01:54,970
Així que només cal posar junts, i
aquest és el número complet en binari.

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

43
00:01:57,640 --> 00:02:00,439
I si volguessis podries
enlairament que més a l'esquerra de zero.

44
00:02:00,439 --> 00:02:01,105
És irrellevant.

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

46
00:02:02,920 --> 00:02:05,733
>> Així que, alternativament,
el que és 0x50 en decimal?

47
00:02:05,733 --> 00:02:08,649
Si vostè volgués, vostè could-- si estàs
més còmode amb el binari,

48
00:02:08,649 --> 00:02:11,340
vostè podria prendre aquesta resposta binària
i convertir això en decimal.

49
00:02:11,340 --> 00:02:13,870
O podríem recordar
que hexadecimal.

50
00:02:13,870 --> 00:02:21,140
Així que 0 està en el lloc 0º, i
el 5 és al 16 al primer lloc.

51
00:02:21,140 --> 00:02:25,990
Així que aquí, tenim 5 vegades 16 a la
primer, més 0 vegades 16 a la zero,

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

53
00:02:27,520 --> 00:02:29,710
I si un mira a la
el títol de la pregunta,

54
00:02:29,710 --> 00:02:32,920
era CS 80, que era una mena de
al·lusió a la resposta a aquest problema.

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

56
00:02:34,460 --> 00:02:35,420
>> Pregunta 5.

57
00:02:35,420 --> 00:02:40,320
Tenim aquest script Scratch, que és
repetir 4 vegades la mantega de cacauet gelea.

58
00:02:40,320 --> 00:02:42,800
Llavors, ¿com ara el codi que en C?

59
00:02:42,800 --> 00:02:47,730
Bé, tenim aquí-- la part en negreta
és l'única part que calia posar en pràctica.

60
00:02:47,730 --> 00:02:51,950
Així que tenim un bucle de 4 que està en bucle 4
vegades, la mantega de cacauet gelea ing-printf,

61
00:02:51,950 --> 00:02:53,910
amb la nova línia que el problema demana.

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

63
00:02:55,250 --> 00:02:57,490
>> Pregunta 6, un altre problema d'Scratch.

64
00:02:57,490 --> 00:03:00,210
Veiem que estem en un bucle per sempre.

65
00:03:00,210 --> 00:03:05,000
Estem dient que la variable i
i després incrementar i en 1.

66
00:03:05,000 --> 00:03:09,580
Ara volem fer que a C. Hi ha
múltiples formes en les que podríem haver fet això.

67
00:03:09,580 --> 00:03:12,840
Aquí passem a codificar el
per sempre com un bucle while (true).

68
00:03:12,840 --> 00:03:16,600
Així que declarem la variable i, només
com teníem i variable en scratch.

69
00:03:16,600 --> 00:03:21,950
Declari la variable i, i per sempre
while (true), diem que la variable i.

70
00:03:21,950 --> 00:03:25,260
Així printf% jo-- o que podria haver utilitzat% d.

71
00:03:25,260 --> 00:03:27,985
Nosaltres diem que la variable, i
després incrementar-lo, i ++.

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

73
00:03:29,560 --> 00:03:30,830
>> Pregunta 7.

74
00:03:30,830 --> 00:03:35,560
Ara volem fer alguna cosa molt similar
Mario punt c del problema plantejat un.

75
00:03:35,560 --> 00:03:39,110
Volem imprimir aquests hashtags,
volem imprimir un cinc

76
00:03:39,110 --> 00:03:40,700
per tres rectangle d'aquests hashes.

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

78
00:03:41,770 --> 00:03:43,162
Llavors, ¿com anem a fer això?

79
00:03:43,162 --> 00:03:45,370
Bé, et donem un tot
paquet de programes, i que acaba de

80
00:03:45,370 --> 00:03:47,560
ha d'omplir en la funció d'impressió de quadrícula.

81
00:03:47,560 --> 00:03:49,540
>> Així que el que es veu com PrintGrid?

82
00:03:49,540 --> 00:03:51,480
Doncs estàs més enllà de la
amplada i l'alçada.

83
00:03:51,480 --> 00:03:53,520
Així que tenim un exterior 4
llaç, això és un bucle

84
00:03:53,520 --> 00:03:57,650
sobretot de les files d'aquest
quadrícula que volem imprimir.

85
00:03:57,650 --> 00:04:01,250
Després tenim el bucle niat entre 4,
aquesta és la impressió sobre cada columna.

86
00:04:01,250 --> 00:04:06,210
Així que per a cada fila, imprimim per
cada columna, un sol hash.

87
00:04:06,210 --> 00:04:10,045
Després, al final de la fila és la impressió d'un
línia de nou senzill per anar a la següent fila.

88
00:04:10,045 --> 00:04:11,420
I això és tot per tota la xarxa.

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

90
00:04:12,810 --> 00:04:13,675
>> Pregunta 8.

91
00:04:13,675 --> 00:04:17,170
Una funció com PrintGrid es diu que
tenir un efecte secundari, però no un retorn

92
00:04:17,170 --> 00:04:17,670
valor.

93
00:04:17,670 --> 00:04:19,209
Explicar la distinció.

94
00:04:19,209 --> 00:04:23,080
Així que això es basa en recordar
el que és un efecte secundari és.

95
00:04:23,080 --> 00:04:25,180
Bé, un retorn value--
sabem PrintGrid no ho fa

96
00:04:25,180 --> 00:04:28,180
tenen valor de retorn, ja que
aquí es diu sense efecte.

97
00:04:28,180 --> 00:04:31,150
Així que qualsevol cosa que retorna void
en realitat no tornar res.

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

99
00:04:32,200 --> 00:04:33,620
Llavors, quin és l'efecte secundari?

100
00:04:33,620 --> 00:04:36,620
Bé, un efecte secundari és
res aquest tipus de persisteix

101
00:04:36,620 --> 00:04:39,500
després dels extrems de la funció
que no era acabem de tornar,

102
00:04:39,500 --> 00:04:41,340
i que no era només de les entrades.

103
00:04:41,340 --> 00:04:44,970
>> Així, per exemple, podríem
canviar una variable global.

104
00:04:44,970 --> 00:04:46,590
Això seria un efecte secundari.

105
00:04:46,590 --> 00:04:49,000
En aquest cas particular, un
efecte secundari molt important

106
00:04:49,000 --> 00:04:51,070
s'imprimeix a la pantalla.

107
00:04:51,070 --> 00:04:53,110
Així que és un efecte secundari
que té PrintGrid.

108
00:04:53,110 --> 00:04:54,980
Imprimim aquestes coses a la pantalla.

109
00:04:54,980 --> 00:04:56,370
I vostè pot pensar en
que com un efecte secundari,

110
00:04:56,370 --> 00:04:58,690
ja que això és una cosa que
persisteix després que acabi aquesta funció.

111
00:04:58,690 --> 00:05:01,481
Això és una cosa que està fora de l'abast
d'aquesta funció que en última instància

112
00:05:01,481 --> 00:05:03,380
està sent canviat, la
contingut de la pantalla.

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

114
00:05:05,200 --> 00:05:05,839
>> Pregunta nou.

115
00:05:05,839 --> 00:05:07,880
Considereu el programa,
a la qual els números de línia

116
00:05:07,880 --> 00:05:09,740
s'han afegit per
En nom de la discussió.

117
00:05:09,740 --> 00:05:13,480
Així que en aquest programa només som
trucant GetString, emmagatzemant-

118
00:05:13,480 --> 00:05:16,220
en aquesta variable s, i després
la impressió que la variable s.

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

120
00:05:16,720 --> 00:05:19,090
Així d'explicar per què la línia un està present.

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

122
00:05:20,920 --> 00:05:23,820
Per què necessitem #include CS50 punt h?

123
00:05:23,820 --> 00:05:26,180
Bé estem cridant a la
Funció GetString,

124
00:05:26,180 --> 00:05:28,840
i GetString es defineix
a la biblioteca CS50.

125
00:05:28,840 --> 00:05:31,600
Així que si no teníem
#include punt CS50 h,

126
00:05:31,600 --> 00:05:35,760
que anava a aconseguir que la declaració implícita
de la funció d'error GetString

127
00:05:35,760 --> 00:05:36,840
del compilador.

128
00:05:36,840 --> 00:05:40,110
Així que hem d'incloure la library--
hem d'incloure l'arxiu de capçalera,

129
00:05:40,110 --> 00:05:42,870
o en cas contrari el compilador no ho farà
reconeixen que hi ha GetString.

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

131
00:05:44,380 --> 00:05:46,140
>> Expliqueu per què la línia dos està present.

132
00:05:46,140 --> 00:05:47,890
Així estàndard punt h io.

133
00:05:47,890 --> 00:05:50,430
És exactament la mateixa
com el problema anterior,

134
00:05:50,430 --> 00:05:53,310
excepte que en lloc de tractar amb
GetString, estem parlant de printf.

135
00:05:53,310 --> 00:05:56,654
Així que si no diem el que necessitem
per incloure estàndard de punt io h,

136
00:05:56,654 --> 00:05:58,820
llavors nosaltres no podríem
utilitzar la funció printf,

137
00:05:58,820 --> 00:06:00,653
perquè el compilador
no saber-ho.

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

139
00:06:01,750 --> 00:06:05,260
>> Què-- quin és el significat
de ple dret en la línia de quatre?

140
00:06:05,260 --> 00:06:08,010
Així que aquí tenim int main (void).

141
00:06:08,010 --> 00:06:10,600
Això és just dir que
no estan rebent cap línia d'ordres

142
00:06:10,600 --> 00:06:12,280
arguments a principal.

143
00:06:12,280 --> 00:06:17,390
Recordeu que nosaltres podríem dir int
principals suports de cadena argv argc int.

144
00:06:17,390 --> 00:06:20,400
Així que aquí ens limitem a dir nul·la dir que
no tenen en compte dels arguments de línia de comandes.

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

146
00:06:21,840 --> 00:06:25,225
>> Explicar, pel que fa a la memòria, exactament
el GetString en línia de sis voltes.

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

148
00:06:27,040 --> 00:06:31,640
GetString està tornant un bloc de
memòria, una gran varietat de personatges.

149
00:06:31,640 --> 00:06:34,870
És realment un retorn
punter al primer caràcter.

150
00:06:34,870 --> 00:06:37,170
Recordeu que una cadena és una estrella de carbó.

151
00:06:37,170 --> 00:06:41,360
Així que s és un punter a la primera
personatge en qualsevol que sigui la cadena és

152
00:06:41,360 --> 00:06:43,510
que l'usuari va entrar en el teclat.

153
00:06:43,510 --> 00:06:47,070
I que la memòria passa a ser malloced,
de manera que la memòria està en el munt.

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

155
00:06:49,080 --> 00:06:50,450
>> Pregunta 13.

156
00:06:50,450 --> 00:06:51,960
Considereu el programa.

157
00:06:51,960 --> 00:06:55,579
Així que tot aquest programa està fent
es printf-ing 1 dividit per 10.

158
00:06:55,579 --> 00:06:57,370
Així que quan es compila i
executat, aquest programa

159
00:06:57,370 --> 00:07:01,170
sortides 0.0, tot i que
1 dividit per 10 és 0,1.

160
00:07:01,170 --> 00:07:02,970
Així que per què és 0.0?

161
00:07:02,970 --> 00:07:05,510
Bé, això es deu a
de la divisió entera.

162
00:07:05,510 --> 00:07:08,580
Així que és un nombre enter 1, 10 és un nombre enter.

163
00:07:08,580 --> 00:07:11,980
Així que 1 dividit per 10, tot
es tracta com nombres enters,

164
00:07:11,980 --> 00:07:16,380
i en C, quan fem la divisió entera,
trunquem qualsevol punt decimal.

165
00:07:16,380 --> 00:07:19,590
Així que 1 dividit per 10 es
0, i llavors estem tractant

166
00:07:19,590 --> 00:07:24,410
per imprimir que com un flotador, per la qual
zero impresa com un flotador és 0.0.

167
00:07:24,410 --> 00:07:27,400
I és per això que obtenim 0.0.

168
00:07:27,400 --> 00:07:28,940
>> Considereu el programa.

169
00:07:28,940 --> 00:07:31,280
Ara estem imprimint 0.1.

170
00:07:31,280 --> 00:07:34,280
Així que no hi ha divisió entera,
només estem imprimint 0,1,

171
00:07:34,280 --> 00:07:37,100
però estem imprimir
a 28 xifres decimals.

172
00:07:37,100 --> 00:07:41,810
I obtenim aquest 0,1000, un munt
de zeros, 5 5 5, bla, bla, bla.

173
00:07:41,810 --> 00:07:45,495
Així que la pregunta aquí és per què ho fa
imprimir que, en lloc d'exactament 0,1?

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

175
00:07:46,620 --> 00:07:49,640
>> Així que la raó aquí és ara
punt imprecisió flotant.

176
00:07:49,640 --> 00:07:53,410
Recordeu que un flotador és a 32 bits.

177
00:07:53,410 --> 00:07:57,540
Així que només podem representar un nombre finit
de valors de punt flotant amb els 32

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

179
00:07:58,560 --> 00:08:01,760
Bé, hi ha, en última instància infinitament
molts dels valors de punt flotant,

180
00:08:01,760 --> 00:08:04,940
i hi ha infinitament molts flotant
els valors de punt d'entre 0 i 1,

181
00:08:04,940 --> 00:08:07,860
i estem òbviament capaç de
representar fins i tot més valors que això.

182
00:08:07,860 --> 00:08:13,230
Així que hem de fer sacrificis per
ser capaç de representar la majoria dels valors.

183
00:08:13,230 --> 00:08:16,960
>> Així com un valor de 0,1, pel que sembla,
no podem representar això exactament.

184
00:08:16,960 --> 00:08:22,500
Així que en lloc de representar el 0,1 fem la
El millor que podem representar aquest 0.100000 maig 5

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

186
00:08:23,260 --> 00:08:26,306
I això és bastant estreta, però
per a una gran quantitat d'aplicacions

187
00:08:26,306 --> 00:08:28,430
vostè ha de preocupar sobre
punt imprecisió flotant,

188
00:08:28,430 --> 00:08:30,930
perquè simplement no podem representar
tots flotant punts exactament.

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

190
00:08:32,500 --> 00:08:33,380
>> Pregunta 15.

191
00:08:33,380 --> 00:08:34,679
Penseu en el codi de sota.

192
00:08:34,679 --> 00:08:36,630
Estem imprimint 1 més 1.

193
00:08:36,630 --> 00:08:38,289
Així que no hi ha truc aquí.

194
00:08:38,289 --> 00:08:41,780
1 més 1 avalua a 2, i
llavors estem imprimint això.

195
00:08:41,780 --> 00:08:42,789
Això només imprimeix 2.

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

197
00:08:43,850 --> 00:08:44,700
>> Pregunta 16.

198
00:08:44,700 --> 00:08:49,450
Ara estem imprimint el caràcter
1 més el caràcter gener.

199
00:08:49,450 --> 00:08:52,110
Així que per què això no
imprimir la mateixa cosa?

200
00:08:52,110 --> 00:08:57,680
Bé, el personatge 1 més el caràcter
1, el personatge té un valor ASCII 49.

201
00:08:57,680 --> 00:09:04,840
Així que això realment està dient 49, més 49, i
en última instància, això va a imprimir 98.

202
00:09:04,840 --> 00:09:06,130
Així que això no imprimeix 2.

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

204
00:09:08,070 --> 00:09:09,271
>> Pregunta 17.

205
00:09:09,271 --> 00:09:11,520
Completar l'aplicació
de imparell a continuació de tal manera

206
00:09:11,520 --> 00:09:14,615
que la funció retorna vertader si
n és imparell i false si n és parell.

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

208
00:09:16,710 --> 00:09:19,330
Aquest és un gran propòsit
per a l'operador mod.

209
00:09:19,330 --> 00:09:24,530
Així que ens prenem el nostre argument n,
si n mod 2 és igual a 1, així

210
00:09:24,530 --> 00:09:28,030
això vol dir que n divideix
per 2 tenia una resta.

211
00:09:28,030 --> 00:09:33,270
Si n dividit per 2 tenia una resta, que
vol dir que n és imparell, de manera que tornar realitat.

212
00:09:33,270 --> 00:09:34,910
Altres vendes tornem falsa.

213
00:09:34,910 --> 00:09:39,070
També podria haver fet n mod 2 iguals
zero, return false, en cas contrari retorna true.

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

215
00:09:41,600 --> 00:09:43,640
>> Penseu en la funció recursiva a continuació.

216
00:09:43,640 --> 00:09:46,920
Així que si n és menor que o
igual a 1, retorna 1,

217
00:09:46,920 --> 00:09:50,430
o torni n vegades f de n menys 1.

218
00:09:50,430 --> 00:09:52,556
Llavors, què és aquesta funció?

219
00:09:52,556 --> 00:09:54,305
Bé, això és només el
funció factorial.

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

221
00:09:55,410 --> 00:09:57,405
Això està molt ben representat
com n factorial.

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

223
00:09:58,720 --> 00:10:02,310
>> Així que ara la pregunta 19, volem
aprofitar aquesta funció recursiva.

224
00:10:02,310 --> 00:10:04,530
Volem que sigui iteratiu.

225
00:10:04,530 --> 00:10:05,874
Llavors, com fem això?

226
00:10:05,874 --> 00:10:07,790
Bo per al personal
solució, i de nou no és

227
00:10:07,790 --> 00:10:11,090
múltiples formes en les que podria haver fet
que, vam començar amb aquest producte int

228
00:10:11,090 --> 00:10:11,812
és igual a 1.

229
00:10:11,812 --> 00:10:13,520
I en tot aquest
bucle for, anem

230
00:10:13,520 --> 00:10:17,590
multiplicar producte a última instància
acabar amb el factorial complet.

231
00:10:17,590 --> 00:10:21,870
Així que per int i és igual a 2, i és
menys d'o igual a n, i ++.

232
00:10:21,870 --> 00:10:24,130
>> Potser es pregunti per què i és igual a 2.

233
00:10:24,130 --> 00:10:28,380
Bé, recordeu que aquí hem de
assegurar-se que el nostre cas base és correcta.

234
00:10:28,380 --> 00:10:32,180
Així que si n és menor o igual
a 1, només estem tornant gener.

235
00:10:32,180 --> 00:10:34,830
Així que aquí, vam començar a i és igual a 2.

236
00:10:34,830 --> 00:10:39,090
Bé, si jo fos 1, llavors ell-- o
si n era 1, llavors el bucle for

237
00:10:39,090 --> 00:10:40,600
no executar en absolut.

238
00:10:40,600 --> 00:10:43,190
I així ho faríem només
producte de tornada, que és 1.

239
00:10:43,190 --> 00:10:45,920
De la mateixa manera, si n eren
ni més ni menys que 1--

240
00:10:45,920 --> 00:10:49,290
si fos 0, 1 negatiu, whatever--
encara estaríem tornant 1,

241
00:10:49,290 --> 00:10:52,260
que és exactament el que el
versió recursiva està fent.

242
00:10:52,260 --> 00:10:54,660
>> Ara, si n és més gran
que 1, llavors anem

243
00:10:54,660 --> 00:10:56,550
fer com a mínim un
iteració d'aquest bucle.

244
00:10:56,550 --> 00:11:00,630
Així que diguem que n és 5, llavors estem
farà vegades de productes és igual a 2.

245
00:11:00,630 --> 00:11:02,165
Així que ara el producte és de 2.

246
00:11:02,165 --> 00:11:04,040
Ara anem a fer
vegades de productes és igual a 3.

247
00:11:04,040 --> 00:11:04,690
Ara és el 6.

248
00:11:04,690 --> 00:11:07,500
Temps de producte és igual a 4, ara és el 24.

249
00:11:07,500 --> 00:11:10,420
Temps de producte és igual a 5, ara és el 120.

250
00:11:10,420 --> 00:11:16,730
Així que, en última instància, estem tornant
120, que és correctament maig factorial.

251
00:11:16,730 --> 00:11:17,510
>> Pregunta 20.

252
00:11:17,510 --> 00:11:22,480
Això és en la que vostè ha de omplir
en aquesta taula amb qualsevol algoritme donat,

253
00:11:22,480 --> 00:11:25,735
res del que hem vist, que
encaixa aquests algorísmica termini

254
00:11:25,735 --> 00:11:28,060
vegades aquests temps d'execució asimptòtica.

255
00:11:28,060 --> 00:11:33,270
Llavors, què és un algoritme que
és l'omega d'1, però gran O de n?

256
00:11:33,270 --> 00:11:35,970
Així que podria ser infinitament
moltes respostes aquí.

257
00:11:35,970 --> 00:11:39,790
La que hem vist probablement més
sovint és només recerca lineal.

258
00:11:39,790 --> 00:11:42,050
>> Així, en el millor dels casos
escenari, el tema que estem

259
00:11:42,050 --> 00:11:44,050
buscant està en el
principi de la llista

260
00:11:44,050 --> 00:11:47,400
i així en omega de passos d'1,
el primer que vam comprovar,

261
00:11:47,400 --> 00:11:49,740
acabem de tornar immediatament
que trobem l'article.

262
00:11:49,740 --> 00:11:52,189
En el pitjor dels casos,
l'article està a l'extrem,

263
00:11:52,189 --> 00:11:53,730
o l'article no està en la llista en absolut.

264
00:11:53,730 --> 00:11:56,700
Així que hem de buscar
tota la llista, tots els n

265
00:11:56,700 --> 00:11:58,480
elements, i és per això que és o de n.

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

267
00:11:59,670 --> 00:12:04,880
>> Així que ara és una cosa que alhora
omega de n log n, i gran O de n log n.

268
00:12:04,880 --> 00:12:08,650
Bé, la cosa més rellevant
que hem vist aquí és fusionar espècie.

269
00:12:08,650 --> 00:12:12,950
Així fusionar espècie, recordar,
és en última instància, Theta

270
00:12:12,950 --> 00:12:16,920
de n log n, on es defineix theta
si tots dos omega i gran O són ​​els mateixos.

271
00:12:16,920 --> 00:12:17,580
Tant n log n.

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

273
00:12:18,690 --> 00:12:21,970
>> Què és una cosa que és omega
de N, i O del quadrat n?

274
00:12:21,970 --> 00:12:23,990
Bé, de nou hi ha
múltiples respostes possibles.

275
00:12:23,990 --> 00:12:26,440
Aquí ens toca dir bombolla espècie.

276
00:12:26,440 --> 00:12:28,840
Inserció espècie també treballaria aquí.

277
00:12:28,840 --> 00:12:31,400
Recordeu que la bombolla de tipus
ha de l'optimització on,

278
00:12:31,400 --> 00:12:34,630
si vostè és capaç d'obtenir
a través de tota la llista

279
00:12:34,630 --> 00:12:37,402
sense necessitat de fer
qualsevol swaps, llavors, bé,

280
00:12:37,402 --> 00:12:40,110
podem tornar immediatament que
la llista es va solucionar per començar.

281
00:12:40,110 --> 00:12:43,185
Així que en el millor dels casos,
és només l'omega de n.

282
00:12:43,185 --> 00:12:45,960
Si no es tracta només d'un bé
perquè el procés de ordenats,

283
00:12:45,960 --> 00:12:48,270
llavors tenim O de n al quadrat swaps.

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

285
00:12:49,330 --> 00:12:55,610
I finalment, tenim la selecció espècie
per n al quadrat, tant omega i gran O.

286
00:12:55,610 --> 00:12:56,850
>> Pregunta 21.

287
00:12:56,850 --> 00:12:58,870
Què hi ha desbordament de sencer?

288
00:12:58,870 --> 00:13:02,160
Bé de nou, similar a l'anterior,
només tenim un nombre finit de bits de

289
00:13:02,160 --> 00:13:04,255
per representar un nombre enter,
per la qual cosa potser 32 bits.

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

291
00:13:06,300 --> 00:13:09,180
Diguem que tenim un enter amb signe.

292
00:13:09,180 --> 00:13:12,800
A continuació, en última instància, el més alt
nombre positiu podem representar

293
00:13:12,800 --> 00:13:15,910
és 2 a l'31 almenys 1.

294
00:13:15,910 --> 00:13:19,370
Llavors, què passa si intentem
a continuació, incrementar aquest sencer?

295
00:13:19,370 --> 00:13:25,320
Bé, anem a anar de 2 a l'31
menys 1, tot el camí fins negatiu 2

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

297
00:13:26,490 --> 00:13:29,470
Així que aquest desbordament de sencers és
quan segueixes incrementant,

298
00:13:29,470 --> 00:13:32,330
i en última instància, no es pot
aconseguir més amunt i que només

299
00:13:32,330 --> 00:13:34,520
envolta tot el camí de tornada
al voltant d'un valor negatiu.

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

301
00:13:35,850 --> 00:13:37,779
>> Què passa amb un desbordament de memòria intermèdia?

302
00:13:37,779 --> 00:13:39,820
Així un tampó overflow--
recorda el que un buffer és.

303
00:13:39,820 --> 00:13:41,000
És només una part de la memòria.

304
00:13:41,000 --> 00:13:43,350
Una cosa així com una matriu és un tampó.

305
00:13:43,350 --> 00:13:46,120
Així que un desbordament de memòria intermèdia és quan
intenta accedir a memòria

306
00:13:46,120 --> 00:13:47,880
més enllà del final de la matriu.

307
00:13:47,880 --> 00:13:50,410
Així que si vostè té una
matriu de mida 5 i vostè

308
00:13:50,410 --> 00:13:53,700
tractar d'accedir a suport de matriu
5 o 6 el suport o el suport 7,

309
00:13:53,700 --> 00:13:56,610
o qualsevol cosa més enllà de la
extrem, o fins i tot gens

310
00:13:56,610 --> 00:14:00,790
suport de sèrie aquí a continuació, negatiu 1--
tots aquests són desbordaments de memòria intermèdia.

311
00:14:00,790 --> 00:14:02,810
Estàs tocant de memòria en mals camins.

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

313
00:14:04,090 --> 00:14:04,730
>> Pregunta 23.

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

315
00:14:05,760 --> 00:14:09,100
Així que en aquest el que necessita
per implementar strlen.

316
00:14:09,100 --> 00:14:11,630
I els diem que es pot
assumeixen s no és nul,

317
00:14:11,630 --> 00:14:13,790
pel que no ha de
fer qualsevol xec per nul.

318
00:14:13,790 --> 00:14:16,190
I hi ha diverses maneres
que podria haver fet això.

319
00:14:16,190 --> 00:14:18,440
Aquí només prenem el senzill.

320
00:14:18,440 --> 00:14:21,780
Comencem amb un comptador, n. n és
comptant el nombre de caràcters que hi ha.

321
00:14:21,780 --> 00:14:25,560
Així que vam començar a 0, i després
iterar sobre la llista completa.

322
00:14:25,560 --> 00:14:29,092
>> És s igual a 0 a suport de la
caràcter terminador nul?

323
00:14:29,092 --> 00:14:31,425
Recordin que estem buscant
el caràcter terminador nul

324
00:14:31,425 --> 00:14:33,360
per determinar quant de temps la nostra cadena és.

325
00:14:33,360 --> 00:14:35,890
Això va a acabar
qualsevol cadena corresponent.

326
00:14:35,890 --> 00:14:39,400
Així que és suport de s 0 igual
per al terminador nul?

327
00:14:39,400 --> 00:14:42,850
Si no és així, llavors anem a
mirar s suport 1, s 2 suport.

328
00:14:42,850 --> 00:14:45,050
Seguim camí fins que
trobar el terminador nul.

329
00:14:45,050 --> 00:14:48,580
Un cop hem trobat, llavors n conté
la longitud total de la cadena,

330
00:14:48,580 --> 00:14:49,942
i només podem tornar aquest.

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

332
00:14:51,180 --> 00:14:51,865
>> Pregunta 24.

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

334
00:14:53,010 --> 00:14:56,050
Així que aquest és l'un en el qual
haver de fer la compensació.

335
00:14:56,050 --> 00:14:59,810
Així que una cosa és bona en un
manera, però de quina manera és dolent?

336
00:14:59,810 --> 00:15:02,980
Així que aquí, fusionar espècie tendeix a
ser més ràpid que la bombolla espècie.

337
00:15:02,980 --> 00:15:06,530
Dit que-- així, hi ha
són múltiples respostes aquí.

338
00:15:06,530 --> 00:15:12,930
Però la principal és que la bombolla espècie
és omega de n per a una llista ordenada.

339
00:15:12,930 --> 00:15:14,950
>> Recordeu que la taula que acabem de veure abans.

340
00:15:14,950 --> 00:15:17,600
Així bombolla ordena omega de
n, el millor dels casos

341
00:15:17,600 --> 00:15:20,010
és que és capaç d'anar més
la llista una vegada, determinar

342
00:15:20,010 --> 00:15:22,270
bé això ja és
ordenats, i retorn.

343
00:15:22,270 --> 00:15:25,960
Ordenament per barreja, sense importar el que
vostè ho fa, és l'omega de n log n.

344
00:15:25,960 --> 00:15:29,200
Així que per a la llista ordenada, bombolla
espècie que serà més ràpid.

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

346
00:15:30,870 --> 00:15:32,430
>> Ara què passa vinculada llistes?

347
00:15:32,430 --> 00:15:36,070
Així que una llista enllaçada pot créixer i encongir
per adaptar-se a tants elements com sigui necessari.

348
00:15:36,070 --> 00:15:38,489
Dit així que--
en general la comparació directa

349
00:15:38,489 --> 00:15:40,280
serà un vinculat
una llista amb una matriu.

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

351
00:15:41,600 --> 00:15:44,050
Així que tot i que les matrius poden
augmentar i reduir fàcilment

352
00:15:44,050 --> 00:15:47,130
per adaptar-se a tants elements
segons sigui necessari, una llista enllaçada

353
00:15:47,130 --> 00:15:49,600
en comparació amb un una array--
matriu té accés aleatori.

354
00:15:49,600 --> 00:15:52,960
Ens pot indexar en qualsevol
en particular element de la matriu.

355
00:15:52,960 --> 00:15:56,430
>> Així que per a una llista enllaçada, no podem
només ha d'anar al cinquè element,

356
00:15:56,430 --> 00:16:00,260
hem de recórrer des del principi
fins arribar al cinquè element.

357
00:16:00,260 --> 00:16:03,990
I això va a impedir-
fer alguna cosa com a recerca binària.

358
00:16:03,990 --> 00:16:08,150
Parlant de recerca binària, recerca binària
tendeix a ser més ràpida que la recerca lineal.

359
00:16:08,150 --> 00:16:11,120
Dit que--
així, una cosa possible

360
00:16:11,120 --> 00:16:13,380
és que no es pot fer binari
buscar en llistes enllaçades,

361
00:16:13,380 --> 00:16:14,730
només pot fer-ho en matrius.

362
00:16:14,730 --> 00:16:18,030
Però, probablement, el més important,
no es pot fer la cerca binària

363
00:16:18,030 --> 00:16:20,690
en una matriu que no està ordenada.

364
00:16:20,690 --> 00:16:23,990
Allà davant pot ser que hagi d'ordenar
la matriu, i només llavors pot

365
00:16:23,990 --> 00:16:25,370
que fas de recerca binària.

366
00:16:25,370 --> 00:16:27,660
Així que si el teu no és
ordenada, per començar,

367
00:16:27,660 --> 00:16:29,250
llavors la recerca lineal podria ser més ràpid.

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

369
00:16:30,620 --> 00:16:31,740
>> Pregunta 27.

370
00:16:31,740 --> 00:16:34,770
Així que consideri el programa a continuació,
que estaran a la següent diapositiva.

371
00:16:34,770 --> 00:16:37,790
I això és en la que estem
voldrà declarar explícitament

372
00:16:37,790 --> 00:16:39,980
els valors per a diferents variables.

373
00:16:39,980 --> 00:16:41,990
Així que donem una ullada a això.

374
00:16:41,990 --> 00:16:43,160
>> Així que la línia un.

375
00:16:43,160 --> 00:16:45,457
Tenim int x és igual a 1.

376
00:16:45,457 --> 00:16:47,040
Aquesta és l'única cosa que ha passat.

377
00:16:47,040 --> 00:16:50,440
Així que en la línia 1, que veiem en la nostra
taula, i que, a, b, i tmp són tots

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

379
00:16:51,540 --> 00:16:52,280
Llavors, ¿què és x?

380
00:16:52,280 --> 00:16:53,860
Bé tot just fixem que igual a 1.

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

382
00:16:55,020 --> 00:16:58,770
I a continuació, la línia dos, bé,
veiem que i s'estableix en 2,

383
00:16:58,770 --> 00:17:00,550
i la taula ja està
emplenat per a nosaltres.

384
00:17:00,550 --> 00:17:03,040
Així que x és 1 iy és 2.

385
00:17:03,040 --> 00:17:05,890
>> Ara, la línia de tres, ara estem
dins de la funció d'intercanvi.

386
00:17:05,890 --> 00:17:07,560
¿Què vam fer passar a intercanviar?

387
00:17:07,560 --> 00:17:11,609
Passem signe x per
1, i símbol d'unió i de b.

388
00:17:11,609 --> 00:17:15,160
Quan el problema anterior
va declarar que la direcció de x

389
00:17:15,160 --> 00:17:17,520
és 0x10, i la direcció d'i és 0x14.

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

391
00:17:18,970 --> 00:17:21,909
Així que a i b són iguals a
0x10 i 0x14, respectivament.

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

393
00:17:23,670 --> 00:17:26,250
>> Ara en línia de tres, ¿quins són x i y?

394
00:17:26,250 --> 00:17:28,554
Bé, res ha canviat
sobre de x i y en aquest punt.

395
00:17:28,554 --> 00:17:30,470
Tot i que són
dins d'un marc principal de pila,

396
00:17:30,470 --> 00:17:32,469
encara tenen la mateixa
els valors que tenien abans.

397
00:17:32,469 --> 00:17:34,030
No hem modificat cap memòria.

398
00:17:34,030 --> 00:17:35,710
Així que x és 1, i és 2.

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

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

401
00:17:37,050 --> 00:17:40,300
Així que ara hem dit int tmp igual a protagonitzar un.

402
00:17:40,300 --> 00:17:44,410
Així que en la línia de quatre, tot
és el mateix excepte per tmp.

403
00:17:44,410 --> 00:17:47,130
No hem canviat cap valor
de res, excepte per tmp.

404
00:17:47,130 --> 00:17:49,230
Estem establint tmp igual a protagonitzar un.

405
00:17:49,230 --> 00:17:50,620
Què és una estrella?

406
00:17:50,620 --> 00:17:56,240
Bé, uns punts a X, per la qual protagonitzen un
va a igualtat de x, que és 1.

407
00:17:56,240 --> 00:18:00,080
Així que tot es copia
baix, i tmp s'estableix en 1.

408
00:18:00,080 --> 00:18:01,110
>> Ara la següent línia.

409
00:18:01,110 --> 00:18:03,380
Estrella és igual a un estel b.

410
00:18:03,380 --> 00:18:10,000
Així per línia five-- bé de nou, tot
que és el mateix, llevat que sigui una estrella és.

411
00:18:10,000 --> 00:18:10,830
Què és una estrella?

412
00:18:10,830 --> 00:18:13,720
Bé, acabem de dir una estrella és x.

413
00:18:13,720 --> 00:18:16,400
Així que estem canviant x a la igualtat d'estrelles b.

414
00:18:16,400 --> 00:18:18,960
Quina és l'estrella b? i. b punts a i.

415
00:18:18,960 --> 00:18:21,030
Així estrella b és i.

416
00:18:21,030 --> 00:18:25,140
Així que estem establint x igual a i,
i tota la resta és igual.

417
00:18:25,140 --> 00:18:29,130
Així que ens veiem en la següent fila que x és ara
2, i la resta són simplement copiar.

418
00:18:29,130 --> 00:18:31,120
>> Ara, en la següent línia, estrella b és igual a tmp.

419
00:18:31,120 --> 00:18:34,740
Bé, acabem de dir estrella b és i,
pel que estem establint i igual a tmp.

420
00:18:34,740 --> 00:18:37,450
Tota la resta és el mateix,
així que tot es copia a baix.

421
00:18:37,450 --> 00:18:42,050
Estem establint i igual a TMP, que és
un, i tota la resta és igual.

422
00:18:42,050 --> 00:18:43,210
>> Ara, per fi, la línia 7.

423
00:18:43,210 --> 00:18:44,700
Estem de tornada a la funció principal.

424
00:18:44,700 --> 00:18:46,350
Estem després d'intercanvi es va acabar.

425
00:18:46,350 --> 00:18:48,972
Hem perdut a, b, i
tmp, però en última instància, ens

426
00:18:48,972 --> 00:18:51,180
no es canvia cap valor
de res en aquest moment,

427
00:18:51,180 --> 00:18:52,800
que acabem de copiar x i i cap avall.

428
00:18:52,800 --> 00:18:56,490
I veiem que x i y són
ara 2 i 1 en lloc d'1 i 2.

429
00:18:56,490 --> 00:18:58,160
El canvi s'ha executat amb èxit.

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

431
00:18:59,500 --> 00:19:00,105
>> Pregunta 28.

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

433
00:19:01,226 --> 00:19:03,100
Suposem que et trobes
els missatges d'error

434
00:19:03,100 --> 00:19:06,790
a continuació en horari d'oficina
l'any que ve com una CA o TF.

435
00:19:06,790 --> 00:19:08,930
Assessorar com solucionar cadascun d'aquests errors.

436
00:19:08,930 --> 00:19:11,160
Així referència indefinida a GetString.

437
00:19:11,160 --> 00:19:12,540
Per què pot vostè veure això?

438
00:19:12,540 --> 00:19:15,380
Bé, si un estudiant està utilitzant
GetString en el seu codi,

439
00:19:15,380 --> 00:19:20,310
s'han inclòs correctament hash CS50
punt h per incloure la biblioteca CS50.

440
00:19:20,310 --> 00:19:22,380
>> Bé, ¿què és el que
que hagi de corregir aquest error?

441
00:19:22,380 --> 00:19:26,810
Han de fer un guió al lcs50
línia d'ordres quan s'està compilant.

442
00:19:26,810 --> 00:19:29,501
Així que si no passen
lcs50 guió so metàl·lic, que són

443
00:19:29,501 --> 00:19:32,000
no tindrà la real
codi que implementa GetString.

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

445
00:19:33,190 --> 00:19:34,170
>> Pregunta 29.

446
00:19:34,170 --> 00:19:36,190
Implícitament declarar
funció de biblioteca strlen.

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

448
00:19:37,550 --> 00:19:40,360
Bé això ara, que no té
fet el hash apropiat incloure.

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

450
00:19:41,440 --> 00:19:45,410
En aquest cas particular, l'arxiu de capçalera
que necessiten per incloure és la cadena de punts h,

451
00:19:45,410 --> 00:19:48,710
i incloent cadena dot h, ara
la student-- ara el compilador

452
00:19:48,710 --> 00:19:51,750
té accés a la
declaracions de strlen,

453
00:19:51,750 --> 00:19:54,120
i se sap que el seu codi
Esteu strlen correctament.

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

455
00:19:55,380 --> 00:19:56,580
>> Pregunta 30.

456
00:19:56,580 --> 00:20:00,240
Més per cent de les conversions
que els arguments de dades.

457
00:20:00,240 --> 00:20:01,540
Llavors, ¿què és això?

458
00:20:01,540 --> 00:20:06,470
Bo recordar que aquests cent
signs-- com són rellevants per printf.

459
00:20:06,470 --> 00:20:08,890
Així que en printf podríem cent-
podríem imprimir alguna cosa

460
00:20:08,890 --> 00:20:11,380
com cent i barra invertida n.

461
00:20:11,380 --> 00:20:15,310
O podem imprimir com cent i,
espai, i per cent, l'espai, i per cent.

462
00:20:15,310 --> 00:20:18,950
Així que per a cada un dels
signes de percentatge, que necessiten

463
00:20:18,950 --> 00:20:21,560
passar una variable al final de printf.

464
00:20:21,560 --> 00:20:26,980
>> Així que si diem que parin printf cent
i barra invertida n prop parin,

465
00:20:26,980 --> 00:20:30,270
així, diem que estem
va a imprimir un nombre enter,

466
00:20:30,270 --> 00:20:33,970
però llavors no passem printf
un enter per imprimir en realitat.

467
00:20:33,970 --> 00:20:37,182
Així que aquí més per cent
conversions que els arguments de dades?

468
00:20:37,182 --> 00:20:39,390
Això és molt dir que tenim
un munt de percentatges,

469
00:20:39,390 --> 00:20:42,445
i no tenim prou variables
per omplir realment en aquests percentatges.

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

471
00:20:44,850 --> 00:20:50,010
>> I llavors, sens dubte, per a la pregunta 31,
definitivament perdut 40 bytes en un blocs.

472
00:20:50,010 --> 00:20:52,350
Així que això és un error de Valgrind.

473
00:20:52,350 --> 00:20:54,720
Això és a dir que
en algun lloc del seu codi,

474
00:20:54,720 --> 00:20:59,010
vostè té una assignació que és 40
bytes gran, així que malloced 40 bytes,

475
00:20:59,010 --> 00:21:00,515
i mai es va alliberar.

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

477
00:21:02,480 --> 00:21:05,140
El més probable és que vostè només ha
trobar alguna pèrdua de memòria,

478
00:21:05,140 --> 00:21:07,650
i trobar on vostè necessita
alliberar aquest bloc de memòria.

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

480
00:21:08,780 --> 00:21:11,910
>> I la pregunta 32,
escriptura no vàlida de mida 4.

481
00:21:11,910 --> 00:21:13,250
Una vegada més es tracta d'un error de Valgrind.

482
00:21:13,250 --> 00:21:15,440
Això no té a veure
amb pèrdues de memòria ara.

483
00:21:15,440 --> 00:21:20,750
És a dir, més likely-- Vull dir, és
algun tipus de drets de memòria no vàlida.

484
00:21:20,750 --> 00:21:23,270
I el més probable és que això és cert
tipus de desbordament de memòria intermèdia.

485
00:21:23,270 --> 00:21:26,560
Quan vostè té una matriu, potser
una matriu d'enters, i anem a

486
00:21:26,560 --> 00:21:30,115
diuen que és de mida 5, i vostè
tractar de tocar matriu suport maig.

487
00:21:30,115 --> 00:21:34,150
Així que si s'intenta escriure en aquesta
valor, això no és un tros de la memòria

488
00:21:34,150 --> 00:21:37,440
que en realitat es té accés a, i
per la qual cosa anem a aconseguir aquest error,

489
00:21:37,440 --> 00:21:39,272
dient escriptura no vàlida de mida 4.

490
00:21:39,272 --> 00:21:42,480
Valgrind va a reconèixer que ets
tractant de tocar la memòria de forma inadequada.

491
00:21:42,480 --> 00:21:43,980
>> I això és tot per quiz0.

492
00:21:43,980 --> 00:21:47,065
Estic Rob Bowden, i això és CS50.

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