1
00:00:00,000 --> 00:00:02,570
[Powered by Google Translate] [Odjeljak 3 - ugodnije]

2
00:00:02,570 --> 00:00:05,070
[Rob Bowden - Sveučilište Harvard]

3
00:00:05,070 --> 00:00:07,310
>> [Ovo je CS50. - CS50.TV]

4
00:00:07,310 --> 00:00:12,700
>> Dakle, prvo pitanje neobično sročen.

5
00:00:12,700 --> 00:00:17,480
GDB omogućuje "debug" program, ali, točnije, što to neka vam je činiti?

6
00:00:17,480 --> 00:00:22,590
Odgovorit ću vam da je jedan, a ja ne znam što točno se očekuje,

7
00:00:22,590 --> 00:00:27,910
pa sam guessing da je to nešto na tragu toga omogućuje vam korak po korak

8
00:00:27,910 --> 00:00:31,540
kroz program, komunicirati s njom, promjena varijable, učiniti sve te stvari -

9
00:00:31,540 --> 00:00:34,270
osnovi potpuno kontrolirati izvršenje programa

10
00:00:34,270 --> 00:00:38,410
i pregledati bilo dano dio izvršenja programa.

11
00:00:38,410 --> 00:00:43,030
Dakle, one značajke omogućuju ispravljanje stvari.

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

13
00:00:44,830 --> 00:00:50,520
Zašto binarno pretraživanje zahtijevaju da polje biti riješeno?

14
00:00:50,520 --> 00:00:53,360
Tko želi odgovoriti na to?

15
00:00:56,120 --> 00:01:00,070
[Student] Jer to ne radi, ako to nije riješeno. >> Da. [Smijeh]

16
00:01:00,070 --> 00:01:04,910
Ako to nije sortiran, onda je nemoguće da ga dijeli na dva dijela

17
00:01:04,910 --> 00:01:07,850
i znam da je sve na lijevoj strani je sve manje i sve desno

18
00:01:07,850 --> 00:01:10,490
veća od srednje vrijednosti.

19
00:01:10,490 --> 00:01:12,790
Dakle, to treba biti riješeno.

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

21
00:01:14,170 --> 00:01:17,570
Zašto je mjehurić vrsta u O iz n kvadrata?

22
00:01:17,570 --> 00:01:23,230
Se bilo tko prvi žele dati vrlo brzo visokoj razini pregled onoga što balon vrsta je?

23
00:01:25,950 --> 00:01:33,020
[Student] Vi zapravo proći kroz svaki element, a vi provjerite prvih nekoliko elemenata.

24
00:01:33,020 --> 00:01:37,150
Ako oni od tamo gdje ih zamijeniti, a zatim provjerite sljedećoj nekoliko elemenata i tako dalje.

25
00:01:37,150 --> 00:01:40,770
Kada dođete do kraja, onda znate da je najveći element koji se nalazi na kraju,

26
00:01:40,770 --> 00:01:42,750
tako da zanemari da je jedan onda držati na ide kroz,

27
00:01:42,750 --> 00:01:48,490
i svaki put morate provjeriti jedan manje elementa dok ne unesete promjene. >> Da.

28
00:01:48,490 --> 00:01:58,470
To se zove mjehur vrsta jer ako flip niz na svojoj strani, tako da je gore i dolje, okomito,

29
00:01:58,470 --> 00:02:03,100
onda velike vrijednosti će potonuti na dno i male vrijednosti će mjehurić do vrha.

30
00:02:03,100 --> 00:02:05,210
To je kako je dobio ime.

31
00:02:05,210 --> 00:02:08,220
I da, samo proći.

32
00:02:08,220 --> 00:02:11,190
Možete zadržati ide kroz polje, zamjene veći vrijednost

33
00:02:11,190 --> 00:02:14,040
dobiti najveće vrijednosti na dnu.

34
00:02:14,040 --> 00:02:17,500
>> Zašto je to O n kvadrata?

35
00:02:18,690 --> 00:02:24,620
Prvo, ne netko želi reći zašto je to O n kvadrat?

36
00:02:24,620 --> 00:02:28,760
[Student] Jer za svaku vožnji to ide n puta.

37
00:02:28,760 --> 00:02:32,100
Vi samo možete biti sigurni da ste uzeli najveći Element dokraja,

38
00:02:32,100 --> 00:02:35,230
onda morate ponoviti onoliko elemenata. >> Da.

39
00:02:35,230 --> 00:02:41,800
Dakle, imajte na umu ono veliko O znači i što velike Omega znači.

40
00:02:41,800 --> 00:02:50,560
Veliki O je kao gornje granice o tome koliko sporo to zapravo može pokrenuti.

41
00:02:50,560 --> 00:02:58,990
Dakle, rekavši da je O od n kvadrata, to nije O n inače će biti u mogućnosti to trčanje

42
00:02:58,990 --> 00:03:02,640
u linearnom vremenu, ali to je O n kockicama

43
00:03:02,640 --> 00:03:06,390
jer je omeđen O n kubu.

44
00:03:06,390 --> 00:03:12,300
Ako je omeđen O iz n kvadrata, onda je omeđen također n kubu.

45
00:03:12,300 --> 00:03:20,280
Dakle, to je n kvadratna, au apsolutnom najgorem slučaju to ne može učiniti bolje od n kvadrata,

46
00:03:20,280 --> 00:03:22,830
što je razlog zašto je O od n na kvadrat.

47
00:03:22,830 --> 00:03:31,200
Dakle, da vidi blagi matematiku na tome da izlazi da se n kvadratna,

48
00:03:31,200 --> 00:03:40,530
ako imamo pet stvari u našem popisu, prvi put koliko swaps bismo mogli potencijalno trebate napraviti

49
00:03:40,530 --> 00:03:47,170
kako bi se to? Ajmo zapravo samo -

50
00:03:47,170 --> 00:03:52,040
Koliko swaps ćemo morati napraviti u prvoj vožnji bubble vrste kroz niz?

51
00:03:52,040 --> 00:03:53,540
[Student] n - 1. >> Da.

52
00:03:53,540 --> 00:03:58,340
>> Ako postoji pet elemenata, mi smo idući u morati napraviti n - 1.

53
00:03:58,340 --> 00:04:01,100
Zatim na drugom jednom koliko swap ćemo morati napraviti?

54
00:04:01,100 --> 00:04:03,440
[Student] n - 2. >> Da.

55
00:04:03,440 --> 00:04:11,640
A treći će biti n - 3, a zatim za praktičnost ću napisati zadnji dvije

56
00:04:11,640 --> 00:04:15,270
kao i onda ćemo morati napraviti dvije zamjene i jedan swap.

57
00:04:15,270 --> 00:04:19,899
Valjda zadnji svibanj ili svibanj zapravo ne treba dogoditi.

58
00:04:19,899 --> 00:04:22,820
Je li zamjena? Ne znam.

59
00:04:22,820 --> 00:04:26,490
Dakle, to su ukupni iznosi swapova ili barem usporedbe morate napraviti.

60
00:04:26,490 --> 00:04:29,910
Čak i ako ne zamijeniti, još uvijek je potrebno usporediti vrijednosti.

61
00:04:29,910 --> 00:04:33,910
Dakle, tu su n - 1 usporedbe u prvoj vožnji kroz niz.

62
00:04:33,910 --> 00:04:42,050
Ako preurediti ove stvari, ajmo zapravo čine ga šest stvari, tako stvari stog gore lijepo,

63
00:04:42,050 --> 00:04:44,790
i onda ću napraviti 3, 2, 1.

64
00:04:44,790 --> 00:04:49,910
Dakle, samo preraspodjela ove svote, želimo vidjeti koliko usporedbe možemo napraviti

65
00:04:49,910 --> 00:04:52,700
u cijelom algoritam.

66
00:04:52,700 --> 00:04:56,550
Dakle, ako vam donosimo ove momke ovdje dolje,

67
00:04:56,550 --> 00:05:07,470
onda smo još uvijek samo zbrajanjem međutim mnoge usporedbe su postojale.

68
00:05:07,470 --> 00:05:13,280
Ali ako ćemo sumirati to, a mi zaključimo to i mi zaključimo to,

69
00:05:13,280 --> 00:05:18,130
to je još uvijek isti problem. Mi samo zbrojiti one posebne skupine.

70
00:05:18,130 --> 00:05:22,400
>> Dakle, sada smo zbrajanjem tri n-a. To je ne samo tri n-a.

71
00:05:22,400 --> 00:05:27,650
Uvijek će biti n / 2 n-a.

72
00:05:27,650 --> 00:05:29,430
Dakle, ovdje mi se dogoditi da imaju šest.

73
00:05:29,430 --> 00:05:34,830
Ako smo imali 10 stvari, onda bismo mogli učiniti ovo grupiranje za pet različitih parova stvarima

74
00:05:34,830 --> 00:05:37,180
, a završiti s n + n + n + N + n.

75
00:05:37,180 --> 00:05:45,840
Dakle, uvijek ćeš dobiti n / 2 n-a, i tako to ćemo ga pribilježiti se da n kvadrat / 2.

76
00:05:45,840 --> 00:05:48,890
I tako, iako je čimbenik poluvremenu, što će se dogoditi da dođe u

77
00:05:48,890 --> 00:05:54,190
zbog činjenice da se kroz svaku iteraciju preko niza ćemo usporediti jedan manje

78
00:05:54,190 --> 00:05:58,040
tako da je, kako smo dobili više od dva, ali to je još uvijek n kvadratna.

79
00:05:58,040 --> 00:06:01,650
Mi ne brinu o konstantnim faktorom od pola.

80
00:06:01,650 --> 00:06:07,760
Dakle, puno velikih O stvari ovako se oslanja na samo vrsta radi ovu vrstu matematike,

81
00:06:07,760 --> 00:06:12,260
radi aritmetičke sume i geometrijski niz stvari,

82
00:06:12,260 --> 00:06:17,750
ali većina od njih u ovom kolegiju su prilično jednostavne.

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

84
00:06:19,290 --> 00:06:24,430
Zašto je umetanje vrsta u Omega od n? Što omega znači?

85
00:06:24,430 --> 00:06:27,730
[Dva učenika govoreći odjednom - nerazumljivih] >> Da.

86
00:06:27,730 --> 00:06:30,630
Omega možete misliti kao donja granica.

87
00:06:30,630 --> 00:06:36,550
>> Dakle, bez obzira na to koliko je učinkovita vaša umetanje vrsta algoritam,

88
00:06:36,550 --> 00:06:41,810
bez obzira na popisu koji je donesen u, to je uvijek usporediti barem n stvari

89
00:06:41,810 --> 00:06:44,620
ili to mora ponoviti više n stvari.

90
00:06:44,620 --> 00:06:47,280
Zašto je to?

91
00:06:47,280 --> 00:06:51,190
[Student] Jer ako je popis već sortiran, zatim kroz prva iteracija

92
00:06:51,190 --> 00:06:54,080
možete samo jamčiti da je prvi element koji je najmanje,

93
00:06:54,080 --> 00:06:56,490
i drugi iteracija možete samo jamčiti prva dva su

94
00:06:56,490 --> 00:07:00,010
jer ne znate da je ostatak popisa je razvrstan. >> Da.

95
00:07:00,010 --> 00:07:08,910
Ako prođe u potpunosti sortirani popisu, barem ćete morati ići preko sve elemente

96
00:07:08,910 --> 00:07:12,180
da se vidi da ništa ne treba biti ganut okolo.

97
00:07:12,180 --> 00:07:14,720
Dakle, prolazeći preko popisa i govori oh, ovo je već razvrstani,

98
00:07:14,720 --> 00:07:18,240
to je nemoguće za vas da znate da je izdvojiti do te provjeriti svaki element

99
00:07:18,240 --> 00:07:20,660
da se vidi da su u sortiraju bi.

100
00:07:20,660 --> 00:07:25,290
Dakle donju granicu unosa vrste je Omega n.

101
00:07:25,290 --> 00:07:28,210
Što je najgore slučaj trčanje vrijeme spajanja vrste,

102
00:07:28,210 --> 00:07:31,390
najgorem slučaju biti veliki O opet?

103
00:07:31,390 --> 00:07:37,660
Dakle, u najgorem slučaju, kako se spajanje vrsta pokrenuti?

104
00:07:42,170 --> 00:07:43,690
[Student] N log n. >> Da.

105
00:07:43,690 --> 00:07:49,990
Najbrži opći sortiranje algoritmi su n log n. Vi ne možete učiniti bolje.

106
00:07:51,930 --> 00:07:55,130
>> Postoje posebni slučajevi, a ako imamo vremena danas - ali mi vjerojatno won't -

