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

2
00:00:09,572 --> 00:00:12,030
ROB BOWDEN: Oi, eu sou Rob Bowden,
e vamos falar sobre quiz0.

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

4
00:00:13,280 --> 00:00:14,545
>> Então, primeira pergunta.

5
00:00:14,545 --> 00:00:17,750
Esta é a pergunta que
você precisava para codificar o número

6
00:00:17,750 --> 00:00:21,270
127 nos bulbos binários.

7
00:00:21,270 --> 00:00:23,550
Se você quisesse, você poderia
fazer a conversão regular

8
00:00:23,550 --> 00:00:25,950
de bi-- ou, de decimal para binário.

9
00:00:25,950 --> 00:00:28,300
Mas isso provavelmente vai
para ter um monte de tempo.

10
00:00:28,300 --> 00:00:31,750
Quero dizer, você pode descobrir que,
OK, um está lá, 2 está lá,

11
00:00:31,750 --> 00:00:33,650
4 está lá, 8 está lá.

12
00:00:33,650 --> 00:00:39,280
Maneira mais fácil, é de 128 127 menos um.

13
00:00:39,280 --> 00:00:42,013
Essa lâmpada mais à esquerda é o 128-bit.

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

15
00:00:43,490 --> 00:00:47,860
Assim, 127 é realmente apenas tudo
das outras lâmpadas,

16
00:00:47,860 --> 00:00:51,420
já que é o mais à esquerda
lâmpada menos 1.

17
00:00:51,420 --> 00:00:52,800
Isso é tudo para essa pergunta.

18
00:00:52,800 --> 00:00:54,060
>> Pergunta um.

19
00:00:54,060 --> 00:00:56,710
Assim, com 3 bits que puder
representam 8 valores distintos.

20
00:00:56,710 --> 00:01:01,000
Por que, então, é de 7 a maior não-negativo
inteiro decimal pode representar?

21
00:01:01,000 --> 00:01:04,050
Bem, se só podemos
representam 8 valores distintos,

22
00:01:04,050 --> 00:01:07,430
então o que nós vamos ser
representando é de 0 a 7.

23
00:01:07,430 --> 00:01:08,745
0 leva-se um dos valores.

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

25
00:01:09,980 --> 00:01:11,190
>> Pergunta dois.

26
00:01:11,190 --> 00:01:14,610
Com n bits, quantas distinta
valores que podem representar?

27
00:01:14,610 --> 00:01:19,080
Assim, com n bits, você tem 2
os valores possíveis para cada bit.

28
00:01:19,080 --> 00:01:22,300
Portanto, temos dois valores possíveis para
o primeiro bit, dois valores possíveis

29
00:01:22,300 --> 00:01:24,450
para o segundo, 2
possível para a terceira.

30
00:01:24,450 --> 00:01:28,730
E de modo que é 2 vezes 2 vezes 2, e
em última análise, a resposta é de 2 a n.

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

32
00:01:30,010 --> 00:01:31,100
>> Pergunta três.

33
00:01:31,100 --> 00:01:33,450
O que é 0x50 em binário?

34
00:01:33,450 --> 00:01:39,490
Então lembre-se de que tem um hexadecimal muito
conversão simples de binário.

35
00:01:39,490 --> 00:01:43,180
Então aqui, nós só precisamos olhar para
a 5 e a 0 de forma independente.

36
00:01:43,180 --> 00:01:45,110
Então, qual é 5 em binário?

37
00:01:45,110 --> 00:01:48,400
0101, que é o 1 bit eo bit 4.

38
00:01:48,400 --> 00:01:49,900
Qual é 0 em binário?

39
00:01:49,900 --> 00:01:50,520
Não complicado.

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

41
00:01:52,180 --> 00:01:54,970
Então, basta colocá-los juntos, e
que é o número total de binário.

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

43
00:01:57,640 --> 00:02:00,439
E se você quisesse você poderia
decolar que mais à esquerda zero.

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

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

46
00:02:02,920 --> 00:02:05,733
>> Então, em alternativa,
o que é 0x50 em decimal?

47
00:02:05,733 --> 00:02:08,649
Se você quisesse, você could-- se você estiver
mais confortável com o binário,

48
00:02:08,649 --> 00:02:11,340
você poderia tomar essa resposta binária
e convertê-lo em decimal.

49
00:02:11,340 --> 00:02:13,870
Ou podemos apenas lembrar
que hexadecimal.

50
00:02:13,870 --> 00:02:21,140
Assim que 0 é no 0 º lugar, e
a 5 é, no 16 para o primeiro lugar.

51
00:02:21,140 --> 00:02:25,990
Então, aqui, temos 5 vezes 16 para o
em primeiro lugar, além de 16 0 vezes para a zero,

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

53
00:02:27,520 --> 00:02:29,710
E se você olhou para o
título para a pergunta,

54
00:02:29,710 --> 00:02:32,920
era CS 80, que era uma espécie de
dica para a resposta a este problema.

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

56
00:02:34,460 --> 00:02:35,420
>> Pergunta cinco.

57
00:02:35,420 --> 00:02:40,320
Temos este roteiro zero, o que é
repetindo 4 vezes manteiga de amendoim geléia.

58
00:02:40,320 --> 00:02:42,800
Assim como nós agora o código que em C?

59
00:02:42,800 --> 00:02:47,730
Bem, nós temos aqui-- a parte em negrito
é a única parte que você tinha de implementar.

60
00:02:47,730 --> 00:02:51,950
Portanto, temos um 4 loop que é looping 4
vezes,-ing printf Peanut Butter Jelly,

61
00:02:51,950 --> 00:02:53,910
com a nova linha que o problema pede.

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

63
00:02:55,250 --> 00:02:57,490
>> Pergunta seis, outro problema do risco.

64
00:02:57,490 --> 00:03:00,210
Nós vemos que estamos em um loop para sempre.

