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