107
00:07:55,130 --> 00:07:59,330
mogli smo vidjeti onaj koji radi bolje od n log n.

108
00:07:59,330 --> 00:08:04,050
No, u općem slučaju, ne možete učiniti bolje od n log n.

109
00:08:04,050 --> 00:08:09,680
A spajanje vrsta se događa da se jedan te bi trebao znati za ovo naravno da je n log n.

110
00:08:09,680 --> 00:08:13,260
I tako smo zapravo ćete biti provedbi koja danas.

111
00:08:13,260 --> 00:08:18,070
I konačno, u ne više od tri rečenice, kako ne rade odabir sortiranja?

112
00:08:18,070 --> 00:08:20,370
Da li netko želi odgovoriti, a ja ću brojati svoje kazne

113
00:08:20,370 --> 00:08:22,390
jer ako idete preko 3 -

114
00:08:25,530 --> 00:08:28,330
Se bilo tko sjetiti odabira vrste?

115
00:08:31,280 --> 00:08:37,809
Izbor vrsta je obično prilično lako zapamtiti samo po imenu.

116
00:08:37,809 --> 00:08:45,350
Vi samo ponoviti preko polja, pronaći ono što je najveća vrijednost ili najmanji -

117
00:08:45,350 --> 00:08:47,290
god bi ste sortiranje u.

118
00:08:47,290 --> 00:08:50,750
Pa recimo da smo sortiranje od najmanjih do najvećih.

119
00:08:50,750 --> 00:08:55,250
Možete ponoviti preko polja, u potrazi za bilo minimalna element,

120
00:08:55,250 --> 00:08:59,750
odaberite ga, a zatim ga zamijeniti samo ono što je na prvom mjestu.

121
00:08:59,750 --> 00:09:04,090
A onda na drugom prolazu preko polja, tražiti minimalno elementa opet,

122
00:09:04,090 --> 00:09:07,490
odaberite ga, a zatim ga zamijeniti s onim što je u drugom položaju.

123
00:09:07,490 --> 00:09:10,650
Dakle, mi smo samo branje i odabiru minimalne vrijednosti

124
00:09:10,650 --> 00:09:16,050
te ih umetanjem u prednjem dijelu polja dok se sortiraju.

125
00:09:19,210 --> 00:09:21,560
Pitanja o tome?

126
00:09:21,560 --> 00:09:25,710
>> To neminovno pojaviti u oblicima morate ispuniti kada ste podnošenja pset.

127
00:09:29,010 --> 00:09:32,360
Oni su u osnovi odgovore na njih.

128
00:09:32,360 --> 00:09:34,230
Ok, tako da sada kodiranja problema.

129
00:09:34,230 --> 00:09:40,140
Već sam poslao preko e-maila - Je li netko uopće dobiti taj e-mail? Ok.

130
00:09:40,140 --> 00:09:46,630
Već sam poslao preko e-maila prostor koji ćemo koristiti,

131
00:09:46,630 --> 00:09:52,120
a ako kliknete na moje ime - pa mislim da ću biti na dnu

132
00:09:52,120 --> 00:09:57,170
zbog retrogradne r - ali ako kliknete na moje ime vidjet ćete dvije izmjene.

133
00:09:57,170 --> 00:10:02,650
Revizija 1 će se već sam kopirati i zalijepiti kôd u prostore

134
00:10:02,650 --> 00:10:06,900
za pretraživanje stvar koju će morati provesti.

135
00:10:06,900 --> 00:10:10,540
I Revizija 2 će biti vrsta stvar koja mi provesti nakon toga.

136
00:10:10,540 --> 00:10:15,770
Dakle, možete kliknuti na mom Revizija 1 i raditi od tamo.

137
00:10:17,350 --> 00:10:22,060
A sada želimo provesti binarnog pretraživanja.

138
00:10:22,060 --> 00:10:26,470
>> Se bilo tko želi samo dati pseudocode visokoj razini objašnjenje

139
00:10:26,470 --> 00:10:31,440
od čega ćemo morati napraviti za pretraživanje? Da.

140
00:10:31,440 --> 00:10:36,170
[Student] Ti samo uzmi sredinu polja i vidjeti ako je ono što tražite

141
00:10:36,170 --> 00:10:38,650
manji od onog ili više od toga.

142
00:10:38,650 --> 00:10:41,080
A ako je manje, idete na polovicu da je manje,

143
00:10:41,080 --> 00:10:44,750
a ako je više, možete ići do polovice koja je sve više i li to ponoviti dok ste upravo dobili jednu stvar.

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

145
00:10:46,570 --> 00:10:51,320
Uočite da naš brojevi niz već sortiran,

146
00:10:51,320 --> 00:10:57,190
pa to znači da možemo iskoristiti da i mi prvo mogao provjeriti,

147
00:10:57,190 --> 00:11:00,390
ok, ja sam u potrazi za brojem 50.

148
00:11:00,390 --> 00:11:03,720
Dakle, ja mogu ići u sredini.

149
00:11:03,720 --> 00:11:07,380
Srednji je teško definirati kad je čak i nekoliko stvari,

150
00:11:07,380 --> 00:11:10,820
ali recimo samo da ćemo uvijek izrežite na sredini.

151
00:11:10,820 --> 00:11:14,420
Dakle, ovdje imamo 8 stvari, tako da je srednji će biti 16 godina.

152
00:11:14,420 --> 00:11:17,330
Ja sam u potrazi za 50, pa 50 je veća od 16 godina.

153
00:11:17,330 --> 00:11:21,310
Dakle, sada sam u osnovi može liječiti moju lepezu kao tih elemenata.

154
00:11:21,310 --> 00:11:23,450
Ja mogu baciti sve od 16 više.

155
00:11:23,450 --> 00:11:27,440
Sada mi niz je samo ta četiri elementa, a ja ponavljam.

156
00:11:27,440 --> 00:11:31,910
Pa onda želim pronaći sredinu opet, što će biti 42.

157
00:11:31,910 --> 00:11:34,730
42 je manje od 50, tako da mogu baciti daleko ta dva elementa.

158
00:11:34,730 --> 00:11:36,890
Ovo je moj preostali polje.

159
00:11:36,890 --> 00:11:38,430
Ja ću naći sredinu opet.

160
00:11:38,430 --> 00:11:42,100
Valjda 50 bio loš primjer, jer sam uvijek bio daleko bacanje stvari na lijevoj strani,

161
00:11:42,100 --> 00:11:48,280
ali po istom mjerom, ako sam u potrazi za nečim

162
00:11:48,280 --> 00:11:52,100
i to je manje od elementa Ja trenutno gledam,

163
00:11:52,100 --> 00:11:55,080
onda ću baciti sve na desnoj strani.

164
00:11:55,080 --> 00:11:58,150
Dakle, sada moramo provesti da.

165
00:11:58,150 --> 00:12:02,310
Primijetit ćete da moramo proći u veličini.

166
00:12:02,310 --> 00:12:06,730
Možemo također ne trebaju hard-code veličine.

167
00:12:06,730 --> 00:12:11,640
Dakle, ako smo dobili osloboditi od koji # define -

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

169
00:12:21,430 --> 00:12:27,180
Kako mogu lijepo shvatiti što je veličina brojeva niz trenutno?

170
00:12:27,180 --> 00:12:30,950
>> Koliko su elementi u brojkama niz?

171
00:12:30,950 --> 00:12:33,630
[Student] Brojevi, zagrade,. Dužina?

172
00:12:33,630 --> 00:12:36,600
[Bowden] To ne postoji u C.

173
00:12:36,600 --> 00:12:38,580
Trebate. Duljina.

174
00:12:38,580 --> 00:12:42,010
Polja nemaju svojstva, tako da ne postoji dužina svojstvo polja

175
00:12:42,010 --> 00:12:45,650
samo da će vam dati ma koliko dugo se dogodi da se.

176
00:12:48,180 --> 00:12:51,620
[Student] Vidi koliko memorije ima i podijeliti sa koliko - >> Da.

177
00:12:51,620 --> 00:12:55,810
Dakle, kako možemo vidjeti koliko memorije ima? >> [Student] sizeof. >> Da, sizeof.

178
00:12:55,810 --> 00:13:01,680
Sizeof je operator koji će se vratiti na veličinu brojeva niza.

179
00:13:01,680 --> 00:13:10,060
I to će biti, međutim mnogi prirodni brojevi postoje trenuci veličine cijeli broj

180
00:13:10,060 --> 00:13:14,050
budući da je koliko memorije to je zapravo uzimanje gore.

181
00:13:14,050 --> 00:13:17,630
Dakle, ako želim broj stvari u polju,

182
00:13:17,630 --> 00:13:20,560
onda ću žele podijeliti po veličini cijeli broj.

183
00:13:22,820 --> 00:13:26,010
Ok. Dakle, koji vam omogućuje da prođem u veličini ovdje.

184
00:13:26,010 --> 00:13:29,430
Zašto trebam proći u veličini uopće?

185
00:13:29,430 --> 00:13:38,570
Zašto ne mogu učiniti samo ovdje int size = sizeof (plast) / sizeof (int)?

186
00:13:38,570 --> 00:13:41,490
Zašto to ne rade?

187
00:13:41,490 --> 00:13:44,470
[Student] To nije globalna varijabla.

188
00:13:44,470 --> 00:13:51,540
[Bowden] plastu sijena postoji i mi smo prolazi u brojkama kao plastu sijena,

189
00:13:51,540 --> 00:13:54,700
i to je vrsta nagovještaj onoga što će doći. Da.

190
00:13:54,700 --> 00:14:00,170
[Student] plastu sijena je samo referenca na njega, tako da će se vratiti koliko je velika da referenca.

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

192
00:14:02,150 --> 00:14:09,000
Sumnjam u predavanju koje ste vidjeli hrpu još stvarno, zar ne?

193
00:14:09,000 --> 00:14:11,270
Upravo smo razgovarali o tome.

194
00:14:11,270 --> 00:14:16,090
Dakle, stog je mjesto gdje sve svoje varijable će biti pohranjena.

195
00:14:16,090 --> 00:14:19,960
>> Bilo memorije koja se dodjeljuje za lokalne varijable se događa u snopu,

196
00:14:19,960 --> 00:14:24,790
i svaka funkcija dobiva svoj prostor na dimnjak, vlastiti stog okvir je ono što se zove.

197
00:14:24,790 --> 00:14:31,590
Dakle, glavna ima svoj stog okvir, a unutar njega će postojati ovu brojeva niz,

198
00:14:31,590 --> 00:14:34,270
i to će biti od veličine sizeof (brojevi).

199
00:14:34,270 --> 00:14:38,180
To će imati veličinu brojeva podijeljenih po veličini elemenata,

200
00:14:38,180 --> 00:14:42,010
ali da su svi živi u glavnom je stog okvir.

201
00:14:42,010 --> 00:14:45,190
Kad mi zovemo pretraživanje, traži dobiva svoj stack okvir,

202
00:14:45,190 --> 00:14:48,840
vlastiti prostor za pohranu svih svojih lokalnih varijabli.

203
00:14:48,840 --> 00:14:56,420
No ti argumenti - tako plast nije kopija cijelog tog polja.

204
00:14:56,420 --> 00:15:00,990
Mi ne prođe u cijelom nizu kao kopiju u potrazi.

205
00:15:00,990 --> 00:15:04,030
To samo prolazi referencu na tom polju.

206
00:15:04,030 --> 00:15:11,470
Dakle, traži se može pristupiti tim brojeve kroz ovaj referencu.

207
00:15:11,470 --> 00:15:17,100
To je još uvijek pristupa stvari koje žive unutar glavnih je stog okvira,

208
00:15:17,100 --> 00:15:22,990
ali u osnovi, kada smo dobili naputke, koji bi trebao biti uskoro,

209
00:15:22,990 --> 00:15:24,980
to je ono što upućuje se.

210
00:15:24,980 --> 00:15:29,400
Kazaljke su samo reference na stvari, a možete koristiti pokazivače za pristup stvari

211
00:15:29,400 --> 00:15:32,030
koji su u drugim stvarima 'stog okvire.

212
00:15:32,030 --> 00:15:37,660
Dakle, iako je broj lokalnih za glavni, još uvijek možete pristupiti putem ovog pokazivača.

213
00:15:37,660 --> 00:15:41,770
No, budući da je samo pokazivač, a to je samo referenca,

214
00:15:41,770 --> 00:15:45,040
sizeof (plast) samo vraća veličinu referencu sama.

215
00:15:45,040 --> 00:15:47,950
To ne vrati na veličinu stvar to pokazuje da.

216
00:15:47,950 --> 00:15:51,110
To ne vrati stvarnu veličinu brojeva.

