1
00:00:00,000 --> 00:00:02,570
[Powered by Google Translate] [Sekcja 3 - bardziej komfortowe]

2
00:00:02,570 --> 00:00:05,070
[Rob Bowden - Harvard University]

3
00:00:05,070 --> 00:00:07,310
>> [To jest CS50. - CS50.TV]

4
00:00:07,310 --> 00:00:12,700
>> Więc pierwsze pytanie jest dziwnie sformułowane.

5
00:00:12,700 --> 00:00:17,480
GDB pozwala "debugować" programu, a dokładniej, co to pozwala zrobić?

6
00:00:17,480 --> 00:00:22,590
Odpowiem, że jeden, a ja nie wiem, co się dokładnie z oczekiwaniami,

7
00:00:22,590 --> 00:00:27,910
więc zgaduję, że to coś na wzór tego pozwala krok po kroku

8
00:00:27,910 --> 00:00:31,540
chodzić w ramach programu, interakcji z nią, zmienne zmienić, zrobić wszystkie te rzeczy -

9
00:00:31,540 --> 00:00:34,270
w zasadzie całkowicie kontrolować wykonywania programu

10
00:00:34,270 --> 00:00:38,410
i sprawdzić dowolną część realizacji programu.

11
00:00:38,410 --> 00:00:43,030
Więc te funkcje pozwalają debugować rzeczy.

12
00:00:43,030 --> 00:00:44,830
Okay.

13
00:00:44,830 --> 00:00:50,520
Dlaczego poszukiwanie binarne wymagają array być posortowane?

14
00:00:50,520 --> 00:00:53,360
Kto chce odpowiedzieć?

15
00:00:56,120 --> 00:01:00,070
[Uczeń] Bo to nie działa, jeśli nie jest posortowane. >> Tak. [Śmiech]

16
00:01:00,070 --> 00:01:04,910
Jeśli nie jest posortowane, a potem, że to niemożliwe, aby podzielić go na pół

17
00:01:04,910 --> 00:01:07,850
i wiem, że wszystko, na lewo jest mniej i wszystko w prawo

18
00:01:07,850 --> 00:01:10,490
jest większa niż wartość środkowa.

19
00:01:10,490 --> 00:01:12,790
Więc musi być sortowane.

20
00:01:12,790 --> 00:01:14,170
Okay.

21
00:01:14,170 --> 00:01:17,570
Dlaczego jest sortowanie bąbelkowe w O n kwadratu?

22
00:01:17,570 --> 00:01:23,230
Czy ktoś najpierw chce dać bardzo szybki przegląd na wysokim poziomie, co sortowanie bąbelkowe jest?

23
00:01:25,950 --> 00:01:33,020
[Uczeń] Jesteś zasadniczo przejść przez każdy element i sprawdzić kilka pierwszych elementów.

24
00:01:33,020 --> 00:01:37,150
Jeśli są z którym zamienić je, a następnie sprawdzić kilka następnych elementów i tak dalej.

25
00:01:37,150 --> 00:01:40,770
Gdy dojdziesz do końca, to wiesz, że największy element jest umieszczony na końcu,

26
00:01:40,770 --> 00:01:42,750
więc ignorować, że jeden potem dalej przechodzi,

27
00:01:42,750 --> 00:01:48,490
i za każdym razem trzeba sprawdzić jeden mniej elementu dopóki nie wprowadzi zmian. >> Tak.

28
00:01:48,490 --> 00:01:58,470
To się nazywa sortowanie bąbelkowe bo jeśli odwrócić tablicę na boku, więc jest w górę iw dół, pionowy,

29
00:01:58,470 --> 00:02:03,100
wówczas duże wartości będzie opadają na dno, a małe wartości będą bubble do góry.

30
00:02:03,100 --> 00:02:05,210
Tak to ma swoją nazwę.

31
00:02:05,210 --> 00:02:08,220
I tak, po prostu przejść.

32
00:02:08,220 --> 00:02:11,190
Ciągle przechodzi tablicy, zamiana większą wartość

33
00:02:11,190 --> 00:02:14,040
, aby uzyskać największe wartości dolnej.

34
00:02:14,040 --> 00:02:17,500
>> Dlaczego jest to O n kwadratu?

35
00:02:18,690 --> 00:02:24,620
Po pierwsze, czy ktoś chce powiedzieć, dlaczego to O n do kwadratu?

36
00:02:24,620 --> 00:02:28,760
[Uczeń] Ponieważ na każdym biegu idzie n razy.

37
00:02:28,760 --> 00:02:32,100
Można być pewnym, że już podjęte była największym elementowi w dół,

38
00:02:32,100 --> 00:02:35,230
następnie trzeba powtórzyć, że dla tak wielu elementów. >> Tak.

39
00:02:35,230 --> 00:02:41,800
Pamiętaj więc, co big O oznacza i co oznacza duże Omega.

40
00:02:41,800 --> 00:02:50,560
Big O to jak górna granica jak wolno może rzeczywiście działać.

41
00:02:50,560 --> 00:02:58,990
Tak więc, mówiąc, że to O n. kwadratu, to nie jest O n albo będzie w stanie uruchomić

42
00:02:58,990 --> 00:03:02,640
w czasie liniowym, ale do sześcianu O n

43
00:03:02,640 --> 00:03:06,390
ponieważ jest ograniczony przez O n sześcienny.

44
00:03:06,390 --> 00:03:12,300
Jeśli jest ograniczony przez O n kwadratu, to jest to ograniczone również przez n do sześcianu.

45
00:03:12,300 --> 00:03:20,280
Więc to jest n do kwadratu, w absolutnej najgorszym wypadku nie można zrobić lepiej niż n kwadratów,

46
00:03:20,280 --> 00:03:22,830
dlatego, że to wy z n do kwadratu.

47
00:03:22,830 --> 00:03:31,200
Tak więc, aby zobaczyć, w jaki sposób nieznaczny matematyki to wychodzi się n do kwadratu,

48
00:03:31,200 --> 00:03:40,530
jeśli mamy pięć rzeczy w naszej liście, pierwszy raz, jak wiele możemy swaps potencjalnie trzeba uczynić

49
00:03:40,530 --> 00:03:47,170
aby otrzymać? Miejmy właściwie tylko -

50
00:03:47,170 --> 00:03:52,040
Ile swapy będziemy musieli zrobić w pierwszej serii sortowanie bąbelkowe w tablicy?

51
00:03:52,040 --> 00:03:53,540
[Uczeń] n - 1. >> Tak.

52
00:03:53,540 --> 00:03:58,340
>> Jeśli są 5 elementów, będziemy potrzebować do n - 1.

53
00:03:58,340 --> 00:04:01,100
Następnie na drugim ile swapy będziemy musieli zrobić?

54
00:04:01,100 --> 00:04:03,440
[Uczeń] n - 2. >> Tak.

55
00:04:03,440 --> 00:04:11,640
I trzeci będzie N - 3, a następnie dla wygody będzie napisać dwóch ostatnich

56
00:04:11,640 --> 00:04:15,270
jak wtedy będziemy potrzebować, aby 2 swapy i 1 SWAP.

57
00:04:15,270 --> 00:04:19,899
Chyba ostatnia może lub nie może faktycznie trzeba się zdarzyć.

58
00:04:19,899 --> 00:04:22,820
Czy wymiany? Nie wiem.

59
00:04:22,820 --> 00:04:26,490
Więc to są łączne kwoty transakcji swap lub przynajmniej porównanie masz zrobić.

60
00:04:26,490 --> 00:04:29,910
Nawet, jeśli nie zamienić, trzeba jeszcze, aby porównać wartości.

61
00:04:29,910 --> 00:04:33,910
Tak więc istnieje n - 1 porównań w pierwszej serii przez tablicę.

62
00:04:33,910 --> 00:04:42,050
Jeśli zmienić te rzeczy, niech zarabia na sześć rzeczy, więc rzeczy stos ładnie,

63
00:04:42,050 --> 00:04:44,790
i zrobię 3, 2, 1.

64
00:04:44,790 --> 00:04:49,910
Więc po prostu przekształcenie tych kwot, chcemy zobaczyć, jak wiele porównań dokonujemy

65
00:04:49,910 --> 00:04:52,700
w całym algorytmu.

66
00:04:52,700 --> 00:04:56,550
Więc jeśli wprowadzą te chłopaki tu,

67
00:04:56,550 --> 00:05:07,470
to mamy jeszcze tylko podsumowanie jednak wiele porównań były.

68
00:05:07,470 --> 00:05:13,280
Ale jeśli podsumować te i podsumować te i podsumować te,

69
00:05:13,280 --> 00:05:18,130
To wciąż ten sam problem. My po prostu sumować tych szczególnych grup.

70
00:05:18,130 --> 00:05:22,400
>> Więc teraz podsumowując 3 n-tych. To nie jest tylko 3 n-tych.

71
00:05:22,400 --> 00:05:27,650
To zawsze będzie n / 2 n-tych.

72
00:05:27,650 --> 00:05:29,430
Mamy tu więc zdarzy się, że 6.

73
00:05:29,430 --> 00:05:34,830
Gdybyśmy mieli 10 rzeczy, to możemy zrobić to ugrupowania 5 różnych par rzeczy

74
00:05:34,830 --> 00:05:37,180
i kończy się z n + n + n + n + n.

75
00:05:37,180 --> 00:05:45,840
Więc zawsze dostanie n / 2 n, a więc to my jot go do n do kwadratu / 2.

76
00:05:45,840 --> 00:05:48,890
A więc nawet jeśli jest to czynnik pół, co zdarza się w

77
00:05:48,890 --> 00:05:54,190
ze względu na to, że za pomocą każdego iteracji przez tablicy 1 mniej porównać

78
00:05:54,190 --> 00:05:58,040
tak to w jaki sposób dostać się na 2, ale wciąż jest n do kwadratu.

79
00:05:58,040 --> 00:06:01,650
Nie dbamy o stały współczynnik o połowę.

80
00:06:01,650 --> 00:06:07,760
Tak wiele dużych rzeczy O tak zależy tylko rodzaju robi ten rodzaj matematyki,

81
00:06:07,760 --> 00:06:12,260
robi sum arytmetycznych i geometrycznych rzeczy serii,

82
00:06:12,260 --> 00:06:17,750
ale większość z nich w tym kursie są dość oczywiste.

83
00:06:17,750 --> 00:06:19,290
Okay.

84
00:06:19,290 --> 00:06:24,430
Dlaczego sortowania wstawiania Omega n? Co omega oznacza?

85
00:06:24,430 --> 00:06:27,730
[Dwóch studentów mówiących naraz - niezrozumiały] >> Tak.

86
00:06:27,730 --> 00:06:30,630
Omega możesz myśleć jak dolna granica.

87
00:06:30,630 --> 00:06:36,550
>> Tak więc bez względu na to, jak skuteczne Twój algorytm sortowania wstawiania jest,

88
00:06:36,550 --> 00:06:41,810
niezależnie od tego, który jest na liście przyjętej w, to zawsze musi porównać co najmniej n rzeczy

89
00:06:41,810 --> 00:06:44,620
lub musi iterować n rzeczy.

90
00:06:44,620 --> 00:06:47,280
Dlaczego tak jest?

91
00:06:47,280 --> 00:06:51,190
[Uczeń] Bo jeśli lista jest już posortowana, potem przez pierwsze powtórzenie

92
00:06:51,190 --> 00:06:54,080
można jedynie zagwarantować, że pierwszy element jest najmniej,

93
00:06:54,080 --> 00:06:56,490
i drugiej iteracji można gwarantować jedynie dwa pierwsze są

94
00:06:56,490 --> 00:07:00,010
bo nie wiesz, że reszta listy są sortowane. >> Tak.

95
00:07:00,010 --> 00:07:08,910
Jeśli przechodzą w zupełnie sortowanie listy, przynajmniej masz iść na wszystkie elementy

96
00:07:08,910 --> 00:07:12,180
widząc, że nic nie trzeba przemieszczać.

97
00:07:12,180 --> 00:07:14,720
Więc pomijając listę i mówią oh, to jest już posortowane,

98
00:07:14,720 --> 00:07:18,240
niemożliwe jest, aby wiedzieć, to posortowane aż sprawdzić każdy element

99
00:07:18,240 --> 00:07:20,660
aby zobaczyć, że są one w uporządkowanej kolejności.

100
00:07:20,660 --> 00:07:25,290
Więc dolną granicę sortowanie wstawiania jest Omega n.

101
00:07:25,290 --> 00:07:28,210
Co w najgorszym przypadku czas pracy sortowanie korespondencji seryjnej,

102
00:07:28,210 --> 00:07:31,390
w najgorszym przypadku jest O wielkie jeszcze raz?

103
00:07:31,390 --> 00:07:37,660
Tak więc w najgorszym przypadku, w jaki sposób sort merge uruchomić?

104
00:07:42,170 --> 00:07:43,690
[Uczeń] N log n. >> Tak.

105
00:07:43,690 --> 00:07:49,990
Najszybsze ogólne algorytmy sortowania są n log n. Nie można zrobić lepiej.

106
00:07:51,930 --> 00:07:55,130
>> Istnieją szczególne przypadki, a jeśli mamy czas dziś - ale prawdopodobnie won't -

107
00:07:55,130 --> 00:07:59,330
możemy zobaczyć jeden, który nie lepiej niż n log n.

108
00:07:59,330 --> 00:08:04,050
Jednak w ogólnym przypadku nie można zrobić lepiej niż n log n.