65
00:03:00,210 --> 00:03:05,000
Nós estamos dizendo que a variável i
e, em seguida, incrementando i por um.

66
00:03:05,000 --> 00:03:09,580
Agora nós queremos fazer isso em C. Há
múltiplas formas que poderíamos ter feito isto.

67
00:03:09,580 --> 00:03:12,840
Aqui nós aconteceu para codificar o
para sempre como um laço while (true).

68
00:03:12,840 --> 00:03:16,600
Assim, declaramos a variável i, apenas
como tivemos i variável no Scratch.

69
00:03:16,600 --> 00:03:21,950
Declare a variável i, e para sempre
while (true), nós dizemos que a variável i.

70
00:03:21,950 --> 00:03:25,260
Então printf% i-- ou você poderia ter usado% d.

71
00:03:25,260 --> 00:03:27,985
Dizemos que variável e
então incrementá-lo, i ++.

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

73
00:03:29,560 --> 00:03:30,830
>> Pergunta sete.

74
00:03:30,830 --> 00:03:35,560
Agora, queremos fazer algo muito semelhante
Mario ponto c do problema definido.

75
00:03:35,560 --> 00:03:39,110
Queremos imprimir estas hashtags,
queremos imprimir um cinco

76
00:03:39,110 --> 00:03:40,700
por três retângulo destes hashes.

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

78
00:03:41,770 --> 00:03:43,162
Então, como é que vamos fazer isso?

79
00:03:43,162 --> 00:03:45,370
Bem, nós damos-lhe um todo
monte de código, e você só

80
00:03:45,370 --> 00:03:47,560
tem que preencher a função de grade de impressão.

81
00:03:47,560 --> 00:03:49,540
>> Então, o que PrintGrid parece?

82
00:03:49,540 --> 00:03:51,480
Bem, você é passado o
largura e a altura.

83
00:03:51,480 --> 00:03:53,520
Portanto, temos um exterior 4
loop, que é looping

84
00:03:53,520 --> 00:03:57,650
ao longo de todas as linhas do presente
grade que queremos imprimir.

85
00:03:57,650 --> 00:04:01,250
Então nós temos a 4 circuito inter-nested,
essa é a impressão sobre cada coluna.

86
00:04:01,250 --> 00:04:06,210
Assim, para cada linha, nós imprimimos para
cada coluna, um único hash.

87
00:04:06,210 --> 00:04:10,045
Então, no final da linha que imprime um
única linha nova para ir para a próxima linha.

88
00:04:10,045 --> 00:04:11,420
E é isso por toda a rede.

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

90
00:04:12,810 --> 00:04:13,675
>> Pergunta oito.

91
00:04:13,675 --> 00:04:17,170
Uma função como PrintGrid é dito
ter um efeito colateral, mas não um retorno

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

93
00:04:17,670 --> 00:04:19,209
Explique a distinção.

94
00:04:19,209 --> 00:04:23,080
Então, isso depende de você lembrar
o que é um efeito colateral é.

95
00:04:23,080 --> 00:04:25,180
Bem, um retorno value--
sabemos PrintGrid não

96
00:04:25,180 --> 00:04:28,180
tem valor de retorno, uma vez que
aqui se diz vazio.

97
00:04:28,180 --> 00:04:31,150
Então, qualquer coisa que retorna void
realmente não retorna nada.

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

99
00:04:32,200 --> 00:04:33,620
Então, qual é o efeito colateral?

100
00:04:33,620 --> 00:04:36,620
Bem, um efeito colateral é
qualquer coisa que tipo de persistir

101
00:04:36,620 --> 00:04:39,500
após o término da função
que não era apenas retornou,

102
00:04:39,500 --> 00:04:41,340
e não foi só a partir dos insumos.

103
00:04:41,340 --> 00:04:44,970
>> Assim, por exemplo, podemos
alterar uma variável global.

104
00:04:44,970 --> 00:04:46,590
Isso seria um efeito colateral.

105
00:04:46,590 --> 00:04:49,000
Neste caso particular, uma
efeito colateral muito importante

106
00:04:49,000 --> 00:04:51,070
está imprimindo na tela.

107
00:04:51,070 --> 00:04:53,110
Assim que é um efeito colateral
PrintGrid que tem.

108
00:04:53,110 --> 00:04:54,980
Nós imprimir essas coisas para a tela.

109
00:04:54,980 --> 00:04:56,370
E você pode pensar
que como um efeito colateral,

110
00:04:56,370 --> 00:04:58,690
já que é algo que
persistir após essa função termina.

111
00:04:58,690 --> 00:05:01,481
Isso é algo fora do escopo
desta função que, em última análise

112
00:05:01,481 --> 00:05:03,380
está sendo alterado, o
conteúdo da tela.

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

114
00:05:05,200 --> 00:05:05,839
>> Pergunta nove.

115
00:05:05,839 --> 00:05:07,880
Considere o programa abaixo,
para que os números de linha

116
00:05:07,880 --> 00:05:09,740
foram adicionados para
a causa da discussão.

117
00:05:09,740 --> 00:05:13,480
Portanto, neste programa estamos apenas
chamando GetString, armazenando-o

118
00:05:13,480 --> 00:05:16,220
Nesta variável s, e depois
imprimir essa variável s.

119
00:05:16,220 --> 00:05:16,720
Está bem.

120
00:05:16,720 --> 00:05:19,090
Assim, explicar por que uma linha está presente.

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

122
00:05:20,920 --> 00:05:23,820
Por que precisamos de #include CS50 dot h?

123
00:05:23,820 --> 00:05:26,180
Bem, nós estamos chamando a
Função GetString,

124
00:05:26,180 --> 00:05:28,840
e GetString é definida
na biblioteca CS50.

125
00:05:28,840 --> 00:05:31,600
Então, se não tivéssemos
#include CS50 ponto h,