217
00:15:51,110 --> 00:15:55,660
I tako to ne ide na posao kao što smo željeli.

218
00:15:55,660 --> 00:15:57,320
>> Pitanja o tome?

219
00:15:57,320 --> 00:16:03,250
Pokazivači će nestati u znatno više krvavoj detalje u tjednima koji dolaze.

220
00:16:06,750 --> 00:16:13,740
I to je razlog zašto puno stvari koje možete vidjeti, većina pretraživanja stvari ili sortiranje stvari,

221
00:16:13,740 --> 00:16:16,990
oni su gotovo svi će morati uzeti stvarnu veličinu polja,

222
00:16:16,990 --> 00:16:20,440
jer u C, nemamo pojma što je veličina polja je.

223
00:16:20,440 --> 00:16:22,720
Morate ručno ga proći u.

224
00:16:22,720 --> 00:16:27,190
I ne možete ručno proći u cijelom nizu jer ste upravo prolazi u odnosu

225
00:16:27,190 --> 00:16:30,390
i to se ne može dobiti veličinu iz referencu.

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

227
00:16:32,300 --> 00:16:38,160
Dakle, sada želimo provesti što je ranije objašnjeno.

228
00:16:38,160 --> 00:16:41,530
Možete raditi na tome za minutu,

229
00:16:41,530 --> 00:16:45,250
i ne morate se brinuti o sve savršeno 100% radi.

230
00:16:45,250 --> 00:16:51,410
Samo napišite do polovine pseudocode za koliko mislite da bi trebao raditi.

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

232
00:16:53,630 --> 00:16:56,350
Nema potrebe da se u potpunosti biti učinjeno s ovim gostiju.

233
00:16:56,350 --> 00:17:02,380
Ali ne bilo tko osjeća ugodno s onim što su dosad,

234
00:17:02,380 --> 00:17:05,599
kao nešto što možemo raditi s zajedno?

235
00:17:05,599 --> 00:17:09,690
Se bilo tko želi volontirati? Ili sam nasumično će pokupiti.

236
00:17:12,680 --> 00:17:18,599
To ne mora biti točno, po svim mjerilima, ali nešto možemo mijenjati u radno stanje.

237
00:17:18,599 --> 00:17:20,720
[Student] Naravno. >> Ok.

238
00:17:20,720 --> 00:17:27,220
Tako možete uštedjeti reviziju klikom na ikonu malo Save.

239
00:17:27,220 --> 00:17:29,950
Ti si Ramya, zar ne? >> [Student] Aha. >> [Bowden] Ok.

240
00:17:29,950 --> 00:17:35,140
Dakle, sada mogu vidjeti vaš reviziju i svatko se može podići reviziju.

241
00:17:35,140 --> 00:17:38,600
A ovdje imamo - Ok.

242
00:17:38,600 --> 00:17:43,160
Dakle Ramya otišao s rekurzivni rješenje, što je svakako vrijedi rješenje.

243
00:17:43,160 --> 00:17:44,970
Postoje dva načina na koje možete napraviti ovaj problem.

244
00:17:44,970 --> 00:17:48,060
Možete to učiniti iterativno ili rekurzivno.

245
00:17:48,060 --> 00:17:53,860
Većina problema možete naići da se može obaviti rekurzivno također može biti učinjeno iterativno.

246
00:17:53,860 --> 00:17:58,510
Dakle, ovdje smo to učinili rekurzivno.

247
00:17:58,510 --> 00:18:03,730
>> Da li netko želi definirati što to znači da funkcija rekurzivna?

248
00:18:07,210 --> 00:18:08,920
[Student] Kada imate funkciju se nazvati

249
00:18:08,920 --> 00:18:13,470
i onda se pozvati dok ona izlazi s točno i istinito. >> Da.

250
00:18:13,470 --> 00:18:17,680
Rekurzivna funkcija je samo funkcija koja se poziva.

251
00:18:17,680 --> 00:18:24,140
Postoje tri velike stvari koje rekurzivna funkcija mora imati.

252
00:18:24,140 --> 00:18:27,310
Prvi je očito, to se zove.

253
00:18:27,310 --> 00:18:29,650
Drugi je osnovni slučaj.

254
00:18:29,650 --> 00:18:33,390
Dakle, u nekom trenutku funkcija treba prestati se zove,

255
00:18:33,390 --> 00:18:35,610
i to je ono baza slučaj je za.

256
00:18:35,610 --> 00:18:43,860
Dakle, ovdje znamo da bismo trebali prestati, trebamo odustati u našoj potrazi

257
00:18:43,860 --> 00:18:48,150
kada početi jednak kraj - i mi ćemo ići preko onoga što to znači.

258
00:18:48,150 --> 00:18:52,130
Ali konačno, posljednja stvar koja je važna za rekurzivnih funkcija:

259
00:18:52,130 --> 00:18:59,250
funkcije nekako mora pristupiti slučaj baze.

260
00:18:59,250 --> 00:19:04,140
Sviđa mi se, ako niste zapravo ažuriranje ništa kada bi drugi rekurzivni poziv,

261
00:19:04,140 --> 00:19:07,880
ako ste doslovno samo da zove funkciju ponovno s istim argumentima

262
00:19:07,880 --> 00:19:10,130
i nema globalne varijable su se promijenile ili ništa,

263
00:19:10,130 --> 00:19:14,430
nikada nećete postići slučaj bazu, u kojem slučaju to je loše.

264
00:19:14,430 --> 00:19:17,950
To će biti beskonačan rekurzije i stog prelijevati.

265
00:19:17,950 --> 00:19:24,330
No, ovdje vidimo da ažuriranje se događa jer smo ažuriranju započeti + kraj / 2,

266
00:19:24,330 --> 00:19:28,180
ažurirat ćemo kraj argument ovdje, ažurirat ćemo početnu argument ovdje.

267
00:19:28,180 --> 00:19:32,860
Tako je u svim rekurzivnim pozivima smo ažuriranja nešto. Ok.

268
00:19:32,860 --> 00:19:38,110
Želite li nas provesti kroz svoje rješenje? >> Naravno.

269
00:19:38,110 --> 00:19:44,270
Ja sam koristeći SearchHelp tako da svaki put kad sam napraviti ovu funkciju poziv

270
00:19:44,270 --> 00:19:47,910
Imam početak gdje sam u potrazi za u polje i kraj

271
00:19:47,910 --> 00:19:49,380
gdje tražim lepezu.

272
00:19:49,380 --> 00:19:55,330
>> Na svakom koraku gdje je rekavši da je srednji element, koji je početak + kraj / 2,

273
00:19:55,330 --> 00:19:58,850
je da jednak onome što tražimo?

274
00:19:58,850 --> 00:20:04,650
A ako je, onda smo ga našli, i mislim da dobiva prošao gore razine rekurzije.

275
00:20:04,650 --> 00:20:12,540
A ako to nije istina, onda smo provjeriti je li to srednja vrijednost niza je prevelika,

276
00:20:12,540 --> 00:20:19,320
u kojem slučaju gledamo na lijevoj polovici niza odlaskom od početka do sredine indeksa.

277
00:20:19,320 --> 00:20:22,710
I inače mi prekidnu polovicu.

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

279
00:20:24,740 --> 00:20:27,730
Zvuči dobro.

280
00:20:27,730 --> 00:20:36,640
Ok, tako par stvari, i zapravo, ovo je vrlo visoka razina stvar

281
00:20:36,640 --> 00:20:41,270
da nikada nećete znati za ovaj tečaj, ali to je istina.

282
00:20:41,270 --> 00:20:46,080
Rekurzivno funkcije, uvijek čuti da su oni loš posao

283
00:20:46,080 --> 00:20:51,160
jer ako rekurzivno nazivati ​​se previše puta, možete dobiti stack overflow

284
00:20:51,160 --> 00:20:54,990
jer, kao što sam rekao prije, svaka funkcija dobiva svoj vlastiti stog okvir.

285
00:20:54,990 --> 00:20:59,500
Dakle, svaki poziv rekurzivne funkcije dobiva svoj vlastiti stog okvir.

286
00:20:59,500 --> 00:21:04,140
Dakle, ako bi 1000 rekurzivnih poziva, možete dobiti 1.000 stog okvire,

287
00:21:04,140 --> 00:21:08,390
i brzo možete voditi da imaju previše stack okviri i stvari samo razbiti.

288
00:21:08,390 --> 00:21:13,480
Dakle, to je razlog zašto rekurzivni funkcije su općenito loše.

289
00:21:13,480 --> 00:21:19,370
No, tu je lijepo podskup rekurzivnih funkcija zove rep-rekurzivnih funkcija,

290
00:21:19,370 --> 00:21:26,120
i to se događa da se primjer jedne gdje ako prevodilac Obavijesti to

291
00:21:26,120 --> 00:21:29,920
i to bi, mislim - u zveka ako prođe to-O2 zastave

292
00:21:29,920 --> 00:21:33,250
onda ćete primijetiti je to rep rekurzivna i napraviti stvari dobro.

293
00:21:33,250 --> 00:21:40,050
>> To će ponovno isti stog okvir iznova i iznova za svaki rekurzivni poziv.

294
00:21:40,050 --> 00:21:47,010
I tako jer ste koristeći istu stog okvir, ne morate brinuti o

295
00:21:47,010 --> 00:21:51,690
ikada stog prelijeva, a istodobno, kao što ste rekli prije,

296
00:21:51,690 --> 00:21:56,380
gdje kada se vratite istina, onda to mora vratiti do svih tih stog okvira

297
00:21:56,380 --> 00:22:01,740
i 10. poziv na SearchHelp mora vratiti na 9., mora se vratiti na 8..

298
00:22:01,740 --> 00:22:05,360
Tako da ne treba da se desi kada su funkcije rep rekurzivna.

299
00:22:05,360 --> 00:22:13,740
I tako ono što čini ova funkcija rep rekurzivna je obavijest da je za bilo koju pozivom na searchHelp

300
00:22:13,740 --> 00:22:18,470
rekurzivna poziva da se to što je ono što je povratka.

301
00:22:18,470 --> 00:22:25,290
Tako je u prvom pozivu na SearchHelp, ili ćemo se odmah vratiti false,

302
00:22:25,290 --> 00:22:29,590
odmah vratiti istina, ili ćemo napraviti rekurzivni poziv SearchHelp

303
00:22:29,590 --> 00:22:33,810
gdje ono što smo povratka je ono što taj poziv se vraća.

304
00:22:33,810 --> 00:22:51,560
I ne možemo to učiniti ako mi je nešto poput int x = SearchHelp, povratka x * 2,

305
00:22:51,560 --> 00:22:55,440
samo su neki slučajni promjena.

306
00:22:55,440 --> 00:23:01,470
>> Dakle, sada je to rekurzivna poziv, ovaj int x = SearchHelp rekurzivni poziv,

307
00:23:01,470 --> 00:23:05,740
više nije rep rekurzivna, jer se zapravo ne mora vratiti

308
00:23:05,740 --> 00:23:10,400
povratak na prethodnu stog okvira, tako da je prethodni poziv na funkciju

309
00:23:10,400 --> 00:23:13,040
onda mogu nešto učiniti s povratnom vrijednosti.

310
00:23:13,040 --> 00:23:22,190
Dakle, ovo nije rep rekurzivna, ali ono što smo imali prije nego što je lijepo rep rekurzivna. Da.

311
00:23:22,190 --> 00:23:27,000
[Student] Ne bi drugi osnovni slučaj biti provjeren prvi

312
00:23:27,000 --> 00:23:30,640
jer bi moglo biti situacija u kojoj kada prođe to argument

313
00:23:30,640 --> 00:23:35,770
ste početi = kraj, ali oni su igla vrijednost.

314
00:23:35,770 --> 00:23:47,310
Pitanje nije možemo izvoditi u slučaju kada na kraju je igla vrijednost

315
00:23:47,310 --> 00:23:52,000
ili početak = kraj, na odgovarajući način, početi = kraj

316
00:23:52,000 --> 00:23:59,480
i niste zapravo provjerio tu određenu vrijednost, ali,

317
00:23:59,480 --> 00:24:03,910
onda početi + kraj / 2 samo će biti iste vrijednosti.

318
00:24:03,910 --> 00:24:07,890
No, već smo se vratili lažna i nikad se nismo zapravo provjeriti vrijednost.

319
00:24:07,890 --> 00:24:14,240
Tako barem, u prvom pozivu, ako je veličina 0, onda želimo vratiti false.

320
00:24:14,240 --> 00:24:17,710
Ali, ako je veličina 1, zatim početak ne ide na ravnopravnoj kraju,

321
00:24:17,710 --> 00:24:19,820
a mi ćemo barem provjeriti jedan element.