109
00:08:04,050 --> 00:08:09,680
I scalania sort bywa jeden należy wiedzieć na ten kurs, który jest n log n.

110
00:08:09,680 --> 00:08:13,260
I tak będziemy faktycznie wykonywania tego dzisiaj.

111
00:08:13,260 --> 00:08:18,070
I wreszcie, w nie więcej niż trzech zdaniach, jak działa sort wyboru?

112
00:08:18,070 --> 00:08:20,370
Czy ktoś chce odpowiedzieć, a ja liczyć swoje wyroki

113
00:08:20,370 --> 00:08:22,390
bo jeśli iść na 3 -

114
00:08:25,530 --> 00:08:28,330
Czy ktoś pamięta rodzaju selekcja?

115
00:08:31,280 --> 00:08:37,809
Sort wybór jest zazwyczaj dość łatwe do zapamiętania tylko z nazwy.

116
00:08:37,809 --> 00:08:45,350
Po prostu iteracyjne nad tablicy znaleźć cokolwiek największa wartość jest lub najmniejszy -

117
00:08:45,350 --> 00:08:47,290
cokolwiek by pan sortowania w.

118
00:08:47,290 --> 00:08:50,750
Powiedzmy więc, że mamy do sortowania od najmniejszych do największych.

119
00:08:50,750 --> 00:08:55,250
Iteracyjne nad tablicy, szukamy jakiegoś minimum elementem,

120
00:08:55,250 --> 00:08:59,750
zaznacz go, a następnie po prostu zamienić, co jest na pierwszym miejscu.

121
00:08:59,750 --> 00:09:04,090
, A następnie w drugim przejściu nad tablicy, szukać minimalnym elementem ponownie

122
00:09:04,090 --> 00:09:07,490
zaznacz go, a następnie zamień go z tym co jest na drugiej pozycji.

123
00:09:07,490 --> 00:09:10,650
Więc to tylko wybór, minimalne wartości

124
00:09:10,650 --> 00:09:16,050
i wkładanie ich do przodu, aż do tablicy jest sortowany.

125
00:09:19,210 --> 00:09:21,560
Pytania na temat tego?

126
00:09:21,560 --> 00:09:25,710
>> To nieuchronnie pojawiają się w formach trzeba wypełnić, gdy jesteś złożeniem PSET.

127
00:09:29,010 --> 00:09:32,360
Są to w zasadzie odpowiedzi na te.

128
00:09:32,360 --> 00:09:34,230
Ok, więc teraz kodowanie problemów.

129
00:09:34,230 --> 00:09:40,140
Już wysłane na e-mail - Czy nikt uzyskać e-mail? Okay.

130
00:09:40,140 --> 00:09:46,630
Już wysłane na e-mail przestrzeń, że będziemy się przy użyciu,

131
00:09:46,630 --> 00:09:52,120
i po kliknięciu na moje nazwisko - tak myślę, że będzie na dnie

132
00:09:52,120 --> 00:09:57,170
ze względu na wsteczną r - ale jeśli klikniesz na moje nazwisko zobaczysz 2 wersje.

133
00:09:57,170 --> 00:10:02,650
Wersja 1 zostanie już kopiować i wklejać kod do przestrzeni

134
00:10:02,650 --> 00:10:06,900
na rzecz wyszukiwania będziesz mieć do wykonania.

135
00:10:06,900 --> 00:10:10,540
Wersja 2 i będzie rzeczą sort że realizujemy po.

136
00:10:10,540 --> 00:10:15,770
Więc możesz kliknąć na mojej wersji 1 i pracować tam.

137
00:10:17,350 --> 00:10:22,060
A teraz chcemy zaimplementować wyszukiwania binarnego.

138
00:10:22,060 --> 00:10:26,470
>> Czy ktoś chce się po prostu dać pseudokod wysokiego szczebla wyjaśnienie

139
00:10:26,470 --> 00:10:31,440
z tego, co zamierzamy zrobić dla wyszukiwania? Tak.

140
00:10:31,440 --> 00:10:36,170
[Uczeń] Wystarczy wziąć środek tablicy i zobaczyć, czy to, czego szukasz

141
00:10:36,170 --> 00:10:38,650
jest mniejsza niż lub więcej.

142
00:10:38,650 --> 00:10:41,080
A jeśli jest to mniej, idziesz do połowy, która jest mniejsza,

143
00:10:41,080 --> 00:10:44,750
i jeśli jest więcej, można przejść do pół to więcej i powtórzyć, że aż po prostu jedno.

144
00:10:44,750 --> 00:10:46,570
[Bowden] Tak.

145
00:10:46,570 --> 00:10:51,320
Zauważ, że nasza tablica liczby jest już posortowane,

146
00:10:51,320 --> 00:10:57,190
i tak, że to oznacza, że ​​możemy skorzystać z tego i możemy najpierw sprawdzić,

147
00:10:57,190 --> 00:11:00,390
okay, szukam numeru 50.

148
00:11:00,390 --> 00:11:03,720
Więc mogę iść do środka.

149
00:11:03,720 --> 00:11:07,380
Bliski jest trudne do zdefiniowania, kiedy jest jeszcze wiele rzeczy,

150
00:11:07,380 --> 00:11:10,820
ale powiedzmy, my zawsze obciąć do środka.

151
00:11:10,820 --> 00:11:14,420
Więc tutaj mamy 8 rzeczy, więc środek będzie 16.

152
00:11:14,420 --> 00:11:17,330
Szukam 50, więc 50 jest większa niż 16.

153
00:11:17,330 --> 00:11:21,310
Więc teraz mogę w zasadzie traktuję tablicy jako tych elementów.

154
00:11:21,310 --> 00:11:23,450
Mogę wyrzucić wszystko z 16 powyżej.

155
00:11:23,450 --> 00:11:27,440
Teraz moja tablica jest po prostu te 4 elementy, powtarzam.

156
00:11:27,440 --> 00:11:31,910
Więc chcę, aby znaleźć środek ponownie, co będzie 42.

157
00:11:31,910 --> 00:11:34,730
42 jest mniejsza niż 50, więc mogę wyrzucić te dwa elementy.

158
00:11:34,730 --> 00:11:36,890
To jest moja pozostała tablica.

159
00:11:36,890 --> 00:11:38,430
Zamierzam znaleźć środek ponownie.

160
00:11:38,430 --> 00:11:42,100
Chyba 50 był zły przykład, bo zawsze wyrzucać rzeczy, na lewo,

161
00:11:42,100 --> 00:11:48,280
ale przez sam środek, jeśli szukam czegoś

162
00:11:48,280 --> 00:11:52,100
i jest to mniej niż element Jestem obecnie patrzysz,

163
00:11:52,100 --> 00:11:55,080
potem zamierzam wyrzucić wszystko do prawej.

164
00:11:55,080 --> 00:11:58,150
Więc teraz musimy wdrożyć to.

165
00:11:58,150 --> 00:12:02,310
Zauważ, że musimy przekazać w wielkości.

166
00:12:02,310 --> 00:12:06,730
Nie możemy również muszą ciężko wielkości kodu.

167
00:12:06,730 --> 00:12:11,640
Więc jeśli pozbędziemy się, że # define -

168
00:12:19,630 --> 00:12:21,430
Okay.

169
00:12:21,430 --> 00:12:27,180
Jak można dowiedzieć się, co ładnie rozmiar tablicy numerów jest obecnie?

170
00:12:27,180 --> 00:12:30,950
>> Ile elementów znajduje się w tablicy liczb?

171
00:12:30,950 --> 00:12:33,630
[Animacja] Liczby, wsporniki,. Długość?

172
00:12:33,630 --> 00:12:36,600
[Bowden] To nie istnieje w języku C.

173
00:12:36,600 --> 00:12:38,580
Potrzebujesz. Długość.

174
00:12:38,580 --> 00:12:42,010
Tablice nie posiadają właściwości, więc nie ma właściwość length tablicy

175
00:12:42,010 --> 00:12:45,650
że będzie po prostu dać Ci jednak długo zdarza się.

176
00:12:48,180 --> 00:12:51,620
[Uczeń] Zobacz, ile pamięci ma i podzielić przez ile - >> Tak.

177
00:12:51,620 --> 00:12:55,810
Więc jak możemy zobaczyć, ile pamięci ma? >> [Uczeń] sizeof. >> Tak, sizeof.

178
00:12:55,810 --> 00:13:01,680
Sizeof jest operatorem, który zamierza powrócić na rozmiar tablicy numerów.

179
00:13:01,680 --> 00:13:10,060
I że będzie to jednak wiele liczb całkowitych istnieją razy rozmiar integer

180
00:13:10,060 --> 00:13:14,050
ponieważ jest to ilość pamięci to faktycznie podejmowania.

181
00:13:14,050 --> 00:13:17,630
Więc jeśli chcesz, wiele rzeczy w tablicy,

182
00:13:17,630 --> 00:13:20,560
następnie będę chciał podzielić przez wielkość liczby całkowitej.

183
00:13:22,820 --> 00:13:26,010
Okay. Tak, że pozwala mi przejść w rozmiarze tutaj.

184
00:13:26,010 --> 00:13:29,430
Dlaczego muszę przechodzić w wielkości w ogóle?

185
00:13:29,430 --> 00:13:38,570
Dlaczego nie można po prostu zrobić tutaj int size = sizeof (stóg siana) / sizeof (int)?

186
00:13:38,570 --> 00:13:41,490
Dlaczego to nie działa?

187
00:13:41,490 --> 00:13:44,470
[Uczeń] Nie globalna zmienna jest.

188
00:13:44,470 --> 00:13:51,540
[Bowden] Haystack istnieje i jesteśmy przechodząc w ilościach stogu siana

189
00:13:51,540 --> 00:13:54,700
i jest to swego rodzaju zapowiedzią tego, co nadchodzi. Tak.

190
00:13:54,700 --> 00:14:00,170
[Uczeń] Haystack jest tylko odniesienie do niej, więc byłoby wrócić jak duży, że odniesienie jest.

191
00:14:00,170 --> 00:14:02,150
Tak.

192
00:14:02,150 --> 00:14:09,000
Wątpię w wykładzie, który widziałem stos jeszcze bardzo, prawda?

193
00:14:09,000 --> 00:14:11,270
Właśnie mówili o tym.

194
00:14:11,270 --> 00:14:16,090
Więc stos jest gdzie wszystkie zmienne zostaną zapisane.

195
00:14:16,090 --> 00:14:19,960
>> Każde wspomnienie, które jest przeznaczone dla zmiennych lokalnych dzieje w stosie,

196
00:14:19,960 --> 00:14:24,790
i każda funkcja dostaje swoją własną przestrzeń na stos, jego własne ramki stosu jest to, co się nazywa.

197
00:14:24,790 --> 00:14:31,590
Więc główny ma swoje ramki stosu, a wewnątrz niego istnieć będzie tę tablicę numerów,

198
00:14:31,590 --> 00:14:34,270
i to będzie z sizeof wielkości (numery).

199
00:14:34,270 --> 00:14:38,180
To będzie mieć wielkość liczb podzielonych według wielkości elementów,

200
00:14:38,180 --> 00:14:42,010
ale wszystkie mieszka w ramce stosu funkcji main.

201
00:14:42,010 --> 00:14:45,190
Gdy dzwonimy wyszukiwanie, wyszukiwarka ma swój własny ramki stosu,

202
00:14:45,190 --> 00:14:48,840
własnego miejsca do przechowywania wszystkich swoich zmiennych lokalnych.

203
00:14:48,840 --> 00:14:56,420
Ale te argumenty - tak stóg nie kopię tej całej tablicy jest.

204
00:14:56,420 --> 00:15:00,990
Nie przekazujemy w całej tablicy jako kopia do wyszukiwania.

205
00:15:00,990 --> 00:15:04,030
To po prostu przechodzi przez odniesienie do tej tablicy.

206
00:15:04,030 --> 00:15:11,470
Więc wyszukiwania może dostęp do tych numerów przez ten odnośnik.

207
00:15:11,470 --> 00:15:17,100
To wciąż dostępu do rzeczy, które żyją wewnątrz ramki stosu funkcji main,

208
00:15:17,100 --> 00:15:22,990
ale w zasadzie, kiedy dotrzemy do wskaźników, które powinny być szybko,

209
00:15:22,990 --> 00:15:24,980
to, co wskaźniki są.

210
00:15:24,980 --> 00:15:29,400
Wskaźniki są tylko odniesienia do rzeczy, i można użyć wskaźników dostępu do rzeczy

211
00:15:29,400 --> 00:15:32,030
które są w ramkach innych rzeczy "komin.

212
00:15:32,030 --> 00:15:37,660
Więc nawet jeśli liczba jest lokalny główny, nadal możemy uzyskać do niego dostęp za pomocą tego wskaźnika.

213
00:15:37,660 --> 00:15:41,770
Ale ponieważ jest to tylko wskaźnik, a to tylko odniesienie,

214
00:15:41,770 --> 00:15:45,040
sizeof (stóg siana) po prostu zwraca wielkość odsyłającego.

215
00:15:45,040 --> 00:15:47,950
Nie zwraca wielkość rzeczy to wskazuje.

216
00:15:47,950 --> 00:15:51,110
Nie zwraca rzeczywisty rozmiar liczb.

217
00:15:51,110 --> 00:15:55,660
I tak to nie będzie działać jak my chcemy.

218
00:15:55,660 --> 00:15:57,320
>> Pytania na temat tego?

219
00:15:57,320 --> 00:16:03,250
Wskaźniki zostaną szczegółowo włożono znacznie bardziej krwawym w tygodniach.