126
00:05:31,600 --> 00:05:35,760
teríamos que declaração implícita
do erro da função GetString

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

128
00:05:36,840 --> 00:05:40,110
Então, precisamos incluir o library--
precisamos incluir o arquivo de cabeçalho,

129
00:05:40,110 --> 00:05:42,870
ou então o compilador não vai
reconhecer que existe GetString.

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

131
00:05:44,380 --> 00:05:46,140
>> Explique por que a linha dois está presente.

132
00:05:46,140 --> 00:05:47,890
Assim padrão dot h io.

133
00:05:47,890 --> 00:05:50,430
É exatamente o mesmo
como o problema anterior,

134
00:05:50,430 --> 00:05:53,310
exceto em vez de lidar com
GetString, estamos falando de printf.

135
00:05:53,310 --> 00:05:56,654
Então, se nós não dissemos que precisamos
para incluir padrão io ponto h,

136
00:05:56,654 --> 00:05:58,820
então não seria capaz
para usar a função printf,

137
00:05:58,820 --> 00:06:00,653
porque o compilador
não saber sobre ele.

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

139
00:06:01,750 --> 00:06:05,260
>> Para entendermos que o que é o significado
de anular em linha de quatro?

140
00:06:05,260 --> 00:06:08,010
Portanto, temos aqui int main (void).

141
00:06:08,010 --> 00:06:10,600
Isso é apenas dizendo que nós
não estão recebendo qualquer linha de comando

142
00:06:10,600 --> 00:06:12,280
argumentos para principal.

143
00:06:12,280 --> 00:06:17,390
Lembre-se que nós poderíamos dizer int
principais suportes int argc argv corda.

144
00:06:17,390 --> 00:06:20,400
Então aqui nós apenas dizer vazio de dizer que
estão ignorando os argumentos de linha de comando.

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

146
00:06:21,840 --> 00:06:25,225
>> Explique, no que diz respeito à memória, exatamente
o que GetString em linha seis retornos.

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

148
00:06:27,040 --> 00:06:31,640
GetString está retornando de um bloco de
memória, uma matriz de caracteres.

149
00:06:31,640 --> 00:06:34,870
É realmente de voltar a
ponteiro para o primeiro caractere.

150
00:06:34,870 --> 00:06:37,170
Lembre-se que uma string é uma estrela de char.

151
00:06:37,170 --> 00:06:41,360
Assim, s é um ponteiro para o primeiro
personagem em qualquer que seja a seqüência é

152
00:06:41,360 --> 00:06:43,510
que o usuário digitou no teclado.

153
00:06:43,510 --> 00:06:47,070
E que a memória passa a ser malloced,
para que a memória está no heap.

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

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

156
00:06:50,450 --> 00:06:51,960
Considere o programa abaixo.

157
00:06:51,960 --> 00:06:55,579
Então, tudo isso programa está fazendo
é printf-ing 1 dividido por 10.

158
00:06:55,579 --> 00:06:57,370
Então, quando compilado e
executado, este programa

159
00:06:57,370 --> 00:07:01,170
saídas 0.0, apesar de
1 dividido por 10 é de 0,1.

160
00:07:01,170 --> 00:07:02,970
Então por que é 0.0?

161
00:07:02,970 --> 00:07:05,510
Bem, isso é porque
da divisão inteira.

162
00:07:05,510 --> 00:07:08,580
Assim, é um número inteiro de 1, 10 é um número inteiro.

163
00:07:08,580 --> 00:07:11,980
Então, 1 dividido por 10, tudo
é tratada como números inteiros,

164
00:07:11,980 --> 00:07:16,380
e no C, quando fazemos a divisão inteira,
nós truncar qualquer ponto decimal.

165
00:07:16,380 --> 00:07:19,590
Então, 1 dividido por 10 é
0, e então nós estamos tentando

166
00:07:19,590 --> 00:07:24,410
para imprimir que, como uma bóia, de modo
zero, impresso como um float é de 0,0.

167
00:07:24,410 --> 00:07:27,400
E é por isso que temos 0,0.

168
00:07:27,400 --> 00:07:28,940
>> Considere o programa abaixo.

169
00:07:28,940 --> 00:07:31,280
Agora estamos imprimindo 0.1.

170
00:07:31,280 --> 00:07:34,280
Portanto, não há divisão de inteiros,
estamos apenas a impressão de 0,1,

171
00:07:34,280 --> 00:07:37,100
mas estamos de imprimi-lo
28 casas decimais.

172
00:07:37,100 --> 00:07:41,810
E temos essa 0,1000, um grupo inteiro
de zeros, 5 5 5, blá blá blá.

173
00:07:41,810 --> 00:07:45,495
Portanto, a questão aqui é por isso que o faz
imprimir que, em vez de exatamente 0,1?

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

175
00:07:46,620 --> 00:07:49,640
>> Assim, a razão é aqui agora
ponto flutuante imprecisão.

176
00:07:49,640 --> 00:07:53,410
Lembre-se que um float é de apenas 32 bits.

177
00:07:53,410 --> 00:07:57,540
Por isso, só pode representar um número finito
de valores de ponto flutuante com os 32

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

179
00:07:58,560 --> 00:08:01,760
Bem, há, em última instância infinitamente
muitos valores de ponto flutuante,

180
00:08:01,760 --> 00:08:04,940
e há infinitamente muitos flutuante
valores pontuais em entre 0 e 1,

181
00:08:04,940 --> 00:08:07,860
e estamos, obviamente, capaz de
representam ainda mais valores do que isso.

182
00:08:07,860 --> 00:08:13,230
Então nós temos que fazer sacrifícios para
ser capaz de representar a maioria dos valores.

183
00:08:13,230 --> 00:08:16,960
>> Assim, um valor como 0,1, aparentemente
não podemos garantir que exatamente.