322
00:24:19,820 --> 00:24:26,750
Ali mislim da si u pravu da možemo završiti u slučaju kada pokrenete + kraj / 2,

323
00:24:26,750 --> 00:24:31,190
početak završi na isti način kao početak + end / 2,

324
00:24:31,190 --> 00:24:35,350
ali mi nikada zapravo provjerio tog elementa.

325
00:24:35,350 --> 00:24:44,740
>> Dakle, ako smo prvo provjerite je srednji element koji je vrijednost tražimo,

326
00:24:44,740 --> 00:24:47,110
onda možemo odmah vratiti istina.

327
00:24:47,110 --> 00:24:50,740
Jer ako su oni jednaki, onda nema smisla dalje

328
00:24:50,740 --> 00:24:58,440
jer mi smo samo će ažurirati u slučaju kada smo na jednom elementu niza.

329
00:24:58,440 --> 00:25:01,110
Ako je jedan element koji nije jedan tražimo,

330
00:25:01,110 --> 00:25:03,530
onda je sve u redu. Da.

331
00:25:03,530 --> 00:25:08,900
[Student] Stvar je u tome da je od veličine je zapravo veći od broja elemenata u polju,

332
00:25:08,900 --> 00:25:13,070
tu je već pomak - >> Tako će površina -

333
00:25:13,070 --> 00:25:19,380
[Student] Recimo, ako je polje je veličina 0, onda SearchHelp zapravo će provjeriti plast sijena od 0

334
00:25:19,380 --> 00:25:21,490
na prvi poziv.

335
00:25:21,490 --> 00:25:25,300
Niz ima veličinu 0, pa je 0 - >> Da.

336
00:25:25,300 --> 00:25:30,750
Postoji još jedna stvar koja - to bi moglo biti dobro. Razmislimo.

337
00:25:30,750 --> 00:25:40,120
Dakle, ako je polje imao 10 elemenata i srednje jednom ćemo provjeriti je indeks 5,

338
00:25:40,120 --> 00:25:45,700
tako da smo provjeru 5, a recimo da je vrijednost manja.

339
00:25:45,700 --> 00:25:50,720
Dakle, mi smo bacanje sve dalje od 5 nadalje.

340
00:25:50,720 --> 00:25:54,030
Dakle, početi + kraj / 2 će biti naš novi kraj,

341
00:25:54,030 --> 00:25:57,450
pa da, to je uvijek će ostati izvan kraja niza.

342
00:25:57,450 --> 00:26:03,570
Ako je to slučaj, ako je to čak i čudno, onda bismo provjerili, kažu, 4,

343
00:26:03,570 --> 00:26:05,770
ali mi smo još uvijek daleko bacanje -

344
00:26:05,770 --> 00:26:13,500
Tako da, na kraju uvijek će biti izvan stvarnog kraja niza.

345
00:26:13,500 --> 00:26:18,350
Dakle elementima smo s naglaskom na, na kraju uvijek će biti jedan nakon toga.

346
00:26:18,350 --> 00:26:24,270
I tako, ako ne start ikad jednak kraj, mi smo u niz veličina 0.

347
00:26:24,270 --> 00:26:35,600
>> Druga stvar koju sam mislio je da smo osvježavamo početak treba započeti + kraj / 2,

348
00:26:35,600 --> 00:26:44,020
pa to je slučaj da sam poteškoća s, gdje je početak kraja + / 2

349
00:26:44,020 --> 00:26:46,820
je element koji smo provjeru.

350
00:26:46,820 --> 00:26:58,150
Ajmo reći da smo imali ovaj 10-elementa niz. God.

351
00:26:58,150 --> 00:27:03,250
Dakle, početi + kraj / 2 će biti nešto poput ovoga,

352
00:27:03,250 --> 00:27:07,060
a ako to nije vrijednost, recimo želimo ažurirati.

353
00:27:07,060 --> 00:27:10,060
Vrijednost je veća, pa mi želimo da pogledate ovaj polovici niza.

354
00:27:10,060 --> 00:27:15,910
Pa kako smo ažuriranju početak, ažurirat ćemo početi sada biti taj element.

355
00:27:15,910 --> 00:27:23,790
No, to još uvijek može raditi, ili barem, što možete učiniti start + kraj / 2 + 1.

356
00:27:23,790 --> 00:27:27,850
[Student] Ne treba započeti + kraj [nečujno] >> Da.

357
00:27:27,850 --> 00:27:33,240
Već smo provjeriti taj element i znam da to nije onaj tražimo.

358
00:27:33,240 --> 00:27:36,800
Dakle, ne trebamo ažurirati početak da se taj element.

359
00:27:36,800 --> 00:27:39,560
Mi samo možemo ga preskočiti i ažurirati početi da se taj element.

360
00:27:39,560 --> 00:27:46,060
I je li ikada slučaj, recimo, da je to bio kraj,

361
00:27:46,060 --> 00:27:53,140
pa onda započeti će biti ovako, započeti + kraj / 2 će biti ovako,

362
00:27:53,140 --> 00:28:00,580
započeti + kraj - Da, mislim da mogu završiti u beskrajnom rekurzije.

363
00:28:00,580 --> 00:28:12,690
Recimo da je to samo niz veličine 2 ili nizom veličine 1. Mislim da će to raditi.

364
00:28:12,690 --> 00:28:19,490
Dakle, trenutno, start je taj element i na kraju je jedan izvan njega.

365
00:28:19,490 --> 00:28:24,110
Dakle, element koji ćemo provjeriti je li to jedan,

366
00:28:24,110 --> 00:28:29,400
i onda kad smo ažurirali početak, ažurirat ćemo početi da bude 0 + 1/2,

367
00:28:29,400 --> 00:28:33,160
koji će nam završiti natrag s početka se taj element.

368
00:28:33,160 --> 00:28:36,210
>> Tako smo provjeru istog elementa iznova i iznova.

369
00:28:36,210 --> 00:28:43,310
Dakle, ovo je slučaj gdje je svaki rekurzivni poziv zapravo mora ažurirati nešto.

370
00:28:43,310 --> 00:28:48,370
Dakle, trebamo učiniti start + end / 2 + 1, ili pak postoji slučaj

371
00:28:48,370 --> 00:28:50,710
gdje nismo zapravo ažuriranja početak.

372
00:28:50,710 --> 00:28:53,820
Svatko vidi da?

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

374
00:28:56,310 --> 00:29:03,860
Ima li netko pitanja o ovoj otopini ili bilo više komentare?

375
00:29:05,220 --> 00:29:10,280
Ok. Se bilo tko imati rješenje iterativnog da svi možemo pogledati?

376
00:29:17,400 --> 00:29:20,940
Jesmo li svi to učiniti rekurzivno?

377
00:29:20,940 --> 00:29:25,950
Ili također mislim ako njezin otvorena, onda možda ćete morati zanemariti svoju prethodnu jednom.

378
00:29:25,950 --> 00:29:28,810
Da li to automatski spremiti? Nisam pozitivno.

379
00:29:35,090 --> 00:29:39,130
Se bilo tko imati iterativni?

380
00:29:39,130 --> 00:29:42,430
Možemo hodati kroz njega zajedno, ako ne.

381
00:29:46,080 --> 00:29:48,100
Ideja će biti isti.

382
00:30:00,260 --> 00:30:02,830
Iterativne rješenje.

383
00:30:02,830 --> 00:30:07,140
Mi ćemo htjeti osnovi učiniti istu ideju

384
00:30:07,140 --> 00:30:16,530
gdje želimo pratiti nove kraju niza i novi početak niza

385
00:30:16,530 --> 00:30:18,510
i to iznova i iznova.

386
00:30:18,510 --> 00:30:22,430
A ako je ono što smo praćenje kao početak i kraj ikad sijeku,

387
00:30:22,430 --> 00:30:29,020
onda ga nismo pronašli, a možemo se vratiti false.

388
00:30:29,020 --> 00:30:37,540
Pa kako ću to učiniti? Svatko ima prijedloge ili koda za mene podići?

389
00:30:42,190 --> 00:30:47,450
[Student] Do while petlja. >> Da.

390
00:30:47,450 --> 00:30:49,450
Ti si idući u ištanje to napraviti petlju.

391
00:30:49,450 --> 00:30:51,830
>> Jeste li imali kod sam mogao podići, ili ono što si htio sugerirati?

392
00:30:51,830 --> 00:30:56,340
[Student] Mislim da je tako. >> Redu. To čini stvari lakše. Što je vaše ime?

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

394
00:31:00,140 --> 00:31:04,190
Revizija 1. Ok.

395
00:31:04,190 --> 00:31:13,200
Slaba je ono što smo nazvali početi prije.

396
00:31:13,200 --> 00:31:17,080
Gore nije baš ono što smo nazvali kraj prije.

397
00:31:17,080 --> 00:31:22,750
Zapravo, na kraju je sada u polju. To je element koji bi trebali uzeti u obzir.

398
00:31:22,750 --> 00:31:26,890
Tako nisko je 0, gore je veličina polja - 1,

399
00:31:26,890 --> 00:31:34,780
a sada smo petlje, a mi smo provjeru -

400
00:31:34,780 --> 00:31:37,340
Pretpostavljam da možete hodati kroz njega.

401
00:31:37,340 --> 00:31:41,420
Što je vaše razmišljanje kroz to? Nas Šetnja kroz kodu.

402
00:31:41,420 --> 00:31:49,940
[Student] Naravno. Pogledajte plastu sijena vrijednosti u sredini i usporedite ga iglom.

403
00:31:49,940 --> 00:31:58,520
Dakle, ako je veći od vašeg igle, onda želite - Oh, zapravo, da bi trebao biti unatrag.

404
00:31:58,520 --> 00:32:05,180
Ti si idući u ištanje to baciti desnu polovicu, pa da, to bi trebao biti način.

405
00:32:05,180 --> 00:32:08,830
[Bowden] Dakle, to bi trebalo biti manje? Je li to ono što je rekao? >> [Student] Aha.

406
00:32:08,830 --> 00:32:10,390
[Bowden] Ok. Manje.

407
00:32:10,390 --> 00:32:15,700
Dakle, ako je ono što gledamo je manje od onoga što želimo,

408
00:32:15,700 --> 00:32:19,410
onda da, želimo baciti lijevu polovicu,

409
00:32:19,410 --> 00:32:22,210
što znači da smo ažuriranju sve smo s obzirom na

410
00:32:22,210 --> 00:32:26,610
pomicanjem nisko na desno od polja.

411
00:32:26,610 --> 00:32:30,130
Ovo izgleda dobro.

412
00:32:30,130 --> 00:32:34,550
Mislim da ima isti problem da mi je rekao na prethodni mjesec,

413
00:32:34,550 --> 00:32:49,760
gdje ako je niska razina 0 i do 1, a zatim niska + gore / 2 ide postaviti da se ista stvar ponovo.

414
00:32:49,760 --> 00:32:53,860
>> A čak i ako to nije slučaj, to je još uvijek učinkovitija u najmanju ruku

415
00:32:53,860 --> 00:32:57,630
jednostavno odbaciti element smo samo gledali što znamo je pogrešno.

416
00:32:57,630 --> 00:33:03,240
Tako niska + gore / 2 + 1 - >> [student] To bi trebao biti drugi način.

417
00:33:03,240 --> 00:33:05,900
[Bowden] Ili to treba biti - 1, a drugi bi trebao biti + 1.

418
00:33:05,900 --> 00:33:09,580
[Student] I tu bi trebala biti dvostruka znaka jednakosti. >> [Bowden] Aha.

419
00:33:09,580 --> 00:33:11,340
[Student] Aha.

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

421
00:33:15,910 --> 00:33:21,280
I na kraju, da sada imamo tu + 1 do 1 stvar,

422
00:33:21,280 --> 00:33:31,520
je to - to ne može biti - je li to ikad moguće za niske završiti s vrijednošću većom od gore?

423
00:33:35,710 --> 00:33:40,320
Mislim jedini način da se može dogoditi - Je li to moguće? >> [Student] ne znam.

424
00:33:40,320 --> 00:33:45,220
Ali, ako to dobiva skraćen, a zatim dobiva minus da jedan i onda - >> Da.

425
00:33:45,220 --> 00:33:47,480
[Student] To bi eventualno dobili messed up.

426
00:33:49,700 --> 00:33:53,940
Mislim da bi trebao biti dobar samo zato

427
00:33:53,940 --> 00:33:58,800
za to završiti niža morali bi biti jednaki, mislim.

428
00:33:58,800 --> 00:34:03,070
No, ako su jednaki, onda mi ne bi učinio while petlja za početak

429
00:34:03,070 --> 00:34:06,670
a mi bi samo vratili vrijednost. Dakle, mislim da smo dobro sada.

