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

2
00:00:09,572 --> 00:00:12,030
罗布·鲍登：你好，我是罗布·鲍登，
让我们来谈谈quiz0。

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

4
00:00:13,280 --> 00:00:14,545
>> 所以，第一个问题。

5
00:00:14,545 --> 00:00:17,750
这就是问题所在
你需要的代码数量

6
00:00:17,750 --> 00:00:21,270
127在二进制灯泡。

7
00:00:21,270 --> 00:00:23,550
如果你愿意，你可以
做常规转换

8
00:00:23,550 --> 00:00:25,950
从bi--或者，从十进制到二进制的。

9
00:00:25,950 --> 00:00:28,300
但是这可能会
采取了大量的时间。

10
00:00:28,300 --> 00:00:31,750
我的意思是，你可以弄清楚的是，
OK，1是在那里，2是在那里，

11
00:00:31,750 --> 00:00:33,650
4在那里，8是在那里。

12
00:00:33,650 --> 00:00:39,280
更简单的方法，127是128减1。

13
00:00:39,280 --> 00:00:42,013
即最左边的灯泡是128位。

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

15
00:00:43,490 --> 00:00:47,860
所以127是真的只是所有
其他灯泡，

16
00:00:47,860 --> 00:00:51,420
因为这是最左边
灯泡减1。

17
00:00:51,420 --> 00:00:52,800
这是它的问题。

18
00:00:52,800 --> 00:00:54,060
>> 问题之一。

19
00:00:54,060 --> 00:00:56,710
因此，与3位即可
表示8个不同的值。

20
00:00:56,710 --> 00:01:01,000
那么，为什么是7最大的非负
十进制整数，你可以代表什么呢？

21
00:01:01,000 --> 00:01:04,050
那么，如果我们只能
代表8个不同的值，

22
00:01:04,050 --> 00:01:07,430
那么我们将是
表示为0到7。

23
00:01:07,430 --> 00:01:08,745
0占用的值之一。

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

25
00:01:09,980 --> 00:01:11,190
>> 问题二。

26
00:01:11,190 --> 00:01:14,610
用n位，多少个不同的
值你能代表什么呢？

27
00:01:14,610 --> 00:01:19,080
所以，用n位，你有2个
可能的值的每个比特。

28
00:01:19,080 --> 00:01:22,300
因此，我们有2个可能的值
第一个比特，2个可能的值

29
00:01:22,300 --> 00:01:24,450
对于第二，2-
可能的三分之一。

30
00:01:24,450 --> 00:01:28,730
所以这是2倍2倍2，和
最终的答案是2到n。

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

32
00:01:30,010 --> 00:01:31,100
>> 问题三。

33
00:01:31,100 --> 00:01:33,450
什么是二进制为0x50？

34
00:01:33,450 --> 00:01:39,490
所以请记住，十六进制有一个非常
简单的转换为二进制。

35
00:01:39,490 --> 00:01:43,180
所以在这里，我们只需要看看
在5和0独立。

36
00:01:43,180 --> 00:01:45,110
那么，什么是5二进制？

37
00:01:45,110 --> 00:01:48,400
0101，这是1位和4位。

38
00:01:48,400 --> 00:01:49,900
什么是0的二进制？

39
00:01:49,900 --> 00:01:50,520
不靠谱。

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

41
00:01:52,180 --> 00:01:54,970
因此，只要把它们放在一起，并
这是二进制的完整号码。

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

43
00:01:57,640 --> 00:02:00,439
如果你想你能
起飞的最左边为零。

44
00:02:00,439 --> 00:02:01,105
这是无关紧要的。

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

46
00:02:02,920 --> 00:02:05,733
>> 所以后来另外，
什么是为0x50十进制？

47
00:02:05,733 --> 00:02:08,649
如果你想，你could--如果你
更舒适的二进制文件，

48
00:02:08,649 --> 00:02:11,340
你可以采取二进制的答案
并且将其转换成十进制。

49
00:02:11,340 --> 00:02:13,870
或者，我们可以只记得
这十六进制。

50
00:02:13,870 --> 00:02:21,140
使0是在第0位，并
该图5是在16到第一位置。

51
00:02:21,140 --> 00:02:25,990
所以在这里，我们有5次16到
首先，加0次16至零，

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

53
00:02:27,520 --> 00:02:29,710
如果你看了
所有权的问题，

54
00:02:29,710 --> 00:02:32,920
这是CS 80，这是一种
提示要回答这个问题。

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

56
00:02:34,460 --> 00:02:35,420
>> 问题五。

57
00:02:35,420 --> 00:02:40,320
我们有这样的划痕脚本，它是
重复4次花生酱果冻。

58
00:02:40,320 --> 00:02:42,800
所以，我们现在怎么办的代码，在C？

59
00:02:42,800 --> 00:02:47,730
好了，我们有这里 - 部分以粗体
就是你必须实现的唯一部分。

60
00:02:47,730 --> 00:02:51,950
因此，我们有一个4循环的循环4
次，printf的，荷兰国际集团花生酱果冻，

61
00:02:51,950 --> 00:02:53,910
新线的问题询问。

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

63
00:02:55,250 --> 00:02:57,490
>> 问题六，另一个划痕的问题。

64
00:02:57,490 --> 00:03:00,210
我们看到，我们正处在一个永远循环。

65
00:03:00,210 --> 00:03:05,000
我们说的变量i
再递增i增加1。