184
00:08:16,960 --> 00:08:22,500
Então, ao invés de representar 0,1 nós fazemos o
melhor que podemos representar este 0.100000 5 5

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

186
00:08:23,260 --> 00:08:26,306
E isso é muito perto, mas
para uma série de aplicações

187
00:08:26,306 --> 00:08:28,430
você tem que se preocupar com
ponto flutuante imprecisão,

188
00:08:28,430 --> 00:08:30,930
porque nós simplesmente não pode representar
todos os pontos flutuantes exatamente.

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

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

191
00:08:33,380 --> 00:08:34,679
Considere o código abaixo.

192
00:08:34,679 --> 00:08:36,630
Estamos apenas a impressão 1 mais 1.

193
00:08:36,630 --> 00:08:38,289
Portanto, não há nenhum truque aqui.

194
00:08:38,289 --> 00:08:41,780
1 mais 1 avalia a 2, e
então nós estamos imprimindo isso.

195
00:08:41,780 --> 00:08:42,789
Isso só imprime 2.

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

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

198
00:08:44,700 --> 00:08:49,450
Agora estamos imprimindo o caráter
1 mais o caráter 1.

199
00:08:49,450 --> 00:08:52,110
Então, por que isso não faz
imprimir a mesma coisa?

200
00:08:52,110 --> 00:08:57,680
Bem, o personagem 1 mais o caráter
1, o personagem tem um valor ASCII 49.

201
00:08:57,680 --> 00:09:04,840
Então, isso realmente está dizendo 49 mais 49, e
em última análise, isso vai imprimir 98.

202
00:09:04,840 --> 00:09:06,130
Portanto, este não imprime 2.

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

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

205
00:09:09,271 --> 00:09:11,520
Completar a implementação
de impar abaixo de tal maneira

206
00:09:11,520 --> 00:09:14,615
que a função retorna true se
n é estranho e falso se n é par.

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

208
00:09:16,710 --> 00:09:19,330
Esta é uma grande propósito
para o operador mod.

209
00:09:19,330 --> 00:09:24,530
Então, tomamos nosso argumento n,
se n mod 2 é igual a 1, bem

210
00:09:24,530 --> 00:09:28,030
que significa que n dividido
por 2 tinha um resto.

211
00:09:28,030 --> 00:09:33,270
Se n dividido por 2 tinha um remanescente, que
significa que n é ímpar, então voltamos verdade.

212
00:09:33,270 --> 00:09:34,910
Outra coisa que retornar falso.

213
00:09:34,910 --> 00:09:39,070
Você também poderia ter feito n mod 2 é igual a
zero, retornar falso, senão retornar verdadeiro.

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

215
00:09:41,600 --> 00:09:43,640
>> Considere a função recursiva abaixo.

216
00:09:43,640 --> 00:09:46,920
Assim, se n é inferior ou
igual a 1, de regresso 1,

217
00:09:46,920 --> 00:09:50,430
else return n vezes f de n menos um.

218
00:09:50,430 --> 00:09:52,556
Então, qual é essa função?

219
00:09:52,556 --> 00:09:54,305
Bem, este é apenas o
função fatorial.

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

221
00:09:55,410 --> 00:09:57,405
Isso está muito bem representado
como n fatorial.

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

223
00:09:58,720 --> 00:10:02,310
>> Assim questão 19 agora, queremos
assumir esta função recursiva.

224
00:10:02,310 --> 00:10:04,530
Queremos torná-lo interativo.

225
00:10:04,530 --> 00:10:05,874
Então, como vamos fazer isso?

226
00:10:05,874 --> 00:10:07,790
Bem para o pessoal
solução, e novamente há

227
00:10:07,790 --> 00:10:11,090
várias maneiras que você poderia ter feito
que, começamos com este produto int

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

229
00:10:11,812 --> 00:10:13,520
E ao longo deste
loop for, vamos

230
00:10:13,520 --> 00:10:17,590
se multiplicar produto para finalmente
acabar com o fatorial completo.

231
00:10:17,590 --> 00:10:21,870
Assim, para int i é igual a 2, i é
inferior ou igual a n, i ++.

232
00:10:21,870 --> 00:10:24,130
>> Você pode estar se perguntando por que eu é igual a 2.

233
00:10:24,130 --> 00:10:28,380
Bem, lembre-se que aqui temos que
fazer com que o nosso caso base está correto.

234
00:10:28,380 --> 00:10:32,180
Assim, se n for menor ou igual
1, nós estamos apenas retornando uma.

235
00:10:32,180 --> 00:10:34,830
Então, aqui, começamos a i é igual a 2.

236
00:10:34,830 --> 00:10:39,090
Bem, se eu fosse um, então as-- ou
se n fosse 1, então o loop

237
00:10:39,090 --> 00:10:40,600
não seria executado em tudo.

238
00:10:40,600 --> 00:10:43,190
E assim teríamos apenas
produto de retorno, que é 1.

239
00:10:43,190 --> 00:10:45,920
Da mesma forma, se n fosse
nada menos do que 1--

240
00:10:45,920 --> 00:10:49,290
se fosse 0, 1 negativo, whatever--
nós ainda estaríamos voltando 1,

241
00:10:49,290 --> 00:10:52,260
que é exatamente o que o
versão recursiva está fazendo.

242
00:10:52,260 --> 00:10:54,660
>> Agora, se n for maior
que 1, então nós vamos

243
00:10:54,660 --> 00:10:56,550
fazer pelo menos um
iteração deste circuito.

244
00:10:56,550 --> 00:11:00,630
Então, digamos que n é 5, então nós estamos
vai fazer vezes de produtos é igual a 2.

245
00:11:00,630 --> 00:11:02,165
Portanto, agora o produto é 2.

246
00:11:02,165 --> 00:11:04,040
Agora nós vamos fazer
é igual a 3 vezes produtos.

247
00:11:04,040 --> 00:11:04,690
Agora é 6.