430
00:34:06,670 --> 00:34:11,530
Primijetit ćete da iako je ovaj problem više nije rekurzivna,

431
00:34:11,530 --> 00:34:17,400
Ista vrsta ideja primijeniti gdje možemo vidjeti kako se to tako lako dade

432
00:34:17,400 --> 00:34:23,659
na rekurzivni rješenje po činjenici da smo samo ažuriranje indeksa iznova i iznova,

433
00:34:23,659 --> 00:34:29,960
činimo Problem manji i manji, usredotočili smo se na podskup polja.

434
00:34:29,960 --> 00:34:40,860
[Student] Ako je niska je 0 i do 1, oni će oboje biti 0 + 1/2, koja će ići na 0,

435
00:34:40,860 --> 00:34:44,429
i onda će biti + 1, jedan će biti - 1.

436
00:34:47,000 --> 00:34:50,870
[Student] Gdje smo provjeru jednakosti?

437
00:34:50,870 --> 00:34:55,100
Kao i ako sredini je zapravo igla?

438
00:34:55,100 --> 00:34:58,590
Mi trenutno ne radi? Oh!

439
00:35:00,610 --> 00:35:02,460
Ako it's -

440
00:35:05,340 --> 00:35:13,740
Da. Ne možemo samo napraviti test ovdje dolje, jer recimo prvi sredini -

441
00:35:13,740 --> 00:35:16,430
[Student] To je zapravo sviđa ne bacaju vezan.

442
00:35:16,430 --> 00:35:20,220
Dakle, ako ste baciti vezan, morate ga prvo provjerite ili što god.

443
00:35:20,220 --> 00:35:23,350
Ah. Da. >> [Student] Aha.

444
00:35:23,350 --> 00:35:29,650
Dakle, sada smo bačeni na jednom smo trenutno pogledao,

445
00:35:29,650 --> 00:35:33,260
što znači da sada treba također imati

446
00:35:33,260 --> 00:35:44,810
ako (plast [(niska + gore) / 2] == igla), onda se možemo vratiti istina.

447
00:35:44,810 --> 00:35:52,070
I da li sam stavio drugi ili samo ako, to znači doslovno istu stvar

448
00:35:52,070 --> 00:35:57,110
jer bi to vratilo istina.

449
00:35:57,110 --> 00:36:01,450
Dakle, ja ću staviti još ako, ali to ne smeta.

450
00:36:01,450 --> 00:36:10,440
>> Dakle, još ako je to, ostalo je ovo, i to je uobičajena stvar sam učiniti

451
00:36:10,440 --> 00:36:14,340
gdje, čak i ako je to slučaj u kojem je sve dobro ovdje,

452
00:36:14,340 --> 00:36:22,780
kao niska nikada ne može biti veći od gore, to nije vrijedno razmišljanja o tome da li je to istina.

453
00:36:22,780 --> 00:36:28,010
Tako da se može, kao i reći dok niska je manja od ili jednaka

454
00:36:28,010 --> 00:36:30,720
ili dok niska je manje od

455
00:36:30,720 --> 00:36:35,300
pa ako su ikada jednaka ili niske dogodi proći gore,

456
00:36:35,300 --> 00:36:40,130
onda možemo pobjeći iz ove petlje.

457
00:36:41,410 --> 00:36:44,630
Pitanja, problemi, komentari?

458
00:36:47,080 --> 00:36:49,270
Ok. Ovo izgleda dobro.

459
00:36:49,270 --> 00:36:52,230
Sada želimo učiniti vrsta.

460
00:36:52,230 --> 00:37:04,030
Ako ćemo ići na moj drugi revizije, vidimo iste brojeve,

461
00:37:04,030 --> 00:37:07,550
ali sada više nisu u sortiraju bi.

462
00:37:07,550 --> 00:37:12,840
I mi želimo provesti neku korištenja bilo algoritam u O n log n.

463
00:37:12,840 --> 00:37:17,240
Dakle, koje algoritam ne mislite da bismo trebali provesti ovdje? >> [Student] Spajanje vrsta.

464
00:37:17,240 --> 00:37:23,810
[Bowden] Aha. Spoji vrsta je O (n log n), tako da je ono što ćemo učiniti.

465
00:37:23,810 --> 00:37:26,680
I problem će biti prilično slično,

466
00:37:26,680 --> 00:37:31,920
gdje se lako dade na rekurzivni rješenje.

467
00:37:31,920 --> 00:37:35,580
Mi također može doći do iterativnog rješenja, ako želimo,

468
00:37:35,580 --> 00:37:42,540
ali rekurzije će biti lakše ovdje i mi trebali učiniti rekurzija.

469
00:37:45,120 --> 00:37:49,530
Pretpostavljam da ćemo kroz spajanje sortiraj prvi,

470
00:37:49,530 --> 00:37:54,280
iako je lijep video na spajanje kakve već. [Smijeh]

471
00:37:54,280 --> 00:37:59,780
Dakle spojiti kakve postoje - ja gubit toliko ovoga rada.

472
00:37:59,780 --> 00:38:02,080
Oh, tamo je samo jedan lijevo.

473
00:38:02,080 --> 00:38:03,630
Dakle spojiti.

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

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

476
00:38:29,910 --> 00:38:33,460
Spajanje traje dva odvojena polja.

477
00:38:33,460 --> 00:38:36,780
Pojedinačno ta dva polja su oba razvrstani.

478
00:38:36,780 --> 00:38:40,970
Dakle, ovo polje, 1, 3, 5, sortirati. Ovo polje, 0, 2, 4, sortirati.

479
00:38:40,970 --> 00:38:46,710
Sada ono spajanje treba učiniti je kombinirati ih u jedan niz koji je sama sortiraju.

480
00:38:46,710 --> 00:38:57,130
Dakle, želimo niz veličine 6 koja će imati ove elemente unutar nje

481
00:38:57,130 --> 00:38:59,390
u sortiraju bi.

482
00:38:59,390 --> 00:39:03,390
>> I tako možemo iskoristiti činjenicu da su ta dva polja razvrstanih

483
00:39:03,390 --> 00:39:06,800
to učiniti u linearnom vremenu,

484
00:39:06,800 --> 00:39:13,510
linearni vremenski smisao ako je to polje je veličine x, a to je veličina y,

485
00:39:13,510 --> 00:39:20,970
tada je ukupni algoritam treba biti O (x + y). Ok.

486
00:39:20,970 --> 00:39:23,150
Dakle, prijedlozi.

487
00:39:23,150 --> 00:39:26,030
[Student] Možemo početi s lijeve strane?

488
00:39:26,030 --> 00:39:30,150
Tako ćete staviti 0 dolje, a zatim 1 i onda ovdje ste na dva.

489
00:39:30,150 --> 00:39:33,320
Dakle, to je vrsta kao što imate karticu koja se kreće na desno. >> [Bowden] Aha.

490
00:39:33,320 --> 00:39:41,070
Za oba polja, ako smo samo usredotočiti na lijevom elementa.

491
00:39:41,070 --> 00:39:43,530
Budući da su oba polja razvrstani, znamo da su ove dvije elementi

492
00:39:43,530 --> 00:39:46,920
su najmanji elementi u oba polja.

493
00:39:46,920 --> 00:39:53,500
Dakle, to znači da je jedan od tih dvaju elemenata mora biti najmanji element u našem spojeni niz.

494
00:39:53,500 --> 00:39:58,190
To samo tako dogodi da najmanji je jedan na desnoj ovom trenutku.

495
00:39:58,190 --> 00:40:02,580
Dakle, uzmemo 0, umetnite ga na lijevoj strani, jer je 0 manje od 1,

496
00:40:02,580 --> 00:40:08,210
tako da se 0, umetnite ga u našoj prvoj poziciji, a onda ćemo ažurirati ovaj

497
00:40:08,210 --> 00:40:12,070
do sada usredotočiti na prvi element.

498
00:40:12,070 --> 00:40:14,570
I sada smo ponoviti.

499
00:40:14,570 --> 00:40:20,670
Dakle, sada smo usporediti dva i jedan. 1 je manji, pa ćemo umetnuti jedan.

500
00:40:20,670 --> 00:40:25,300
Mi ažurirati ovu pokazivač ukazati na ovim tipom.

501
00:40:25,300 --> 00:40:33,160
Sada smo to učiniti opet, pa dva. To će se ažurirati, usporedite ove dvije, tri.

502
00:40:33,160 --> 00:40:37,770
Ova ažuriranja, a zatim četiri i pet.

503
00:40:37,770 --> 00:40:42,110
Tako da je spajanje.

504
00:40:42,110 --> 00:40:49,010
>> To bi trebao biti prilično očito da je to linearno vrijeme jer smo samo ići preko svakom elementu jednom.

505
00:40:49,010 --> 00:40:55,980
I to je najveći korak prema provedbi spajanja vrsta je to.

506
00:40:55,980 --> 00:40:59,330
I to nije tako teško.

507
00:40:59,330 --> 00:41:15,020
Prije nekoliko stvari koje treba brinuti je recimo bili smo spajanjem 1, 2, 3, 4, 5, 6.

508
00:41:15,020 --> 00:41:30,930
U tom slučaju možemo završiti u scenariju u kojem je ovo jedna će biti manja,

509
00:41:30,930 --> 00:41:36,160
onda ćemo ažurirati ovaj pokazivač, ovo će biti manji, ažurirati ovaj,

510
00:41:36,160 --> 00:41:41,280
ovaj je manji, a sada morate priznati

511
00:41:41,280 --> 00:41:44,220
kada ste zapravo ponestane elemenata za usporedbu.

512
00:41:44,220 --> 00:41:49,400
Budući da smo već koristili ovaj cijeli niz,

513
00:41:49,400 --> 00:41:55,190
sve na ovom polju sada je samo umetnuta u ovdje.

514
00:41:55,190 --> 00:42:02,040
Dakle, ako mi ikada naiđete na mjestu gdje je jedan od naših polja potpuno je spojio već,

515
00:42:02,040 --> 00:42:06,510
onda mi samo uzeti sve elemente drugog niza i stavite ih na kraju niza.

516
00:42:06,510 --> 00:42:13,630
Dakle, mi samo možemo umetnuti 4, 5, 6. Ok.

517
00:42:13,630 --> 00:42:18,070
To je jedna stvar koju treba paziti.

518
00:42:22,080 --> 00:42:26,120
Implementacija koji bi trebao biti korak 1.

519
00:42:26,120 --> 00:42:32,600
Spoji sortirati onda na temelju toga, to je dva koraka, dva glup koraci.

520
00:42:38,800 --> 00:42:42,090
Ajmo dati ovaj niz.

521
00:42:57,920 --> 00:43:05,680
Dakle spojiti vrsta, korak 1 je rekurzivno razbiti niz na polovice.

522
00:43:05,680 --> 00:43:09,350
Dakle podijeliti ovaj niz na polovice.

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

524
00:43:22,920 --> 00:43:25,800
A sada smo to učiniti opet smo podijeljeni to na polovice.

525
00:43:25,800 --> 00:43:27,530
Jednostavno ću to učiniti na ovoj strani.

526
00:43:27,530 --> 00:43:34,790
Dakle 4, 15 i 16, 50.

527
00:43:34,790 --> 00:43:37,440
Želimo učiniti istu stvar ovdje.

528
00:43:37,440 --> 00:43:40,340
I sada smo ga podijeliti na polovice opet.

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

530
00:43:51,080 --> 00:43:53,170
Tako da je naša baza slučaj.

531
00:43:53,170 --> 00:44:00,540
Nakon što su polja su veličine 1, onda ćemo prestati s podjelom na polovice.

532
00:44:00,540 --> 00:44:03,190
>> Sada što ćemo učiniti s tim?

533
00:44:03,190 --> 00:44:15,730
Mi završiti to će također razbiti u 8, 23, 42, i 108.

534
00:44:15,730 --> 00:44:24,000
Dakle, sada da smo u ovom trenutku, sada korak dva od spajanja kakve samo spajanjem parova na popisima.

535
00:44:24,000 --> 00:44:27,610
Dakle, želimo spajanje tih. Mi samo zovi spojiti.

536
00:44:27,610 --> 00:44:31,410
Znamo pisma će se vratiti ih u sortiraju bi.

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

538
00:44:33,920 --> 00:44:41,440
Sada želimo spojiti njih, i da će se vratiti popis s onima u sortiraju bi,

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

540
00:44:44,160 --> 00:44:57,380
Mi spojiti one - Ja ne mogu pisati - 8, 23 i 42, 108.

541
00:44:57,380 --> 00:45:02,890
Dakle, imamo spojene para odjednom.

542
00:45:02,890 --> 00:45:05,140
Sada mi samo spojiti ponovno.