66
00:03:05,000 --> 00:03:09,580
现在，我们想要做的是在C有
多种方法，我们可以这样做。

67
00:03:09,580 --> 00:03:12,840
在这里，我们碰巧的代码
永远循环的，而（真）。

68
00:03:12,840 --> 00:03:16,600
因此，我们声明变量i，只是
像我们有变量i的划痕。

69
00:03:16,600 --> 00:03:21,950
声明变量i，并永远
而（真），我们说的变量i。

70
00:03:21,950 --> 00:03:25,260
所以printf的％我 - 或者你可以用过％D。

71
00:03:25,260 --> 00:03:27,985
我们说的变量，
然后增加它，我++。

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

73
00:03:29,560 --> 00:03:30,830
>> 问题七。

74
00:03:30,830 --> 00:03:35,560
现在，我们想要做的事情非常相似
马里奥C点的设置问题之一。

75
00:03:35,560 --> 00:03:39,110
我们希望打印这些井号标签，
我们要打印一个五

76
00:03:39,110 --> 00:03:40,700
由三个矩形这些散列。

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

78
00:03:41,770 --> 00:03:43,162
那么我们如何做到这一点？

79
00:03:43,162 --> 00:03:45,370
好了，我们给你一个整体
一串代码，你只需

80
00:03:45,370 --> 00:03:47,560
必须填写打印网格功能。

81
00:03:47,560 --> 00:03:49,540
>> 那么，是什么PrintGrid样子？

82
00:03:49,540 --> 00:03:51,480
以及你过去的
宽度和高度。

83
00:03:51,480 --> 00:03:53,520
因此，我们有一个外4
循环，这就是循环

84
00:03:53,520 --> 00:03:57,650
在所有的这行的
我们要打印出来的网格。

85
00:03:57,650 --> 00:04:01,250
然后我们有跨嵌套4环，
这是印在每一列。

86
00:04:01,250 --> 00:04:06,210
因此，对于每一行，我们打印了
每列中，一个单一的哈希值。

87
00:04:06,210 --> 00:04:10,045
然后在该行的末尾，我们打印
单新走行到下一行。

88
00:04:10,045 --> 00:04:11,420
这就是它整个电网。

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

90
00:04:12,810 --> 00:04:13,675
>> 问题八。

91
00:04:13,675 --> 00:04:17,170
像PrintGrid一个函数被认为是
有一个副作用，而不是返回

92
00:04:17,170 --> 00:04:17,670
值。

93
00:04:17,670 --> 00:04:19,209
解释的区别。

94
00:04:19,209 --> 00:04:23,080
因此，这依赖于你记住
一个副作用是什么。

95
00:04:23,080 --> 00:04:25,180
好了，回归value--
我们知道PrintGrid不

96
00:04:25,180 --> 00:04:28,180
有返回值，因为
在这里它说无效。

97
00:04:28,180 --> 00:04:31,150
因此，返回void什么
并没有真正返回任何东西。

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

99
00:04:32,200 --> 00:04:33,620
那么什么是副作用？

100
00:04:33,620 --> 00:04:36,620
那么，一个副作用是
什么样的是坚持

101
00:04:36,620 --> 00:04:39,500
该函数结束后
这不是刚刚回国，

102
00:04:39,500 --> 00:04:41,340
而且它不只是从投入。

103
00:04:41,340 --> 00:04:44,970
>> 因此，举例来说，我们可能
改变一个全局变量。

104
00:04:44,970 --> 00:04:46,590
这将是一个副作用。

105
00:04:46,590 --> 00:04:49,000
在这个特殊的情况下，
非常重要的副作用

106
00:04:49,000 --> 00:04:51,070
被打印到屏幕上。

107
00:04:51,070 --> 00:04:53,110
所以这是一种副作用
这PrintGrid了。

108
00:04:53,110 --> 00:04:54,980
我们打​​印这些东西到屏幕上。

109
00:04:54,980 --> 00:04:56,370
你能想到的
这作为副作用，

110
00:04:56,370 --> 00:04:58,690
因为这件事情，
坚持这个函数结束后。

111
00:04:58,690 --> 00:05:01,481
这范围之外的东西
这个功能的最终

112
00:05:01,481 --> 00:05:03,380
被改变，则
屏幕的内容。

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

114
00:05:05,200 --> 00:05:05,839
>> 问题9。

115
00:05:05,839 --> 00:05:07,880
考虑下面的程序，
哪个行号

116
00:05:07,880 --> 00:05:09,740
已经被添加为
就事论事。

117
00:05:09,740 --> 00:05:13,480
因此，这个程序我们只是
打电话的GetString，将其存储

118
00:05:13,480 --> 00:05:16,220
在此变量s，然后
打印该变量s。

119
00:05:16,220 --> 00:05:16,720
行。

120
00:05:16,720 --> 00:05:19,090
因此，解释为什么行一个存在。

121
00:05:19,090 --> 00:05:20,920
＃包括CS50点小时。

122
00:05:20,920 --> 00:05:23,820
为什么我们需要＃包括CS50点H +

123
00:05:23,820 --> 00:05:26,180
嗯，我们正在调用
GetString的功能，

124
00:05:26,180 --> 00:05:28,840
和GetString的定义
在CS50库。

125
00:05:28,840 --> 00:05:31,600
所以，如果我们没有
＃包括CS50点H，

126
00:05:31,600 --> 00:05:35,760
我们将得到的隐式声明
中的GetString函数错误