248
00:11:04,690 --> 00:11:07,500
Produto vezes é igual a 4, agora é 24.

249
00:11:07,500 --> 00:11:10,420
Produto é igual a 5 vezes, agora é de 120.

250
00:11:10,420 --> 00:11:16,730
Então, em última análise, estamos voltando
120, que é corretamente 5 fatorial.

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

252
00:11:17,510 --> 00:11:22,480
Este é aquele em que você tem que preencher
nesta tabela com qualquer algoritmo,

253
00:11:22,480 --> 00:11:25,735
qualquer coisa que já vimos, que
se encaixa nesses prazo algorítmica

254
00:11:25,735 --> 00:11:28,060
vezes esses tempos de execução assintótica.

255
00:11:28,060 --> 00:11:33,270
Então, o que é um algoritmo que
omega é de 1, mas grande O de n?

256
00:11:33,270 --> 00:11:35,970
Portanto, não poderia ser infinitamente
muitas respostas aqui.

257
00:11:35,970 --> 00:11:39,790
O que temos visto, provavelmente, mais
freqüentemente é apenas busca linear.

258
00:11:39,790 --> 00:11:42,050
>> Assim, no melhor dos casos
cenário, o item que estamos

259
00:11:42,050 --> 00:11:44,050
procurando está no
início da lista

260
00:11:44,050 --> 00:11:47,400
e assim em omega de 1 passos,
a primeira coisa que verificar,

261
00:11:47,400 --> 00:11:49,740
nós apenas retornar imediatamente
que encontramos o item.

262
00:11:49,740 --> 00:11:52,189
Na pior das hipóteses,
o produto é, no final,

263
00:11:52,189 --> 00:11:53,730
ou o item não está na lista de todo.

264
00:11:53,730 --> 00:11:56,700
Então, temos que procurar
toda a lista, tudo n

265
00:11:56,700 --> 00:11:58,480
elementos, e é por isso que é o de n.

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

267
00:11:59,670 --> 00:12:04,880
>> Portanto, agora é algo que é ao mesmo tempo
omega de log n n, e grande O de n log n.

268
00:12:04,880 --> 00:12:08,650
Bem, a coisa mais relevante
nós vimos aqui é merge sort.

269
00:12:08,650 --> 00:12:12,950
Então, merge sort, lembre-se,
é, em última análise teta

270
00:12:12,950 --> 00:12:16,920
de n log n, onde teta é definida
se ambos omega e grande O são os mesmos.

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

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

273
00:12:18,690 --> 00:12:21,970
>> O que é algo que é omega
de n, e O de n ao quadrado?

274
00:12:21,970 --> 00:12:23,990
Bem, mais uma vez há
várias respostas possíveis.

275
00:12:23,990 --> 00:12:26,440
Aqui nós acontecer a dizer bubble sort.

276
00:12:26,440 --> 00:12:28,840
Ordenação por inserção também funcionaria aqui.

277
00:12:28,840 --> 00:12:31,400
Lembre-se que bubble sort
tem que optimização, onde,

278
00:12:31,400 --> 00:12:34,630
se você é capaz de obter
toda a lista

279
00:12:34,630 --> 00:12:37,402
sem a necessidade de fazer
quaisquer swaps, então, bem,

280
00:12:37,402 --> 00:12:40,110
podemos voltar imediatamente que
a lista foi classificada para começar.

281
00:12:40,110 --> 00:12:43,185
Assim, na melhor das hipóteses,
é apenas omega de n.

282
00:12:43,185 --> 00:12:45,960
Se ele não é apenas um bem
lista para começar com ordenados,

283
00:12:45,960 --> 00:12:48,270
então nós temos O de n ao quadrado swaps.

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

285
00:12:49,330 --> 00:12:55,610
E, finalmente, temos a seleção espécie
para n ao quadrado, ambos omega e grande O.

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

287
00:12:56,850 --> 00:12:58,870
O que há de integer overflow?

288
00:12:58,870 --> 00:13:02,160
Bem de novo, semelhante à anterior,
temos apenas um número finito de pedaços

289
00:13:02,160 --> 00:13:04,255
para representar um número inteiro,
Então, talvez 32 bits.

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

291
00:13:06,300 --> 00:13:09,180
Vamos dizer que temos um inteiro assinado.

292
00:13:09,180 --> 00:13:12,800
Em seguida, em última análise, a maior
número positivo que pode representar

293
00:13:12,800 --> 00:13:15,910
é de 2 a 31 menos 1.

294
00:13:15,910 --> 00:13:19,370
Então o que acontece se tentarmos
então incrementar esse número inteiro?

295
00:13:19,370 --> 00:13:25,320
Bem, nós estamos indo para ir de 2 a 31
menos 1, todo o caminho para negativa 2

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

297
00:13:26,490 --> 00:13:29,470
Portanto, este é integer overflow
quando você manter o incremento,

298
00:13:29,470 --> 00:13:32,330
e, finalmente, você não pode
obter mais alto e ele só

299
00:13:32,330 --> 00:13:34,520
envolve toda a maneira para trás
em torno de um valor negativo.

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

301
00:13:35,850 --> 00:13:37,779
>> Que tal um buffer overflow?

302
00:13:37,779 --> 00:13:39,820
Assim, um tampão de overflow--
lembre-se que é um buffer.

303
00:13:39,820 --> 00:13:41,000
É apenas um pedaço de memória.

304
00:13:41,000 --> 00:13:43,350
Algo como uma matriz é um buffer.

305
00:13:43,350 --> 00:13:46,120
Então, um buffer overflow é quando
você tenta acessar a memória

306
00:13:46,120 --> 00:13:47,880
além do final do array.

307
00:13:47,880 --> 00:13:50,410
Então, se você tem um
matriz de tamanho 5 e você