543
00:45:05,140 --> 00:45:10,130
Primijetite da svaka od tih lista je razvrstani u sebi,

544
00:45:10,130 --> 00:45:15,220
i onda mi samo možemo spojiti ove liste da biste dobili popis veličine 4 koji je sortiran

545
00:45:15,220 --> 00:45:19,990
i spajanje ove dvije liste da biste dobili popis veličine 4 koji je sortiran.

546
00:45:19,990 --> 00:45:25,710
I na kraju, možemo spojiti te dvije liste veličine 4 dobiti jedan popis veličine 8 koji je sortiran.

547
00:45:25,710 --> 00:45:34,030
Dakle, da se vidi da je to ukupna n log n, što smo već vidjeli da pisma je linearna,

548
00:45:34,030 --> 00:45:40,390
pa kad smo koja se bavi spajanjem tih, pa kao ukupni trošak spajanja

549
00:45:40,390 --> 00:45:43,410
za ova dva popisa je samo dva, jer -

550
00:45:43,410 --> 00:45:49,610
Ili dobro, to je O n, ali n ovdje je samo ta dva elementa, tako da je dvoje.

551
00:45:49,610 --> 00:45:52,850
A ovo dvoje će biti dva i to dva će biti dva i to dva će biti 2,

552
00:45:52,850 --> 00:45:58,820
pa preko svih spaja da trebamo učiniti, mi završiti radi n.

553
00:45:58,820 --> 00:46:03,210
Kao 2 + 2 + 2 + 2 8, što je n,

554
00:46:03,210 --> 00:46:08,060
tako da trošak spajanja u ovom setu je n.

555
00:46:08,060 --> 00:46:10,810
I onda ista stvar ovdje.

556
00:46:10,810 --> 00:46:16,980
Mi ćemo spojiti ove dvije, onda ti 2, a pojedinačno je ovo spajanje neće potrajati četiri operacije,

557
00:46:16,980 --> 00:46:23,610
ova pisma će potrajati četiri operacije, ali opet, između svih njih,

558
00:46:23,610 --> 00:46:29,030
smo završili spajanje n ukupno stvari, pa je ovaj korak ima n.

559
00:46:29,030 --> 00:46:33,670
I tako svaki stupanj traje n elemenata se spojili.

560
00:46:33,670 --> 00:46:36,110
>> A koliko razina postoje?

561
00:46:36,110 --> 00:46:40,160
Na svakoj razini, naš niz raste po veličini dva.

562
00:46:40,160 --> 00:46:44,590
Ovdje su naši polja su veličine 1, ovdje su veličine 2, ovdje su veličine 4,

563
00:46:44,590 --> 00:46:46,470
i na kraju, oni veličine 8.

564
00:46:46,470 --> 00:46:56,450
Dakle, budući da je udvostručenje, tu će biti ukupno log n od tih razina.

565
00:46:56,450 --> 00:47:02,090
Dakle, s log n razina, svaka razina pojedinca uzimanje n ukupno poslovanje,

566
00:47:02,090 --> 00:47:05,720
smo dobili n log n algoritam.

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

568
00:47:08,940 --> 00:47:13,320
Jeste ljudi već je napredak na tome kako implementirati ovo?

569
00:47:13,320 --> 00:47:18,260
Je li itko već u stanju u kojem ja mogu samo podići svoj kod?

570
00:47:20,320 --> 00:47:22,260
Ja mogu dati minutu.

571
00:47:24,770 --> 00:47:27,470
Ovaj jedan će biti više.

572
00:47:27,470 --> 00:47:28,730
Ja visoko preporučiti ponavljati -

573
00:47:28,730 --> 00:47:30,510
Vi ne morate učiniti rekurzija za spajanje

574
00:47:30,510 --> 00:47:33,750
jer to rekurzija za spajanje, ti si idući u morati proći hrpu različitih veličina.

575
00:47:33,750 --> 00:47:37,150
Možete, ali to je neugodno.

576
00:47:37,150 --> 00:47:43,720
Ali rekurzije za kakve sama je prilično jednostavan.

577
00:47:43,720 --> 00:47:49,190
Vi samo doslovno nazvati vrsta na lijevoj polovici, sortiranje na desnoj polovici. Ok.

578
00:47:51,770 --> 00:47:54,860
Svatko ima nešto ja mogu podići još?

579
00:47:54,860 --> 00:47:57,540
Inače ću dati minutu.

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

581
00:47:59,900 --> 00:48:02,970
Svatko ima nešto što možemo raditi s?

582
00:48:05,450 --> 00:48:09,680
Inače ćemo samo raditi s ovim, a zatim proširiti od tamo.

583
00:48:09,680 --> 00:48:14,050
>> Svatko ima više od toga da ja mogu podići?

584
00:48:14,050 --> 00:48:17,770
[Student] Aha. Možete podići minu. >> Redu.

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

586
00:48:22,170 --> 00:48:25,280
[Student] Bilo je puno uvjeta. >> Oh, pucati. Može li -

587
00:48:25,280 --> 00:48:28,110
[Student] Moram ga spasiti. >> Da.

588
00:48:32,420 --> 00:48:35,730
Tako smo činio spajanje odvojeno.

589
00:48:35,730 --> 00:48:38,570
Oh, ali to nije tako loše.

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

591
00:48:41,650 --> 00:48:47,080
Dakle, svojevrsna je sama samo zove mergeSortHelp.

592
00:48:47,080 --> 00:48:49,530
Objasnite nam što mergeSortHelp radi.

593
00:48:49,530 --> 00:48:55,700
[Student] MergeSortHelp prilično puno radi na dva glavna koraka,

594
00:48:55,700 --> 00:49:01,270
koja je sortirati svaki polovicu polja, a zatim spojiti oboje.

595
00:49:04,960 --> 00:49:08,050
[Bowden] Ok, tako da će mi dati drugi.

596
00:49:10,850 --> 00:49:13,210
Mislim da je ovo - >> [student] trebam -

597
00:49:17,100 --> 00:49:19,400
Da. Ja sam nešto nedostaje.

598
00:49:19,400 --> 00:49:23,100
U spajanja, shvatio sam da moram stvoriti novi niz

599
00:49:23,100 --> 00:49:26,530
jer ja ne mogu to učiniti na mjestu. >> Da. Vi ne možete. Ispravite.

600
00:49:26,530 --> 00:49:28,170
[Student] Tako sam stvoriti novi niz.

601
00:49:28,170 --> 00:49:31,510
Zaboravio sam na kraju spojiti na ponovno promijeniti.

602
00:49:31,510 --> 00:49:34,490
Ok. Potreban nam je novi niz.

603
00:49:34,490 --> 00:49:41,000
U spajanja vrste, to je gotovo uvijek točno.

604
00:49:41,000 --> 00:49:44,340
Dio troškova boljeg algoritma vrijeme-mudar

605
00:49:44,340 --> 00:49:47,310
je gotovo uvijek trebaju koristiti malo više memorije.

606
00:49:47,310 --> 00:49:51,570
Dakle, ovdje, bez obzira koliko ti spojiti vrsta,

607
00:49:51,570 --> 00:49:54,780
vi bi neizbježno morati koristiti neke dodatne memorije.

608
00:49:54,780 --> 00:49:58,240
On ili ona je stvorio novi niz.

609
00:49:58,240 --> 00:50:03,400
I onda reći na kraju samo trebamo kopirati novi niz u izvornom polju.

610
00:50:03,400 --> 00:50:04,830
[Student] Mislim da je tako, da.

611
00:50:04,830 --> 00:50:08,210
Ja ne znam da li radi u smislu računajući pozivom ili bilo što drugo -

612
00:50:08,210 --> 00:50:11,650
Da, to će raditi. >> [Student] Ok.

613
00:50:20,620 --> 00:50:24,480
Jeste li probati trčanje to? >> [Student] Ne, ne još. >> Ok.

614
00:50:24,480 --> 00:50:28,880
Pokušajte ga izvodi, a onda ću razgovarati o tome za drugi.

615
00:50:28,880 --> 00:50:35,200
[Student] moram imati sve funkcije prototipova i sve, zar ne?

616
00:50:37,640 --> 00:50:40,840
Funkcija prototipovi. Oh, misliš kao - Da.

617
00:50:40,840 --> 00:50:43,040
Sortiraj zove mergeSortHelp.

618
00:50:43,040 --> 00:50:47,390
>> Dakle, kako bi za sortiranje na poziv mergeSortHelp, mergeSortHelp moraju ili su definirane

619
00:50:47,390 --> 00:50:56,370
prije sortiraj ili samo trebamo prototip. Dovoljno je kopirati i zalijepiti da.

620
00:50:56,370 --> 00:50:59,490
I slično, mergeSortHelp zove pisma,

621
00:50:59,490 --> 00:51:03,830
ali pisma nije definirano, pa možemo samo neka mergeSortHelp znati

622
00:51:03,830 --> 00:51:08,700
da to je ono pismo će izgledati, i to je to.

623
00:51:09,950 --> 00:51:15,730
Dakle mergeSortHelp.

624
00:51:22,770 --> 00:51:32,660
Imamo problem ovdje gdje nemamo osnovni slučaj.

625
00:51:32,660 --> 00:51:38,110
MergeSortHelp je rekurzivna, tako da bilo rekurzivna funkcija

626
00:51:38,110 --> 00:51:42,610
će trebati nekakvu bazu slučaju znati kada prestati rekurzivno se poziva.

627
00:51:42,610 --> 00:51:45,590
Što je naša baza slučaj će ovdje biti? Da.

628
00:51:45,590 --> 00:51:49,110
[Student] Ako je veličina jednog? >> [Bowden] Da.

629
00:51:49,110 --> 00:51:56,220
Dakle, kao što smo vidjeli tamo, prestali smo cijepanje polja

630
00:51:56,220 --> 00:52:01,850
kad smo ušli u polja veličine 1, koji su neizbježno se sortiraju.

631
00:52:01,850 --> 00:52:09,530
Dakle, ako veličina jednaka 1, znamo niz već sortiran,

632
00:52:09,530 --> 00:52:12,970
pa mi samo možemo vratiti.

633
00:52:12,970 --> 00:52:16,880
>> Primijetit ćete da je praznina, tako da mi ne vrati ništa posebno, samo smo se vratili.

634
00:52:16,880 --> 00:52:19,580
Ok. Dakle, to je naša baza slučaj.

635
00:52:19,580 --> 00:52:27,440
Pretpostavljam da naš osnovni scenarij bi također mogao biti ako mi se dogoditi da se spajanjem niz veličine 0,

636
00:52:27,440 --> 00:52:30,030
smo vjerojatno želite da se zaustavi u nekom trenutku,

637
00:52:30,030 --> 00:52:33,610
pa mi samo možemo reći veličinu manje od 2 ili manje od ili jednako 1

638
00:52:33,610 --> 00:52:37,150
tako da će to raditi za bilo niz sada.

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

640
00:52:38,870 --> 00:52:42,740
Dakle, to je naša baza slučaj.

641
00:52:42,740 --> 00:52:45,950
Sada ne želite da nas kroz spajanja?

642
00:52:45,950 --> 00:52:49,140
Što svi ti slučajevi znače?

643
00:52:49,140 --> 00:52:54,480
Ovdje gore, mi samo radimo istu ideju, -

644
00:52:56,970 --> 00:53:02,470
[Student] Moram se prolazi veličine sa svim mergeSortHelp pozive.

645
00:53:02,470 --> 00:53:10,080
Dodao sam veličinu kao dodatni primarna i da to ne postoji, kao što su veličina / 2.

646
00:53:10,080 --> 00:53:16,210
[Bowden] Oh, veličina / 2, površina / 2. >> [Student] Da, i također u gore funkciju kao dobro.

647
00:53:16,210 --> 00:53:21,320
[Bowden] Ovdje? >> [Student] Samo veličina. >> [Bowden] Aha. Veličina, veličina? >> [Student] Aha.

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

649
00:53:23,010 --> 00:53:26,580
Dopustite mi da mislim na drugi.

650
00:53:26,580 --> 00:53:28,780
Ne bježimo u pitanju?

651
00:53:28,780 --> 00:53:33,690
Mi smo uvijek liječenju lijevo kao 0. >> [Student] Ne

652
00:53:33,690 --> 00:53:36,340
To je u redu previše. Oprostite. To bi trebao biti početak. Da.

653
00:53:36,340 --> 00:53:39,230
[Bowden] Ok. Sviđa mi se to bolje.

654
00:53:39,230 --> 00:53:43,880
I kraj. Ok.

655
00:53:43,880 --> 00:53:47,200
Dakle, sada želite da nas kroz spajanja? >> [Student] Ok.