220
00:16:06,750 --> 00:16:13,740
I dlatego wiele rzeczy, które widzisz, większość rzeczy wyszukiwania lub rzeczy sortowania,

221
00:16:13,740 --> 00:16:16,990
oni prawie wszystko będzie trzeba podjąć rzeczywisty rozmiar tablicy,

222
00:16:16,990 --> 00:16:20,440
bo w C, nie mamy pojęcia, co rozmiar tablicy jest.

223
00:16:20,440 --> 00:16:22,720
Trzeba ręcznie przenieść go w.

224
00:16:22,720 --> 00:16:27,190
I nie można ręcznie przekazać w całej tablicy, bo jesteś tylko przejazdem w odwołaniu

225
00:16:27,190 --> 00:16:30,390
i nie można uzyskać rozmiaru z odniesienia.

226
00:16:30,390 --> 00:16:32,300
Okay.

227
00:16:32,300 --> 00:16:38,160
Więc teraz chcemy zaimplementować co wyjaśniono wcześniej.

228
00:16:38,160 --> 00:16:41,530
Można pracować na nim przez chwilę,

229
00:16:41,530 --> 00:16:45,250
i nie musisz martwić się o wszystko idealnie 100% pracy.

230
00:16:45,250 --> 00:16:51,410
Wystarczy napisać do Pseudokod pół dla jak myślisz powinno działać.

231
00:16:52,000 --> 00:16:53,630
Okay.

232
00:16:53,630 --> 00:16:56,350
Nie trzeba być całkowicie wykonane z tym jeszcze.

233
00:16:56,350 --> 00:17:02,380
Ale czy ktokolwiek czuł się komfortowo z tym, co do tej pory,

234
00:17:02,380 --> 00:17:05,599
jak coś możemy pracować razem?

235
00:17:05,599 --> 00:17:09,690
Czy ktoś chce zostać wolontariuszem? Lub będzie losowo wybierać.

236
00:17:12,680 --> 00:17:18,599
To nie musi być w porządku pod każdym względem, ale coś możemy zmodyfikować do stanu roboczego.

237
00:17:18,599 --> 00:17:20,720
[Uczeń] Jasne. >> Okay.

238
00:17:20,720 --> 00:17:27,220
Więc można zapisać zmiany, klikając na małą ikonę Zapisz.

239
00:17:27,220 --> 00:17:29,950
Jesteś Ramya, prawda? >> [Uczeń] Tak. >> [Bowden] Dobra.

240
00:17:29,950 --> 00:17:35,140
Więc teraz mogę zobaczyć swoją wersję i każdy może wyciągnąć rewizji.

241
00:17:35,140 --> 00:17:38,600
I tu mamy - Dobra.

242
00:17:38,600 --> 00:17:43,160
Więc Ramya poszedł z rekurencyjnej rozwiązaniu, które jest na pewno ważne rozwiązanie.

243
00:17:43,160 --> 00:17:44,970
Istnieją dwa sposoby, które można zrobić z tym problemem.

244
00:17:44,970 --> 00:17:48,060
Można to zrobić iteracyjnie lub rekurencyjnie.

245
00:17:48,060 --> 00:17:53,860
Większość problemów można napotkać, że można zrobić rekurencyjnie można zrobić iteracyjnie.

246
00:17:53,860 --> 00:17:58,510
Więc zrobiliśmy to rekurencyjnie.

247
00:17:58,510 --> 00:18:03,730
>> Czy ktoś chce zdefiniować, co to znaczy, aby funkcja rekurencyjna?

248
00:18:07,210 --> 00:18:08,920
[Uczeń] Kiedy masz funkcję wywoła się

249
00:18:08,920 --> 00:18:13,470
i skontaktować się aż wychodzi z prawdą i prawda. >> Tak.

250
00:18:13,470 --> 00:18:17,680
Funkcja rekurencyjna to tylko funkcja, która zwraca się.

251
00:18:17,680 --> 00:18:24,140
Istnieją trzy wielkie rzeczy, że funkcja rekurencyjna musi mieć.

252
00:18:24,140 --> 00:18:27,310
Pierwszy jest oczywiście, że wzywa się.

253
00:18:27,310 --> 00:18:29,650
Drugi wariant podstawowy.

254
00:18:29,650 --> 00:18:33,390
Więc w pewnym momencie funkcja musi przestać nazywać siebie,

255
00:18:33,390 --> 00:18:35,610
i to, co jest dla bazowym.

256
00:18:35,610 --> 00:18:43,860
Więc wiemy, że należy się zatrzymać, należy zrezygnować w poszukiwaniu

257
00:18:43,860 --> 00:18:48,150
podczas startu wynosi koniec - i pojedziemy nad tym, co to znaczy.

258
00:18:48,150 --> 00:18:52,130
Ale w końcu, ostatnią rzeczą, że to ważne dla funkcji rekurencyjnych:

259
00:18:52,130 --> 00:18:59,250
funkcje musi jakoś podejść do sprawy podstawowej.

260
00:18:59,250 --> 00:19:04,140
Lubię, jeśli nie masz nic faktycznie aktualizacji podczas dokonywania sekundy wywołanie rekurencyjne,

261
00:19:04,140 --> 00:19:07,880
jeśli jesteś dosłownie wywołanie funkcji ponownie z tymi samymi argumentami

262
00:19:07,880 --> 00:19:10,130
i nie zmienne globalne zmieniło czy coś,

263
00:19:10,130 --> 00:19:14,430
nigdy nie dotrze do przypadku bazowego, w tym przypadku, że jest źle.

264
00:19:14,430 --> 00:19:17,950
To będzie nieskończonej rekurencji i przepełnienie stosu.

265
00:19:17,950 --> 00:19:24,330
Ale tutaj widzimy, że aktualizacja się dzieje ponieważ aktualizujemy rozpocząć + End / 2,

266
00:19:24,330 --> 00:19:28,180
mamy aktualizację argument kończy się tutaj, jesteśmy aktualizacji argument Kliknij tutaj.

267
00:19:28,180 --> 00:19:32,860
Tak więc we wszystkich rekurencyjnych wywołań Aktualizujemy coś. Okay.

268
00:19:32,860 --> 00:19:38,110
Chcesz iść z nami przez Twojego rozwiązania? >> Jasne.

269
00:19:38,110 --> 00:19:44,270
Używam SearchHelp tak, że za każdym razem robię to wywołanie funkcji

270
00:19:44,270 --> 00:19:47,910
Mam początek gdzie szukam w tablicy i koniec

271
00:19:47,910 --> 00:19:49,380
, gdzie szukam tablicy.

272
00:19:49,380 --> 00:19:55,330
>> Na każdym kroku, gdzie jest to, mówiąc, że to środkowy element, który jest start + end / 2,

273
00:19:55,330 --> 00:19:58,850
jest równa, co szukasz?

274
00:19:58,850 --> 00:20:04,650
A jeśli tak jest, to okazało się to, i myślę, że zostanie przeniesiony do poziomów rekursji.

275
00:20:04,650 --> 00:20:12,540
A jeśli to nie jest prawda, to musimy sprawdzić, czy środkowa wartość w tablicy jest zbyt duża,

276
00:20:12,540 --> 00:20:19,320
w tym przypadku patrzymy na lewej połowie tablicy przechodząc od początku do środkowym indeksu.

277
00:20:19,320 --> 00:20:22,710
I inaczej robimy pół zakończenia.

278
00:20:22,710 --> 00:20:24,740
[Bowden] Dobra.

279
00:20:24,740 --> 00:20:27,730
To brzmi dobrze.

280
00:20:27,730 --> 00:20:36,640
Ok, więc kilka rzeczy, i rzeczywiście, jest to bardzo wysoki poziom, co

281
00:20:36,640 --> 00:20:41,270
że nigdy nie będzie trzeba wiedzieć o tym oczywiście, ale to jest prawda.

282
00:20:41,270 --> 00:20:46,080
Funkcje rekurencyjne, zawsze słyszę, że są one złe ofertę

283
00:20:46,080 --> 00:20:51,160
bo jeśli nazywasz siebie rekurencyjnie zbyt wiele razy, można uzyskać przepełnienie stosu

284
00:20:51,160 --> 00:20:54,990
ponieważ, jak powiedziałem wcześniej, każda funkcja ma swój własny ramki stosu.

285
00:20:54,990 --> 00:20:59,500
Więc każde wywołanie rekurencyjnej funkcji otrzymuje własną ramkę stosu.

286
00:20:59,500 --> 00:21:04,140
Więc jeśli się 1.000 rekurencyjnych wywołań, dostajesz 1.000 stosu ramki,

287
00:21:04,140 --> 00:21:08,390
i szybko można doprowadzić do zbyt wielu ramek stosu i miejscach po prostu złamać.

288
00:21:08,390 --> 00:21:13,480
Więc dlatego funkcje rekurencyjne są na ogół złe.

289
00:21:13,480 --> 00:21:19,370
Ale jest ładny podzbiór funkcji rekurencyjnych nazywa tail-rekurencyjnych funkcji,

290
00:21:19,370 --> 00:21:26,120
a to akurat jest przykładem jednego gdzie jeśli kompilator napotka na

291
00:21:26,120 --> 00:21:29,920
i powinien, jak sądzę - w Clang jeśli podajesz go flag-O2

292
00:21:29,920 --> 00:21:33,250
to będzie to zauważyć, jest ogon recursive i zrobić rzeczy dobre.

293
00:21:33,250 --> 00:21:40,050
>> Będzie używać tego samego ramki stosu kółko każdego rekurencyjnego wywołania.

294
00:21:40,050 --> 00:21:47,010
I tak, ponieważ używasz tego samego ramki stosu, nie musisz się martwić o

295
00:21:47,010 --> 00:21:51,690
coraz stosu brzegi, a w tym samym czasie, tak, jak wspomniano wcześniej,

296
00:21:51,690 --> 00:21:56,380
gdzie kiedyś wrócisz prawda, to musi wrócić do tych wszystkich ramek stosu

297
00:21:56,380 --> 00:22:01,740
oraz 10. wywołanie SearchHelp musi powrócić do 9, ma, aby powrócić do 8..

298
00:22:01,740 --> 00:22:05,360
Tak, że nie musi się zdarzyć, gdy funkcje są ogon rekurencyjne.

299
00:22:05,360 --> 00:22:13,740
A więc to, co sprawia, że ​​ta funkcja tail recursive jest zauważyć, że dla każdego zaproszenia do searchHelp

300
00:22:13,740 --> 00:22:18,470
wywołanie rekurencyjne, że robi to, co to jest powrót.

301
00:22:18,470 --> 00:22:25,290
Tak więc w ramach pierwszego zaproszenia do SearchHelp, to albo natychmiast zwróci false,

302
00:22:25,290 --> 00:22:29,590
niezwłocznie zwróci true, lub robimy wywołania rekurencyjnego SearchHelp

303
00:22:29,590 --> 00:22:33,810
gdzie co mamy powrót co, że połączenie jest powrót.

304
00:22:33,810 --> 00:22:51,560
I nie mogliśmy tego robić, jeśli zrobiliśmy coś int x = SearchHelp, return x * 2,

305
00:22:51,560 --> 00:22:55,440
tylko niektóre losowo zmiana.

306
00:22:55,440 --> 00:23:01,470
>> Więc teraz to wywołanie rekurencyjne, to int x = SearchHelp wywołanie rekurencyjne,

307
00:23:01,470 --> 00:23:05,740
nie jest już ogon recursive ponieważ rzeczywiście ma powrócić

308
00:23:05,740 --> 00:23:10,400
Powrót do poprzedniej ramki stos, tak że do poprzedniego połączenia funkcji

309
00:23:10,400 --> 00:23:13,040
może wtedy coś z wartości zwracanej.

310
00:23:13,040 --> 00:23:22,190
Więc to nie ogon recursive jest, ale to, co mieliśmy przed jest ładnie ogon rekurencyjne. Tak.

311
00:23:22,190 --> 00:23:27,000
[Uczeń] nie powinno sekund bazowym zostać najpierw sprawdzone

312
00:23:27,000 --> 00:23:30,640
bo nie może być sytuacji, w której podczas przekazywania jej argumentu

313
00:23:30,640 --> 00:23:35,770
masz zacząć = koniec, ale są one wartość igła.

314
00:23:35,770 --> 00:23:47,310
Pytanie nie możemy uruchomić w przypadku, gdy koniec jest wartość igła

315
00:23:47,310 --> 00:23:52,000
lub uruchom = koniec, odpowiednio, start = koniec

316
00:23:52,000 --> 00:23:59,480
i nie zostały faktycznie sprawdziliśmy, że szczególną wartość jeszcze,

317
00:23:59,480 --> 00:24:03,910
uruchom + End / 2 jest tylko będzie taka sama wartość.

318
00:24:03,910 --> 00:24:07,890
Ale my już zwróciło fałszywe i nigdy rzeczywiście sprawdził wartość.

319
00:24:07,890 --> 00:24:14,240
Więc przynajmniej w pierwszej rozmowy, jeśli rozmiar jest 0, to chcemy, aby powrócić false.

320
00:24:14,240 --> 00:24:17,710
Ale jeśli rozmiar jest 1, a następnie start nie będzie równego końca,

321
00:24:17,710 --> 00:24:19,820
a my przynajmniej sprawdzić jeden element.

322
00:24:19,820 --> 00:24:26,750
Ale myślę, że masz rację, że możemy skończyć w przypadku, gdy rozpoczęcie + End / 2,

