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
Я имею в виду, вы можете выяснить, что,
ОК, 1 находится в там, 2 находится в там,

11
00:00:31,750 --> 00:00:33,650
4 находится в там, 8 находится в там.

12
00:00:33,650 --> 00:00:39,280
Легче образом, 127 128 минус один.

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
С п битов, сколько различных
Значения могут вы представляете?

27
00:01:14,610 --> 00:01:19,080
Так, с п битов, у вас есть 2
Возможные значения для каждого бита.

28
00:01:19,080 --> 00:01:22,300
Таким образом, мы имеем два возможных значения для
первый бит, 2 возможных значения

29
00:01:22,300 --> 00:01:24,450
для второго, 2
возможно для третьего.

30
00:01:24,450 --> 00:01:28,730
И таким образом, это в 2 раза 2 раза 2, и
в конечном счете, ответ на 2 л.

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
Ну, у нас есть here-- часть жирным шрифтом
это единственная часть, нужно было реализовывать.

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
Теперь мы хотим сделать, что в С. Есть
несколько способов мы могли бы сделать это.

67
00:03:09,580 --> 00:03:12,840
Здесь мы случайно закодировать
навсегда петля как некоторое время (правда).

68
00:03:12,840 --> 00:03:16,600
Таким образом, мы объявляем переменную I, просто
у нас был переменную я в пустом.

69
00:03:16,600 --> 00:03:21,950
Объявите переменную I, и навсегда
в то время как (правда), мы говорим, переменную я.

70
00:03:21,950 --> 00:03:25,260
Так Printf% i-- или вы могли бы использовать% 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
Теперь мы хотим сделать что-то очень похожее
Марио точка с из проблемы установите один.

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
Поэтому все, что не возвращает
на самом деле не ничего возвращать.

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
>> Вопрос девять.

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
в этой переменной х, а затем
печать этой переменной с.

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
#include CS50 точка ч.

122
00:05:20,920 --> 00:05:23,820
Почему мы должны #include CS50 точка час?

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
Так что, если у нас не было
#include CS50 точка ч,

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
Так стандарт ю точка ч.

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 точка час,

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
Основные 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
Помните, что строка является символ звезды.

151
00:06:37,170 --> 00:06:41,360
Так с является указателем на первый
характер в любой строка

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 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
что функция возвращает истину, если
п нечетное и ложно, если п четно.

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

208
00:09:16,710 --> 00:09:19,330
Это великая цель
для мод оператора.

209
00:09:19,330 --> 00:09:24,530
Поэтому наша аргумент п,
если н модулю 2 равна 1, а

210
00:09:24,530 --> 00:09:28,030
что означает, что п делится
на 2 имел остаток.

211
00:09:28,030 --> 00:09:33,270
Если п делится на 2 имел остаток, что
означает, что п нечетное, поэтому мы вернемся верно.

212
00:09:33,270 --> 00:09:34,910
Иначе мы вернуться ложным.

213
00:09:34,910 --> 00:09:39,070
Вы также могли бы сделать п по модулю 2 равных
нулю, вернуться ложным, иначе возвращает истину.

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
еще возвращение п раз е н минус 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
Это красиво представлены
как н факториала.

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
И на протяжении всего этого
для петли, мы собираемся

230
00:10:13,520 --> 00:10:17,590
чтобы быть умножения продукт в конечном счете,
в конечном итоге с полной факториала.

231
00:10:17,590 --> 00:10:21,870
Так что для междунар я равняется 2, я это
меньше или равно N, I ++.

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
Так вот здесь, у нас начинаются я равна 2.

236
00:10:34,830 --> 00:10:39,090
Ну, если бы я был один, то the-- или
если н были 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
Точно так же, если н были
что-нибудь менее 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
>> Теперь, если п больше
1, то мы собираемся

243
00:10:54,660 --> 00:10:56,550
делать по меньшей мере один
итерации этого цикла.

244
00:10:56,550 --> 00:11:00,630
Так скажем, п 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, но большая 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
Поэтому мы должны искать
Весь список, все п

265
00:11:56,700 --> 00:11:58,480
элементы, и именно поэтому это о н.

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

267
00:11:59,670 --> 00:12:04,880
>> Так что теперь это что-то, это и
омега н лог н, и большая O н лог н.

268
00:12:04,880 --> 00:12:08,650
Ну самое непосредственное отношение вещь
мы видели здесь сливаются рода.

269
00:12:08,650 --> 00:12:12,950
Так сливаются рода, помните,
в конечном счете, тета

270
00:12:12,950 --> 00:12:16,920
н лог п, где тета определяется
если оба омега и большой вывода одинаковы.

271
00:12:16,920 --> 00:12:17,580
Оба п § п.

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

273
00:12:18,690 --> 00:12:21,970
>> Что-то, что это омега
п, и O п квадрат?

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
Таким образом, в лучшем случае,
это просто омега п.