127
00:05:35,760 --> 00:05:36,840
从编译器。

128
00:05:36,840 --> 00:05:40,110
因此，我们需要包括library--
我们需要包含头文件，

129
00:05:40,110 --> 00:05:42,870
否则，编译器不会
认识到GetString的存在。

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

131
00:05:44,380 --> 00:05:46,140
>> 解释为什么两个线路是否存在。

132
00:05:46,140 --> 00:05:47,890
因此，标准的IO点小时。

133
00:05:47,890 --> 00:05:50,430
它是完全一样的
如前面的问题，

134
00:05:50,430 --> 00:05:53,310
除了没有处理
GetString的，我们谈论的printf。

135
00:05:53,310 --> 00:05:56,654
因此，如果我们不说，我们需要
包括标准的IO点H，

136
00:05:56,654 --> 00:05:58,820
那么我们就不能
使用printf函数，

137
00:05:58,820 --> 00:06:00,653
因为编译器
不知道这件事。

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

139
00:06:01,750 --> 00:06:05,260
>> Why--有何意义
无效的四线？

140
00:06:05,260 --> 00:06:08,010
所以在这里我们有INT主要（无效）。

141
00:06:08,010 --> 00:06:10,600
这只是说，我们
没有得到任何命令行

142
00:06:10,600 --> 00:06:12,280
参数为主。

143
00:06:12,280 --> 00:06:17,390
请记住，我们可以说INT
主要整型的argc字符串argv的括号内。

144
00:06:17,390 --> 00:06:20,400
所以在这里我们只说空说，我们
被忽略的命令行参数。

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

146
00:06:21,840 --> 00:06:25,225
>> 说明，相对于存储器，恰
什么样的GetString的直列六缸回报。

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

148
00:06:27,040 --> 00:06:31,640
GetString的是返回的块
存储器，字符数组。

149
00:06:31,640 --> 00:06:34,870
这真是一个返回
指针的第一个字符。

150
00:06:34,870 --> 00:06:37,170
请记住，一个字符串是一个char明星。

151
00:06:37,170 --> 00:06:41,360
所以s是一个指向第一个
字符的任何字符串

152
00:06:41,360 --> 00:06:43,510
该用户输入的键盘。

153
00:06:43,510 --> 00:06:47,070
而且内存恰好是malloced，
使内存堆中。

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

155
00:06:49,080 --> 00:06:50,450
>> 问题13。

156
00:06:50,450 --> 00:06:51,960
考虑下面的程序。

157
00:06:51,960 --> 00:06:55,579
所以，这一切的计划是做
是的printf-荷兰国际集团1除以10。

158
00:06:55,579 --> 00:06:57,370
所以，在编译时和
执行该程序

159
00:06:57,370 --> 00:07:01,170
产出0.0，即使
1除以10是0.1。

160
00:07:01,170 --> 00:07:02,970
那么，为什么它是0.0？

161
00:07:02,970 --> 00:07:05,510
那么，这是因为
的整数除法。

162
00:07:05,510 --> 00:07:08,580
所以图1是一个整数，10是一个整数。

163
00:07:08,580 --> 00:07:11,980
因此，1除以10，一切
被视为整数，

164
00:07:11,980 --> 00:07:16,380
而在C中，当我们做整数除法，
我们截取小数点。

165
00:07:16,380 --> 00:07:19,590
因此，1除以10
0，然后我们试图

166
00:07:19,590 --> 00:07:24,410
打印，作为浮点数，所以
零印作为浮点数0.0。

167
00:07:24,410 --> 00:07:27,400
这就是为什么我们得到0.0。

168
00:07:27,400 --> 00:07:28,940
>> 考虑下面的程序。

169
00:07:28,940 --> 00:07:31,280
现在，我们正在打印0.1。

170
00:07:31,280 --> 00:07:34,280
因此，没有整数除法，
我们只是打印0.1，

171
00:07:34,280 --> 00:07:37,100
但我们在打印
28位小数。

172
00:07:37,100 --> 00:07:41,810
我们得到这个0.1000，一大堆
零，5 5 5，等等等等。

173
00:07:41,810 --> 00:07:45,495
因此，这里的问题是，为什么它
打印，而不是正好是0.1，？

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

175
00:07:46,620 --> 00:07:49,640
>> 因此，这里的原因是现在
浮点不精确。

176
00:07:49,640 --> 00:07:53,410
请记住，一个浮动的只有32位。

177
00:07:53,410 --> 00:07:57,540
因此，我们只能代表数量有限
浮点值与32

178
00:07:57,540 --> 00:07:58,560
位。

179
00:07:58,560 --> 00:08:01,760
那么有最终无限
许多浮点值，

180
00:08:01,760 --> 00:08:04,940
并有无限多的浮动
在0和1之间点值

181
00:08:04,940 --> 00:08:07,860
我们很明显的能
代表比甚至更多的价值。

182
00:08:07,860 --> 00:08:13,230
因此，我们必须做出牺牲
能够代表最值。

183
00:08:13,230 --> 00:08:16,960
>> 因此，像0.1的值，显然
我们不能代表完全一样。

184
00:08:16,960 --> 00:08:22,500
而不是代表0.1，所以我们做的
最好的，我们可以代表这个0.100000 5

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

186
00:08:23,260 --> 00:08:26,306
那是相当接近，但
对于很多应用程序

187
00:08:26,306 --> 00:08:28,430
你不必担心
浮点不精确，