323
00:24:26,750 --> 00:24:31,190
początek kończy się takie same, jak uruchomianie końcowego / 2

324
00:24:31,190 --> 00:24:35,350
ale nigdy tak naprawdę sprawdzić ten element.

325
00:24:35,350 --> 00:24:44,740
>> Jeśli więc najpierw sprawdzić, jest środkowym elementem wartości szukamy,

326
00:24:44,740 --> 00:24:47,110
wtedy możemy natychmiast zwróci true.

327
00:24:47,110 --> 00:24:50,740
Inaczej, jeśli są równe, to nie ma sensu w kontynuowaniu

328
00:24:50,740 --> 00:24:58,440
ponieważ jesteśmy po prostu będzie zaktualizować do przypadku, w którym jesteśmy na tablicy pojedynczego elementu.

329
00:24:58,440 --> 00:25:01,110
Jeśli to pojedynczy element, nie ten, którego szukamy jest

330
00:25:01,110 --> 00:25:03,530
wtedy wszystko jest w porządku. Tak.

331
00:25:03,530 --> 00:25:08,900
[Uczeń] jest to, że od wielkości, jest rzeczywiście większa niż liczba elementów w tablicy,

332
00:25:08,900 --> 00:25:13,070
istnieje już offset - >> Tak będzie rozmiar -

333
00:25:13,070 --> 00:25:19,380
[Uczeń] Powiedz jeśli tablica był rozmiar 0, a następnie SearchHelp rzeczywiście sprawdzić stogu siana 0

334
00:25:19,380 --> 00:25:21,490
pierwszego połączenia.

335
00:25:21,490 --> 00:25:25,300
Tablica ma rozmiar 0, więc 0 jest - >> Tak.

336
00:25:25,300 --> 00:25:30,750
Jest jeszcze jedna rzecz, która - może być dobry. Zastanówmy się.

337
00:25:30,750 --> 00:25:40,120
Więc jeśli tablica miała 10 elementów i środkowy będziemy sprawdzać to index 5,

338
00:25:40,120 --> 00:25:45,700
jesteśmy więc sprawdzenie 5, a powiedzmy, że wartość jest mniejsza.

339
00:25:45,700 --> 00:25:50,720
Więc jesteśmy rzucając wszystko od 5 wzwyż.

340
00:25:50,720 --> 00:25:54,030
Więc zacznij + end / 2 będzie nasz nowy koniec,

341
00:25:54,030 --> 00:25:57,450
więc tak, to zawsze tam na pobyt poza koniec tablicy.

342
00:25:57,450 --> 00:26:03,570
Jeśli to przypadek, czy to parzyste lub nieparzyste, to możemy sprawdzić, powiedzmy, 4,

343
00:26:03,570 --> 00:26:05,770
ale nadal wyrzucać -

344
00:26:05,770 --> 00:26:13,500
Więc tak, koniec jest zawsze będzie poza aktualne końca tablicy.

345
00:26:13,500 --> 00:26:18,350
Więc elementów skupiamy się, koniec jest zawsze będzie jeden po.

346
00:26:18,350 --> 00:26:24,270
A jeśli tak nie zawsze równy początek końca, jesteśmy w tablicy o rozmiarze 0.

347
00:26:24,270 --> 00:26:35,600
>> Inna sprawa, to myślałem, że aktualizujemy początek należy uruchomić + End / 2,

348
00:26:35,600 --> 00:26:44,020
więc to jest tak, że mam problemy z, gdzie start + End / 2

349
00:26:44,020 --> 00:26:46,820
jest elementem sprawdzamy.

350
00:26:46,820 --> 00:26:58,150
Powiedzmy, że mieliśmy tego 10-tablicy. Cokolwiek.

351
00:26:58,150 --> 00:27:03,250
Więc zacznij + end / 2 będzie coś jak to,

352
00:27:03,250 --> 00:27:07,060
a jeśli nie jest to wartość, że chcemy, aby zaktualizować.

353
00:27:07,060 --> 00:27:10,060
Wartość jest większa, więc chcemy patrzeć na to pół tablicy.

354
00:27:10,060 --> 00:27:15,910
Więc jak mamy aktualizację początek, mamy aktualizację początek teraz ten element.

355
00:27:15,910 --> 00:27:23,790
Ale to może nadal działać, lub co najmniej, można zrobić początek + koniec / 2 + 1.

356
00:27:23,790 --> 00:27:27,850
[Uczeń] Nie trzeba zacząć + END [niesłyszalne] >> Tak.

357
00:27:27,850 --> 00:27:33,240
Mamy już sprawdzony ten element i wiem, że nie jest jedynym, którego szukamy.

358
00:27:33,240 --> 00:27:36,800
Tak więc nie trzeba aktualizować zaczynają być ten element.

359
00:27:36,800 --> 00:27:39,560
Możemy po prostu pominąć i aktualizacji rozpocznie się ten element.

360
00:27:39,560 --> 00:27:46,060
I jest tam kiedykolwiek przypadek, powiedzmy, że to był koniec,

361
00:27:46,060 --> 00:27:53,140
tak, to będzie to początek, zacznij + End / 2 będzie to,

362
00:27:53,140 --> 00:28:00,580
rozpocząć + END - Tak, myślę, że to może skończyć się w nieskończonej rekursji.

363
00:28:00,580 --> 00:28:12,690
Powiedzmy, że jest to po prostu tablica wielkości 2 lub tablicy o wielkości 1. Myślę, że to będzie działać.

364
00:28:12,690 --> 00:28:19,490
Tak więc obecnie, jest to, że początek i koniec elementu jest 1 poza nią.

365
00:28:19,490 --> 00:28:24,110
Tak więc element, który mamy zamiar sprawdzić jest ten jeden,

366
00:28:24,110 --> 00:28:29,400
a następnie, gdy aktualizujemy start, jesteśmy aktualizacji zaczynają być 0 + 1/2,

367
00:28:29,400 --> 00:28:33,160
który skończy się nam z powrotem zacząć się ten element.

368
00:28:33,160 --> 00:28:36,210
>> Więc sprawdzamy ten sam element w kółko.

369
00:28:36,210 --> 00:28:43,310
Więc to jest przypadek, w którym każdy wywołanie rekurencyjne muszą faktycznie zaktualizować coś.

370
00:28:43,310 --> 00:28:48,370
Więc trzeba zrobić początek + End / 2 + 1, albo tam sprawa

371
00:28:48,370 --> 00:28:50,710
gdzie nie faktycznie aktualizowanie start.

372
00:28:50,710 --> 00:28:53,820
Każdy widzi?

373
00:28:53,820 --> 00:28:56,310
Okay.

374
00:28:56,310 --> 00:29:03,860
Czy ktoś ma pytania dotyczące tego rozwiązania lub komentarze więcej?

375
00:29:05,220 --> 00:29:10,280
Okay. Czy ktoś ma rozwiązanie iteracyjne, że wszyscy możemy patrzeć?

376
00:29:17,400 --> 00:29:20,940
Czy my wszyscy go rekurencyjnie?

377
00:29:20,940 --> 00:29:25,950
Albo też myślę, że jeśli otworzył jej, to możesz mieć przesłonięte poprzedniego.

378
00:29:25,950 --> 00:29:28,810
Czy to automatycznie zapisać? Nie jestem pewien.

379
00:29:35,090 --> 00:29:39,130
Czy ktoś ma iteracyjną?

380
00:29:39,130 --> 00:29:42,430
Możemy przejść przez to razem, jeśli nie.

381
00:29:46,080 --> 00:29:48,100
Pomysł będzie taki sam.

382
00:30:00,260 --> 00:30:02,830
Iteracyjnego rozwiązania.

383
00:30:02,830 --> 00:30:07,140
Będziemy chcieli zrobić w zasadzie ten sam pomysł

384
00:30:07,140 --> 00:30:16,530
gdzie chcemy śledzić nowej końca tablicy i nowy początek tablicy

385
00:30:16,530 --> 00:30:18,510
i zrobić to w kółko.

386
00:30:18,510 --> 00:30:22,430
A jeśli, co mamy śledzenie jako początek i koniec zawsze przecinają się,

387
00:30:22,430 --> 00:30:29,020
wówczas nie znaleźliśmy go i możemy powrócić false.

388
00:30:29,020 --> 00:30:37,540
Więc jak mam to zrobić? Ktoś ma sugestie lub kod dla mnie, by podciągnąć?

389
00:30:42,190 --> 00:30:47,450
[Student] Czy pętlę while. >> Tak.

390
00:30:47,450 --> 00:30:49,450
Będziesz chcą zrobić pętlę.

391
00:30:49,450 --> 00:30:51,830
>> Czy masz kod mogłem wyciągnąć, czy co chciałeś zasugerować?

392
00:30:51,830 --> 00:30:56,340
[Uczeń] Myślę, że tak. >> Dobrze. To sprawia, że ​​łatwiej. Co było na imię?

393
00:30:56,340 --> 00:30:57,890
[Uczeń] Lucas.

394
00:31:00,140 --> 00:31:04,190
Wersja 1. Okay.

395
00:31:04,190 --> 00:31:13,200
Niski jest to, co nazywa się rozpocząć wcześniej.

396
00:31:13,200 --> 00:31:17,080
Up nie jest całkiem co nazwaliśmy koniec wcześniej.

397
00:31:17,080 --> 00:31:22,750
Faktycznie, koniec jest teraz w tablicy. To element powinien rozważyć.

398
00:31:22,750 --> 00:31:26,890
Jest tak niskie, 0, jest się rozmiar tablicy - 1

399
00:31:26,890 --> 00:31:34,780
i teraz jesteśmy pętli, jak również sprawdza -

400
00:31:34,780 --> 00:31:37,340
Myślę, że można przez nie przejść.

401
00:31:37,340 --> 00:31:41,420
Jakie było Twoje myślenie przez to? Spacer z nami przez kodzie.

402
00:31:41,420 --> 00:31:49,940
[Uczeń] Jasne. Sprawdź wartość stogu siana w środku i porównaj je igłą.

403
00:31:49,940 --> 00:31:58,520
Więc jeśli jest większy niż igły, a następnie chcesz - oh, faktycznie, że powinno być odwrotnie.

404
00:31:58,520 --> 00:32:05,180
Będziesz chcą wyrzucić prawą połowę, a więc tak, to powinno być mowy.

405
00:32:05,180 --> 00:32:08,830
[Bowden] Więc to powinno być mniej? Czy to, co pan powiedział? >> [Uczeń] Tak.

406
00:32:08,830 --> 00:32:10,390
[Bowden] Dobra. Mniej.

407
00:32:10,390 --> 00:32:15,700
Więc jeśli to czego szukamy w jest mniejszy niż to, co chcemy,

408
00:32:15,700 --> 00:32:19,410
to tak, chcemy wyrzucić lewą połowę,

409
00:32:19,410 --> 00:32:22,210
co oznacza, że ​​aktualizujemy wszystko mówimy o

410
00:32:22,210 --> 00:32:26,610
niskie przesuwając na prawo tablicy.

411
00:32:26,610 --> 00:32:30,130
To wygląda dobrze.

412
00:32:30,130 --> 00:32:34,550
Myślę, że ma ten sam problem, że powiedział na poprzedniej,

413
00:32:34,550 --> 00:32:49,760
gdzie jeśli niski jest 0 i wyżej jest 1, to niski + up / 2 będzie ustawiony jako samo ponownie.

414
00:32:49,760 --> 00:32:53,860
>> I nawet jeśli to nie jest przypadek, to jest jeszcze bardziej wydajny przynajmniej

415
00:32:53,860 --> 00:32:57,630
po prostu wyrzucić element po prostu spojrzał na którym wiemy, że jest źle.

416
00:32:57,630 --> 00:33:03,240
Tak niskie + up / 2 + 1 - >> [uczeń] To powinno być inaczej.

417
00:33:03,240 --> 00:33:05,900
[Bowden] albo powinno to - 1, a druga należy + 1.

418
00:33:05,900 --> 00:33:09,580
[Uczeń] I nie powinno być podwójne znaku równości. >> [Bowden] Tak.

419
00:33:09,580 --> 00:33:11,340
[Uczeń] Tak.

420
00:33:14,540 --> 00:33:15,910
Okay.

421
00:33:15,910 --> 00:33:21,280
I wreszcie, że teraz mamy tego + 1 - 1 rzecz,

422
00:33:21,280 --> 00:33:31,520
jest to - to nie może być - jest to zawsze możliwe, niskie do końca się z wartości większej niż up?

423
00:33:35,710 --> 00:33:40,320
Myślę, że tylko w ten sposób może się zdarzyć - Czy to możliwe? >> [Uczeń] I nie wiem.

424
00:33:40,320 --> 00:33:45,220
Ale jeśli to ma obcięty i następnie dostaje minus, że 1, a następnie - >> Tak.

425
00:33:45,220 --> 00:33:47,480
[Uczeń] To może się zawiedli.

426
00:33:49,700 --> 00:33:53,940
Myślę, że powinno być dobre tylko dlatego, że

427
00:33:53,940 --> 00:33:58,800
bo do końca się niższe musiałyby one być równe, tak myślę.

428
00:33:58,800 --> 00:34:03,070
Ale jeśli są one równe, to nie zrobiłby podczas pętli na początek

429
00:34:03,070 --> 00:34:06,670
i po prostu by się zwróciło wartość. Więc myślę, że jesteśmy dobrzy teraz.

430
00:34:06,670 --> 00:34:11,530
Należy zauważyć, że nawet jeśli nie jest problemem rekurencyjne,