656
00:53:47,200 --> 00:53:52,150
Ja sam samo hodanje kroz ovaj novi niz koji sam stvorio.

657
00:53:52,150 --> 00:53:57,420
Njegova veličina je veličina dijela polja da želimo biti razvrstani

658
00:53:57,420 --> 00:54:03,460
i pokušava pronaći element koji sam trebala staviti u novi niz koraka.

659
00:54:03,460 --> 00:54:10,140
Pa za to, prvo sam ček ako lijeva polovica niz nastavlja imati bilo više elemenata,

660
00:54:10,140 --> 00:54:14,260
a ako se to ne dogodi, onda ići dolje na tom drugom stanju, što samo govori

661
00:54:14,260 --> 00:54:20,180
ok, to mora biti u pravom niz, a mi ćemo to staviti u trenutnoj indeksa newArray.

662
00:54:20,180 --> 00:54:27,620
>> A onda na neki drugi način, ja sam ček ako desnoj strani polja također je završio,

663
00:54:27,620 --> 00:54:30,630
u kojem slučaju ja samo staviti u lijevo.

664
00:54:30,630 --> 00:54:34,180
To zapravo ne bi moglo biti potrebno. Nisam siguran.

665
00:54:34,180 --> 00:54:40,970
Ali svejedno, ostale dvije ček koji od dva su manji u lijevo ili desno.

666
00:54:40,970 --> 00:54:49,770
I također u svakom slučaju, ja sam povećavanjem god rezervirano sam povećavati.

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

668
00:54:52,040 --> 00:54:53,840
To izgleda dobro.

669
00:54:53,840 --> 00:54:58,800
Se bilo tko imati komentare ili nedoumica ili pitanja?

670
00:55:00,660 --> 00:55:07,720
Dakle, u četiri slučaja koje moramo donijeti stvari u biti samo - ili to izgleda kao pet -

671
00:55:07,720 --> 00:55:13,100
ali moramo uzeti u obzir da li lijevo polje je ponestalo stvari koje treba spojiti,

672
00:55:13,100 --> 00:55:16,390
li pravo polje je ponestalo stvari moramo spojiti -

673
00:55:16,390 --> 00:55:18,400
Ja sam pokazujući na ništa.

674
00:55:18,400 --> 00:55:21,730
Dakle, da li lijevo polje je ponestalo stvari ili desno polje je ponestalo stvari.

675
00:55:21,730 --> 00:55:24,320
Oni su dva slučaja.

676
00:55:24,320 --> 00:55:30,920
Mi također trebaju trivijalan slučaj li lijevo stvar je manje nego pravu stvar.

677
00:55:30,920 --> 00:55:33,910
Tada želimo izabrati lijevu stvar.

678
00:55:33,910 --> 00:55:37,630
Oni su slučajevi.

679
00:55:37,630 --> 00:55:40,990
Dakle, ovo je pravo, tako da je to.

680
00:55:40,990 --> 00:55:46,760
Array lijevo. To je 1, 2, 3. Ok. Tako da, oni su četiri stvari koje možda želite učiniti.

681
00:55:50,350 --> 00:55:54,510
I nećemo ići preko iterativno rješenje.

682
00:55:54,510 --> 00:55:55,980
Ja ne bih preporučio -

683
00:55:55,980 --> 00:56:03,070
Spoji vrsta je primjer funkcije koja je, kako se ne rep rekurzivna,

684
00:56:03,070 --> 00:56:07,040
to nije lako napraviti to rep rekurzivna,

685
00:56:07,040 --> 00:56:13,450
ali to nije vrlo lako napraviti to iterativan.

686
00:56:13,450 --> 00:56:16,910
To je vrlo jednostavno.

687
00:56:16,910 --> 00:56:19,170
Ova provedba spajanja vrste,

688
00:56:19,170 --> 00:56:22,140
pisama, bez obzira što radite, idete izgraditi spajanje.

689
00:56:22,140 --> 00:56:29,170
>> Dakle spojiti vrsta izgrađen na vrhu spajanja rekurzivno je samo ove tri linije.

690
00:56:29,170 --> 00:56:34,700
Iterativno, to je više neugodno i teže da razmišljaju o tome.

691
00:56:34,700 --> 00:56:41,860
Ali primijetite da to nije rep rekurzivna jer mergeSortHelp - kada sebe naziva -

692
00:56:41,860 --> 00:56:46,590
to još uvijek treba raditi stvari nakon toga rekurzivnih poziva povrataka.

693
00:56:46,590 --> 00:56:50,830
Dakle, ovo okvir stog mora nastaviti postojati čak i nakon pozivanja to.

694
00:56:50,830 --> 00:56:54,170
I onda kada se to nazivamo, okvir stog mora nastaviti postojati

695
00:56:54,170 --> 00:56:57,780
jer čak i nakon tog razgovora, još uvijek je potrebno spojiti.

696
00:56:57,780 --> 00:57:01,920
I to je Netrivijalno da bi ovaj rep rekurzivna.

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

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

699
00:57:09,860 --> 00:57:13,400
Dakle, ide natrag za sortiranje - Oh, postoje dvije stvari koje želim pokazati. Ok.

700
00:57:13,400 --> 00:57:17,840
Vraćajući se vrsta, mi ćemo to učiniti brzo.

701
00:57:17,840 --> 00:57:21,030
Ili traži. Sortiraj? Sortiraj. Da.

702
00:57:21,030 --> 00:57:22,730
Vraćajući se na početke vrste.

703
00:57:22,730 --> 00:57:29,870
Želimo stvoriti algoritam koji sortira array koristeći bilo algoritam

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

705
00:57:33,660 --> 00:57:40,860
Pa kako je to moguće? Se bilo tko imati bilo kakve -

706
00:57:40,860 --> 00:57:44,300
Ja natuknuo prije na -

707
00:57:44,300 --> 00:57:48,300
Ako smo oko poboljšanja od n log n na O od n,

708
00:57:48,300 --> 00:57:51,450
smo poboljšali našu algoritam vrijeme-mudar,

709
00:57:51,450 --> 00:57:55,250
što znači ono što ćemo morati učiniti da bi se za to?

710
00:57:55,250 --> 00:57:59,520
[Student] Space. >> Da. Mi ćemo biti koristeći više prostora.

711
00:57:59,520 --> 00:58:04,490
A nije ni samo više prostora, to je eksponencijalno više prostora.

712
00:58:04,490 --> 00:58:14,320
Dakle, mislim da je ova vrsta algoritma je pseudo nešto, pseudo polinom -

713
00:58:14,320 --> 00:58:18,980
pseudo - ja ne mogu sjetiti. Pseudo nešto.

714
00:58:18,980 --> 00:58:22,210
Ali to je zato što mi je potrebno koristiti toliko prostora

715
00:58:22,210 --> 00:58:28,610
da je to ostvarivo, ali nije realno.

716
00:58:28,610 --> 00:58:31,220
>> I kako smo to postigli?

717
00:58:31,220 --> 00:58:36,810
Možemo postići ako možemo jamčiti da će bilo koji određeni element u niz

718
00:58:36,810 --> 00:58:39,600
je ispod određene veličine.

719
00:58:42,070 --> 00:58:44,500
Dakle, neka je samo reći da je veličina 200,

720
00:58:44,500 --> 00:58:48,130
bilo je element u niz ispod veličine 200.

721
00:58:48,130 --> 00:58:51,080
I to je zapravo vrlo realna.

722
00:58:51,080 --> 00:58:58,660
Možete vrlo lako imati niz da znate sve što je u njemu

723
00:58:58,660 --> 00:59:00,570
će biti manje od nekog broja.

724
00:59:00,570 --> 00:59:07,400
Kao i ako imate neke apsolutno masivan vektor ili nešto

725
00:59:07,400 --> 00:59:11,810
ali znate sve će biti između 0 i 5,

726
00:59:11,810 --> 00:59:14,790
onda će to biti znatno brže to učiniti.

727
00:59:14,790 --> 00:59:17,930
, A vezani na bilo koji od elemenata 5,

728
00:59:17,930 --> 00:59:21,980
pa to bound, to je koliko memorije ti si idući u biti koristeći.

729
00:59:21,980 --> 00:59:26,300
Dakle, vezan je 200.

730
00:59:26,300 --> 00:59:32,960
U teoriji je uvijek vezan jer cijeli može biti samo do 4000000000,

731
00:59:32,960 --> 00:59:40,600
ali to je nerealno jer tada ćemo biti koristeći prostor

732
00:59:40,600 --> 00:59:44,400
po nalogu 4000000000. Tako da je nerealno.

733
00:59:44,400 --> 00:59:47,060
No, ovdje ćemo reći da je naša vezan je 200.

734
00:59:47,060 --> 00:59:59,570
Trik kako to rade u O iz n je možemo napraviti još niz naziva grofovi veličine OBVEZU.

735
00:59:59,570 --> 01:00:10,470
Tako zapravo, to je prečac za - ja zapravo ne znam da li jeka to.

736
01:00:11,150 --> 01:00:15,330
No, u GCC-u najmanju ruku - Žao pretpostavku zveka to čini previše -

737
01:00:15,330 --> 01:00:18,180
to će samo inicijalizirati cijelu lepezu biti 0s.