188
00:08:28,430 --> 00:08:30,930
因为我们只是不能代表
所有浮动点完全吻合。

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

190
00:08:32,500 --> 00:08:33,380
>> 问题15。

191
00:08:33,380 --> 00:08:34,679
考虑下面的代码。

192
00:08:34,679 --> 00:08:36,630
我们只是打印1加1。

193
00:08:36,630 --> 00:08:38,289
所以这里没有窍门。

194
00:08:38,289 --> 00:08:41,780
1加1的计算结果为2，且
那么我们打印了。

195
00:08:41,780 --> 00:08:42,789
这只是打印2。

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

197
00:08:43,850 --> 00:08:44,700
>> 问题16。

198
00:08:44,700 --> 00:08:49,450
现在，我们要打印的字符
1加1的字符。

199
00:08:49,450 --> 00:08:52,110
那么，为什么这个不
打印同样的事情？

200
00:08:52,110 --> 00:08:57,680
以及人物1加字符
1，字符1的ASCII值为49。

201
00:08:57,680 --> 00:09:04,840
所以这真的是说49加49，和
最终这将打印98。

202
00:09:04,840 --> 00:09:06,130
因此，这不打印2。

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

204
00:09:08,070 --> 00:09:09,271
>> 问题17。

205
00:09:09,271 --> 00:09:11,520
完成实施
在这样一种方式之下奇

206
00:09:11,520 --> 00:09:14,615
该函数返回true，如果
n为奇数和假当n为偶数。

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

208
00:09:16,710 --> 00:09:19,330
这是一个伟大的目的
对于mod运算符。

209
00:09:19,330 --> 00:09:24,530
因此，我们把我们的参数n，
如果n MOD 2等于1，以及

210
00:09:24,530 --> 00:09:28,030
这意味着n除
由2有剩余。

211
00:09:28,030 --> 00:09:33,270
如果n除以2有一个余数，即
也就是说n为奇数，所以我们返回true。

212
00:09:33,270 --> 00:09:34,910
否则我们返回false。

213
00:09:34,910 --> 00:09:39,070
你也可以做N模等于2
零，则返回false，否则返回true。

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

215
00:09:41,600 --> 00:09:43,640
>> 考虑递归函数如下。

216
00:09:43,640 --> 00:09:46,920
因此，如果n小于或
等于1，则返回1，

217
00:09:46,920 --> 00:09:50,430
否则返回n次F N减1。

218
00:09:50,430 --> 00:09:52,556
所以，这是什么功能？

219
00:09:52,556 --> 00:09:54,305
好吧，这只是
阶乘函数。

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

221
00:09:55,410 --> 00:09:57,405
这是很好的代表
随着n的阶乘。

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

223
00:09:58,720 --> 00:10:02,310
>> 所以，问题19，现在，我们要
借此递归函数。

224
00:10:02,310 --> 00:10:04,530
我们想让它反复。

225
00:10:04,530 --> 00:10:05,874
那么，如何才能做到这一点？

226
00:10:05,874 --> 00:10:07,790
以及为员工
溶液中，并且再次有

227
00:10:07,790 --> 00:10:11,090
你可以做多种方式
这一点，我们先从这个INT产品

228
00:10:11,090 --> 00:10:11,812
等于1。

229
00:10:11,812 --> 00:10:13,520
和本
for循环中，我们将

230
00:10:13,520 --> 00:10:17,590
最终要乘以产品
结束与全因子。

231
00:10:17,590 --> 00:10:21,870
所以，对于int i等于2，我是
小于或等于n，我+ +。

232
00:10:21,870 --> 00:10:24,130
>> 你也许会奇怪，为什么我等于2。

233
00:10:24,130 --> 00:10:28,380
好了，记住，下面我们就来
确保我们的基本情形是正确的。

234
00:10:28,380 --> 00:10:32,180
因此，如果n小于或等于
1，我们只是返回1。

235
00:10:32,180 --> 00:10:34,830
所以在这里，我们开始在i等于2。

236
00:10:34,830 --> 00:10:39,090
那么，如果我是1，那么the--或
如果n为1，则对环

237
00:10:39,090 --> 00:10:40,600
会不会执行的。

238
00:10:40,600 --> 00:10:43,190
因此，我们将只
返回的产品，这是1。

239
00:10:43,190 --> 00:10:45,920
类似地，如果n是
任何小于1--

240
00:10:45,920 --> 00:10:49,290
如果它是0，负1，whatever--
我们还是要回到1，

241
00:10:49,290 --> 00:10:52,260
这正是
递归版本做。

242
00:10:52,260 --> 00:10:54,660
>> 现在，如果n是大于
大于1，那么我们就要

243
00:10:54,660 --> 00:10:56,550
这样做至少有一个
迭代这个循环。

244
00:10:56,550 --> 00:11:00,630
所以我们可以说，n是5，那么我们就
要做到产品的时间等于2。

245
00:11:00,630 --> 00:11:02,165
所以，现在的产品是2。

246
00:11:02,165 --> 00:11:04,040
现在，我们要做的
产品的时候等于3。

247
00:11:04,040 --> 00:11:04,690
现在是6。

248
00:11:04,690 --> 00:11:07,500
产品多次等于4，现在是24。

249
00:11:07,500 --> 00:11:10,420
产品倍等于5，现在是120元。

250
00:11:10,420 --> 00:11:16,730
这样的话，最终，我们返回
120，这是正确的5阶乘。