431
00:34:11,530 --> 00:34:17,400
samego rodzaju pomysłów zastosowania, gdy widzimy, jak to tak łatwo nadaje się

432
00:34:17,400 --> 00:34:23,659
do rekurencyjnego roztworu przez to, że jesteśmy po prostu aktualizuje indeksy w kółko,

433
00:34:23,659 --> 00:34:29,960
robimy problemu mniejsze, skupiamy się na podzbiorze tablicy.

434
00:34:29,960 --> 00:34:40,860
[Tablica] Jeśli jest niska jest do 0 i 1, to one być 0 + 1/2, które go do 0,

435
00:34:40,860 --> 00:34:44,429
i jeden będzie + 1, jeden będzie - 1.

436
00:34:47,000 --> 00:34:50,870
[Uczeń] Gdzie my sprawdzenie równości?

437
00:34:50,870 --> 00:34:55,100
Lubię gdy środkowy jest faktycznie igła?

438
00:34:55,100 --> 00:34:58,590
Nie jesteśmy obecnie robi? Oh!

439
00:35:00,610 --> 00:35:02,460
Jeśli it's -

440
00:35:05,340 --> 00:35:13,740
Tak. Nie możemy po prostu zrobić test na dół, bo powiedzmy pierwszej połowie -

441
00:35:13,740 --> 00:35:16,430
[Uczeń] To faktycznie jak nie wyrzucać przywiązani.

442
00:35:16,430 --> 00:35:20,220
Więc jeśli wyrzucić bound, trzeba go najpierw sprawdzić czy cokolwiek innego.

443
00:35:20,220 --> 00:35:23,350
Ah. Tak. >> [Uczeń] Tak.

444
00:35:23,350 --> 00:35:29,650
Więc teraz mamy wyrzucać tego, ale aktualnie patrzy,

445
00:35:29,650 --> 00:35:33,260
co oznacza, że ​​teraz trzeba mieć

446
00:35:33,260 --> 00:35:44,810
if (stóg [(niski + up) / 2] == igły), to możemy wrócić true.

447
00:35:44,810 --> 00:35:52,070
I czy mogę umieścić indziej lub po prostu wtedy, gdy oznacza to dosłownie to samo

448
00:35:52,070 --> 00:35:57,110
ponieważ byłoby to zwróciło true.

449
00:35:57,110 --> 00:36:01,450
Więc Powiem else if, ale to nie ma znaczenia.

450
00:36:01,450 --> 00:36:10,440
>> Więc jeśli jeszcze to, jeszcze to, i to jest wspólne, co robię

451
00:36:10,440 --> 00:36:14,340
gdzie nawet jeśli jest to przypadek, w którym wszystko jest dobre tutaj,

452
00:36:14,340 --> 00:36:22,780
jak nisko nigdy nie może być większa niż w górę, nie warto o tym, czy rozumowanie, że to prawda jest.

453
00:36:22,780 --> 00:36:28,010
Tak więc, jak można powiedzieć, a również niskie jest mniejsza niż lub równa

454
00:36:28,010 --> 00:36:30,720
lub gdy jest mniejsza niż niskiej

455
00:36:30,720 --> 00:36:35,300
więc jeśli kiedykolwiek równa lub niskie zdarza, żeby odpuścić,

456
00:36:35,300 --> 00:36:40,130
to możemy wyjść z tej pętli.

457
00:36:41,410 --> 00:36:44,630
Pytania, problemy, komentarze?

458
00:36:47,080 --> 00:36:49,270
Okay. To wygląda dobrze.

459
00:36:49,270 --> 00:36:52,230
Teraz chcemy zrobić sortowanie.

460
00:36:52,230 --> 00:37:04,030
Jeśli idziemy do mojego drugiego przeglądu, widzimy te same numery,

461
00:37:04,030 --> 00:37:07,550
ale teraz już nie są w uporządkowanej kolejności.

462
00:37:07,550 --> 00:37:12,840
I chcemy realizować przy użyciu dowolnego rodzaju algorytmu w O n log n.

463
00:37:12,840 --> 00:37:17,240
Więc który algorytm myślisz powinniśmy wdrażać tutaj? >> [Uczeń] sort Merge.

464
00:37:17,240 --> 00:37:23,810
[Bowden] Tak. Merge sort jest O (n log n), więc to, co będziemy robić.

465
00:37:23,810 --> 00:37:26,680
A problem będzie bardzo podobne,

466
00:37:26,680 --> 00:37:31,920
gdzie łatwo nadaje się do rozwiązania rekurencyjnej.

467
00:37:31,920 --> 00:37:35,580
Możemy również wymyślić iteracyjnego rozwiązania, jeśli chcemy,

468
00:37:35,580 --> 00:37:42,540
ale rekurencja będzie łatwiej tu i powinniśmy zrobić rekursji.

469
00:37:45,120 --> 00:37:49,530
Chyba będziemy chodzić przez sortowanie seryjnej pierwszy,

470
00:37:49,530 --> 00:37:54,280
choć nie jest to piękny film na sortowanie seryjnej już. [Śmiech]

471
00:37:54,280 --> 00:37:59,780
Więc seryjnej sortowanie Nie - Jestem tracić tak dużo tej pracy.

472
00:37:59,780 --> 00:38:02,080
Och, jest tylko jeden.

473
00:38:02,080 --> 00:38:03,630
Więc seryjnej.

474
00:38:08,190 --> 00:38:12,470
O, 1, 3, 5.

475
00:38:26,090 --> 00:38:27,440
Okay.

476
00:38:29,910 --> 00:38:33,460
Merge ma dwa osobne tablice.

477
00:38:33,460 --> 00:38:36,780
Indywidualnie te dwie tablice są zarówno posortowane.

478
00:38:36,780 --> 00:38:40,970
Więc ta tablica, 1, 3, 5, sortowane. Ta tablica, 0, 2, 4, posortowane.

479
00:38:40,970 --> 00:38:46,710
Teraz to, co należy zrobić, to merge połączyć je w jednej tablicy, która sama jest posortowane.

480
00:38:46,710 --> 00:38:57,130
Więc chcemy tablicę wielkości 6, które ma mieć te elementy w jej wnętrzu

481
00:38:57,130 --> 00:38:59,390
w uporządkowanej kolejności.

482
00:38:59,390 --> 00:39:03,390
>> I tak możemy skorzystać z faktu, że te dwie tablice są sortowanie

483
00:39:03,390 --> 00:39:06,800
to zrobić w czasie liniowym,

484
00:39:06,800 --> 00:39:13,510
liniowy znaczenie czas, jeśli tablica jest x rozmiar i to jest y rozmiar,

485
00:39:13,510 --> 00:39:20,970
a następnie powinien być całkowita Algorytm O (x + y). Okay.

486
00:39:20,970 --> 00:39:23,150
Więc sugestie.

487
00:39:23,150 --> 00:39:26,030
[Student] Czy możemy zacząć od lewej strony?

488
00:39:26,030 --> 00:39:30,150
Więc umieścić 0 w dół, a potem 1 i tutaj jesteś w 2.

489
00:39:30,150 --> 00:39:33,320
Więc to jest trochę jak masz kartę, która porusza się w prawo. >> [Bowden] Tak.

490
00:39:33,320 --> 00:39:41,070
Dla obu tych tablic, jeśli po prostu skupić się na skrajnym lewym elemencie.

491
00:39:41,070 --> 00:39:43,530
Ponieważ obie tablice są sortowane, wiemy, że te 2 elementy

492
00:39:43,530 --> 00:39:46,920
Są to najmniejsze elementy obu macierzy.

493
00:39:46,920 --> 00:39:53,500
To znaczy, że 1 2 tych elementów muszą być w naszym najmniejszy element połączonego tablicy.

494
00:39:53,500 --> 00:39:58,190
Tak się składa, że ​​najmniejszy jest jedno po prawej tej chwili.

495
00:39:58,190 --> 00:40:02,580
Więc bierzemy 0, włóż go na lewo, ponieważ 0 jest mniejsza niż 1,

496
00:40:02,580 --> 00:40:08,210
więc wziąć 0, włóż ją do naszej pierwszej pozycji, a potem zaktualizować to

497
00:40:08,210 --> 00:40:12,070
do skoncentrowania się obecnie na pierwszym elemencie.

498
00:40:12,070 --> 00:40:14,570
A teraz mamy powtórzyć.

499
00:40:14,570 --> 00:40:20,670
Więc teraz porównaj 2 i 1. 1 jest mniejszy, więc będziemy wstawiać 1.

500
00:40:20,670 --> 00:40:25,300
Aktualizujemy ten wskaźnik, aby wskazywał tego faceta.

501
00:40:25,300 --> 00:40:33,160
Teraz możemy zrobić to jeszcze raz, więc 2. Spowoduje to aktualizację, porównać te 2, 3.

502
00:40:33,160 --> 00:40:37,770
Aktualizuje, potem 4 i 5.

503
00:40:37,770 --> 00:40:42,110
Więc to jest merge.

504
00:40:42,110 --> 00:40:49,010
>> Powinno być oczywiste, że jest to czas liniowy ponieważ wystarczy przejść przez każdego elementu raz.

505
00:40:49,010 --> 00:40:55,980
I to jest największy krok do realizacji sort merge to robi.

506
00:40:55,980 --> 00:40:59,330
I to nie jest takie trudne.

507
00:40:59,330 --> 00:41:15,020
Kilka rzeczy się martwić o to, powiedzmy byliśmy połączenie 1, 2, 3, 4, 5, 6.

508
00:41:15,020 --> 00:41:30,930
W tym przypadku kończy się w sytuacji, w której ten ktoś ma zamiar być mniejsze,

509
00:41:30,930 --> 00:41:36,160
potem aktualizować ten wskaźnik, ten będzie mniejszy, zaktualizować to

510
00:41:36,160 --> 00:41:41,280
ten jest mniejszy, a teraz trzeba uznać

511
00:41:41,280 --> 00:41:44,220
kiedy już rzeczywiście zabraknie elementów do porównania z.

512
00:41:44,220 --> 00:41:49,400
Skoro już z całą tę tablicę,

513
00:41:49,400 --> 00:41:55,190
wszystko w tej tablicy jest teraz po prostu wstawiony tutaj.

514
00:41:55,190 --> 00:42:02,040
Więc jeśli kiedykolwiek biegać do punktu, w którym jeden z naszych tablic jest całkowicie połączyła się już,

515
00:42:02,040 --> 00:42:06,510
a następnie po prostu się wszystkie elementy drugiej tablicy i umieścić je w koniec tablicy.

516
00:42:06,510 --> 00:42:13,630
Więc może po prostu wstawić 4, 5, 6. Okay.

517
00:42:13,630 --> 00:42:18,070
To jest jedna rzecz, aby uważać.

518
00:42:22,080 --> 00:42:26,120
Wykonawcze, które powinny być krokiem 1.

519
00:42:26,120 --> 00:42:32,600
Scalanie sortować następnie na tej podstawie, to 2 kroki, 2 głupie kroki.

520
00:42:38,800 --> 00:42:42,090
Miejmy tylko dać tej tablicy.

521
00:42:57,920 --> 00:43:05,680
Więc seryjnej sortowanie, krok 1 jest rekurencyjnie złamać tablicę do połowy.

522
00:43:05,680 --> 00:43:09,350
Więc podzielić tę tablicę na połówki.

523
00:43:09,350 --> 00:43:22,920
Mamy obecnie 4, 15, 16, 50 i 8, 23, 42, 108.

524
00:43:22,920 --> 00:43:25,800
A teraz możemy to zrobić ponownie i dzielimy je na połówki.

525
00:43:25,800 --> 00:43:27,530
Po prostu będzie to zrobić na tej stronie.

526
00:43:27,530 --> 00:43:34,790
Tak więc 4, 15 i 16, 50.

527
00:43:34,790 --> 00:43:37,440
Chcemy zrobić to samo tutaj.

528
00:43:37,440 --> 00:43:40,340
A teraz mamy podzielić ją na pół ponownie.

529
00:43:40,340 --> 00:43:51,080
I mamy 4, 15, 16, 50.

530
00:43:51,080 --> 00:43:53,170
Więc to jest nasza sprawa bazy.

531
00:43:53,170 --> 00:44:00,540
Po tablice są wielkości 1, to kończy się na podziale na połówki.

532
00:44:00,540 --> 00:44:03,190
>> Teraz co mamy z tym zrobić?

533
00:44:03,190 --> 00:44:15,730
Mamy w końcu będzie to również dzielą się na 8, 23, 42 i 108.

534
00:44:15,730 --> 00:44:24,000
Więc teraz, że jesteśmy w tym miejscu, teraz krok dwa sortowanie korespondencji seryjnej jest tylko łączenie par do wykazów.

535
00:44:24,000 --> 00:44:27,610
Dlatego chcemy, aby połączyć te. Po prostu zadzwoń seryjnej.

536
00:44:27,610 --> 00:44:31,410
Wiemy merge zwróci je w uporządkowanej kolejności.

537
00:44:31,410 --> 00:44:33,920
4, 15.

538
00:44:33,920 --> 00:44:41,440
Teraz chcemy to połączyć i że zwróci listę z tymi, w uporządkowanej kolejności,

539
00:44:41,440 --> 00:44:44,160
16, 50..

540
00:44:44,160 --> 00:44:57,380
Łączymy te - nie mogę pisać - 8, 23 i 42, 108.

541
00:44:57,380 --> 00:45:02,890
Więc mamy scalonych par raz.

542
00:45:02,890 --> 00:45:05,140
Teraz musimy połączyć ponownie.