282
00:12:43,185 --> 00:12:45,960
Если это не просто красиво
сортируются список для начала,

283
00:12:45,960 --> 00:12:48,270
то у нас есть O п квадрате свопы.

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

285
00:12:49,330 --> 00:12:55,610
И, наконец, у нас есть выбор рода
для п квадрат, как омега и большой О.

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
Начнем с прилавка, п. п
считая, сколько символов есть.

321
00:14:21,780 --> 00:14:25,560
Итак, мы начинаем с 0, и тогда мы
перебрать весь список.

322
00:14:25,560 --> 00:14:29,092
>> Разве с кронштейном 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
Так с кронштейном 0 равны
к нулевой символ?

327
00:14:39,400 --> 00:14:42,850
Если это не так, то мы собираемся
посмотреть на ов кронштейне 1, S кронштейна 2.

328
00:14:42,850 --> 00:14:45,050
Мы не продолжаем, пока мы
найти нулевой терминатор.

329
00:14:45,050 --> 00:14:48,580
После того, как мы нашли его, то п содержит
общая длина строки,

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
Но главный из них, что пузырьковая сортировка
является омегой п для отсортированного списка.

339
00:15:12,930 --> 00:15:14,950
>> Помните, что стол, который мы только что видели ранее.

340
00:15:14,950 --> 00:15:17,600
Так пузырь сортирует омегу
н, в лучшем случае

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
не Слияние рода, независимо от того,
что вы делаете, является омега н лог н.

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
У нас есть интервал х равен 1.

376
00:16:45,457 --> 00:16:47,040
Это единственное, что случилось.

377
00:16:47,040 --> 00:16:50,440
Таким образом, на первой линии, мы видим в нашем
Таблица, что у, а, б, и TMP все

378
00:16:50,440 --> 00:16:51,540
затемнены.

379
00:16:51,540 --> 00:16:52,280
Так что же такое х?

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
А потом выстраиваются два, ну,
мы видим, что у установлен в 2,

383
00:16:58,770 --> 00:17:00,550
и таблица уже
заполняется для нас.

384
00:17:00,550 --> 00:17:03,040
Так х представляет 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
Мы прошли амперсанд х для
и амперсанд у для б.

388
00:17:11,609 --> 00:17:15,160
Где проблема раньше
указано, что адрес X

389
00:17:15,160 --> 00:17:17,520
является 0x10, а также адрес у является 0x14.

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

391
00:17:18,970 --> 00:17:21,909
Так и б равны
0x10 и 0x14, соответственно.

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

393
00:17:23,670 --> 00:17:26,250
>> Теперь на третьей линии, каковы хну?

394
00:17:26,250 --> 00:17:28,554
Ну, ничего не изменилось
о х и у в этой точке.

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
Так х равен 1, у равен 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
Ну, а точки х, так звезды
собирается равной х, который является 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
Ну, мы только что сказали, звезда является х.

413
00:18:13,720 --> 00:18:16,400
Таким образом, мы меняем х на равную звезды б.

414
00:18:16,400 --> 00:18:18,960
Что такое звезда б? у. б указывает на у.

415
00:18:18,960 --> 00:18:21,030
Так звезда б это у.

416
00:18:21,030 --> 00:18:25,140
Так мы устанавливаем х равно у,
а все остальное то же самое.

417
00:18:25,140 --> 00:18:29,130
Итак, мы видим в следующем ряду, что х является сейчас
2, а остальные просто копируются вниз.

418
00:18:29,130 --> 00:18:31,120
>> Теперь в следующей строке, звезда б равна TMP.

419
00:18:31,120 --> 00:18:34,740
Ну, мы только что сказали, звезда Ь у,
так мы устанавливаем у равно TMP.

420
00:18:34,740 --> 00:18:37,450
Все остальное то же самое,
таким образом, все копируется вниз.

421
00:18:37,450 --> 00:18:42,050
Мы устанавливаем у равную 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
мы просто скопировать хну вниз.

428
00:18:52,800 --> 00:18:56,490
И мы видим, что х и у
Теперь 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
ниже в течение рабочего дня
в следующем году, как Калифорния или 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
точка ч, чтобы включить библиотеку 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
В данном конкретном случае, файл заголовка
они должны включать в себя это строка точка ч,

451
00:19:45,410 --> 00:19:48,710
и в том числе строки точка ч, в настоящее время
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 мы могли бы процентов, что
мы могли бы напечатать что-нибудь

460
00:20:08,890 --> 00:20:11,380
как процентов я обратную косую черту н.

461
00:20:11,380 --> 00:20:15,310
Или мы могли бы напечатать, как процент I,
пространство, процентов я, пространство, процентов я.

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 скобка процентов
я обратную косую черту н тесные Парень,

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