251
00:11:16,730 --> 00:11:17,510
>> 问题20。

252
00:11:17,510 --> 00:11:22,480
这是一个你必须填写
在该表中的任何给定的算法，

253
00:11:22,480 --> 00:11:25,735
任何事情，我们已经看到，这
符合这些算法的运行

254
00:11:25,735 --> 00:11:28,060
这些时代渐近运行时间。

255
00:11:28,060 --> 00:11:33,270
那么，什么是一个算法，
欧米茄是1，但为n的大O？

256
00:11:33,270 --> 00:11:35,970
所以有可能是无限
很多答案在这里。

257
00:11:35,970 --> 00:11:39,790
我们已经看到了可能是最一
经常只是线性搜索。

258
00:11:39,790 --> 00:11:42,050
>> 因此，在最佳情况
情况下，我们的项目

259
00:11:42,050 --> 00:11:44,050
寻找的是在
开始列表的

260
00:11:44,050 --> 00:11:47,400
所以在1步欧米茄，
我们检查的第一件事，

261
00:11:47,400 --> 00:11:49,740
我们只是立即返回
我们发现该项目。

262
00:11:49,740 --> 00:11:52,189
在最坏的情况下，
该项目是在末端，

263
00:11:52,189 --> 00:11:53,730
或产品不在列表中的。

264
00:11:53,730 --> 00:11:56,700
因此，我们必须寻找
整个列表，所有的n

265
00:11:56,700 --> 00:11:58,480
元素，这就是为什么它是0：N的。

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

267
00:11:59,670 --> 00:12:04,880
>> 所以，现在它的东西，既是
欧米茄的n log n的和正数为n的大O。

268
00:12:04,880 --> 00:12:08,650
以及最相关的事情
我们在这里看到的是归并排序。

269
00:12:08,650 --> 00:12:12,950
所以，归并排序，请记住，
最终THETA

270
00:12:12,950 --> 00:12:16,920
的n log n，其中THETA定义的
如果两个欧米茄和大O是相同的。

271
00:12:16,920 --> 00:12:17,580
以上所说的n日志N。

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

273
00:12:18,690 --> 00:12:21,970
>> 有什么东西是欧米茄
的n和n阿方？

274
00:12:21,970 --> 00:12:23,990
好吧，再有
多种可能的答案。

275
00:12:23,990 --> 00:12:26,440
在这里，我们碰巧说冒泡排序。

276
00:12:26,440 --> 00:12:28,840
插入排序也将在这里工作。

277
00:12:28,840 --> 00:12:31,400
请记住，冒泡排序
具有优化的地方，

278
00:12:31,400 --> 00:12:34,630
如果你能得到
整个列表

279
00:12:34,630 --> 00:12:37,402
而不需要做
任何掉期，然后，嗯，

280
00:12:37,402 --> 00:12:40,110
我们可以立即返回
列表进行排序开始。

281
00:12:40,110 --> 00:12:43,185
所以，在最好的情况下，
它只是欧米茄的n。

282
00:12:43,185 --> 00:12:45,960
如果它不只是一个很好的
排序的列表，首先，

283
00:12:45,960 --> 00:12:48,270
那么，我们有n个阿方互换。

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

285
00:12:49,330 --> 00:12:55,610
最后，我们选择排序
对于n的平方，两个欧米茄和大O.

286
00:12:55,610 --> 00:12:56,850
>> 问题21。

287
00:12:56,850 --> 00:12:58,870
什么是整数溢出？

288
00:12:58,870 --> 00:13:02,160
好了，类似于早期，
我们只有有限个位

289
00:13:02,160 --> 00:13:04,255
来表示的整数，
所以也许32位。

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

291
00:13:06,300 --> 00:13:09,180
比方说，我们有一个有符号整数。

292
00:13:09,180 --> 00:13:12,800
那么，最终的最高
正数，我们可以代表

293
00:13:12,800 --> 00:13:15,910
为2至31减去1。

294
00:13:15,910 --> 00:13:19,370
那么，如果我们试图发生
然后增加该整数？

295
00:13:19,370 --> 00:13:25,320
好了，我们将在2要到31
减1，一直到负2路

296
00:13:25,320 --> 00:13:26,490
到31。

297
00:13:26,490 --> 00:13:29,470
所以这个整数溢出
当你不断递增，

298
00:13:29,470 --> 00:13:32,330
最终你不能
得到任何提高，它只是

299
00:13:32,330 --> 00:13:34,520
包装所有的方式回到
周围为负值。

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

301
00:13:35,850 --> 00:13:37,779
>> 那么缓冲区溢出？

302
00:13:37,779 --> 00:13:39,820
所以缓冲overflow--
记得一个缓冲区。

303
00:13:39,820 --> 00:13:41,000
它的内存只是一大块。

304
00:13:41,000 --> 00:13:43,350
类似数组是一个缓冲区。

305
00:13:43,350 --> 00:13:46,120
因此，缓冲区溢出是当
您尝试访问的内存

306
00:13:46,120 --> 00:13:47,880
超出该阵列的端部。

307
00:13:47,880 --> 00:13:50,410
所以，如果你有一个
5号和您的阵列

308
00:13:50,410 --> 00:13:53,700
尝试访问阵列支架
5或6架或支架7，

309
00:13:53,700 --> 00:13:56,610
或超越什么
端，或甚至任何