543
00:45:05,140 --> 00:45:10,130
Należy zauważyć, że każdy z tych list jest sortowana w sobie,

544
00:45:10,130 --> 00:45:15,220
a może po prostu połączyć te listy, aby uzyskać listę wielkości 4, która jest posortowana

545
00:45:15,220 --> 00:45:19,990
i połączyć te dwie listy, aby uzyskać listę wielkości 4, które są sortowane.

546
00:45:19,990 --> 00:45:25,710
I wreszcie, możemy połączyć te dwie listy wielkości 4, aby uzyskać jeden wykaz wielkości 8, które są sortowane.

547
00:45:25,710 --> 00:45:34,030
Tak więc, aby zobaczyć, że jest to całkowita n log n, już zobaczył, że merge jest liniowy,

548
00:45:34,030 --> 00:45:40,390
tak, gdy mamy do czynienia z połączenia tych, więc jak całkowity koszt scalenia

549
00:45:40,390 --> 00:45:43,410
dla obu tych list jest tylko 2, bo -

550
00:45:43,410 --> 00:45:49,610
Albo dobrze, to O n, ale n tutaj jest tylko te 2 elementy, więc to 2.

551
00:45:49,610 --> 00:45:52,850
A te 2 będą 2 i te 2 będą 2 i te 2 będą 2,

552
00:45:52,850 --> 00:45:58,820
więc po wszystkich scala, które musimy zrobić, to w końcu robi n.

553
00:45:58,820 --> 00:46:03,210
Jak 2 + 2 + 2 + 2 jest 8, który jest N,

554
00:46:03,210 --> 00:46:08,060
więc koszt połączenia w zestawie jest N.

555
00:46:08,060 --> 00:46:10,810
, A następnie to samo tutaj.

556
00:46:10,810 --> 00:46:16,980
Będziemy łączyć te 2, to te 2 i indywidualnie to merge weźmie cztery operacje,

557
00:46:16,980 --> 00:46:23,610
to merge weźmie cztery operacje, ale po raz kolejny, pomiędzy tym wszystkim,

558
00:46:23,610 --> 00:46:29,030
kończymy połączenie n suma rzeczy, a więc ten krok zajmuje n.

559
00:46:29,030 --> 00:46:33,670
I tak każdy poziom ma n elementów zostały połączone.

560
00:46:33,670 --> 00:46:36,110
>> A ile poziomy są tam?

561
00:46:36,110 --> 00:46:40,160
Na każdym poziomie, nasza tablica rośnie o wielkości 2.

562
00:46:40,160 --> 00:46:44,590
Tutaj nasze tablice są wielkości 1, tutaj są wielkości 2, tutaj są wielkości 4,

563
00:46:44,590 --> 00:46:46,470
i wreszcie, że są wielkości 8.

564
00:46:46,470 --> 00:46:56,450
Tak więc, ponieważ jest dwukrotnie, nie będą łącznie log N tych poziomach.

565
00:46:56,450 --> 00:47:02,090
Więc z log n poziomów, każdy poziom przy n suma operacji,

566
00:47:02,090 --> 00:47:05,720
otrzymujemy log n n algorytm.

567
00:47:05,720 --> 00:47:07,790
Pytania?

568
00:47:08,940 --> 00:47:13,320
Czy ludzie już poczyniła postępy w zakresie sposobu realizacji tego?

569
00:47:13,320 --> 00:47:18,260
Czy ktoś jest już w stanie, w którym można po prostu wyciągnąć swój kod?

570
00:47:20,320 --> 00:47:22,260
Mogę dać chwilę.

571
00:47:24,770 --> 00:47:27,470
Ten będzie dłuższy.

572
00:47:27,470 --> 00:47:28,730
Gorąco polecam powtórzy -

573
00:47:28,730 --> 00:47:30,510
Nie musisz robić rekursji do scalenia

574
00:47:30,510 --> 00:47:33,750
bo zrobić rekursji dla korespondencji seryjnej, będziesz musiał przejść kilka różnych rozmiarach.

575
00:47:33,750 --> 00:47:37,150
Można, ale jest to denerwujące.

576
00:47:37,150 --> 00:47:43,720
Ale rekursji dla rodzaju sam w sobie jest całkiem proste.

577
00:47:43,720 --> 00:47:49,190
Wystarczy dosłownie nazwać swego rodzaju na lewej połowie, sortowanie na prawej połowie. Okay.

578
00:47:51,770 --> 00:47:54,860
Każdy ma coś można podciągnąć jeszcze?

579
00:47:54,860 --> 00:47:57,540
Albo dam minut.

580
00:47:58,210 --> 00:47:59,900
Okay.

581
00:47:59,900 --> 00:48:02,970
Ktoś ma coś, co możemy pracować?

582
00:48:05,450 --> 00:48:09,680
Albo będziemy po prostu pracować z tym, a następnie rozwiń stamtąd.

583
00:48:09,680 --> 00:48:14,050
>> Każdy, kto ma więcej niż to, że można wyciągnąć?

584
00:48:14,050 --> 00:48:17,770
[Uczeń] Tak. Można podciągnąć moją. >> Dobrze.

585
00:48:17,770 --> 00:48:19,730
Tak!

586
00:48:22,170 --> 00:48:25,280
[Uczeń] Było wiele warunków. >> Och, strzelać. Można -

587
00:48:25,280 --> 00:48:28,110
[Uczeń] Mam go zapisać. >> Tak.

588
00:48:32,420 --> 00:48:35,730
Więc zrobiliśmy scalania oddzielnie.

589
00:48:35,730 --> 00:48:38,570
Oh, ale to nie jest tak źle.

590
00:48:39,790 --> 00:48:41,650
Okay.

591
00:48:41,650 --> 00:48:47,080
Więc sort jest sama po prostu wywołanie mergeSortHelp.

592
00:48:47,080 --> 00:48:49,530
Wyjaśnij nam co mergeSortHelp robi.

593
00:48:49,530 --> 00:48:55,700
[Uczeń] MergeSortHelp prawie robi dwa główne etapy,

594
00:48:55,700 --> 00:49:01,270
które jest do sortowania każdej połowie tablicy, a następnie połączenie ich obu.

595
00:49:04,960 --> 00:49:08,050
[Bowden] Okay, więc daj mi chwilę.

596
00:49:10,850 --> 00:49:13,210
Myślę, że to - >> [uczeń] muszę -

597
00:49:17,100 --> 00:49:19,400
Tak. Brakuje mi czegoś.

598
00:49:19,400 --> 00:49:23,100
W korespondencji seryjnej, zdaję sobie sprawę, że trzeba utworzyć nową tablicę

599
00:49:23,100 --> 00:49:26,530
ponieważ nie mogłem zrobić to na miejscu. >> Tak. Nie możesz. Poprawić.

600
00:49:26,530 --> 00:49:28,170
[Uczeń] Więc utworzyć nową tablicę.

601
00:49:28,170 --> 00:49:31,510
Zapomniałem w końcu łączą się ponownie zmienić.

602
00:49:31,510 --> 00:49:34,490
Okay. Potrzebujemy nowej tablicy.

603
00:49:34,490 --> 00:49:41,000
W sortowanie korespondencji seryjnej, to prawie zawsze prawdziwe.

604
00:49:41,000 --> 00:49:44,340
Część kosztów lepszego algorytmu mądrej czasu

605
00:49:44,340 --> 00:49:47,310
jest prawie zawsze konieczności użycia nieco więcej pamięci.

606
00:49:47,310 --> 00:49:51,570
Więc, nie ważne jak to zrobić scalania sortowanie,

607
00:49:51,570 --> 00:49:54,780
byś nieuchronnie trzeba użyć trochę więcej pamięci.

608
00:49:54,780 --> 00:49:58,240
On lub ona stworzyła nową tablicę.

609
00:49:58,240 --> 00:50:03,400
I wtedy można powiedzieć na koniec, że wystarczy skopiować nową tablicę do oryginalnej tablicy.

610
00:50:03,400 --> 00:50:04,830
[Uczeń] Myślę, że tak.

611
00:50:04,830 --> 00:50:08,210
Nie wiem, czy to działa w zakresie liczenia przez odniesienie lub cokolwiek -

612
00:50:08,210 --> 00:50:11,650
Tak, to będzie działać. >> [Uczeń] Dobra.

613
00:50:20,620 --> 00:50:24,480
Czy spróbować uruchomić to? >> [Uczeń] Nie, jeszcze nie. >> Okay.

614
00:50:24,480 --> 00:50:28,880
Spróbuj uruchomić go, a następnie porozmawiam o tym przez chwilę.

615
00:50:28,880 --> 00:50:35,200
[Uczeń] Muszę mieć wszystkie prototypy funkcji i wszystko, prawda?

616
00:50:37,640 --> 00:50:40,840
Prototypy funkcji. Och, masz na myśli - Tak.

617
00:50:40,840 --> 00:50:43,040
Sortuj dzwoni mergeSortHelp.

618
00:50:43,040 --> 00:50:47,390
>> Tak, aby rodzaj, aby zadzwonić mergeSortHelp, mergeSortHelp musi albo zostały zdefiniowane

619
00:50:47,390 --> 00:50:56,370
przed sortowanie lub po prostu potrzebujesz prototyp. Po prostu skopiuj i wklej to.

620
00:50:56,370 --> 00:50:59,490
I podobnie, mergeSortHelp dzwoni połączenie,

621
00:50:59,490 --> 00:51:03,830
ale seryjnej nie został jeszcze określony, więc możemy po prostu pozwolić mergeSortHelp wiedzieć

622
00:51:03,830 --> 00:51:08,700
że to co łączyć będzie wyglądać, i to jest to.

623
00:51:09,950 --> 00:51:15,730
Więc mergeSortHelp.

624
00:51:22,770 --> 00:51:32,660
Mamy problem, tu, gdzie nie mamy przypadek bazowy.

625
00:51:32,660 --> 00:51:38,110
MergeSortHelp jest cykliczne, więc każda funkcja rekurencyjna

626
00:51:38,110 --> 00:51:42,610
będzie potrzebować jakiegoś przypadku bazowego wiedzieć kiedy przestać rekurencyjnie nazywając siebie.

627
00:51:42,610 --> 00:51:45,590
Co jest naszym bazowym będzie tutaj? Tak.

628
00:51:45,590 --> 00:51:49,110
[Uczeń] Jeśli rozmiar jest 1? >> [Bowden] Tak.

629
00:51:49,110 --> 00:51:56,220
Tak jak widzieliśmy tam, zatrzymaliśmy dzielenie tablic

630
00:51:56,220 --> 00:52:01,850
gdy dotarliśmy na tablice o rozmiarze 1, co nieuchronnie są posortowane siebie.

631
00:52:01,850 --> 00:52:09,530
Więc jeśli rozmiar wynosi 1, wiemy, tablica jest już posortowane,

632
00:52:09,530 --> 00:52:12,970
więc możemy po prostu wrócić.

633
00:52:12,970 --> 00:52:16,880
>> Zauważ, że jest nieważna, więc nie zwraca niczego szczególnego, po prostu wrócić.

634
00:52:16,880 --> 00:52:19,580
Okay. Więc to jest nasza sprawa bazy.

635
00:52:19,580 --> 00:52:27,440
Chyba naszym przypadku baza może być również, jeśli zdarzy nam się łączyć tablicę wielkości 0

636
00:52:27,440 --> 00:52:30,030
zapewne chce się zatrzymać w pewnym momencie,

637
00:52:30,030 --> 00:52:33,610
tak więc można powiedzieć, o rozmiarze mniejszym niż 2 lub mniej niż lub równe 1

638
00:52:33,610 --> 00:52:37,150
tak, że to będzie działać dla każdej tablicy teraz.

639
00:52:37,150 --> 00:52:38,870
Okay.

640
00:52:38,870 --> 00:52:42,740
Więc to jest nasza sprawa bazy.

641
00:52:42,740 --> 00:52:45,950
Teraz chcesz iść z nami przez seryjnej?

642
00:52:45,950 --> 00:52:49,140
Co wszystkie te przypadki oznaczają?

643
00:52:49,140 --> 00:52:54,480
Tutaj, po prostu robi to sam pomysł, -

644
00:52:56,970 --> 00:53:02,470
[Uczeń] I trzeba przechodząc rozmiar wszystkich połączeń mergeSortHelp.

645
00:53:02,470 --> 00:53:10,080
I dodaje rozmiar jako dodatkowy podstawowych i go tam nie ma, podobnie jak rozmiar / 2.

646
00:53:10,080 --> 00:53:16,210
[Bowden] Oh, rozmiar / 2, rozmiar / 2. >> [Uczeń] Tak, jak również w wyżej, jak również funkcji.

647
00:53:16,210 --> 00:53:21,320
[Bowden] Tutaj? >> [Uczeń] Just rozmiar. >> [Bowden] Oh. Rozmiar, rozmiar? >> [Uczeń] Tak.

648
00:53:21,320 --> 00:53:23,010
[Bowden] Dobra.

649
00:53:23,010 --> 00:53:26,580
Niech pomyślę o sekundy.

650
00:53:26,580 --> 00:53:28,780
Czy możemy uruchomić do problemu?

651
00:53:28,780 --> 00:53:33,690
Jesteśmy zawsze traktując lewo jako 0. >> [Uczeń] L.

652
00:53:33,690 --> 00:53:36,340
To jest złe też. Przepraszam. Powinien być początek. Tak.

653
00:53:36,340 --> 00:53:39,230
[Bowden] Dobra. Podoba mi się to lepiej.