308
00:13:50,410 --> 00:13:53,700
tentar acessar o suporte de matriz
5 ou 6 suporte ou suporte 7,

309
00:13:53,700 --> 00:13:56,610
ou qualquer coisa além do
final, ou mesmo nada

310
00:13:56,610 --> 00:14:00,790
suporte de matriz below-- negativo 1--
todos esses são estouros de buffer.

311
00:14:00,790 --> 00:14:02,810
Você está tocando memória em maus caminhos.

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

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

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

315
00:14:05,760 --> 00:14:09,100
Então, em um presente que você precisa
para implementar strlen.

316
00:14:09,100 --> 00:14:11,630
E nós lhes dizemos que você pode
assumir s não será nulo,

317
00:14:11,630 --> 00:14:13,790
assim você não tem que
fazer qualquer verificação para nulo.

318
00:14:13,790 --> 00:14:16,190
E existem várias maneiras
você poderia ter feito isso.

319
00:14:16,190 --> 00:14:18,440
Aqui nós apenas tomar o simples.

320
00:14:18,440 --> 00:14:21,780
Começamos com um contador, n. n é
contar quantos caracteres existem.

321
00:14:21,780 --> 00:14:25,560
Então, vamos começar com 0, e então nós
iterar sobre a lista inteira.

322
00:14:25,560 --> 00:14:29,092
>> S é igual a 0 suporte do
caractere terminador nulo?

323
00:14:29,092 --> 00:14:31,425
Lembre-se que estamos procurando
o caractere terminador nulo

324
00:14:31,425 --> 00:14:33,360
para determinar quanto tempo a nossa cadeia é.

325
00:14:33,360 --> 00:14:35,890
Isso vai terminar
qualquer seqüência relevante.

326
00:14:35,890 --> 00:14:39,400
Então é s suporte 0 igual
para o terminador nulo?

327
00:14:39,400 --> 00:14:42,850
Se não é, então vamos
olhar para s faixa 1, s 2 suporte.

328
00:14:42,850 --> 00:14:45,050
Continuamos até que
encontrar o terminador nulo.

329
00:14:45,050 --> 00:14:48,580
Uma vez que nós encontramos, então n contém
o comprimento total da cadeia,

330
00:14:48,580 --> 00:14:49,942
e podemos retornar apenas isso.

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

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

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

334
00:14:53,010 --> 00:14:56,050
Portanto, este é aquele em que você
tem que fazer o trade off.

335
00:14:56,050 --> 00:14:59,810
Então, uma coisa é boa em um
maneira, mas de que maneira é ruim?

336
00:14:59,810 --> 00:15:02,980
Então, aqui, merge sort tende a
ser mais rápido do bubble sort.

337
00:15:02,980 --> 00:15:06,530
Dito isso-- bem, não
várias respostas aqui.

338
00:15:06,530 --> 00:15:12,930
Mas o principal é que bubble sort
é omega de n para uma lista ordenada.

339
00:15:12,930 --> 00:15:14,950
>> Lembre-se que a tabela que acabamos de ver antes.

340
00:15:14,950 --> 00:15:17,600
Então bolha classifica omega de
n, o melhor cenário

341
00:15:17,600 --> 00:15:20,010
é que é capaz de ir um pouco mais
lista uma vez, determinar

342
00:15:20,010 --> 00:15:22,270
hey isso já é
classificadas e retorno.

343
00:15:22,270 --> 00:15:25,960
Merge sort, não importa o que
você faz, é omega de log n n.

344
00:15:25,960 --> 00:15:29,200
Assim, por lista ordenada, bolha
tipo vai ser mais rápido.

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

346
00:15:30,870 --> 00:15:32,430
>> Agora que sobre listas ligadas?

347
00:15:32,430 --> 00:15:36,070
Assim, uma lista ligada pode crescer e encolher
para caber tantos elementos como necessário.

348
00:15:36,070 --> 00:15:38,489
Dito assim que--
normalmente a comparação directa

349
00:15:38,489 --> 00:15:40,280
vai ser um ligado
lista com um array.

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

351
00:15:41,600 --> 00:15:44,050
Assim, mesmo que as matrizes podem
facilmente aumentar e diminuir

352
00:15:44,050 --> 00:15:47,130
para caber tantos elementos
conforme necessário, uma lista ligada

353
00:15:47,130 --> 00:15:49,600
em comparação com um um array--
matriz tem acesso aleatório.

354
00:15:49,600 --> 00:15:52,960
Podemos índice em qualquer
nomeadamente elemento da matriz.

355
00:15:52,960 --> 00:15:56,430
>> Assim, para uma lista ligada, não podemos
basta ir até o quinto elemento,

356
00:15:56,430 --> 00:16:00,260
temos que percorrer desde o início
até chegarmos ao quinto elemento.

357
00:16:00,260 --> 00:16:03,990
E isso vai nos impedir de
fazer algo como busca binária.

358
00:16:03,990 --> 00:16:08,150
Falando de busca binária, busca binária
tende a ser mais rápido do que a busca linear.

359
00:16:08,150 --> 00:16:11,120
Dito que--
assim, uma coisa possível

360
00:16:11,120 --> 00:16:13,380
é que você não pode fazer binário
pesquisar em listas ligadas,

361
00:16:13,380 --> 00:16:14,730
você só pode fazê-lo em arrays.

362
00:16:14,730 --> 00:16:18,030
Mas, provavelmente, mais importante ainda,
você não pode fazer busca binária

363
00:16:18,030 --> 00:16:20,690
em uma matriz que não está classificada.

364
00:16:20,690 --> 00:16:23,990
Upfront você pode precisar para classificar
a matriz, e só então pode

365
00:16:23,990 --> 00:16:25,370
você faz a busca binária.

366
00:16:25,370 --> 00:16:27,660
Portanto, se sua coisa não é
ordenada, para começar,

367
00:16:27,660 --> 00:16:29,250
em seguida, busca linear pode ser mais rápido.

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

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