310
00:13:56,610 --> 00:14:00,790
below--阵列支架负面1--
所有这些都是缓冲区溢出。

311
00:14:00,790 --> 00:14:02,810
你触碰内存在恶劣的方式。

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

313
00:14:04,090 --> 00:14:04,730
>> 问题23。

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

315
00:14:05,760 --> 00:14:09,100
所以在这一块你需要
实现strlen的。

316
00:14:09,100 --> 00:14:11,630
我们告诉你，你可以
假设的意志不能为空，

317
00:14:11,630 --> 00:14:13,790
所以你不必
做任何检查空。

318
00:14:13,790 --> 00:14:16,190
并有多种方式
你可以这样做了。

319
00:14:16,190 --> 00:14:18,440
在这里，我们只取简单。

320
00:14:18,440 --> 00:14:21,780
我们先从一个计数器，N。 n为
计算有多少个字符有。

321
00:14:21,780 --> 00:14:25,560
因此，我们从0开始，然后我们
遍历整个链表。

322
00:14:25,560 --> 00:14:29,092
>> 为s托架0等于
空值终止符？

323
00:14:29,092 --> 00:14:31,425
请记住，我们正在寻找
空终止符

324
00:14:31,425 --> 00:14:33,360
以确定多长时间我们的字符串是。

325
00:14:33,360 --> 00:14:35,890
这是要终止
任何相关的字符串。

326
00:14:35,890 --> 00:14:39,400
所以是S支架等于0
以空终止？

327
00:14:39,400 --> 00:14:42,850
如果不是，那么我们要
看看在s支架1，S 2架。

328
00:14:42,850 --> 00:14:45,050
我们继续下去，直到我们
找到空终止。

329
00:14:45,050 --> 00:14:48,580
一旦我们发现了它，那么n包含
字符串的总长度，

330
00:14:48,580 --> 00:14:49,942
我们可以只返回。

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

332
00:14:51,180 --> 00:14:51,865
>> 问题24。

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

334
00:14:53,010 --> 00:14:56,050
因此，这是一个，你
必须做出权衡。

335
00:14:56,050 --> 00:14:59,810
所以，有一件事是在一个很好的
的方式，但以何种方式是坏？

336
00:14:59,810 --> 00:15:02,980
所以在这里，归并排序趋于
比冒泡排序快。

337
00:15:02,980 --> 00:15:06,530
尽管如此that--很好，有
多个答案在这里。

338
00:15:06,530 --> 00:15:12,930
但最主要的是，冒泡排序
是欧米茄的n的有序表。

339
00:15:12,930 --> 00:15:14,950
>> 还记得我们刚才前面看到的那个表。

340
00:15:14,950 --> 00:15:17,600
所以，泡各种各样的欧米加
N，在最好的情况下

341
00:15:17,600 --> 00:15:20,010
是它能够只走了过来
列表中一次，确定

342
00:15:20,010 --> 00:15:22,270
嘿，这个东西已经是
分类和回归。

343
00:15:22,270 --> 00:15:25,960
归并排序，不管是什么
你这样做，是正数为n的欧米茄。

344
00:15:25,960 --> 00:15:29,200
因此，对于排序的列表，泡沫
排序将是更快的。

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

346
00:15:30,870 --> 00:15:32,430
>> 现在来谈谈链表？

347
00:15:32,430 --> 00:15:36,070
这样一个链表可以增大和缩小
根据需要以适合尽可能多的元素。

348
00:15:36,070 --> 00:15:38,489
话虽如此that--
通常的直接比较

349
00:15:38,489 --> 00:15:40,280
将是一个链接
列出与阵列。

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

351
00:15:41,600 --> 00:15:44,050
因此，即使阵列可
轻松地扩展和收缩

352
00:15:44,050 --> 00:15:47,130
以适应尽可能多的元素
根据需要，一个链表

353
00:15:47,130 --> 00:15:49,600
相比于一个array--一个
数组随机访问。

354
00:15:49,600 --> 00:15:52,960
我们可以索引到任何
所述阵列的特定元素。

355
00:15:52,960 --> 00:15:56,430
>> 因此，对于一个链表，我们不能
只要到了第五元素，

356
00:15:56,430 --> 00:16:00,260
我们必须从一开始遍历
直到我们得到的第五元素。

357
00:16:00,260 --> 00:16:03,990
而这会阻止我们
做类似二进制搜索。

358
00:16:03,990 --> 00:16:08,150
说起二进制搜索，二进制搜索
往往比线性搜索更快。

359
00:16:08,150 --> 00:16:11,120
尽管如此that--
因此，一种可能的事

360
00:16:11,120 --> 00:16:13,380
是你不能做的二进制
搜索链表，

361
00:16:13,380 --> 00:16:14,730
你只能做的阵列。

362
00:16:14,730 --> 00:16:18,030
但或许更重要的是
你不能做二进制搜索

363
00:16:18,030 --> 00:16:20,690
在未排序的数组。

364
00:16:20,690 --> 00:16:23,990
前期可能需要进行排序
数组，然后才可以

365
00:16:23,990 --> 00:16:25,370
你做二进制搜索。

366
00:16:25,370 --> 00:16:27,660
所以，如果你的东西是不是
排序，首先，

367
00:16:27,660 --> 00:16:29,250
然后线性搜索可能会更快。

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

369
00:16:30,620 --> 00:16:31,740
>> 问题27。

370
00:16:31,740 --> 00:16:34,770
因此，考虑下面的程序，
这将在下一幻灯片。