654
00:53:39,230 --> 00:53:43,880
I koniec. Okay.

655
00:53:43,880 --> 00:53:47,200
Więc teraz chcesz iść z nami przez seryjnej? >> [Uczeń] Dobra.

656
00:53:47,200 --> 00:53:52,150
Jestem po prostu chodzenie po tej nowej tablicy, który stworzyłem.

657
00:53:52,150 --> 00:53:57,420
Jej rozmiar jest wielkość części tablicy, że chcemy być sortowane

658
00:53:57,420 --> 00:54:03,460
i próbuje znaleźć element, który należy umieścić w nowym kroku tablicy.

659
00:54:03,460 --> 00:54:10,140
Tak więc, aby to zrobić, najpierw sprawdza, czy jestem lewa połowa tablicy nadal masz więcej elementów,

660
00:54:10,140 --> 00:54:14,260
a jeśli nie, to idź do tego innego stanu, który tylko mówi

661
00:54:14,260 --> 00:54:20,180
okay, to musi być w dobrym tablicy, a my umieścić, że w bieżącym indeksie newArray.

662
00:54:20,180 --> 00:54:27,620
>> A następnie w przeciwnym wypadku jestem sprawdzania czy prawa strona tablicy jest również zakończona,

663
00:54:27,620 --> 00:54:30,630
w takim przypadku po prostu umieścić w lewej.

664
00:54:30,630 --> 00:54:34,180
W rzeczywistości, że może nie być konieczne. Nie jestem pewien.

665
00:54:34,180 --> 00:54:40,970
Ale tak czy inaczej, dwa pozostałe sprawdzić, które z tych dwóch są mniejsze w lewo lub w prawo.

666
00:54:40,970 --> 00:54:49,770
, A także w każdym przypadku, jestem inkrementacji zależności zastępczy I przyrost.

667
00:54:49,770 --> 00:54:52,040
[Bowden] Dobra.

668
00:54:52,040 --> 00:54:53,840
To wygląda dobrze.

669
00:54:53,840 --> 00:54:58,800
Czy ktoś ma uwagi lub wątpliwości lub pytania?

670
00:55:00,660 --> 00:55:07,720
Więc czterech spraw, które musimy przynieść rzeczy do po prostu - a wygląda na to, pięć -

671
00:55:07,720 --> 00:55:13,100
ale musimy rozważyć, czy lewa tablica zabrakło rzeczy musimy się łączyć,

672
00:55:13,100 --> 00:55:16,390
czy prawo array zabrakło rzeczy musimy scalić -

673
00:55:16,390 --> 00:55:18,400
Jestem wskazując na nic.

674
00:55:18,400 --> 00:55:21,730
Tak czy lewa tablica zabrakło rzeczy lub prawa tablica zabrakło rzeczy.

675
00:55:21,730 --> 00:55:24,320
To są dwa przypadki.

676
00:55:24,320 --> 00:55:30,920
Potrzebujemy także trywialny przypadek czy lewo rzeczą jest mniejsza niż dobrze.

677
00:55:30,920 --> 00:55:33,910
Następnie chcemy wybrać lewy rzeczy.

678
00:55:33,910 --> 00:55:37,630
To są przypadki.

679
00:55:37,630 --> 00:55:40,990
Więc to było w porządku, więc to jest to.

680
00:55:40,990 --> 00:55:46,760
Array lewo. Jest 1, 2, 3,. Okay. Więc tak, to są cztery rzeczy, może chcemy zrobić.

681
00:55:50,350 --> 00:55:54,510
A my nie będziemy w iteracyjnego rozwiązania.

682
00:55:54,510 --> 00:55:55,980
Nie polecam -

683
00:55:55,980 --> 00:56:03,070
Scalanie sortowania jest przykład funkcji, która jest zarówno nie tail recursive,

684
00:56:03,070 --> 00:56:07,040
to nie jest łatwe do wykonania go tail recursive,

685
00:56:07,040 --> 00:56:13,450
ale nie jest to bardzo łatwe do wykonania go wielokrotnie.

686
00:56:13,450 --> 00:56:16,910
To jest bardzo proste.

687
00:56:16,910 --> 00:56:19,170
Ta implementacja sortowanie korespondencji seryjnej,

688
00:56:19,170 --> 00:56:22,140
seryjnej, nie ważne co robisz, masz zamiar zbudować scalania.

689
00:56:22,140 --> 00:56:29,170
>> Więc scalić sort zbudowany na seryjnej rekurencyjnie jest tylko te trzy linie.

690
00:56:29,170 --> 00:56:34,700
Iteracyjnie, to jest bardziej denerwujące i trudniej myśleć.

691
00:56:34,700 --> 00:56:41,860
Zauważmy jednak, że to nie jest ogon recursive od mergeSortHelp - gdy nazywa się -

692
00:56:41,860 --> 00:56:46,590
nadal musi robić rzeczy po tym rekurencyjnych zwróceniu.

693
00:56:46,590 --> 00:56:50,830
Więc ta ramka stosu musi nadal istnieć nawet po wywołaniu tego.

694
00:56:50,830 --> 00:56:54,170
A potem, kiedy będzie się nazywać, ramka stosu musi nadal istnieć

695
00:56:54,170 --> 00:56:57,780
bo nawet po tej samej rozmowy, wciąż musimy scalić.

696
00:56:57,780 --> 00:57:01,920
I to wcale trywialne, aby ten ogon rekurencyjne.

697
00:57:04,070 --> 00:57:06,270
Pytania?

698
00:57:08,300 --> 00:57:09,860
Dobrze.

699
00:57:09,860 --> 00:57:13,400
Więc wracając do sortowania - oh, nie dwie rzeczy, które chcesz pokazać. Okay.

700
00:57:13,400 --> 00:57:17,840
Wracając do rodzaju, zrobimy to szybko.

701
00:57:17,840 --> 00:57:21,030
Lub wyszukiwania. Sortuj? Sortuj. Tak.

702
00:57:21,030 --> 00:57:22,730
Wracając do początków rodzaju.

703
00:57:22,730 --> 00:57:29,870
Chcemy stworzyć algorytm, który sortuje tablicy przy użyciu dowolnego algorytmu

704
00:57:29,870 --> 00:57:33,660
w O n.

705
00:57:33,660 --> 00:57:40,860
Więc jak to jest możliwe? Czy ktoś ma jakiś rodzaj -

706
00:57:40,860 --> 00:57:44,300
Wspomniałem wcześniej o -

707
00:57:44,300 --> 00:57:48,300
Jeśli mamy zamiar poprawić z N log N-O n,

708
00:57:48,300 --> 00:57:51,450
musimy poprawić naszą algorytm time-mądry,

709
00:57:51,450 --> 00:57:55,250
co oznacza, że ​​co my będzie trzeba zrobić, aby się na to?

710
00:57:55,250 --> 00:57:59,520
[Uczeń] Space. >> Tak. Będziemy używać więcej miejsca.

711
00:57:59,520 --> 00:58:04,490
I nawet nie tylko więcej miejsca, to wykładniczo więcej miejsca.

712
00:58:04,490 --> 00:58:14,320
Więc myślę, że tego typu algorytmu jest pseudo coś wielomian pseudo -

713
00:58:14,320 --> 00:58:18,980
pseudo - ja nie pamiętam. Pseudo coś.

714
00:58:18,980 --> 00:58:22,210
Ale to dlatego, że musimy użyć tak wiele miejsca

715
00:58:22,210 --> 00:58:28,610
To, że jest możliwe, ale nie realne.

716
00:58:28,610 --> 00:58:31,220
>> I w jaki sposób to osiągnąć?

717
00:58:31,220 --> 00:58:36,810
Możemy to osiągnąć, jeśli mamy gwarancję, że jakiś szczególny element w tablicy

718
00:58:36,810 --> 00:58:39,600
jest poniżej pewnego rozmiaru.

719
00:58:42,070 --> 00:58:44,500
Więc powiedzmy, że rozmiar to 200,

720
00:58:44,500 --> 00:58:48,130
każdy element tablicy jest poniżej rozmiar 200.

721
00:58:48,130 --> 00:58:51,080
I to jest rzeczywiście bardzo realistyczne.

722
00:58:51,080 --> 00:58:58,660
Można bardzo łatwo mieć tablicę, że wiesz wszystko, co w nim

723
00:58:58,660 --> 00:59:00,570
będzie poniżej pewnej liczby.

724
00:59:00,570 --> 00:59:07,400
Lubię, jeśli masz jakieś absolutnie ogromny wektor lub coś

725
00:59:07,400 --> 00:59:11,810
ale wiesz, wszystko będzie między 0 i 5,

726
00:59:11,810 --> 00:59:14,790
wtedy będzie to znacznie szybciej to zrobić.

727
00:59:14,790 --> 00:59:17,930
I związany na każdym z elementów jest 5

728
00:59:17,930 --> 00:59:21,980
więc to ograniczenie, to ile pamięci masz zamiar używać.

729
00:59:21,980 --> 00:59:26,300
Tak związany jest 200.

730
00:59:26,300 --> 00:59:32,960
W teorii jest zawsze związany z całkowitą od może wynosić do 4 mld

731
00:59:32,960 --> 00:59:40,600
ale to jest nierealne, ponieważ wtedy bylibyśmy wykorzystania przestrzeni

732
00:59:40,600 --> 00:59:44,400
w postanowieniu z dnia 4 mld euro. Więc to jest nierealne.

733
00:59:44,400 --> 00:59:47,060
Ale tutaj powiemy naszym związany jest 200.

734
00:59:47,060 --> 00:59:59,570
Sztuczka robi to w O n to robimy kolejną tablicę o nazwie zliczenia wielkości związane.

735
00:59:59,570 --> 01:00:10,470
Właściwie, jest to skrót - Ja naprawdę nie wiem, czy Clang to robi.

736
01:00:11,150 --> 01:00:15,330
Ale w GCC przynajmniej - Jestem Clang zakładając robi to też -

737
01:00:15,330 --> 01:00:18,180
to będzie tylko zainicjować całą tablicę być 0s.

738
01:00:18,180 --> 01:00:25,320
Więc jeśli nie chcesz tego robić, wtedy będę mógł oddzielnie zrobić for (int i = 0;

739
01:00:25,320 --> 01:00:31,500
i <BOUND; i + +) i liczy [i] = 0;

740
01:00:31,500 --> 01:00:35,260
Więc teraz wszystko jest inicjowane na 0.

741
01:00:35,260 --> 01:00:39,570
I iteracyjne nad mojej tablicy,

742
01:00:39,570 --> 01:00:51,920
i to, co robię, jest mi liczenie każdego - Chodźmy na dół.

743
01:00:51,920 --> 01:00:55,480
Mamy 4, 15, 16, 50, 8, 23, 42, 108.

744
01:00:55,480 --> 01:01:00,010
Co Liczę jest liczba wystąpień każdego z tych elementów.

745
01:01:00,010 --> 01:01:03,470
Miejmy rzeczywiście dodać jeszcze kilka tutaj z niektórych powtórzeń.

746
01:01:03,470 --> 01:01:11,070
Tak więc mamy tu wartość, wartość, która ma być tablica [i].

747
01:01:11,070 --> 01:01:14,850
Więc val może być 4 lub 8 lub cokolwiek.

748
01:01:14,850 --> 01:01:18,870
A teraz liczę, ile z tej wartości widziałem,

749
01:01:18,870 --> 01:01:21,230
to liczy [Val] +;

750
01:01:21,230 --> 01:01:29,430
Po wykonaniu tej operacji, liczy będzie wyglądać podobnie jak 0001.

751
01:01:29,430 --> 01:01:42,190
Zróbmy liczy [wartość] - Bound + 1.

752
01:01:42,190 --> 01:01:48,230
>> Teraz to tylko do odpowiedzialności za to, że zaczynamy od 0.

753
01:01:48,230 --> 01:01:50,850
Więc jeśli 200 będzie nasza największa liczba,

754
01:01:50,850 --> 01:01:54,720
następnie 0 do 200 to 201 rzeczy.

755
01:01:54,720 --> 01:02:01,540
Więc liczy się, to będzie wyglądać jak 00001, ponieważ mamy jeden 4.

756
01:02:01,540 --> 01:02:10,210
Wtedy będziemy mieli 0001, gdzie będziemy mieć 1 w 8. indeksu count.

757
01:02:10,210 --> 01:02:14,560
Będziemy mieć 2 w 23. indeksu count.

758
01:02:14,560 --> 01:02:17,630
Będziemy mieć 2 w indeksie 42-te hrabiego.

759
01:02:17,630 --> 01:02:21,670
Więc możemy użyć count.

760
01:02:34,270 --> 01:02:44,920
Więc num_of_item = liczy [i].

761
01:02:44,920 --> 01:02:52,540
A jeśli tak jest num_of_item 2, co oznacza, że ​​chcemy wstawić 2 liczby i.

762
01:02:52,540 --> 01:02:55,290
do naszego posortowanej tablicy.

763
01:02:55,290 --> 01:03:02,000
Musimy więc śledzić, jak daleko jesteśmy do tablicy.

764
01:03:02,000 --> 01:03:05,470
So = index 0.

765
01:03:05,470 --> 01:03:09,910
Array - ja po prostu pisać.

766
01:03:16,660 --> 01:03:18,020
Counts -

767
01:03:19,990 --> 01:03:28,580
tablica [indeks + +] = i;

768
01:03:28,580 --> 01:03:32,490
Czy to, co chcę? Myślę, że to, co chcę.