370
00:16:31,740 --> 00:16:34,770
Por isso, considero o programa abaixo,
que será no próximo slide.

371
00:16:34,770 --> 00:16:37,790
E este é o único onde estamos
vai querer declarar explicitamente

372
00:16:37,790 --> 00:16:39,980
os valores para várias variáveis.

373
00:16:39,980 --> 00:16:41,990
Então, vamos olhar para isso.

374
00:16:41,990 --> 00:16:43,160
>> Então linha um.

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

376
00:16:45,457 --> 00:16:47,040
Essa é a única coisa que aconteceu.

377
00:16:47,040 --> 00:16:50,440
Assim, na linha um, vemos em nossa
tabela, que y, a, b, e são todos tmp

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

379
00:16:51,540 --> 00:16:52,280
Então, o que é x?

380
00:16:52,280 --> 00:16:53,860
Bem, nós apenas configurá-lo igual a 1.

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

382
00:16:55,020 --> 00:16:58,770
E depois a linha dois, bem,
vemos que y é definido como 2,

383
00:16:58,770 --> 00:17:00,550
e a tabela já está
preenchido para nós.

384
00:17:00,550 --> 00:17:03,040
Assim, x é 1 e y é 2.

385
00:17:03,040 --> 00:17:05,890
>> Agora, a linha de três, estamos agora
dentro da função swap.

386
00:17:05,890 --> 00:17:07,560
O que nós passamos para trocar?

387
00:17:07,560 --> 00:17:11,609
Passamos comercial x para
um e comercial y de b.

388
00:17:11,609 --> 00:17:15,160
Onde o problema anteriormente
afirmado que o endereço de x

389
00:17:15,160 --> 00:17:17,520
é 0x10, e o endereço de y é 0x14.

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

391
00:17:18,970 --> 00:17:21,909
Assim, a e b são iguais aos
0x10 e 0x14, respectivamente.

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

393
00:17:23,670 --> 00:17:26,250
>> Agora a linha de três, que são x e y?

394
00:17:26,250 --> 00:17:28,554
Bem, nada mudou
cerca de x e y neste ponto.

395
00:17:28,554 --> 00:17:30,470
Mesmo que sejam
dentro de um quadro de pilha principal,

396
00:17:30,470 --> 00:17:32,469
eles ainda têm o mesmo
valores que faziam antes.

397
00:17:32,469 --> 00:17:34,030
Nós não modificou nenhuma memória.

398
00:17:34,030 --> 00:17:35,710
Assim, x é 1, y é 2.

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

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

401
00:17:37,050 --> 00:17:40,300
Então, agora nós dissemos int tmp igual para estrelar um.

402
00:17:40,300 --> 00:17:44,410
Assim, na linha de quatro, tudo
é o mesmo, exceto para tmp.

403
00:17:44,410 --> 00:17:47,130
Nós não mudamos os valores
de qualquer coisa, exceto para tmp.

404
00:17:47,130 --> 00:17:49,230
Estamos criando tmp igual para estrelar um.

405
00:17:49,230 --> 00:17:50,620
O que é uma estrela?

406
00:17:50,620 --> 00:17:56,240
Bem, alguns pontos de x, Então estrelar um
vai x igual, o que é um.

407
00:17:56,240 --> 00:18:00,080
Então, tudo se copia
para baixo, e tmp é definido como 1.

408
00:18:00,080 --> 00:18:01,110
>> Agora, a próxima linha.

409
00:18:01,110 --> 00:18:03,380
Estrela um é igual a estrela b.

410
00:18:03,380 --> 00:18:10,000
Então por linha five-- bem novamente, tudo
é o mesmo, exceto que quer uma estrela é.

411
00:18:10,000 --> 00:18:10,830
O que é uma estrela?

412
00:18:10,830 --> 00:18:13,720
Bem, nós apenas dissemos estrela é um x.

413
00:18:13,720 --> 00:18:16,400
Então, nós estamos mudando x para igual estrela b.

414
00:18:16,400 --> 00:18:18,960
O que é a estrela b? y. b aponta para y.

415
00:18:18,960 --> 00:18:21,030
Assim estrela b é y.

416
00:18:21,030 --> 00:18:25,140
Então, nós estamos definindo x igual a y,
e tudo o resto é o mesmo.

417
00:18:25,140 --> 00:18:29,130
Assim, vemos na próxima linha que x é agora
2, eo resto são apenas copiados para baixo.

418
00:18:29,130 --> 00:18:31,120
>> Agora, na próxima linha, estrela b é igual tmp.

419
00:18:31,120 --> 00:18:34,740
Bem, nós apenas dissemos estrela b é y,
por isso, estamos definindo y igual a tmp.

420
00:18:34,740 --> 00:18:37,450
Tudo o resto é o mesmo,
portanto, tudo é copiado para baixo.

421
00:18:37,450 --> 00:18:42,050
Estamos definindo y igual a tmp, que é
um, e tudo o resto é o mesmo.

422
00:18:42,050 --> 00:18:43,210
>> Agora, finalmente, a linha sete.

423
00:18:43,210 --> 00:18:44,700
Estamos de volta na função principal.

424
00:18:44,700 --> 00:18:46,350
Estamos atrás de swap está terminado.

425
00:18:46,350 --> 00:18:48,972
Perdemos a, b, e
tmp, mas em última análise,

426
00:18:48,972 --> 00:18:51,180
não alterar quaisquer valores
de nada neste momento,

427
00:18:51,180 --> 00:18:52,800
nós apenas copiar x e y para baixo.

428
00:18:52,800 --> 00:18:56,490
E vemos que x e y são
1 e 2 agora, em vez de 1 e 2.

429
00:18:56,490 --> 00:18:58,160
O swap tem executado com sucesso.

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

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

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