371
00:16:34,770 --> 00:16:37,790
这是一个在那里我们
会想明确说明

372
00:16:37,790 --> 00:16:39,980
的值不同的变数。

373
00:16:39,980 --> 00:16:41,990
因此，让我们看一下。

374
00:16:41,990 --> 00:16:43,160
>> 因此，行一个。

375
00:16:43,160 --> 00:16:45,457
我们有整数x等于1。

376
00:16:45,457 --> 00:16:47,040
这就是发生的事情，唯一的事。

377
00:16:47,040 --> 00:16:50,440
因此，在一行中，我们看到我们的
表中，Y，A，b和tmp中都

378
00:16:50,440 --> 00:16:51,540
昏了过去。

379
00:16:51,540 --> 00:16:52,280
那么，什么是X？

380
00:16:52,280 --> 00:16:53,860
嗯，我们只是将它设置为1。

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

382
00:16:55,020 --> 00:16:58,770
然后两线，好吧，
我们看到的是y被设置为2，

383
00:16:58,770 --> 00:17:00,550
而且该表是已
填补了我们​​。

384
00:17:00,550 --> 00:17:03,040
所以x是1，y是2。

385
00:17:03,040 --> 00:17:05,890
>> 现在，三线，我们现在是
里面的交换功能。

386
00:17:05,890 --> 00:17:07,560
没有我们通过什么来交换？

387
00:17:07,560 --> 00:17:11,609
我们通过符号X的
一，和符号Y表示B。

388
00:17:11,609 --> 00:17:15,160
问题出在哪里更早
表示x的地址

389
00:17:15,160 --> 00:17:17,520
是0x10的，和y的地址为0×14。

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

391
00:17:18,970 --> 00:17:21,909
所以a和b都等于
为0x10和0x14的分别。

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

393
00:17:23,670 --> 00:17:26,250
>> 现在，在3线，什么是x和y？

394
00:17:26,250 --> 00:17:28,554
好了，一切都没有改变
关于x和y在这一点上。

395
00:17:28,554 --> 00:17:30,470
即使他们是
主堆栈帧里面，

396
00:17:30,470 --> 00:17:32,469
他们仍然有同样的
价值观，他们以前那样。

397
00:17:32,469 --> 00:17:34,030
我们没有修改任何内存。

398
00:17:34,030 --> 00:17:35,710
因此x为1，y为2。

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

400
00:17:36,550 --> 00:17:37,050
行。

401
00:17:37,050 --> 00:17:40,300
所以现在我们说INT TMP等于一个明星。

402
00:17:40,300 --> 00:17:44,410
因此，在四号线，一切
是除TMP一样。

403
00:17:44,410 --> 00:17:47,130
我们没有改变任何值
任何东西，除了TMP。

404
00:17:47,130 --> 00:17:49,230
我们正在设置TMP等于一个明星。

405
00:17:49,230 --> 00:17:50,620
什么是明星？

406
00:17:50,620 --> 00:17:56,240
好了，点X，所以一个明星
将会等于x，它是1。

407
00:17:56,240 --> 00:18:00,080
所以，一切都被复制
下来，而tmp中被设置为1。

408
00:18:00,080 --> 00:18:01,110
>> 现在的下一行。

409
00:18:01,110 --> 00:18:03,380
明星等于星级的住宿。

410
00:18:03,380 --> 00:18:10,000
因此，通过线five--好了，一切都
除非是无论明星是一样的。

411
00:18:10,000 --> 00:18:10,830
什么是明星？

412
00:18:10,830 --> 00:18:13,720
好了，我们刚才说的明星为x。

413
00:18:13,720 --> 00:18:16,400
所以，我们正在改变x等于明星B。

414
00:18:16,400 --> 00:18:18,960
什么是明星B？年。 B点为y。

415
00:18:18,960 --> 00:18:21,030
所以，明星B为y。

416
00:18:21,030 --> 00:18:25,140
因此，我们设定X等于Y，
和其他一切是一样的。

417
00:18:25,140 --> 00:18:29,130
因此，我们的下一行中看到，x是现在
2，剩下的只是抄了下来。

418
00:18:29,130 --> 00:18:31,120
>> 现在，在下一行，星B等于tmp目录。

419
00:18:31,120 --> 00:18:34,740
好了，我们刚才说的星b为Y，
所以我们则设置y等于tmp目录。

420
00:18:34,740 --> 00:18:37,450
其他的都是一样的，
所以一切都被复制下来。

421
00:18:37,450 --> 00:18:42,050
我们则设置y等于tmp中，这是
一个，其他都是一样的。

422
00:18:42,050 --> 00:18:43,210
>> 现在，终于，七号线。

423
00:18:43,210 --> 00:18:44,700
我们又回到在主函数。

424
00:18:44,700 --> 00:18:46,350
我们交换完成后。

425
00:18:46,350 --> 00:18:48,972
我们已经失去的a，b，和
TMP，但最终我们

426
00:18:48,972 --> 00:18:51,180
不更改任何值
在这一点上任何东西，

427
00:18:51,180 --> 00:18:52,800
我们只要复制x和y下来。

428
00:18:52,800 --> 00:18:56,490
而且我们看到，x和y是
现在2和1，而不是1和2。

429
00:18:56,490 --> 00:18:58,160
交换成功执行。

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

431
00:18:59,500 --> 00:19:00,105
>> 问题28。

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