769
01:03:35,100 --> 01:03:38,290
Tak, to wygląda dobrze. Okay.

770
01:03:38,290 --> 01:03:43,050
Więc nie wszyscy rozumieją, jaki jest cel mojej tablicy liczy jest?

771
01:03:43,050 --> 01:03:48,140
Liczy liczby wystąpień każdego z tych numerów.

772
01:03:48,140 --> 01:03:51,780
Wtedy jestem iteracja tej tablicy liczy,

773
01:03:51,780 --> 01:03:57,190
i-ty pozycji w tablicy liczy

774
01:03:57,190 --> 01:04:01,930
jest liczba i to, które powinny pojawić się w moim posortowanej tablicy.

775
01:04:01,930 --> 01:04:06,840
Dlatego liczy się z 4 będzie 1

776
01:04:06,840 --> 01:04:11,840
i hrabiowie 8 będzie 1, liczy się od 23 będzie 2.

777
01:04:11,840 --> 01:04:16,900
Więc tak jak wielu z nich chcę wstawić do mojej posortowanej tablicy.

778
01:04:16,900 --> 01:04:19,200
Potem po prostu to zrobić.

779
01:04:19,200 --> 01:04:28,960
Jestem włożeniem num_of_item i nic mi do posortowanej tablicy.

780
01:04:28,960 --> 01:04:31,670
>> Pytania?

781
01:04:32,460 --> 01:04:43,100
I znowu, to jest czas liniowy, ponieważ jesteśmy tylko iterowanie raz,

782
01:04:43,100 --> 01:04:47,470
ale jest również liniowa, co ta liczba bywa,

783
01:04:47,470 --> 01:04:50,730
i tak mocno zależy na tym, co związane jest.

784
01:04:50,730 --> 01:04:53,290
Z związaną z 200, to nie jest tak źle.

785
01:04:53,290 --> 01:04:58,330
Jeśli związany będzie 10.000, to jest trochę gorzej,

786
01:04:58,330 --> 01:05:01,360
ale jeśli związany będzie 4 mld to kompletnie nierealne

787
01:05:01,360 --> 01:05:07,720
i ta tablica będzie miała być wielkości 4 miliardów, co jest nierealne.

788
01:05:07,720 --> 01:05:10,860
Więc to jest to. Pytania?

789
01:05:10,860 --> 01:05:13,270
[Niesłyszalne reakcja studentów] >> Ok.

790
01:05:13,270 --> 01:05:15,710
Uświadomiłem sobie jedną rzecz, kiedy przechodziliśmy.

791
01:05:17,980 --> 01:05:23,720
Myślę, że problemem było w Lucasa i chyba każdy jeden widzieliśmy.

792
01:05:23,720 --> 01:05:26,330
Zupełnie zapomniałem.

793
01:05:26,330 --> 01:05:31,040
Jedyne co chciałem skomentować to, że gdy masz do czynienia z rzeczy jak indeksów

794
01:05:31,040 --> 01:05:38,320
nigdy tak naprawdę nie zobaczyć, kiedy piszesz do pętli,

795
01:05:38,320 --> 01:05:41,120
ale technicznie, gdy masz do czynienia z tych indeksów

796
01:05:41,120 --> 01:05:45,950
należy prawie zawsze do czynienia z liczb całkowitych bez znaku.

797
01:05:45,950 --> 01:05:53,850
Powodem tego jest to, gdy masz do czynienia z podpisanych liczb całkowitych,

798
01:05:53,850 --> 01:05:56,090
więc jeśli masz 2 podpisane liczby całkowite i dodać je razem

799
01:05:56,090 --> 01:06:00,640
i kończy się zbyt duży, to możesz skończyć z liczby ujemnej.

800
01:06:00,640 --> 01:06:03,410
Więc to, co jest przepełnienie całkowitoliczbowe.

801
01:06:03,410 --> 01:06:10,500
>> Jeśli dodać 2 miliardy, a 1 mld zł, I skończyć z ujemnym 1 miliarda euro.

802
01:06:10,500 --> 01:06:15,480
W ten sposób całkowite pracować na komputerach.

803
01:06:15,480 --> 01:06:17,510
Więc problem z użyciem -

804
01:06:17,510 --> 01:06:23,500
To jest w porządku, chyba że dzieje się niski 2 mld euro a nawet zdarza się 1 mld

805
01:06:23,500 --> 01:06:27,120
to ta będzie ujemna 1 miliard, a następnie jedziemy do podziału, że 2

806
01:06:27,120 --> 01:06:29,730
i kończy się z ujemnej 500 mln EUR.

807
01:06:29,730 --> 01:06:33,760
Więc jest to tylko problem, jeśli zdarzy ci się być na przeszukiwaniu tablicy

808
01:06:33,760 --> 01:06:38,070
miliardów rzeczy.

809
01:06:38,070 --> 01:06:44,050
Ale jeśli niski + up dzieje się przelewem, to jest to problem.

810
01:06:44,050 --> 01:06:47,750
Tak szybko, jak my je niepodpisane, to 2 miliardy plus 1 mld 3 mld euro.

811
01:06:47,750 --> 01:06:51,960
3 miliardów podzielone przez 2 jest 1,5 mld euro.

812
01:06:51,960 --> 01:06:55,670
Tak szybko, jak one są niepodpisane, wszystko jest idealne.

813
01:06:55,670 --> 01:06:59,900
A więc to jest również kwestia, kiedy jesteś pisania dla pętli,

814
01:06:59,900 --> 01:07:03,940
i faktycznie, to pewnie robi to automatycznie.

815
01:07:09,130 --> 01:07:12,330
To właściwie tylko krzyczeć na Ciebie.

816
01:07:12,330 --> 01:07:21,610
Więc jeśli ta liczba jest zbyt duża, aby być tylko liczbą całkowitą, ale byłoby to zmieścić w unsigned integer,

817
01:07:21,610 --> 01:07:24,970
będzie krzyczeć na ciebie, więc dlatego tak naprawdę nie napotkasz problemu.

818
01:07:29,150 --> 01:07:34,820
Można zobaczyć, że indeks nie będzie ujemny,

819
01:07:34,820 --> 01:07:39,220
i tak, gdy jesteś iteracja tablicy

820
01:07:39,220 --> 01:07:43,970
można prawie zawsze mówią unsigned int i, ale naprawdę nie trzeba.

821
01:07:43,970 --> 01:07:47,110
Wszystko będzie działać prawie tak samo dobrze.

822
01:07:48,740 --> 01:07:50,090
Okay. [Szepcze] Która godzina?

823
01:07:50,090 --> 01:07:54,020
Ostatnią rzeczą, chciałem pokazać - a ja po prostu to zrobić bardzo szybko.

824
01:07:54,020 --> 01:08:03,190
Wiesz, jak mamy # define więc możemy # define MAX jako 5, czy coś?

825
01:08:03,190 --> 01:08:05,940
Nie róbmy MAX. # Define PRZESTRZEGANIE jak 200. To, co zrobiliśmy wcześniej.

826
01:08:05,940 --> 01:08:10,380
Która definiuje stałe, które jest tylko będzie kopiowane i wklejane

827
01:08:10,380 --> 01:08:13,010
gdziekolwiek się napisać związany.

828
01:08:13,010 --> 01:08:18,189
>> Tak naprawdę możemy zrobić więcej # definiuje.

829
01:08:18,189 --> 01:08:21,170
Możemy # define funkcji.

830
01:08:21,170 --> 01:08:23,410
Oni nie są tak naprawdę funkcji, ale my nazywamy ich funkcje.

831
01:08:23,410 --> 01:08:36,000
Przykładem może być coś jak MAX (x, y) jest zdefiniowana jako (x <y y: x). Okay.

832
01:08:36,000 --> 01:08:40,660
Więc należy się przyzwyczaić do składni operatora trójskładnikowych

833
01:08:40,660 --> 01:08:49,029
ale x mniejsze od y? Powrót y, else return x.

834
01:08:49,029 --> 01:08:54,390
Więc widać, można zrobić tego oddzielną funkcję,

835
01:08:54,390 --> 01:09:01,399
a funkcja może być jak bool MAX ma 2 argumenty, zwrócić.

836
01:09:01,399 --> 01:09:08,340
Jest to jedna z najczęstszych z nich widzę uczyniły tak. Nazywamy je makr.

837
01:09:08,340 --> 01:09:11,790
To makro.

838
01:09:11,790 --> 01:09:15,859
To jest tylko składnia dla niego.

839
01:09:15,859 --> 01:09:18,740
Można napisać makro robić, co chcesz.

840
01:09:18,740 --> 01:09:22,649
Jesteś często zobaczyć makr do debugowania printfs i rzeczy.

841
01:09:22,649 --> 01:09:29,410
Więc typu printf, istnieją specjalne stałe w C jak podkreślają LINE podkreślenia,

842
01:09:29,410 --> 01:09:31,710
2 podkreśla LINE podkreślenia,

843
01:09:31,710 --> 01:09:37,550
i jest tam także myślę, że 2 podkreślenia FUNC. To może być to. Coś w tym stylu.

844
01:09:37,550 --> 01:09:40,880
Te rzeczy zostanie zastąpiony nazwą funkcji

845
01:09:40,880 --> 01:09:42,930
lub numer linii, na której jesteś.

846
01:09:42,930 --> 01:09:48,630
Często piszesz debugowania printfs że tu mogę po prostu pisać

847
01:09:48,630 --> 01:09:54,260
DEBUG i będzie drukować numer linii i funkcji, które zdarza mi się być w

848
01:09:54,260 --> 01:09:57,020
że spotkałem takiego oświadczenia DEBUG.

849
01:09:57,020 --> 01:09:59,550
Można także wydrukować inne rzeczy.

850
01:09:59,550 --> 01:10:05,990
Więc jedna rzecz, należy zwrócić uwagę na to, jeśli zdarzy mi się # define DOUBLE_MAX

851
01:10:05,990 --> 01:10:11,380
za coś takiego jak 2 * y, a 2 * x.

852
01:10:11,380 --> 01:10:14,310
Więc dla powodu czegokolwiek, zdarzy ci się zrobić wiele.

853
01:10:14,310 --> 01:10:16,650
Więc zrób to makro.

854
01:10:16,650 --> 01:10:18,680
To jest rzeczywiście uszkodzony.

855
01:10:18,680 --> 01:10:23,050
Nazwałbym go coś jak DOUBLE_MAX (3, 6).

856
01:10:23,050 --> 01:10:27,530
Więc co należy zwrócić?

857
01:10:28,840 --> 01:10:30,580
[Uczeń] 12.

858
01:10:30,580 --> 01:10:34,800
Tak, 12 powinien być zwrócony, a 12 jest zwracana.

859
01:10:34,800 --> 01:10:43,350
3 jest zastępowany dla x, 6 zostanie zastąpiony na y, a wracamy 2 * 6, czyli 12.

860
01:10:43,350 --> 01:10:47,710
Teraz to, co na ten temat? Co powinno zostać zwrócone?

861
01:10:47,710 --> 01:10:50,330
[Uczeń] 14. >> Idealnie 14.

862
01:10:50,330 --> 01:10:55,290
Problemem jest to, że jak hash definiuje pracę, pamiętaj, że jest to dosłowne kopiowanie i wklejanie

863
01:10:55,290 --> 01:11:00,160
wszystkiego dość dużo, więc co to ma być interpretowane jako

864
01:11:00,160 --> 01:11:11,270
jest 3 mniej niż 1 plus 6, 2 razy 1 plus 6, 2 razy 3.

865
01:11:11,270 --> 01:11:19,780
>> Więc z tego powodu prawie zawsze zawinąć wszystko w nawiasach.

866
01:11:22,180 --> 01:11:25,050
Każda zmienna prawie zawsze zawinąć w nawiasach.

867
01:11:25,050 --> 01:11:29,570
Istnieją przypadki, kiedy nie trzeba, tak jak wiem, że nie muszę tego robić tutaj

868
01:11:29,570 --> 01:11:32,110
bo mniej niż jest to prawie zawsze po prostu się do pracy,

869
01:11:32,110 --> 01:11:34,330
chociaż to może nawet nie być prawdą.

870
01:11:34,330 --> 01:11:41,870
Jeśli coś jest śmieszne jak DOUBLE_MAX (1 == 2),

871
01:11:41,870 --> 01:11:49,760
wtedy, że zamierza się zastąpić 3 mniej niż 1 równa jest równa 2,

872
01:11:49,760 --> 01:11:53,460
i tak to jest to zrobić 3 mniejsza niż 1, to się równa 2,

873
01:11:53,460 --> 01:11:55,620
co jest nie to, co chcemy.

874
01:11:55,620 --> 01:12:00,730
Dlatego aby uniknąć ewentualnych problemów pierwszeństwa operatora,

875
01:12:00,730 --> 01:12:02,870
zawsze zawinąć w nawiasach.

876
01:12:03,290 --> 01:12:07,700
Okay. I to, 5:30.

877
01:12:08,140 --> 01:12:12,470
Jeśli masz jakieś pytania dotyczące PSET, daj nam znać.

878
01:12:12,470 --> 01:12:18,010
Powinno być zabawne, a także wydanie haker jest bardziej realistyczny

879
01:12:18,010 --> 01:12:22,980
niż wydanie hakerów zeszłorocznego, więc mamy nadzieję, że wielu z was spróbować.

880
01:12:22,980 --> 01:12:26,460
Ostatni rok był bardzo przytłaczające.

881
01:12:28,370 --> 01:12:30,000
>> [CS50.TV]