433
00:19:01,226 --> 00:19:03,100
Suponha que você encontrar
as mensagens de erro

434
00:19:03,100 --> 00:19:06,790
abaixo, durante o horário de expediente
no próximo ano, como CA ou TF.

435
00:19:06,790 --> 00:19:08,930
Aconselhar como corrigir cada um desses erros.

436
00:19:08,930 --> 00:19:11,160
Referência, de modo indefinido para GetString.

437
00:19:11,160 --> 00:19:12,540
Por que você pode ver isso?

438
00:19:12,540 --> 00:19:15,380
Bem, se um aluno está usando
GetString em seu código,

439
00:19:15,380 --> 00:19:20,310
eles corretamente hash incluído CS50
dot h para incluir a biblioteca CS50.

440
00:19:20,310 --> 00:19:22,380
>> Bem, o que eles fazem
precisa corrigir esse erro?

441
00:19:22,380 --> 00:19:26,810
Eles precisam fazer uma lcs50 traço no
linha de comando quando se está compilando.

442
00:19:26,810 --> 00:19:29,501
Então, se eles não passam
clang lcs50 traço, eles são

443
00:19:29,501 --> 00:19:32,000
não vai ter o real
código que implementa GetString.

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

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

446
00:19:34,170 --> 00:19:36,190
Implicitamente declarando
função da biblioteca strlen.

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

448
00:19:37,550 --> 00:19:40,360
Bem, isso agora, eles não têm
feito o hash correto incluir.

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

450
00:19:41,440 --> 00:19:45,410
Neste caso particular, o arquivo de cabeçalho
eles precisam incluir é string ponto h,

451
00:19:45,410 --> 00:19:48,710
e incluindo seqüência ponto h, agora
o student-- agora o compilador

452
00:19:48,710 --> 00:19:51,750
tem acesso ao
declarações de strlen,

453
00:19:51,750 --> 00:19:54,120
e ele sabe que o seu código
está usando strlen corretamente.

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

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

456
00:19:56,580 --> 00:20:00,240
Mais conversões por cento
do que argumentos de dados.

457
00:20:00,240 --> 00:20:01,540
Então, o que é isso?

458
00:20:01,540 --> 00:20:06,470
Bom lembrar que estes cento
signs-- como eles são relevantes para printf.

459
00:20:06,470 --> 00:20:08,890
Assim, em printf podemos percent--
podemos imprimir algo

460
00:20:08,890 --> 00:20:11,380
como por cento i barra invertida n.

461
00:20:11,380 --> 00:20:15,310
Ou podemos imprimir como i por cento,
espaço, i por cento, espaço, i por cento.

462
00:20:15,310 --> 00:20:18,950
Assim, para cada um desses
sinais de porcentagem, precisamos

463
00:20:18,950 --> 00:20:21,560
passar uma variável no final do printf.

464
00:20:21,560 --> 00:20:26,980
>> Então, se nós dizemos paren printf cento
i barra invertida paren n próximos,

465
00:20:26,980 --> 00:20:30,270
bem, dizemos que estamos
vai imprimir um número inteiro,

466
00:20:30,270 --> 00:20:33,970
mas então nós não passar printf
um número inteiro de realmente imprimir.

467
00:20:33,970 --> 00:20:37,182
Então aqui mais por cento
conversões do que argumentos dados?

468
00:20:37,182 --> 00:20:39,390
Isso é dizer que temos
um monte de porcentagens,

469
00:20:39,390 --> 00:20:42,445
e não temos variáveis ​​suficientes
para realmente preencher esses percentuais.

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

471
00:20:44,850 --> 00:20:50,010
>> E, em seguida, definitivamente, para a pergunta 31,
definitivamente perdeu 40 bytes em um blocos.

472
00:20:50,010 --> 00:20:52,350
Portanto, este é um erro Valgrind.

473
00:20:52,350 --> 00:20:54,720
Isto é dizer que
em algum lugar no seu código,

474
00:20:54,720 --> 00:20:59,010
você tem uma atribuição que é de 40
bytes grande para que você malloced 40 bytes,

475
00:20:59,010 --> 00:21:00,515
e você nunca libertou-o.

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

477
00:21:02,480 --> 00:21:05,140
O mais provável é que você só precisa
encontrar algum vazamento de memória,

478
00:21:05,140 --> 00:21:07,650
e descobrir onde você precisa
libertar este bloco de memória.

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

480
00:21:08,780 --> 00:21:11,910
>> E pergunta 32,
write inválido de tamanho 4.

481
00:21:11,910 --> 00:21:13,250
Novamente este é um erro Valgrind.

482
00:21:13,250 --> 00:21:15,440
Isso não tem a ver
com vazamentos de memória agora.

483
00:21:15,440 --> 00:21:20,750
Isto é, a maioria likely-- eu quero dizer, é
algum tipo de direitos de memória inválidos.

484
00:21:20,750 --> 00:21:23,270
E provavelmente isso é algum
tipo de buffer overflow.

485
00:21:23,270 --> 00:21:26,560
Onde você tem uma matriz, talvez
uma matriz de inteiros, e vamos

486
00:21:26,560 --> 00:21:30,115
dizem que é de tamanho 5, e você
tentar tocar suporte matriz 5.

487
00:21:30,115 --> 00:21:34,150
Então, se você tentar escrever para que
valor, que não é um pedaço de memória

488
00:21:34,150 --> 00:21:37,440
que você realmente tem acesso e
assim que você está indo para obter esse erro,

489
00:21:37,440 --> 00:21:39,272
dizendo gravação inválido de tamanho 4.

490
00:21:39,272 --> 00:21:42,480
Valgrind vai reconhecer que você é
tentando tocar de memória de forma inadequada.

491
00:21:42,480 --> 00:21:43,980
>> E é isso por quiz0.

492
00:21:43,980 --> 00:21:47,065
Estou Rob Bowden, e este é CS50.

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