738
01:00:18,180 --> 01:00:25,320
Dakle, ako ne želim to učiniti, onda sam odvojeno mogao učiniti za (int i = 0;

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

740
01:00:31,500 --> 01:00:35,260
Dakle, sada je sve inicijalizirane na 0.

741
01:00:35,260 --> 01:00:39,570
Ja iteraciju preko moje polje,

742
01:00:39,570 --> 01:00:51,920
i što radim je sam brojanja svake - Idemo ovamo.

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

744
01:00:55,480 --> 01:01:00,010
Što Brojim je broj pojavljivanja svakog od tih elemenata.

745
01:01:00,010 --> 01:01:03,470
Ajmo zapravo dodati par više ovdje s nekim ponavlja.

746
01:01:03,470 --> 01:01:11,070
Dakle, vrijednost imamo ovdje, vrijednost koja će biti niz [i].

747
01:01:11,070 --> 01:01:14,850
Dakle, Val mogao biti 4 ili 8 ili bilo što drugo.

748
01:01:14,850 --> 01:01:18,870
I sada sam računajući koliko te vrijednosti koje sam vidio,

749
01:01:18,870 --> 01:01:21,230
pa broji [val] + +;

750
01:01:21,230 --> 01:01:29,430
Nakon što je to učinio, broji će izgledati nešto poput 0001.

751
01:01:29,430 --> 01:01:42,190
Učinimo broji [val] - OBVEZU + 1.

752
01:01:42,190 --> 01:01:48,230
>> Sada je samo na račun za činjenicu da smo počevši od 0.

753
01:01:48,230 --> 01:01:50,850
Dakle, ako 200 će biti naš najveći broj,

754
01:01:50,850 --> 01:01:54,720
zatim 0-200 je 201 stvari.

755
01:01:54,720 --> 01:02:01,540
Dakle točaka, to će izgledati kao 00.001, jer imamo jedan 4.

756
01:02:01,540 --> 01:02:10,210
Tada ćemo imati 0001 gdje ćemo imati jedan u 8. indeksa računati.

757
01:02:10,210 --> 01:02:14,560
Mi ćemo imati dva u 23. indeksa računati.

758
01:02:14,560 --> 01:02:17,630
Mi ćemo imati dva u 42. indeksa računati.

759
01:02:17,630 --> 01:02:21,670
Dakle, možemo koristiti računati.

760
01:02:34,270 --> 01:02:44,920
Dakle num_of_item = broji [i].

761
01:02:44,920 --> 01:02:52,540
I tako, ako num_of_item je 2, to znači da želimo umetnuti dva broja i.

762
01:02:52,540 --> 01:02:55,290
u našoj sortirani niz.

763
01:02:55,290 --> 01:03:02,000
Dakle, moramo pratiti koliko smo u polju.

764
01:03:02,000 --> 01:03:05,470
Dakle, indeks = 0.

765
01:03:05,470 --> 01:03:09,910
Array - samo ću ga napisati.

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

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

768
01:03:28,580 --> 01:03:32,490
Je li to ono što želim? Mislim da je to ono što ja želim.

769
01:03:35,100 --> 01:03:38,290
Da, to izgleda dobro. Ok.

770
01:03:38,290 --> 01:03:43,050
Dakle, ne svatko razumije ono što je svrha mog broji niz je?

771
01:03:43,050 --> 01:03:48,140
To je računajući broj pojavljivanja svakog od tih brojeva.

772
01:03:48,140 --> 01:03:51,780
Tada sam Ponavljanje preko koje broji niz,

773
01:03:51,780 --> 01:03:57,190
i ith položaj u broji niz

774
01:03:57,190 --> 01:04:01,930
je broj i to bi se trebao pojaviti u mom sortirani niz.

775
01:04:01,930 --> 01:04:06,840
To je razlog zašto grofovi 4 će biti jedan

776
01:04:06,840 --> 01:04:11,840
i grofovi 8 će biti 1, grofovi 23 će biti dva.

777
01:04:11,840 --> 01:04:16,900
Dakle, to je kako su mnogi od njih želim umetnuti u mom sortirani niz.

778
01:04:16,900 --> 01:04:19,200
Onda sam to učiniti.

779
01:04:19,200 --> 01:04:28,960
Ja sam umetanja num_of_item sam je u mojoj sortirani niz.

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

781
01:04:32,460 --> 01:04:43,100
I tako opet, ovo je linearno vrijeme jer smo tek Ponavljanje preko ovaj put,

782
01:04:43,100 --> 01:04:47,470
ali to je također linearno u ono što taj broj se dogoditi da bude,

783
01:04:47,470 --> 01:04:50,730
i tako to jako ovisi o tome što vaš je ograda.

784
01:04:50,730 --> 01:04:53,290
Uz vezan za 200, to nije tako loše.

785
01:04:53,290 --> 01:04:58,330
Ako je vaš vezan će biti 10.000, onda je to malo lošije,

786
01:04:58,330 --> 01:05:01,360
ali ako vaš vezan će biti 4000000000, to je potpuno nerealno

787
01:05:01,360 --> 01:05:07,720
i to polje će morati biti veličine 4 milijarde, što je nerealno.

788
01:05:07,720 --> 01:05:10,860
Dakle, to je to. Pitanja?

789
01:05:10,860 --> 01:05:13,270
[Nečujno učenik odgovor] >> Ok.

790
01:05:13,270 --> 01:05:15,710
Shvatio sam jednu drugu stvar, kada smo bili prolazi kroz.

791
01:05:17,980 --> 01:05:23,720
Mislim da je problem bio u Lucas-a i vjerojatno svi do jednog smo vidjeli.

792
01:05:23,720 --> 01:05:26,330
Bio sam potpuno zaboravio.

793
01:05:26,330 --> 01:05:31,040
Jedino što sam htio komentirati je da kada ste se bave stvarima poput indeksa,

794
01:05:31,040 --> 01:05:38,320
nikad stvarno vidi to kada pišete za petlju,

795
01:05:38,320 --> 01:05:41,120
ali tehnički, kad god se bave tim pokazateljima,

796
01:05:41,120 --> 01:05:45,950
trebali prilično puno uvijek nositi sa nepoznate brojeva.

797
01:05:45,950 --> 01:05:53,850
Razlog za to je kada ste se bave potpisanih brojeva,

798
01:05:53,850 --> 01:05:56,090
pa ako imate dvije potpisane prirodna broja i dodajte ih zajedno

799
01:05:56,090 --> 01:06:00,640
i oni završiti prevelika, onda ćete završiti s negativnim brojem.

800
01:06:00,640 --> 01:06:03,410
Dakle, to je ono što cijeli prelijevati je.

801
01:06:03,410 --> 01:06:10,500
>> Ako sam dodati dvije milijarde i jedne milijarde, ja završiti s negativnim jedne milijarde.

802
01:06:10,500 --> 01:06:15,480
To je kako integeri raditi na računalima.

803
01:06:15,480 --> 01:06:17,510
Dakle, problem s korištenjem -

804
01:06:17,510 --> 01:06:23,500
To je u redu, osim ako niska dogodi da se dvije milijarde i gore dogodi da se 1 milijarda,

805
01:06:23,500 --> 01:06:27,120
onda će to biti negativan jedne milijarde, a onda ćemo podijeliti da dvije

806
01:06:27,120 --> 01:06:29,730
, a završiti s negativnim 500 milijuna.

807
01:06:29,730 --> 01:06:33,760
Dakle, to je samo pitanje, ako vam se dogoditi da se u potrazi kroz niz

808
01:06:33,760 --> 01:06:38,070
od milijarde stvari.

809
01:06:38,070 --> 01:06:44,050
No, ako niska + do dogodi do prelijevanja, onda je to problem.

810
01:06:44,050 --> 01:06:47,750
Čim smo ih nepotpisani, zatim 2000000000 plus 1 milijarde 3000000000.

811
01:06:47,750 --> 01:06:51,960
3000000000 podijeljena dva je 1,5 milijardi eura.

812
01:06:51,960 --> 01:06:55,670
Dakle, čim oni nepotpisani, sve je savršeno.

813
01:06:55,670 --> 01:06:59,900
I tako to je također problem kada pišete vaš za petlje,

814
01:06:59,900 --> 01:07:03,940
i zapravo, vjerojatno to čini automatski.

815
01:07:09,130 --> 01:07:12,330
To će zapravo samo vikati na tebe.

816
01:07:12,330 --> 01:07:21,610
Dakle, ako je taj broj prevelik da se u samo cijeli broj, ali to bi se uklopiti u nepotpisani cijeli,

817
01:07:21,610 --> 01:07:24,970
to će vikati na vas, tako da je razlog zašto se nikada stvarno pokrenuti u pitanju.

818
01:07:29,150 --> 01:07:34,820
Možete vidjeti da je indeks nikada neće biti negativan,

819
01:07:34,820 --> 01:07:39,220
pa kad si Ponavljanje preko polja,

820
01:07:39,220 --> 01:07:43,970
možete gotovo uvijek reći nepotpisani int i, ali ne stvarno morati.

821
01:07:43,970 --> 01:07:47,110
Stvari idu na posao prilično jednako dobro.

822
01:07:48,740 --> 01:07:50,090
Ok. [Šapuće] Što je to vrijeme?

823
01:07:50,090 --> 01:07:54,020
Zadnja stvar koju sam htio pokazati - a ja ću samo to učiniti jako brzo.

824
01:07:54,020 --> 01:08:03,190
Vi znate kako smo # define smo tako da smo # može definirati kao MAX 5 ili nešto?

825
01:08:03,190 --> 01:08:05,940
Nemojmo raditi MAX. # Define OBVEZU kao 200. To je ono što smo učinili prije.

826
01:08:05,940 --> 01:08:10,380
To definira konstantu, koja je upravo će se kopirati i zalijepiti

827
01:08:10,380 --> 01:08:13,010
gdje god mi se dogoditi da napiše OBVEZU.

828
01:08:13,010 --> 01:08:18,189
>> Dakle, mi zapravo može učiniti više s # definira.

829
01:08:18,189 --> 01:08:21,170
Mi # mogu definirati funkcije.

830
01:08:21,170 --> 01:08:23,410
Oni zapravo ne funkcionira, ali mi ćemo ih nazvati funkcije.

831
01:08:23,410 --> 01:08:36,000
Primjer bi bio nešto poput MAX (x, y) je definiran kao (x <y y:? X). Ok.

832
01:08:36,000 --> 01:08:40,660
Dakle, trebali naviknuti na ternarni operatera sintakse,

833
01:08:40,660 --> 01:08:49,029
ali je x manji od y? Povratak y, drugi povratak x.

834
01:08:49,029 --> 01:08:54,390
Tako možete vidjeti što mogu napraviti ovu posebnu funkciju,

835
01:08:54,390 --> 01:09:01,399
i funkcija mogla biti kao bool MAX traje dva argumente, ovo vratiti.

836
01:09:01,399 --> 01:09:08,340
Ovo je jedan od najčešćih one vidim učinio ovako. Zovemo ih makroi.

837
01:09:08,340 --> 01:09:11,790
To je makro.

838
01:09:11,790 --> 01:09:15,859
Ovo je samo sintaksa za to.

839
01:09:15,859 --> 01:09:18,740
Možete pisati makronaredbe raditi što god želite.

840
01:09:18,740 --> 01:09:22,649
Vi često vidjeti makronaredbe za ispravljanje pogrešaka printfs i stvari.

841
01:09:22,649 --> 01:09:29,410
Dakle tipa printf, postoje posebni konstante u C kao donja LINE naglašavaju,

842
01:09:29,410 --> 01:09:31,710
2 podvlači LINE naglašavaju,

843
01:09:31,710 --> 01:09:37,550
a tu je i mislim dva naglašava FUNC. To bi moglo biti to. Nešto poput toga.

844
01:09:37,550 --> 01:09:40,880
Te stvari će biti zamijenjena sa imenom funkcije

845
01:09:40,880 --> 01:09:42,930
ili broj linija koje ste na.

846
01:09:42,930 --> 01:09:48,630
Često ste napisali za ispravljanje pogrešaka printfs da ovdje dolje sam tada mogao samo napisati

847
01:09:48,630 --> 01:09:54,260
Ispravljanje i ona će se ispisati linije broj i funkciju da sam se dogoditi da se u

848
01:09:54,260 --> 01:09:57,020
da je naišao taj Debug izjavu.

849
01:09:57,020 --> 01:09:59,550
A također možete ispisati druge stvari.

850
01:09:59,550 --> 01:10:05,990
Dakle, jedna stvar koju treba paziti je ako sam se dogoditi da # define DOUBLE_MAX

851
01:10:05,990 --> 01:10:11,380
kao nešto poput 2 * y i 2 * x.

852
01:10:11,380 --> 01:10:14,310
Dakle, za bilo kojeg razloga, možete se dogoditi da to puno.

853
01:10:14,310 --> 01:10:16,650
Dakle, čine ga makro.

854
01:10:16,650 --> 01:10:18,680
To je zapravo slomljena.

855
01:10:18,680 --> 01:10:23,050
Ja bih ga nazvati po nešto nalik DOUBLE_MAX (3, 6).

856
01:10:23,050 --> 01:10:27,530
Pa što bi trebao biti vraćen?

857
01:10:28,840 --> 01:10:30,580
[Student] 12.

858
01:10:30,580 --> 01:10:34,800
Da, 12 bi trebalo biti vraćeno, a 12 se vratio.

859
01:10:34,800 --> 01:10:43,350
3 dobiva zamijeniti za x, 6 dobiva zamijeniti za y, a mi vratiti 2 * 6, koji je 12.

860
01:10:43,350 --> 01:10:47,710
Sada ono što o tome? Što treba vratiti?

861
01:10:47,710 --> 01:10:50,330
[Student] 14. >> Idealnom slučaju, 14.

862
01:10:50,330 --> 01:10:55,290
Pitanje je da kako hash definira rad, sjetite se da je doslovni kopirati i zalijepiti

863
01:10:55,290 --> 01:11:00,160
od ljepušan velik dio sve, tako što će se to može tumačiti kao

864
01:11:00,160 --> 01:11:11,270
je 3 manje od jedan plus šest, dva puta jedan plus šest, dva puta tri.

865
01:11:11,270 --> 01:11:19,780
>> Dakle, iz tog razloga što je gotovo uvijek završiti sve što je u zagradama.

866
01:11:22,180 --> 01:11:25,050
Svaka varijabla ste gotovo uvijek završiti u zagradama.

867
01:11:25,050 --> 01:11:29,570
Postoje slučajevi gdje se ne moraju, kao što znam da ne trebam učiniti da se ovdje

868
01:11:29,570 --> 01:11:32,110
jer manje nego što je prilično puno uvijek samo ide na posao,

869
01:11:32,110 --> 01:11:34,330
iako to nije ni moglo biti istina.

870
01:11:34,330 --> 01:11:41,870
Ako postoji nešto smiješno kao DOUBLE_MAX (1 == 2),

871
01:11:41,870 --> 01:11:49,760
tada će se zamijeniti s tri manje od 1 jednaka jednaka 2,

872
01:11:49,760 --> 01:11:53,460
pa onda će to učiniti tri manje od jedan, ne da jednaka 2,

873
01:11:53,460 --> 01:11:55,620
koji nije ono što želimo.

874
01:11:55,620 --> 01:12:00,730
Dakle, kako bi se spriječilo bilo operatera prednost problema,

875
01:12:00,730 --> 01:12:02,870
Uvijek zamotajte u zagradama.

876
01:12:03,290 --> 01:12:07,700
Ok. I to je to, 5:30.

877
01:12:08,140 --> 01:12:12,470
Ako imate bilo kakvih pitanja o pset, javite nam.

878
01:12:12,470 --> 01:12:18,010
To bi trebao biti zabavno, a haker izdanje također je puno realnija

879
01:12:18,010 --> 01:12:22,980
od hakera izdanju prošle godine, pa se nadamo da puno od vas to probati.

880
01:12:22,980 --> 01:12:26,460
Prošle godine je bila vrlo velika.

881
01:12:28,370 --> 01:12:30,000
>> [CS50.TV]