433
00:19:01,226 --> 00:19:03,100
假设你遇到
该错误消息

434
00:19:03,100 --> 00:19:06,790
办公时间如下
明年的CA或TF。

435
00:19:06,790 --> 00:19:08,930
提醒如何修复这些错误。

436
00:19:08,930 --> 00:19:11,160
所以未定义的引用给GetString。

437
00:19:11,160 --> 00:19:12,540
为什么你可能会看到这个？

438
00:19:12,540 --> 00:19:15,380
好吧，如果学生使用
GetString的在他们的代码，

439
00:19:15,380 --> 00:19:20,310
他们正确地散列包括CS50
点h至包括CS50库。

440
00:19:20,310 --> 00:19:22,380
>> 那么，他们是怎么
要解决这个错误？

441
00:19:22,380 --> 00:19:26,810
他们需要做一个破折号lcs50在
当他们编译的命令行。

442
00:19:26,810 --> 00:19:29,501
因此，如果他们不通过
铛破折号lcs50，他们是

443
00:19:29,501 --> 00:19:32,000
不会有实际
实现GetString的代码。

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

445
00:19:33,190 --> 00:19:34,170
>> 问题29。

446
00:19:34,170 --> 00:19:36,190
隐式声明
库函数strlen的。

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

448
00:19:37,550 --> 00:19:40,360
嗯，这现在，他们都没有
做正确的散列包括。

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

450
00:19:41,440 --> 00:19:45,410
在这种特定情况下，在头文件
他们需要包含的字符串点H，

451
00:19:45,410 --> 00:19:48,710
而包括串点H，现在
现在student--编译器

452
00:19:48,710 --> 00:19:51,750
有权访问
strlen的声明，

453
00:19:51,750 --> 00:19:54,120
它知道你的代码
正确使用strlen的。

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

455
00:19:55,380 --> 00:19:56,580
>> 问题30。

456
00:19:56,580 --> 00:20:00,240
更为％的转化率
比数据参数。

457
00:20:00,240 --> 00:20:01,540
那么这是什么？

458
00:20:01,540 --> 00:20:06,470
清楚地记得，这些百分比
signs--他们是如何相关的printf。

459
00:20:06,470 --> 00:20:08,890
因此，在我们的printf可能percent--
我们可以打印的东西

460
00:20:08,890 --> 00:20:11,380
像我百分之反斜杠ñ。

461
00:20:11,380 --> 00:20:15,310
或者我们可以像打印百分之一，
空间，百分之一，空间，百分比我。

462
00:20:15,310 --> 00:20:18,950
因此，对于每一个这些
百分号，我们需要

463
00:20:18,950 --> 00:20:21,560
传递变量在printf的末尾。

464
00:20:21,560 --> 00:20:26,980
>> 所以，如果我们说的printf括号％的
我反斜杠N分别闭合的括号，

465
00:20:26,980 --> 00:20:30,270
好了，我们说我们是
将要打印的整数，

466
00:20:30,270 --> 00:20:33,970
但我们不通过的printf
一个整数，以实际打印。

467
00:20:33,970 --> 00:20:37,182
所以在这里更多的百分
转换不是数据的参数？

468
00:20:37,182 --> 00:20:39,390
这是说，我们有
一大堆的百分数，

469
00:20:39,390 --> 00:20:42,445
我们没有足够的变量
实际上填写的百分比。

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

471
00:20:44,850 --> 00:20:50,010
>> 然后肯定，对于问题31，
在一个块肯定瘦了40个字节。

472
00:20:50,010 --> 00:20:52,350
所以这是一个Valgrind的错误。

473
00:20:52,350 --> 00:20:54,720
这是说，
在某个地方你的代码，

474
00:20:54,720 --> 00:20:59,010
你有一个分配是40
字节大的，所以你malloced 40个字节，

475
00:20:59,010 --> 00:21:00,515
你永远不会释放它。

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

477
00:21:02,480 --> 00:21:05,140
最有可能你只需要
找一些内存泄漏，

478
00:21:05,140 --> 00:21:07,650
找到你需要
释放内存此块。

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

480
00:21:08,780 --> 00:21:11,910
>> 和问题32，
无效的写入大小4。

481
00:21:11,910 --> 00:21:13,250
再次，这是一个Valgrind的错误。

482
00:21:13,250 --> 00:21:15,440
此不必做
现在有内存泄漏。

483
00:21:15,440 --> 00:21:20,750
这是最likely--我的意思是，这是
某种无效的内存权利。

484
00:21:20,750 --> 00:21:23,270
而最有可能的，这是一些
排序缓冲区溢出。

485
00:21:23,270 --> 00:21:26,560
在那里你有一个数组，也许
一个整型数组，让我们

486
00:21:26,560 --> 00:21:30,115
说这是大小5，你
尝试触摸阵列支架5。

487
00:21:30,115 --> 00:21:34,150
所以，如果你试图写入该
值，这不是一块内存

488
00:21:34,150 --> 00:21:37,440
你实际上可以访问，并
所以你会得到这个错误，

489
00:21:37,440 --> 00:21:39,272
说大小4无效写。

490
00:21:39,272 --> 00:21:42,480
Valgrind的是要认识到你
试图不恰当地触碰到内存。

491
00:21:42,480 --> 00:21:43,980
>> 就是这样的quiz0。

492
00:21:43,980 --> 00:21:47,065
我罗布鲍登，这是CS50。

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