1
00:00:00,000 --> 00:00:02,570
[Powered by Google Translate] [Secțiunea 3 - mai confortabil]

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

3
00:00:05,070 --> 00:00:07,310
>> [Acest lucru este CS50. - CS50.TV]

4
00:00:07,310 --> 00:00:12,700
>> Deci, prima întrebare este formulată ciudat.

5
00:00:12,700 --> 00:00:17,480
GDB vă permite să vă "debug" un program, dar, mai ales, ceea ce nu-l lăsa să faci?

6
00:00:17,480 --> 00:00:22,590
Voi răspunde că, și nu știu exact ce se așteaptă,

7
00:00:22,590 --> 00:00:27,910
așa că eu sunt ghicitul că e ceva de-a lungul liniilor de aceasta vă permite să pas cu pas

8
00:00:27,910 --> 00:00:31,540
plimbare prin programul, interacționează cu ea, variabilele de schimbare, fac toate aceste lucruri -

9
00:00:31,540 --> 00:00:34,270
practic control complet asupra execuției unui program

10
00:00:34,270 --> 00:00:38,410
și de a inspecta orice parte dat de execuție a programului.

11
00:00:38,410 --> 00:00:43,030
Deci, aceste caracteristici vă permit să depanați lucrurile.

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

13
00:00:44,830 --> 00:00:50,520
De ce căutarea binară impune ca o matrice să fie sortate?

14
00:00:50,520 --> 00:00:53,360
Cine vrea să răspund la asta?

15
00:00:56,120 --> 00:01:00,070
[Elev] Pentru că nu funcționează dacă nu este sortat. Da >>. [Râsete]

16
00:01:00,070 --> 00:01:04,910
În cazul în care nu este sortat, atunci este imposibil să-l împartă în jumătate

17
00:01:04,910 --> 00:01:07,850
și știu că totul este mai puțin stânga și la dreapta totul

18
00:01:07,850 --> 00:01:10,490
este mai mare decât valoarea de mijloc.

19
00:01:10,490 --> 00:01:12,790
Deci, aceasta trebuie să fie sortate.

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

21
00:01:14,170 --> 00:01:17,570
De ce este un fel de balon în O pătrat de n?

22
00:01:17,570 --> 00:01:23,230
Vrea cineva primul care îi lasă o foarte rapid la nivel înalt imagine de ansamblu a ceea ce fel bubble este?

23
00:01:25,950 --> 00:01:33,020
[Elev] Tu du-te în principal prin fiecare element și să verificați elemente primele câteva.

24
00:01:33,020 --> 00:01:37,150
Daca nu mai au de unde le-ai schimba, atunci verificați următoarele elemente puține și așa mai departe.

25
00:01:37,150 --> 00:01:40,770
Atunci când ajunge la sfârșitul anului, atunci știi că cel mai mare element este plasat la sfârșitul anului,

26
00:01:40,770 --> 00:01:42,750
astfel încât să ignore că unul, atunci vă păstrați pe trece prin,

27
00:01:42,750 --> 00:01:48,490
și de fiecare dată când trebuie să verificați un element mai puțin, până când nu va aduce modificări. Da >>.

28
00:01:48,490 --> 00:01:58,470
Se numește fel balon pentru că dacă întoarceți matrice pe partea sa, astfel că este în sus și în jos, pe verticală,

29
00:01:58,470 --> 00:02:03,100
apoi valorile mari se va scufunda pe fundul și valorile mici vor bule până la partea de sus.

30
00:02:03,100 --> 00:02:05,210
Asta e modul în care aceasta a primit numele său.

31
00:02:05,210 --> 00:02:08,220
Și da, du-te doar prin.

32
00:02:08,220 --> 00:02:11,190
Tu continui sa mergi prin matrice, schimbarea valoarea mai mare

33
00:02:11,190 --> 00:02:14,040
pentru a obține cele mai mari valori la partea de jos.

34
00:02:14,040 --> 00:02:17,500
>> De ce este O pătrat de n?

35
00:02:18,690 --> 00:02:24,620
În primul rând, nimeni nu vrea să spună ce e de n pătrat O?

36
00:02:24,620 --> 00:02:28,760
[Elev] Deoarece pentru fiecare termen merge de n ori.

37
00:02:28,760 --> 00:02:32,100
Puteți fi siguri că ați luat cea mai mare elementul tot drumul în jos,

38
00:02:32,100 --> 00:02:35,230
atunci va trebui să repet faptul că pentru cât mai multe elemente. Da >>.

39
00:02:35,230 --> 00:02:41,800
Deci, tineti minte ceea ce înseamnă mare O, și ce înseamnă mari Omega.

40
00:02:41,800 --> 00:02:50,560
O mare este ca superioară cu privire la modul lent se poate rula, de fapt.

41
00:02:50,560 --> 00:02:58,990
Deci, prin a spune o Este de pătrat n, nu este de n O altfel ar fi capabil să ruleze

42
00:02:58,990 --> 00:03:02,640
în timp liniar, dar este de n O tocata

43
00:03:02,640 --> 00:03:06,390
deoarece este delimitată de O n cub de.

44
00:03:06,390 --> 00:03:12,300
În cazul în care este delimitată de O din pătrat n, atunci este delimitată, de asemenea, de n tocata.

45
00:03:12,300 --> 00:03:20,280
Deci, este n pătrat, iar în cel mai rău caz, absolut nu se poate face mai bine decât pătrat n,

46
00:03:20,280 --> 00:03:22,830
care este de ce este O de n pătrat.

47
00:03:22,830 --> 00:03:31,200
Deci, pentru a vedea matematica ușoară la cum se face a fi n pătrat,

48
00:03:31,200 --> 00:03:40,530
dacă avem cinci lucruri în lista noastră, prima dată cât de multe am putea swap potential nevoie pentru a face

49
00:03:40,530 --> 00:03:47,170
, în scopul de a obține acest lucru? Să fapt doar -

50
00:03:47,170 --> 00:03:52,040
Câte swap-uri vom avea de a face, în primul tur al bulei fel prin matrice?

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

52
00:03:53,540 --> 00:03:58,340
>> Dacă există 5 elemente, vom avea nevoie de a face n - 1.

53
00:03:58,340 --> 00:04:01,100
Apoi, pe cea de a doua câte swap vom avea de a face?

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

55
00:04:03,440 --> 00:04:11,640
Iar al treilea va fi n - 3, iar apoi pentru comfortul voi scrie ultimele două

56
00:04:11,640 --> 00:04:15,270
ca si atunci vom avea nevoie de a face operațiunile de swap 2 și 1 de swap.

57
00:04:15,270 --> 00:04:19,899
Cred că ultima poate sau nu poate nevoie de fapt să se întâmple.

58
00:04:19,899 --> 00:04:22,820
Este un swap? Nu știu.

59
00:04:22,820 --> 00:04:26,490
Deci, acestea sunt valorile totale ale swap-urilor sau cel puțin comparații pe care trebuie să o facă.

60
00:04:26,490 --> 00:04:29,910
Chiar dacă nu schimbați, tot trebuie să compare valorile.

61
00:04:29,910 --> 00:04:33,910
Deci, există n - 1 comparații în primul tur prin matrice.

62
00:04:33,910 --> 00:04:42,050
Daca aranjati aceste lucruri, să facem de fapt sase lucruri atât de lucruri se adune frumos,

63
00:04:42,050 --> 00:04:44,790
si apoi voi face 3, 2, 1.

64
00:04:44,790 --> 00:04:49,910
Deci, reamenajarea doar aceste sume, vrem să vedem cât de multe comparații facem

65
00:04:49,910 --> 00:04:52,700
în algoritmul intreaga.

66
00:04:52,700 --> 00:04:56,550
Deci, dacă aducem pe tipii ăștia aici,

67
00:04:56,550 --> 00:05:07,470
atunci suntem încă însumând doar comparatii cu toate acestea au existat mai multe.

68
00:05:07,470 --> 00:05:13,280
Dar dacă ne rezuma acestea și am rezuma acestea și însumăm acestea,

69
00:05:13,280 --> 00:05:18,130
e încă aceeași problemă. Noi rezuma doar acele grupuri particulare.

70
00:05:18,130 --> 00:05:22,400
>> Deci, acum suntem însumând 3 a lui n. Nu este vorba doar 3 N lui.

71
00:05:22,400 --> 00:05:27,650
Este întotdeauna o să fie n / 2 n lui.

72
00:05:27,650 --> 00:05:29,430
Deci, aici se întâmplă să avem 6.

73
00:05:29,430 --> 00:05:34,830
Dacă am avea 10 lucruri, atunci am putea face acest lucru grupare pentru 5 perechi diferite de lucruri

74
00:05:34,830 --> 00:05:37,180
și se încheie cu n + n + n + n + n.

75
00:05:37,180 --> 00:05:45,840
Deci, tu ești mergi la a lua mereu n / 2 n lui, și astfel aceasta ne vom jot pentru a pătrat n / 2.

76
00:05:45,840 --> 00:05:48,890
Și așa, chiar dacă e factor de jumătate, care se întâmplă să vină în

77
00:05:48,890 --> 00:05:54,190
din cauza faptului că, prin fiecare iterație peste matrice am compara 1 mai puțin

78
00:05:54,190 --> 00:05:58,040
asa ca asta e modul în care vom ajunge peste 2, dar este încă n pătrat.

79
00:05:58,040 --> 00:06:01,650
Noi nu le pasă de factor constant de o jumătate.

80
00:06:01,650 --> 00:06:07,760
Deci, o mulțime de lucruri mari O astfel se bazează pe doar un fel de a face acest tip de matematica,

81
00:06:07,760 --> 00:06:12,260
faci sume aritmetice si alte chestii serie geometrică,

82
00:06:12,260 --> 00:06:17,750
dar cele mai multe dintre ele în acest curs sunt destul de simple.

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

84
00:06:19,290 --> 00:06:24,430
De ce este un fel de inserție în Omega de n? Ce înseamnă omega înseamnă?

85
00:06:24,430 --> 00:06:27,730
[Doi studenți vorbind la o dată - neinteligibile] >> Da.

86
00:06:27,730 --> 00:06:30,630
Omega vă puteți gândi ca limita inferioară.

87
00:06:30,630 --> 00:06:36,550
>> Deci, indiferent de cât de eficient algoritm de sortare ta de inserare este,

88
00:06:36,550 --> 00:06:41,810
indiferent de lista care a trecut, în, ea are întotdeauna să compare cel puțin n lucrurile

89
00:06:41,810 --> 00:06:44,620
sau trebuie să itera peste lucrurile n.

90
00:06:44,620 --> 00:06:47,280
De ce este asta?

91
00:06:47,280 --> 00:06:51,190
[Elev] Pentru că, dacă lista este deja sortate, apoi prin prima iterație

92
00:06:51,190 --> 00:06:54,080
vă poate garanta că numai elementul prima este cel,

93
00:06:54,080 --> 00:06:56,490
și a doua iterație se poate garanta doar primele două sunt

94
00:06:56,490 --> 00:07:00,010
pentru că nu știi că restul Lista este sortata. Da >>.

95
00:07:00,010 --> 00:07:08,910
Dacă treci într-o listă sortată complet, cel puțin trebuie să te duci peste toate elementele

96
00:07:08,910 --> 00:07:12,180
pentru a vedea că nimic nu trebuie să fie mutate.

97
00:07:12,180 --> 00:07:14,720
Deci, trecerea listă și spunând oh, acest lucru este deja sortat,

98
00:07:14,720 --> 00:07:18,240
este imposibil pentru tine să știi că e sortati până când verificați fiecare element de

99
00:07:18,240 --> 00:07:20,660
pentru a vedea că acestea sunt sortate în ordine.

100
00:07:20,660 --> 00:07:25,290
Deci, limita inferioară la fel de inserare este de n Omega.

101
00:07:25,290 --> 00:07:28,210
Ce se mai rău caz de funcționare timp de sortare îmbinare,

102
00:07:28,210 --> 00:07:31,390
cel mai grav caz fiind O mari din nou?

103
00:07:31,390 --> 00:07:37,660
Deci, în cel mai rău caz, cum se sortează de îmbinare a rula?

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

105
00:07:43,690 --> 00:07:49,990
Cele mai rapide algoritmi generali de sortare sunt n log n. Nu poti sa faci mai bine.

106
00:07:51,930 --> 00:07:55,130
>> Există cazuri speciale, și dacă avem timp de astăzi -, dar noi won't probabil -

107
00:07:55,130 --> 00:07:59,330
am putut vedea unul care face mai bine decât n log n.

108
00:07:59,330 --> 00:08:04,050
Dar, în cazul general, nu puteți face mai bine decât n log n.

109
00:08:04,050 --> 00:08:09,680
Și îmbinarea fel se întâmplă să fie cel pe care îl trebuie să știți pentru acest curs, care este n log n.

110
00:08:09,680 --> 00:08:13,260
Și așa vom fi de fapt de punere în aplicare ca astazi.

111
00:08:13,260 --> 00:08:18,070
Și, în sfârșit, în nu mai mult de trei fraze, cum se sortează de selecție?

112
00:08:18,070 --> 00:08:20,370
Are cineva vrea să răspundă, iar eu voi conta Exemple de dvs.

113
00:08:20,370 --> 00:08:22,390
pentru că dacă te duci peste 3 -

114
00:08:25,530 --> 00:08:28,330
Are cineva aminte de sortare de selecție?

115
00:08:31,280 --> 00:08:37,809
Sortare de selecție este, de obicei, destul de ușor să vă amintiți doar de nume.

116
00:08:37,809 --> 00:08:45,350
Ai repeta doar peste matrice, găsiți oricare ar fi cea mai mare valoare este mai mică sau -

117
00:08:45,350 --> 00:08:47,290
orice ordine ai de sortare inch

118
00:08:47,290 --> 00:08:50,750
Deci, haideți să spunem suntem de sortare de la cel mai mic la cel mai mare.

119
00:08:50,750 --> 00:08:55,250
Ai itera peste matrice, căutați pentru orice elementul minim este,

120
00:08:55,250 --> 00:08:59,750
selectați-l, și apoi schimbați doar ceea ce este în primul rând.

121
00:08:59,750 --> 00:09:04,090
Și apoi pe a doua trecere peste matrice, căutați elementul minim din nou,

122
00:09:04,090 --> 00:09:07,490
selectați-l, apoi schimbați-l cu ceea ce este în poziția a doua.

123
00:09:07,490 --> 00:09:10,650
Deci, noi suntem doar cules și alegerea valorilor minime

124
00:09:10,650 --> 00:09:16,050
și introducerea lor în partea din față a matrice până când acesta este sortat.

125
00:09:19,210 --> 00:09:21,560
Întrebări cu privire la asta?

126
00:09:21,560 --> 00:09:25,710
>> Acestea apar în mod inevitabil la formularele pe care trebuie să completați atunci când sunteți trimiterea PSET.

127
00:09:29,010 --> 00:09:32,360
Acestea sunt practic răspunsuri la cele.

128
00:09:32,360 --> 00:09:34,230
Ok, deci acum codificare probleme.

129
00:09:34,230 --> 00:09:40,140
Am deja trimis prin e-mail - Nu pe nimeni aia e-mail? Bine.

130
00:09:40,140 --> 00:09:46,630
Am deja trimis prin e-mail spațiul pe care vom folosi,

131
00:09:46,630 --> 00:09:52,120
și dacă faceți clic pe numele meu - deci cred ca am de gând să fie în partea de jos

132
00:09:52,120 --> 00:09:57,170
din cauza r spate - dar dacă faceți clic pe numele meu vei vedea 2 revizii.

133
00:09:57,170 --> 00:10:02,650
Revizia 1 va fi deja am copiat și inserat codul în spațiile

134
00:10:02,650 --> 00:10:06,900
pentru lucrul căutare ai de gând să trebuie să pună în aplicare.

135
00:10:06,900 --> 00:10:10,540
Și Revizie 2 va fi lucrul pe care punem în aplicare un fel după aceea.

136
00:10:10,540 --> 00:10:15,770
Deci, puteți să faceți clic pe Revizuirea mea 1 și de a lucra de acolo.

137
00:10:17,350 --> 00:10:22,060
Și acum vrem să pună în aplicare cautare binara.

138
00:10:22,060 --> 00:10:26,470
>> Vrea cineva să dau doar un pseudocod nivel înalt explicația

139
00:10:26,470 --> 00:10:31,440
din ceea ce am de gând să aibă de a face pentru căutare? Da.

140
00:10:31,440 --> 00:10:36,170
[Elev] Tu iei doar mijlocul de matrice și de a vedea dacă ceea ce căutați pentru

141
00:10:36,170 --> 00:10:38,650
este mai mică decât cea sau mai mult decât atât.

142
00:10:38,650 --> 00:10:41,080
Și dacă e mai putin, te duci la jumătate mai puțin,

143
00:10:41,080 --> 00:10:44,750
si daca e mai mult, te duci la jumătate e mai mult și să repeți până când veți obține doar un singur lucru.

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

145
00:10:46,570 --> 00:10:51,320
Observați că numerele noastre de matrice este deja sortat,

146
00:10:51,320 --> 00:10:57,190
și astfel acest lucru înseamnă că putem profita de acest lucru și am putea verifica în primul rând,

147
00:10:57,190 --> 00:11:00,390
ok, caut numărul 50.

148
00:11:00,390 --> 00:11:03,720
Deci, eu pot merge în mijloc.

149
00:11:03,720 --> 00:11:07,380
Mijlociu este greu de definit, atunci când este un număr par de lucruri,

150
00:11:07,380 --> 00:11:10,820
dar hai să spunem că vom trunchia mereu la mijloc.

151
00:11:10,820 --> 00:11:14,420
Deci, aici avem 8 lucruri, astfel încât mijloc ar fi 16.

152
00:11:14,420 --> 00:11:17,330
Caut 50, deci 50 este mai mare de 16.

153
00:11:17,330 --> 00:11:21,310
Asa ca acum pot trata practic matrice mea ca aceste elemente.

154
00:11:21,310 --> 00:11:23,450
Pot să arunc totul, de la 16 de peste.

155
00:11:23,450 --> 00:11:27,440
Acum matrice mea este doar aceste 4 elemente, și repet.

156
00:11:27,440 --> 00:11:31,910
Deci, atunci vreau să găsesc mijlocul din nou, care va fi 42.

157
00:11:31,910 --> 00:11:34,730
42 este mai mică de 50, așa că am putea arunca departe aceste două elemente.

158
00:11:34,730 --> 00:11:36,890
Aceasta este matrice mea rămasă.

159
00:11:36,890 --> 00:11:38,430
Am de gând să găsească mijloc din nou.

160
00:11:38,430 --> 00:11:42,100
Cred că 50 a fost un exemplu rău pentru că am fost mereu arunci lucrurile la stânga,

161
00:11:42,100 --> 00:11:48,280
dar de aceeași măsură, în cazul în care caut ceva

162
00:11:48,280 --> 00:11:52,100
și e mai puțin decât elementul mă caută în prezent,

163
00:11:52,100 --> 00:11:55,080
apoi m-am de gând să arunce totul pentru dreapta.

164
00:11:55,080 --> 00:11:58,150
Deci, acum avem nevoie de a pune în aplicare acest lucru.

165
00:11:58,150 --> 00:12:02,310
Observați că avem nevoie să treacă în dimensiune.

166
00:12:02,310 --> 00:12:06,730
Noi nu putem, de asemenea, nevoie pentru a hard-cod dimensiune.

167
00:12:06,730 --> 00:12:11,640
Deci, dacă vom scăpa de faptul că define # -

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

169
00:12:21,430 --> 00:12:27,180
Cum pot da seama ce frumos dimensiunea matrice numere prezent este?

170
00:12:27,180 --> 00:12:30,950
>> Câte elemente sunt în număr de matrice?

171
00:12:30,950 --> 00:12:33,630
[] Studențești numere, console,. Lungime?

172
00:12:33,630 --> 00:12:36,600
[Bowden] care nu există în C.

173
00:12:36,600 --> 00:12:38,580
Nevoie. Lungime.

174
00:12:38,580 --> 00:12:42,010
Matricele nu au proprietăți, astfel încât nu există nici o proprietate lungime de matrice

175
00:12:42,010 --> 00:12:45,650
care vă va oferi doar tu oricât de mult se întâmplă să fie.

176
00:12:48,180 --> 00:12:51,620
[Elev] A se vedea cât de mult de memorie are și împartă de cât de mult - >> Da.

177
00:12:51,620 --> 00:12:55,810
Deci, cum putem vedea câtă memorie are? >> [Elev] sizeof. Da >>, sizeof.

178
00:12:55,810 --> 00:13:01,680
Sizeof este operatorul care va reveni dimensiunea matrice de numere.

179
00:13:01,680 --> 00:13:10,060
Și asta va fi intregi toate acestea, de multe ori, există dimensiunea de un număr întreg

180
00:13:10,060 --> 00:13:14,050
din moment ce e cât de mult de memorie este de fapt inițierea.

181
00:13:14,050 --> 00:13:17,630
Deci, dacă vreau număr de lucruri în matrice,

182
00:13:17,630 --> 00:13:20,560
apoi m-am de gând să doriți să împartă cu dimensiunea de un număr întreg.

183
00:13:22,820 --> 00:13:26,010
Bine. Așa că lasă-mă să trec în mărime aici.

184
00:13:26,010 --> 00:13:29,430
De ce am nevoie pentru a trece în dimensiune, la toate?

185
00:13:29,430 --> 00:13:38,570
De ce nu pot doar să fac aici dimensiunea int = sizeof (carul cu fân) / sizeof (int)?

186
00:13:38,570 --> 00:13:41,490
De ce nu funcționează asta?

187
00:13:41,490 --> 00:13:44,470
[Elev] Nu este o variabilă globală.

188
00:13:44,470 --> 00:13:51,540
Haystack [Bowden] există și ne trece în număr cât carul cu fân,

189
00:13:51,540 --> 00:13:54,700
și aceasta este un fel de prefigurare a ceea ce va urma. Da.

190
00:13:54,700 --> 00:14:00,170
[Elev] Haystack este doar referire la ea, așa că va reveni cât de mare este această trimitere.

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

192
00:14:02,150 --> 00:14:09,000
Mă îndoiesc în curs pe care le-ați văzut încă stivă într-adevăr, nu?

193
00:14:09,000 --> 00:14:11,270
Tocmai am vorbit despre asta.

194
00:14:11,270 --> 00:14:16,090
Deci, în cazul în care toate stiva este de variabile dvs. vor fi stocate.

195
00:14:16,090 --> 00:14:19,960
>> Orice memorie care este alocată pentru variabilele locale se întâmplă în stivă,

196
00:14:19,960 --> 00:14:24,790
și fiecare funcție devine propriul spațiu pe stivă, cadrul său stiva proprie este ceea ce se numește.

197
00:14:24,790 --> 00:14:31,590
Deci principal are rama stiva, și în interiorul acestuia este de gând să existe această matrice numere,

198
00:14:31,590 --> 00:14:34,270
și o să fie de mărime sizeof (numere).

199
00:14:34,270 --> 00:14:38,180
Se va avea dimensiunea de numere separate de o mărime de elemente,

200
00:14:38,180 --> 00:14:42,010
dar faptul că toate viețile în interiorul cadrului stiva principal.

201
00:14:42,010 --> 00:14:45,190
Când ne-am numi căutare, căutarea devine cadrul acestuia stivă proprie,

202
00:14:45,190 --> 00:14:48,840
propriul spațiu pentru a stoca toate variabilele sale locale.

203
00:14:48,840 --> 00:14:56,420
Dar aceste argumente - deci carul cu fân nu este o copie a acestui tablou întreg.

204
00:14:56,420 --> 00:15:00,990
Noi nu trec în întreaga matrice ca o copie în căutare.

205
00:15:00,990 --> 00:15:04,030
Ea trece doar o trimitere la matrice.

206
00:15:04,030 --> 00:15:11,470
Deci, de căutare pot accesa aceste numere prin acest referință.

207
00:15:11,470 --> 00:15:17,100
Este accesarea încă lucrurile care traiesc in interiorul cadrului principal pentru stivă,

208
00:15:17,100 --> 00:15:22,990
dar în esență, când vom ajunge la pointeri, care ar trebui să fie în curând,

209
00:15:22,990 --> 00:15:24,980
aceasta este ceea ce sunt indicii.

210
00:15:24,980 --> 00:15:29,400
Pointeri sunt doar referiri la lucruri, și puteți utiliza indicii pentru a accesa lucruri

211
00:15:29,400 --> 00:15:32,030
care sunt în cadre stack alte lucruri ".

212
00:15:32,030 --> 00:15:37,660
Deci, chiar dacă numere este local principal, putem accesa încă o prin acest indicator.

213
00:15:37,660 --> 00:15:41,770
Dar din moment ce e doar un pointer si e doar o referință,

214
00:15:41,770 --> 00:15:45,040
sizeof (carul cu fân) returnează doar mărimea de referință în sine.

215
00:15:45,040 --> 00:15:47,950
Ea nu se întoarce dimensiunea lucru este îndreptat spre.

216
00:15:47,950 --> 00:15:51,110
Ea nu se întoarce dimensiunea reală a numerelor.

217
00:15:51,110 --> 00:15:55,660
Și astfel acest lucru nu este de gând să lucreze ca vrem sa-l.

218
00:15:55,660 --> 00:15:57,320
>> Întrebări cu privire la asta?

219
00:15:57,320 --> 00:16:03,250
Pointeri va fi plecat în mod semnificativ mai mult în detaliu gory, în săptămânile care vor urma.

220
00:16:06,750 --> 00:16:13,740
Și acesta este motivul pentru care o mulțime de lucruri pe care le vedeți, cele mai multe lucruri de căutare sau de sortare lucruri,

221
00:16:13,740 --> 00:16:16,990
ei aproape toate de gând să nevoie pentru a lua dimensiunea reală a matrice,

222
00:16:16,990 --> 00:16:20,440
deoarece în C, nu avem nici o idee despre ce dimensiunea matrice este.

223
00:16:20,440 --> 00:16:22,720
Ai nevoie să treci manual inch

224
00:16:22,720 --> 00:16:27,190
Și nu poți trece manual în întreaga matrice pentru ca esti doar in trecere în referință

225
00:16:27,190 --> 00:16:30,390
și nu poate obține dimensiunea de referință.

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

227
00:16:32,300 --> 00:16:38,160
Deci, acum vrem să pună în aplicare ceea ce a fost explicat mai înainte.

228
00:16:38,160 --> 00:16:41,530
Puteți lucra pe el pentru un minut,

229
00:16:41,530 --> 00:16:45,250
și nu trebuie să vă faceți griji despre obținerea totul perfect 100% de lucru.

230
00:16:45,250 --> 00:16:51,410
Doar scrie până pseudocod jumătate pentru modul în care credeți că ar trebui să funcționeze.

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

232
00:16:53,630 --> 00:16:56,350
Nu este nevoie să fie complet terminat cu asta încă.

233
00:16:56,350 --> 00:17:02,380
Dar nimeni nu se simt confortabil cu ceea ce au până în prezent,

234
00:17:02,380 --> 00:17:05,599
ca ceva putem lucra împreună?

235
00:17:05,599 --> 00:17:09,690
Vrea cineva să se ofere voluntari? Sau voi alege la întâmplare.

236
00:17:12,680 --> 00:17:18,599
Aceasta nu trebuie să fie dreptul de orice măsură, dar ceva ce putem modifica într-o stare de lucru.

237
00:17:18,599 --> 00:17:20,720
[Elev] Sigur. Bine >>.

238
00:17:20,720 --> 00:17:27,220
Deci, nu te poate salva de revizuire făcând clic pe pictograma mica Salvare.

239
00:17:27,220 --> 00:17:29,950
Ești Ramya, nu? >> [Elev] Da. >> [Bowden] Ok.

240
00:17:29,950 --> 00:17:35,140
Asa ca acum pot vedea revizuire dvs. și toată lumea poate trage în sus de revizuire.

241
00:17:35,140 --> 00:17:38,600
Și aici avem - Ok.

242
00:17:38,600 --> 00:17:43,160
Deci, sa dus cu Ramya soluție recursivă, care este cu siguranta o soluție valabilă.

243
00:17:43,160 --> 00:17:44,970
Există două moduri în care puteți face aceasta problema.

244
00:17:44,970 --> 00:17:48,060
Puteți face, fie ea iterativ sau recursiv.

245
00:17:48,060 --> 00:17:53,860
Cele mai multe probleme pe care le întâmpină, care se poate face recursiv poate fi, de asemenea, face iterativ.

246
00:17:53,860 --> 00:17:58,510
Deci, aici l-am făcut recursiv.

247
00:17:58,510 --> 00:18:03,730
>> Are cineva vrea să definească ce înseamnă să facă o funcție recursivă?

248
00:18:07,210 --> 00:18:08,920
[Elev] Când aveți o funcție în sine apel

249
00:18:08,920 --> 00:18:13,470
și apoi apel în sine până când se iese cu adevărat și adevărat. Da >>.

250
00:18:13,470 --> 00:18:17,680
O funcție recursivă este doar o funcție care se numește.

251
00:18:17,680 --> 00:18:24,140
Există trei lucruri mari care o funcție recursivă trebuie să aibă.

252
00:18:24,140 --> 00:18:27,310
Primul este evident, ea însăși cheamă.

253
00:18:27,310 --> 00:18:29,650
A doua este cazul de bază.

254
00:18:29,650 --> 00:18:33,390
Deci, la un moment dat funcția trebuie să se oprească de asteptare el însuși,

255
00:18:33,390 --> 00:18:35,610
și asta e ceea ce cazul de bază este pentru.

256
00:18:35,610 --> 00:18:43,860
Deci, aici, știm că ar trebui să ne oprim, ar trebui să ne dea în noastre de căutare

257
00:18:43,860 --> 00:18:48,150
atunci când este egal cu începutul sfârșit - și vom trece peste ceea ce înseamnă că.

258
00:18:48,150 --> 00:18:52,130
Dar în cele din urmă, ultimul lucru pe care e important pentru funcțiile recursive:

259
00:18:52,130 --> 00:18:59,250
funcțiile trebuie să se apropie cumva cazul de bază.

260
00:18:59,250 --> 00:19:04,140
Ca și în cazul în care nu ești actualizarea de fapt nimic, atunci când face al doilea apel recursiv,

261
00:19:04,140 --> 00:19:07,880
dacă sunteți literalmente de asteptare doar funcția din nou cu aceleași argumente

262
00:19:07,880 --> 00:19:10,130
și nu variabile globale s-au schimbat sau ceva,

263
00:19:10,130 --> 00:19:14,430
niciodată nu va ajunge la cazul de bază, caz în care e de rău.

264
00:19:14,430 --> 00:19:17,950
Acesta va fi o recursivitate infinită și un preaplin stivă.

265
00:19:17,950 --> 00:19:24,330
Dar aici vedem că actualizarea se intampla deoarece suntem actualizarea începe sfârșitul + / 2,

266
00:19:24,330 --> 00:19:28,180
suntem actualizarea argumentul final aici, suntem actualizarea argumentul început aici.

267
00:19:28,180 --> 00:19:32,860
Deci, în toate apelurile recursive suntem actualizarea ceva. Bine.

268
00:19:32,860 --> 00:19:38,110
Vrei să ne plimbe prin soluția? Sigur >>.

269
00:19:38,110 --> 00:19:44,270
Sunt folosind SearchHelp, astfel încât de fiecare dată când fac acest apel de funcție

270
00:19:44,270 --> 00:19:47,910
Am inceput de unde am caut în matrice și sfârșitul

271
00:19:47,910 --> 00:19:49,380
de unde mă uit matrice.

272
00:19:49,380 --> 00:19:55,330
>> La fiecare pas în cazul în care se spune că este elementul din mijloc, care este începutul sfârșitul anului + / 2,

273
00:19:55,330 --> 00:19:58,850
este egal cu faptul că ceea ce căutăm?

274
00:19:58,850 --> 00:20:04,650
Și dacă este, atunci l-am găsit, și cred că devine trecut la nivelul de recursivitate.

275
00:20:04,650 --> 00:20:12,540
Și dacă asta nu e adevărat, atunci vom verifica dacă valoarea de mijloc a matrice este prea mare,

276
00:20:12,540 --> 00:20:19,320
caz în care ne uităm la jumătatea stângă a matrice de gând la început până la indicele de mijloc.

277
00:20:19,320 --> 00:20:22,710
Și în caz contrar vom face jumătate final.

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

279
00:20:24,740 --> 00:20:27,730
Sună bine.

280
00:20:27,730 --> 00:20:36,640
Ok, deci un cuplu lucruri, și de fapt, acesta este un lucru foarte mare la nivel

281
00:20:36,640 --> 00:20:41,270
că nu va trebui niciodată să știe de acest curs, dar este adevărat.

282
00:20:41,270 --> 00:20:46,080
Funcții recursive, mereu auzit că sunt o afacere proastă

283
00:20:46,080 --> 00:20:51,160
pentru că dacă te sun recursiv de prea multe ori, veți obține Stack Overflow

284
00:20:51,160 --> 00:20:54,990
deoarece, așa cum am spus mai înainte, orice funcție devine cadru de stivă proprie.

285
00:20:54,990 --> 00:20:59,500
Astfel, fiecare apel al funcției recursive devine rama stiva proprie.

286
00:20:59,500 --> 00:21:04,140
Asa ca daca faceti 1000 apeluri recursive, veți obține 1000 de cadre stack,

287
00:21:04,140 --> 00:21:08,390
și repede va conduce la a avea prea multe cadre stack și lucruri rupe doar.

288
00:21:08,390 --> 00:21:13,480
Deci, de aceea funcțiile recursive sunt, în general, de rău.

289
00:21:13,480 --> 00:21:19,370
Dar există un subset de funcții recursive frumos numit coada-recursive funcții,

290
00:21:19,370 --> 00:21:26,120
și acest lucru se întâmplă să fie un exemplu de unul în care, dacă compilatorul observă acest

291
00:21:26,120 --> 00:21:29,920
și ar trebui, cred că - în zăngănit dacă se trece-O2 de pavilion

292
00:21:29,920 --> 00:21:33,250
atunci se va observa acest lucru este coada recursiv și va face lucrurile bine.

293
00:21:33,250 --> 00:21:40,050
>> Acesta va reutiliza același cadru stiva de peste si peste din nou, pentru fiecare apel recursiv.

294
00:21:40,050 --> 00:21:47,010
Și așa din moment ce te folosind aceeași stivă cadru, nu aveți nevoie să vă faceți griji cu privire la

295
00:21:47,010 --> 00:21:51,690
stivă vreodată debordant, și, în același timp, cum ai spus mai înainte,

296
00:21:51,690 --> 00:21:56,380
în cazul în care odată ce te vei întoarce adevărat, atunci ea trebuie să se întoarcă la toate aceste cadre stivei

297
00:21:56,380 --> 00:22:01,740
și apelul de a zecea SearchHelp trebuie să se întoarcă la nouă, trebuie să se întoarcă la al 8-lea.

298
00:22:01,740 --> 00:22:05,360
Așa că nu trebuie să se întâmple atunci când funcțiile sunt coada recursiv.

299
00:22:05,360 --> 00:22:13,740
Și astfel ceea ce face ca această funcție recursivă este coada observa ca pentru orice apel dat la SearchHelp

300
00:22:13,740 --> 00:22:18,470
apelul recursiv care se face este ceea ce se întoarce.

301
00:22:18,470 --> 00:22:25,290
Deci, în primul apel pentru a SearchHelp, ne fie reveni imediat false,

302
00:22:25,290 --> 00:22:29,590
imediat return true, sau vom face un apel recursiv la SearchHelp

303
00:22:29,590 --> 00:22:33,810
în cazul în care ceea ce ne revin ca apelul este ceea ce se întoarce.

304
00:22:33,810 --> 00:22:51,560
Și nu am putut face acest lucru, dacă am făcut ceva de genul int x = SearchHelp, retur x * 2,

305
00:22:51,560 --> 00:22:55,440
doar cateva aleatoare schimbare.

306
00:22:55,440 --> 00:23:01,470
>> Deci, acum, acest apel recursiv, acest int x = SearchHelp apelul recursiv,

307
00:23:01,470 --> 00:23:05,740
nu mai este coada recursiv, pentru că, de fapt nu trebuie să se întoarcă

308
00:23:05,740 --> 00:23:10,400
inapoi la un cadru teancului anterior, astfel că apelul precedent la funcția de

309
00:23:10,400 --> 00:23:13,040
pot apoi face ceva cu valoarea de returnare.

310
00:23:13,040 --> 00:23:22,190
Deci, acest lucru nu este recursiv coada, dar ceea ce am avut înainte de a se frumos coada recursiv. Da.

311
00:23:22,190 --> 00:23:27,000
[Elev] nu ar trebui cazul a doua bază se verifică prima

312
00:23:27,000 --> 00:23:30,640
pentru că ar putea exista o situație în care, atunci când se trece argumentul

313
00:23:30,640 --> 00:23:35,770
ați începe = sfârșitul anului, dar ele sunt o valoare acul.

314
00:23:35,770 --> 00:23:47,310
Problema a fost nu putem rula în cazul în care sfârșitul este valoarea ac

315
00:23:47,310 --> 00:23:52,000
sau de a începe = sfârșitul anului, în mod corespunzător, start = sfârșitul

316
00:23:52,000 --> 00:23:59,480
și nu ați verificat de fapt, ca o valoare deosebită încă,

317
00:23:59,480 --> 00:24:03,910
apoi începe sfârșitul + / 2 este doar de gând să fie aceeași valoare.

318
00:24:03,910 --> 00:24:07,890
Dar ne-am întors deja false și nu am verificat, de fapt valoarea.

319
00:24:07,890 --> 00:24:14,240
Deci, cel puțin, în primul apel, în cazul în care dimensiunea este 0, atunci vrem să se întoarcă fals.

320
00:24:14,240 --> 00:24:17,710
Dar dacă dimensiunea este 1, atunci pornire nu se va sfârși egal,

321
00:24:17,710 --> 00:24:19,820
iar noi vom verifica cel puțin un element unic.

322
00:24:19,820 --> 00:24:26,750
Dar cred că ai dreptate în care putem ajunge într-un caz în care încep + final / 2,

323
00:24:26,750 --> 00:24:31,190
pornire se termină prin a fi la fel ca punct de pornire + sfârșit / 2,

324
00:24:31,190 --> 00:24:35,350
dar niciodata nu am verificat, de fapt acel element.

325
00:24:35,350 --> 00:24:44,740
>> Deci, dacă vom verifica Primul este elementul din mijloc valoarea căutăm,

326
00:24:44,740 --> 00:24:47,110
atunci ne putem întoarce imediat adevărat.

327
00:24:47,110 --> 00:24:50,740
Altfel, dacă acestea sunt egale, atunci nu e nici un punct în a continua

328
00:24:50,740 --> 00:24:58,440
deoarece suntem doar de gând să actualizeze la un caz în care ne aflăm pe o matrice cu un singur element.

329
00:24:58,440 --> 00:25:01,110
În cazul în care singur element nu este cel pe care îl căutăm,

330
00:25:01,110 --> 00:25:03,530
atunci totul e bine. Da.

331
00:25:03,530 --> 00:25:08,900
[Elev] lucru este că, deoarece dimensiunea este de fapt mai mare decât numărul de elemente din matrice,

332
00:25:08,900 --> 00:25:13,070
există deja un decalaj - >> Deci va dimensiona -

333
00:25:13,070 --> 00:25:19,380
[Elev] Spune dacă matrice a fost dimensiunea 0, atunci SearchHelp va verifica, de fapt carul cu fân de la 0

334
00:25:19,380 --> 00:25:21,490
privind primul apel.

335
00:25:21,490 --> 00:25:25,300
Matrice are dimensiunea 0, deci 0 este - >> Da.

336
00:25:25,300 --> 00:25:30,750
Nu e un alt lucru pe care - ar putea fi bine. Să ne gândim.

337
00:25:30,750 --> 00:25:40,120
Deci, dacă matrice a avut 10 elemente și un mijloc vom verifica este indicele 5,

338
00:25:40,120 --> 00:25:45,700
deci suntem de verificare 5, și să spunem că valoarea este mai mică.

339
00:25:45,700 --> 00:25:50,720
Deci suntem aruncat totul departe la 5 mai departe.

340
00:25:50,720 --> 00:25:54,030
Deci, începe sfârșitul + / 2 va fi sfârșitul nostru nou,

341
00:25:54,030 --> 00:25:57,450
Deci da, este întotdeauna o să rămână dincolo de sfârșitul matrice.

342
00:25:57,450 --> 00:26:03,570
Dacă e un caz în cazul în care a fost par sau impar, atunci ne-ar verifica, să zicem, 4,

343
00:26:03,570 --> 00:26:05,770
dar suntem încă departe aruncat -

344
00:26:05,770 --> 00:26:13,500
Deci da, finalul este întotdeauna o să fie dincolo de sfârșitul efectiv al matrice.

345
00:26:13,500 --> 00:26:18,350
Deci, avem toate elementele sunt axate pe, sfârșitul este întotdeauna o să fie unul după asta.

346
00:26:18,350 --> 00:26:24,270
Și astfel, în cazul în care se începe niciodată sfârșit egal, suntem într-o matrice de dimensiune 0.

347
00:26:24,270 --> 00:26:35,600
>> Un alt lucru m-am gândit e că sunt actualizarea început să se înceapă + sfârșitul / 2,

348
00:26:35,600 --> 00:26:44,020
astfel încât acesta este cazul în care am avea probleme cu, în cazul în care încep + final / 2

349
00:26:44,020 --> 00:26:46,820
este elementul suntem verificare.

350
00:26:46,820 --> 00:26:58,150
Să zicem că am avut această matrice 10-element. Oricare ar fi.

351
00:26:58,150 --> 00:27:03,250
Deci, începe sfârșitul + / 2 va fi ceva de genul acesta,

352
00:27:03,250 --> 00:27:07,060
si daca asta nu e valoarea, spune că vrem să actualizați.

353
00:27:07,060 --> 00:27:10,060
Valoarea este mai mare, așa că vrei să te uiți la această jumătate de matrice.

354
00:27:10,060 --> 00:27:15,910
Deci, cum suntem actualizarea început, suntem actualizarea început să fie acum acest element.

355
00:27:15,910 --> 00:27:23,790
Dar acest lucru poate încă mai funcționează, sau cel puțin foarte, puteți face de start + sfârșit / 2 + 1.

356
00:27:23,790 --> 00:27:27,850
[Elev] Nu trebuie să fie înceapă + sfârșitul [neauzit] >> Da.

357
00:27:27,850 --> 00:27:33,240
Am verificat deja acest element și știu că nu e cel pe care îl căutăm.

358
00:27:33,240 --> 00:27:36,800
Deci, nu avem nevoie să actualizați început să fie acest element.

359
00:27:36,800 --> 00:27:39,560
Ne putem sări peste ea și actualizarea începe să fie acest element.

360
00:27:39,560 --> 00:27:46,060
Și există niciodată un caz, să spunem, că acest scop au fost,

361
00:27:46,060 --> 00:27:53,140
așa începe atunci ar fi aceasta, porniți + sfârșitul / 2 ar fi aceasta,

362
00:27:53,140 --> 00:28:00,580
încep + END - Da, cred că pot ajunge în recursivitate infinită.

363
00:28:00,580 --> 00:28:12,690
Să zicem că e doar o matrice de dimensiune 2 sau o matrice de dimensiune 1. Cred că acest lucru va funcționa.

364
00:28:12,690 --> 00:28:19,490
Deci în prezent, acest element de pornire este și la sfârșitul este 1 dincolo de ea.

365
00:28:19,490 --> 00:28:24,110
Deci, elementul care vom verifica este aceasta,

366
00:28:24,110 --> 00:28:29,400
și apoi când am actualizat început, suntem actualizarea început să fie 0 + 1/2,

367
00:28:29,400 --> 00:28:33,160
care ne va termina din nou cu pornire fiind acest element.

368
00:28:33,160 --> 00:28:36,210
>> Deci suntem de verificare același element de peste si peste din nou.

369
00:28:36,210 --> 00:28:43,310
Deci, acesta este cazul în care la fiecare apel recursiv trebuie să actualizeze efectiv ceva.

370
00:28:43,310 --> 00:28:48,370
Deci, avem nevoie să facem pornire + sfârșit / 2 + 1, sau altceva nu e un caz

371
00:28:48,370 --> 00:28:50,710
în cazul în care nu suntem de fapt, actualizarea de pornire.

372
00:28:50,710 --> 00:28:53,820
Toată lumea vedea că?

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

374
00:28:56,310 --> 00:29:03,860
Are cineva întrebări cu privire la această soluție sau orice comentariu mai mult?

375
00:29:05,220 --> 00:29:10,280
Bine. Are cineva o au iterativ soluție care să ne putem uita la toate?

376
00:29:17,400 --> 00:29:20,940
Credeți facem tot recursiv?

377
00:29:20,940 --> 00:29:25,950
Sau, de asemenea, cred că, dacă ei deschis, atunci este posibil să aveți înlocuite cel anterior.

378
00:29:25,950 --> 00:29:28,810
Are o salvați în mod automat? Eu nu sunt pozitive.

379
00:29:35,090 --> 00:29:39,130
Are cineva au iterativ?

380
00:29:39,130 --> 00:29:42,430
Putem merge pe jos prin ea împreună, dacă nu.

381
00:29:46,080 --> 00:29:48,100
Ideea va fi aceeași.

382
00:30:00,260 --> 00:30:02,830
Iterativ soluție.

383
00:30:02,830 --> 00:30:07,140
Am de gând să doriți să faceți în esență aceeași idee

384
00:30:07,140 --> 00:30:16,530
în cazul în care dorim să urmărească sfârșitul noua matrice și nou început de matrice

385
00:30:16,530 --> 00:30:18,510
și de a face asta de peste si peste.

386
00:30:18,510 --> 00:30:22,430
Și dacă ceea ce suntem urmărirea ca de început și de sfârșit vreodată se intersectează,

387
00:30:22,430 --> 00:30:29,020
atunci nu l-am găsit și ne putem întoarce false.

388
00:30:29,020 --> 00:30:37,540
Deci, cum fac asta? Oricine au sugestii sau cod pentru mine de a trage în sus?

389
00:30:42,190 --> 00:30:47,450
[Elev] Fă o buclă în timp ce. Da >>.

390
00:30:47,450 --> 00:30:49,450
Ai de gând să vrei să faci o buclă.

391
00:30:49,450 --> 00:30:51,830
>> Credeți că aveți codul aș putea trage în sus, sau ce aveai de gând să sugereze?

392
00:30:51,830 --> 00:30:56,340
[Elev] Cred că da. >> Regulă. Acest lucru face lucrurile mai ușor. Care a fost numele tău?

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

394
00:31:00,140 --> 00:31:04,190
Revizia 1. Bine.

395
00:31:04,190 --> 00:31:13,200
Minima este ceea ce am numit începe înainte.

396
00:31:13,200 --> 00:31:17,080
Up nu este destul de ceea ce am numit sfârșitul înainte.

397
00:31:17,080 --> 00:31:22,750
De fapt, sfârșitul este acum în matrice. E un element ar trebui să ia în considerare.

398
00:31:22,750 --> 00:31:26,890
Atat de scazut este 0, este de până dimensiunea matrice - 1,

399
00:31:26,890 --> 00:31:34,780
iar acum suntem looping, și suntem de verificare -

400
00:31:34,780 --> 00:31:37,340
Cred ca te poti plimba prin ea.

401
00:31:37,340 --> 00:31:41,420
Care a fost gândirea ta prin asta? Plimbare ne codul.

402
00:31:41,420 --> 00:31:49,940
[Elev] Sigur. Uită-te la valoarea carul cu fân în mijloc și să o compare cu acul.

403
00:31:49,940 --> 00:31:58,520
Deci, dacă e mai mare decât acul, apoi doriți să - oh, de fapt, că ar trebui să fie invers.

404
00:31:58,520 --> 00:32:05,180
Ai de gând să doriți să aruncați jumătatea dreaptă, și astfel da, care ar trebui să fie calea.

405
00:32:05,180 --> 00:32:08,830
[Bowden] Deci, aceasta ar trebui să fie mai puțin? Este că ceea ce ai spus? >> [Elev] Da.

406
00:32:08,830 --> 00:32:10,390
[Bowden] Ok. Mai puțin.

407
00:32:10,390 --> 00:32:15,700
Deci, dacă ceea ce căutăm este mai mică decât la ceea ce ne dorim,

408
00:32:15,700 --> 00:32:19,410
atunci da, vrem să aruncați jumătatea stângă,

409
00:32:19,410 --> 00:32:22,210
ceea ce înseamnă că actualizarea se tot suntem în considerare

410
00:32:22,210 --> 00:32:26,610
prin mutarea scăzut de la dreptul de matrice.

411
00:32:26,610 --> 00:32:30,130
Acest lucru arată bine.

412
00:32:30,130 --> 00:32:34,550
Cred că are aceeași problemă pe care am spus pe cel anterior,

413
00:32:34,550 --> 00:32:49,760
în cazul în care în cazul în care scăzută este 0 și până este 1, atunci scazut + sus / 2 se va configura pentru a fi același lucru din nou.

414
00:32:49,760 --> 00:32:53,860
>> Și chiar dacă nu e cazul, este încă mult mai eficient, cel puțin

415
00:32:53,860 --> 00:32:57,630
pentru a arunca pur și simplu elementul de care tocmai am uitat la ceea ce știm este greșit.

416
00:32:57,630 --> 00:33:03,240
Atât de jos în sus + / 2 + 1 - >> [elev] Asta ar trebui să fie o altă cale.

417
00:33:03,240 --> 00:33:05,900
[Bowden] Sau acest lucru ar fi - 1 și celălalt ar trebui să fie + 1.

418
00:33:05,900 --> 00:33:09,580
[Elev] Și ar trebui să existe o dublă semnul egalității. >> [Bowden] Da.

419
00:33:09,580 --> 00:33:11,340
[Elev] Da.

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

421
00:33:15,910 --> 00:33:21,280
Și, în sfârșit, acum că avem această 1 + - 1 lucru,

422
00:33:21,280 --> 00:33:31,520
este - ar putea să nu fie - este vreodată posibil pentru scăzut pentru a termina cu o valoare mai mare decât până?

423
00:33:35,710 --> 00:33:40,320
Cred că singurul mod în care se poate întâmpla - Este posibil? >> [Elev] Nu stiu.

424
00:33:40,320 --> 00:33:45,220
Dar, în cazul în care devine trunchiat și apoi devine minus 1 și că apoi - >> Da.

425
00:33:45,220 --> 00:33:47,480
[Elev] Aceasta ar fi, eventual, dat peste cap.

426
00:33:49,700 --> 00:33:53,940
Cred că ar trebui să fie bun doar pentru că

427
00:33:53,940 --> 00:33:58,800
pentru ca aceasta să ajung mai mici ar trebui să fie egal, cred.

428
00:33:58,800 --> 00:34:03,070
Dar dacă ele sunt egale, atunci nu ne-ar fi făcut în timp ce bucla pentru a începe cu

429
00:34:03,070 --> 00:34:06,670
și ne-am întors ar fi valoarea. Deci, eu cred că suntem bine acum.

430
00:34:06,670 --> 00:34:11,530
Observați că, deși această problemă nu mai este recursiv,

431
00:34:11,530 --> 00:34:17,400
același tip de idei se aplică în cazul în care putem vedea cum acest atât de ușor se pretează

432
00:34:17,400 --> 00:34:23,659
la o soluție recursivă de faptul că suntem doar actualizarea indicilor de peste si peste, din nou,

433
00:34:23,659 --> 00:34:29,960
facem problema mai mici și mai mici, ne concentrăm pe un subset de matrice.

434
00:34:29,960 --> 00:34:40,860
[Elev] Dacă scăzut este 0 și până este 1, acestea ar fi ambele 0 + 1/2, care ar merge la 0,

435
00:34:40,860 --> 00:34:44,429
și apoi s-ar fi + 1, s-ar fi - 1.

436
00:34:47,000 --> 00:34:50,870
[Elev] În cazul în care ne verificarea egalitate?

437
00:34:50,870 --> 00:34:55,100
Ca și în cazul cel din mijloc este, de fapt acul?

438
00:34:55,100 --> 00:34:58,590
Noi nu facem în prezent asta? Oh!

439
00:35:00,610 --> 00:35:02,460
În cazul în care este -

440
00:35:05,340 --> 00:35:13,740
Da. Noi nu doar putem face testul de aici pentru ca să spunem mijloc de fabricație -

441
00:35:13,740 --> 00:35:16,430
[Elev] E ca si cum, de fapt, nu aruncați legat.

442
00:35:16,430 --> 00:35:20,220
Deci, dacă vă aruncați legat, trebuie să-l verificați mai întâi sau orice altceva.

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

444
00:35:23,350 --> 00:35:29,650
Deci, acum ne-am aruncat pe care am uitat la prezent,

445
00:35:29,650 --> 00:35:33,260
ceea ce înseamnă că acum trebuie să aibă, de asemenea,

446
00:35:33,260 --> 00:35:44,810
în cazul în care (carul cu fân [(low + sus) / 2] == ac), atunci ne putem întoarce adevărat.

447
00:35:44,810 --> 00:35:52,070
Și dacă am pus altceva sau doar în cazul în care, literalmente înseamnă același lucru

448
00:35:52,070 --> 00:35:57,110
deoarece acest lucru ar fi adevărat întors.

449
00:35:57,110 --> 00:36:01,450
Asa ca am sa pun altceva, dacă, dar nu contează.

450
00:36:01,450 --> 00:36:10,440
>> Deci, în cazul în care acest altceva, altceva acest lucru, și acesta este un lucru comun să fac

451
00:36:10,440 --> 00:36:14,340
în cazul în care, chiar dacă acesta este cazul în care totul este bine aici,

452
00:36:14,340 --> 00:36:22,780
cum ar fi scăzut nu poate fi mai mare decât în ​​sus, nu e raționamentul în valoare de aproximativ dacă asta e adevărat.

453
00:36:22,780 --> 00:36:28,010
Deci, s-ar putea la fel de bine spune în timp ce mică este mai mică sau egală cu

454
00:36:28,010 --> 00:36:30,720
sau în timp ce mică este mai mică de

455
00:36:30,720 --> 00:36:35,300
așa că, dacă acestea sunt vreodată egale sau foarte scăzute se întâmplă să treacă în sus,

456
00:36:35,300 --> 00:36:40,130
atunci putem iesi din aceasta bucla.

457
00:36:41,410 --> 00:36:44,630
Întrebări, probleme, comentarii?

458
00:36:47,080 --> 00:36:49,270
Bine. Acest lucru arată bine.

459
00:36:49,270 --> 00:36:52,230
Acum vrem să facem un fel.

460
00:36:52,230 --> 00:37:04,030
Dacă mergem la revizuirea a doua mea, vom vedea aceste aceleași numere,

461
00:37:04,030 --> 00:37:07,550
dar acum nu mai sunt sortate în ordine.

462
00:37:07,550 --> 00:37:12,840
Și dorim să pună în aplicare un fel folosind orice algoritm în O de n log n.

463
00:37:12,840 --> 00:37:17,240
Deci, care algoritmul crezi că ar trebui să pună în aplicare aici? >> [Elev] Merge sortare.

464
00:37:17,240 --> 00:37:23,810
[Bowden] Da. Merge fel este O (n log n), asa ca asta e ceea ce am de gând să fac.

465
00:37:23,810 --> 00:37:26,680
Și problema va fi destul de asemănătoare,

466
00:37:26,680 --> 00:37:31,920
în cazul în care acesta se pretează cu ușurință la o soluție recursivă.

467
00:37:31,920 --> 00:37:35,580
Ne poate veni, de asemenea, cu o soluție iterativ, dacă vrem,

468
00:37:35,580 --> 00:37:42,540
dar recursivitate va fi mai ușor aici, iar noi ar trebui să facem recursivitate.

469
00:37:45,120 --> 00:37:49,530
Cred că vom merge prin sortare îmbinare în primul rând,

470
00:37:49,530 --> 00:37:54,280
deși există un video minunat pe un fel de îmbinare deja. [Râsete]

471
00:37:54,280 --> 00:37:59,780
Îmbinare așa fel, există - Sunt pierd atât de mult din această lucrare.

472
00:37:59,780 --> 00:38:02,080
Oh, există o singură stânga.

473
00:38:02,080 --> 00:38:03,630
Deci îmbinare.

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

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

476
00:38:29,910 --> 00:38:33,460
Merge ia două matrice distincte.

477
00:38:33,460 --> 00:38:36,780
Individual, aceste două tablouri sunt ambele sortate.

478
00:38:36,780 --> 00:38:40,970
Deci această matrice, 1, 3, 5, sortate. Această matrice, 0, 2, 4, sortate.

479
00:38:40,970 --> 00:38:46,710
Acum, ce trebuie să faceți este de îmbinare a le combina într-o singură matrice, care este ea însăși sortate.

480
00:38:46,710 --> 00:38:57,130
Deci, vrem o serie de marimea 6, care va avea aceste elemente în interiorul acestuia

481
00:38:57,130 --> 00:38:59,390
sortate în ordine.

482
00:38:59,390 --> 00:39:03,390
>> Și astfel putem profita de faptul că aceste două matrice sunt sortate

483
00:39:03,390 --> 00:39:06,800
pentru a face acest lucru în timp liniar,

484
00:39:06,800 --> 00:39:13,510
sensul timpului liniar în cazul în care această matrice este format x si y este dimensiunea,

485
00:39:13,510 --> 00:39:20,970
apoi algoritmul totală ar trebui să fie O (x + y). Bine.

486
00:39:20,970 --> 00:39:23,150
Deci, traduceri.

487
00:39:23,150 --> 00:39:26,030
[Elev] Putem porni de la stânga?

488
00:39:26,030 --> 00:39:30,150
Deci, vă veți pune 0 în jos mai întâi și apoi 1 și apoi aici, esti la 2.

489
00:39:30,150 --> 00:39:33,320
Deci e un fel de ai o filă care se mișcă spre dreapta. >> [Bowden] Da.

490
00:39:33,320 --> 00:39:41,070
Pentru ambele aceste tablouri, dacă ne concentrăm doar pe elementul cel mai din stânga.

491
00:39:41,070 --> 00:39:43,530
Deoarece ambele matrice sunt sortate, știm că aceste 2 elemente

492
00:39:43,530 --> 00:39:46,920
sunt cele mai mici elemente din matrice, fie.

493
00:39:46,920 --> 00:39:53,500
Deci asta înseamnă că 1 din aceste 2 elemente trebuie să fie mai mic element din gama noastră îmbinată.

494
00:39:53,500 --> 00:39:58,190
Pur și simplu așa se întâmplă că cea mai mică este cea de pe dreapta de data asta.

495
00:39:58,190 --> 00:40:02,580
Deci, vom lua 0, introduceți-l în stânga deoarece 0 este mai mic decât 1,

496
00:40:02,580 --> 00:40:08,210
astfel încât să ia 0, introduceți-l în poziția noastră în primul rând, și apoi vom actualiza acest

497
00:40:08,210 --> 00:40:12,070
să se concentreze acum pe primul element.

498
00:40:12,070 --> 00:40:14,570
Și acum vom repeta.

499
00:40:14,570 --> 00:40:20,670
Deci, acum vom compara 2 și 1. 1 este mai mică, așa că vom introduce 1.

500
00:40:20,670 --> 00:40:25,300
Noi actualizăm acest indicator pentru a indica tipul ăsta.

501
00:40:25,300 --> 00:40:33,160
Acum, o facem din nou, așa 2. Acest lucru se va actualiza, compara aceste 2, 3.

502
00:40:33,160 --> 00:40:37,770
Acest actualizări, apoi 4 și 5.

503
00:40:37,770 --> 00:40:42,110
Așa că este de îmbinare.

504
00:40:42,110 --> 00:40:49,010
>> Ar trebui să fie destul de evident că este timpul liniar, deoarece vom merge doar pe fiecare element de dată.

505
00:40:49,010 --> 00:40:55,980
Și asta este cel mai mare pas pentru punerea în aplicare sortare îmbinarea face acest lucru.

506
00:40:55,980 --> 00:40:59,330
Și nu e așa de greu.

507
00:40:59,330 --> 00:41:15,020
Câteva lucruri să vă faceți griji despre este să zicem că a fost fuzionarea 1, 2, 3, 4, 5, 6.

508
00:41:15,020 --> 00:41:30,930
În acest caz, vom ajunge în scenariul în care aceasta va fi mai mică,

509
00:41:30,930 --> 00:41:36,160
atunci vom actualiza acest indicator, acesta va fi mai mic, actualiza această,

510
00:41:36,160 --> 00:41:41,280
asta e mai mic, iar acum va trebui să recunoască

511
00:41:41,280 --> 00:41:44,220
atunci când v-ați alerga efectiv de elemente pentru a compara cu.

512
00:41:44,220 --> 00:41:49,400
Din moment ce am folosit deja acest tablou întreg,

513
00:41:49,400 --> 00:41:55,190
totul în această matrice este acum doar introdus în aici.

514
00:41:55,190 --> 00:42:02,040
Deci, dacă vom rula vreodată în punctul în care unul din tablouri noastre este complet fuzionat deja,

515
00:42:02,040 --> 00:42:06,510
atunci vom lua doar toate elementele altă matrice și introduceți-le în capătul matrice.

516
00:42:06,510 --> 00:42:13,630
Deci, putem insera doar 4, 5, 6. Bine.

517
00:42:13,630 --> 00:42:18,070
Acesta este un lucru să fiți atenți pentru.

518
00:42:22,080 --> 00:42:26,120
De punere în aplicare, care ar trebui să fie pasul 1.

519
00:42:26,120 --> 00:42:32,600
Merge apoi sortați pe baza asta, e 2 pasi, 2 trepte stupide.

520
00:42:38,800 --> 00:42:42,090
Să-i dăm doar această matrice.

521
00:42:57,920 --> 00:43:05,680
Îmbinare așa fel, pasul 1 este de a sparge recursiv matrice în jumătăți.

522
00:43:05,680 --> 00:43:09,350
Împărțit astfel încât această matrice în jumătăți.

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

524
00:43:22,920 --> 00:43:25,800
Și acum o facem din nou și ne-am despărțit în aceste jumatati.

525
00:43:25,800 --> 00:43:27,530
Vreau doar să-l fac pe partea asta.

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

527
00:43:34,790 --> 00:43:37,440
Ne-ar face același lucru aici.

528
00:43:37,440 --> 00:43:40,340
Și acum am impartit in jumatati din nou.

529
00:43:40,340 --> 00:43:51,080
Și avem 4, 15, 16, 50.

530
00:43:51,080 --> 00:43:53,170
Așa că este cazul nostru de bază.

531
00:43:53,170 --> 00:44:00,540
Odată ce matrice sunt de dimensiune 1, apoi ne oprim cu divizare în jumătăți.

532
00:44:00,540 --> 00:44:03,190
>> Acum ce facem cu asta?

533
00:44:03,190 --> 00:44:15,730
Am ajuns, de asemenea, acest lucru va rupe în jos în 8, 23, 42, și 108.

534
00:44:15,730 --> 00:44:24,000
Deci, acum că suntem la acest punct, pasul acum doi fel de fuziune este fuzionează doar perechi la listele.

535
00:44:24,000 --> 00:44:27,610
Așa că vrem să fuzioneze acestea. Noi numim doar îmbinare.

536
00:44:27,610 --> 00:44:31,410
Stim îmbinare va reveni la acestea pentru sortat.

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

538
00:44:33,920 --> 00:44:41,440
Acum vrem să fuzioneze acestea, și că se va întoarce o listă cu cele în ordine sortate,

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

540
00:44:44,160 --> 00:44:57,380
Noi cei îmbinare - Eu nu pot scrie - 8, 23 și 42, 108.

541
00:44:57,380 --> 00:45:02,890
Deci avem perechi îmbinate dată.

542
00:45:02,890 --> 00:45:05,140
Acum ne uni din nou doar.

543
00:45:05,140 --> 00:45:10,130
Observați că fiecare dintre aceste liste sunt sortate în sine,

544
00:45:10,130 --> 00:45:15,220
și apoi putem îmbina doar aceste liste pentru a obține o listă de marimea 4, care este sortată

545
00:45:15,220 --> 00:45:19,990
și îmbinarea acestor două liste pentru a obține o listă de marimea 4, care este sortat.

546
00:45:19,990 --> 00:45:25,710
Și, în sfârșit, putem fuziona cele două liste de marimea 4 pentru a obține o listă de dimensiune 8, care este sortat.

547
00:45:25,710 --> 00:45:34,030
Deci, pentru a vedea că acest lucru este total n log n, am văzut că deja de îmbinare este liniar,

548
00:45:34,030 --> 00:45:40,390
asa ca atunci cand avem de a face cu fuziunea acestora, astfel cum ar fi costul total al îmbinării

549
00:45:40,390 --> 00:45:43,410
pentru aceste două liste se află la doar 2, deoarece -

550
00:45:43,410 --> 00:45:49,610
Sau bine, e de n O, dar n aici este doar aceste 2 elemente, asa ca e 2.

551
00:45:49,610 --> 00:45:52,850
Și aceste 2 vor fi 2 si aceste 2 vor fi 2 si aceste 2 va fi de 2,

552
00:45:52,850 --> 00:45:58,820
deci peste toate se contopește de care avem nevoie pentru a face, am ajunge să faci n.

553
00:45:58,820 --> 00:46:03,210
Ca 2 + 2 + 2 + 2 este 8, care este n,

554
00:46:03,210 --> 00:46:08,060
astfel încât costul de a fuziona în acest set este n.

555
00:46:08,060 --> 00:46:10,810
Și apoi același lucru aici.

556
00:46:10,810 --> 00:46:16,980
Vom fuziona aceste 2, atunci acestea 2, și individual această îmbinare va dura patru operațiuni,

557
00:46:16,980 --> 00:46:23,610
această îmbinare va dura patru operații, dar, din nou, între toate acestea,

558
00:46:23,610 --> 00:46:29,030
vom ajunge fuzionarea n lucruri totale, și așa acest pas ia n.

559
00:46:29,030 --> 00:46:33,670
Și astfel fiecare nivel are n elemente fiind îmbinate.

560
00:46:33,670 --> 00:46:36,110
>> Și cum de multe niveluri sunt acolo?

561
00:46:36,110 --> 00:46:40,160
La fiecare nivel, gama noastră crește de dimensiunea 2.

562
00:46:40,160 --> 00:46:44,590
Aici matrice noastre sunt de dimensiune 1, aici sunt de dimensiuni 2, aici sunt de marimea 4,

563
00:46:44,590 --> 00:46:46,470
și, în sfârșit, sunt de dimensiune 8.

564
00:46:46,470 --> 00:46:56,450
Deci, din moment ce este dublarea, se va fi un total de log n dintre aceste niveluri.

565
00:46:56,450 --> 00:47:02,090
Deci, cu log n niveluri, fiecare nivel individual, ținând n totalul operațiunilor,

566
00:47:02,090 --> 00:47:05,720
avem un log n n algoritm.

567
00:47:05,720 --> 00:47:07,790
Întrebări?

568
00:47:08,940 --> 00:47:13,320
S-au făcut deja progrese persoane cu privire la modul de a pune în aplicare acest lucru?

569
00:47:13,320 --> 00:47:18,260
Este cineva deja într-o stare în care pot trage doar până codul lor?

570
00:47:20,320 --> 00:47:22,260
Pot să dau un minut.

571
00:47:24,770 --> 00:47:27,470
Acesta va fi mai mare.

572
00:47:27,470 --> 00:47:28,730
Am foarte recomanda repete -

573
00:47:28,730 --> 00:47:30,510
Tu nu trebuie să faci recursia pentru îmbinare

574
00:47:30,510 --> 00:47:33,750
pentru că a făcut recursie pentru îmbinare, ai de gând să trebuie să treacă un buchet de diferite dimensiuni.

575
00:47:33,750 --> 00:47:37,150
Poți, dar e enervant.

576
00:47:37,150 --> 00:47:43,720
Dar recursia pentru sortare în sine este destul de ușor.

577
00:47:43,720 --> 00:47:49,190
Trebuie doar sunați pur și simplu un fel pe jumătatea din stânga, sortare pe jumătatea din dreapta. Bine.

578
00:47:51,770 --> 00:47:54,860
Oricine are ceva ce poate trage încă?

579
00:47:54,860 --> 00:47:57,540
Sau altceva să-ți dau un minut.

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

581
00:47:59,900 --> 00:48:02,970
Oricine are ceva ce putem lucra cu?

582
00:48:05,450 --> 00:48:09,680
Sau altfel vom lucra doar cu acest lucru și apoi extindeți de acolo.

583
00:48:09,680 --> 00:48:14,050
>> Oricine are mai mult decât aceasta, care pot trage în sus?

584
00:48:14,050 --> 00:48:17,770
[Elev] Da. Puteți trage în sus a mea. >> Regulă.

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

586
00:48:22,170 --> 00:48:25,280
[Elev] Au fost o mulțime de condiții. Oh >>, trage. Poți -

587
00:48:25,280 --> 00:48:28,110
[Elev] Trebuie să-l salveze. Da >>.

588
00:48:32,420 --> 00:48:35,730
Așa că am făcut îmbinare separat.

589
00:48:35,730 --> 00:48:38,570
Oh, dar nu e așa de rău.

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

591
00:48:41,650 --> 00:48:47,080
Deci, este ea însăși un fel de asteptare la doar mergeSortHelp.

592
00:48:47,080 --> 00:48:49,530
Să ne explice ce face mergeSortHelp.

593
00:48:49,530 --> 00:48:55,700
[Elev] MergeSortHelp destul de mult face două etape principale,

594
00:48:55,700 --> 00:49:01,270
care este de a sorta fiecare jumătate din matrice și apoi să fuzioneze amândoi.

595
00:49:04,960 --> 00:49:08,050
[Bowden] Ok, deci da-mi o secundă.

596
00:49:10,850 --> 00:49:13,210
Cred că acest lucru - >> [elev] am nevoie pentru a -

597
00:49:17,100 --> 00:49:19,400
Da. Îmi lipsește ceva.

598
00:49:19,400 --> 00:49:23,100
În îmbinare, îmi dau seama că am nevoie pentru a crea o gamă nouă

599
00:49:23,100 --> 00:49:26,530
pentru că nu am putut face in locul. Da >>. Tu nu poți. Corectează.

600
00:49:26,530 --> 00:49:28,170
[Elev] Așa că am crea o matrice nouă.

601
00:49:28,170 --> 00:49:31,510
Am uitat la sfârșitul anului îmbinare a re-schimbe.

602
00:49:31,510 --> 00:49:34,490
Bine. Avem nevoie de un nou tablou.

603
00:49:34,490 --> 00:49:41,000
Intr-un fel de îmbinare, acest lucru este aproape întotdeauna adevărat.

604
00:49:41,000 --> 00:49:44,340
O parte din costul unui algoritm mai bine timpul-înțelept

605
00:49:44,340 --> 00:49:47,310
este aproape întotdeauna nevoie pentru a utiliza memoria un pic mai mult.

606
00:49:47,310 --> 00:49:51,570
Deci, aici, indiferent cum faci îmbinare sortare,

607
00:49:51,570 --> 00:49:54,780
va trebui în mod inevitabil de a utiliza unele de memorie suplimentar.

608
00:49:54,780 --> 00:49:58,240
El sau ea a creat o matrice nouă.

609
00:49:58,240 --> 00:50:03,400
Și apoi spui la sfârșitul trebuie doar să copiați matrice nou în matrice originală.

610
00:50:03,400 --> 00:50:04,830
[Elev] Cred că da, da.

611
00:50:04,830 --> 00:50:08,210
Nu știu dacă asta funcționează în termeni de numărare de referință sau orice -

612
00:50:08,210 --> 00:50:11,650
Da, acesta va funcționa. >> [Elev] Ok.

613
00:50:20,620 --> 00:50:24,480
Credeți că încercați să rulați acest lucru? >> [Elev] Nu, nu încă. Bine >>.

614
00:50:24,480 --> 00:50:28,880
Încercați să rulați-l, iar apoi voi vorbi despre asta pentru o secunda.

615
00:50:28,880 --> 00:50:35,200
[Elev] am nevoie pentru a avea toate prototipurile de funcții și totul, totuși, nu?

616
00:50:37,640 --> 00:50:40,840
Funcția de prototipuri. Oh, vrei sa spui ca - Da.

617
00:50:40,840 --> 00:50:43,040
Sortare este de asteptare mergeSortHelp.

618
00:50:43,040 --> 00:50:47,390
>> Deci, în scopul de a apela pentru sortare mergeSortHelp, mergeSortHelp trebuie să fie au fost definite

619
00:50:47,390 --> 00:50:56,370
înainte de a sortare sau am nevoie doar de prototip. Doar copiați și lipiți acest lucru.

620
00:50:56,370 --> 00:50:59,490
Și în mod similar, mergeSortHelp este de asteptare îmbinare,

621
00:50:59,490 --> 00:51:03,830
dar îmbinării nu a fost definit încă, astfel încât să putem lăsa să știu mergeSortHelp

622
00:51:03,830 --> 00:51:08,700
că asta e ceea ce se întâmplă fuziona pentru a arata ca, și cu asta basta.

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

624
00:51:22,770 --> 00:51:32,660
Avem o problemă aici, în cazul în care nu avem nici un caz de bază.

625
00:51:32,660 --> 00:51:38,110
MergeSortHelp este recursiv, astfel încât orice recursiv funcția

626
00:51:38,110 --> 00:51:42,610
este de gând să nevoie de un fel de scenariu de bază să știu când să se oprească recursiv se asteptare.

627
00:51:42,610 --> 00:51:45,590
Ceea ce este cazul nostru de bază va fi aici? Da.

628
00:51:45,590 --> 00:51:49,110
[Elev] Dacă dimensiunea este de 1? >> [Bowden] Da.

629
00:51:49,110 --> 00:51:56,220
Deci, cum am văzut acolo, ne-am oprit matrice de divizare

630
00:51:56,220 --> 00:52:01,850
odată ce am intrat în matrice de dimensiune 1, care în mod inevitabil, sunt ele însele sortate.

631
00:52:01,850 --> 00:52:09,530
Deci, în cazul în care dimensiunea este egal cu 1, știm matrice este deja sortat,

632
00:52:09,530 --> 00:52:12,970
astfel încât să putem reveni pur și simplu.

633
00:52:12,970 --> 00:52:16,880
>> Observați că e nul, așa că nu se mai întorc nimic special, doar ne întoarcem.

634
00:52:16,880 --> 00:52:19,580
Bine. Așa că e cazul nostru de bază.

635
00:52:19,580 --> 00:52:27,440
Cred cazul nostru de bază ar putea fi, de asemenea, în cazul în care se întâmplă să fie fuzionarea o serie de mărimea 0,

636
00:52:27,440 --> 00:52:30,030
am dori probabil să se oprească la un moment dat,

637
00:52:30,030 --> 00:52:33,610
astfel încât să putem spune doar dimensiune mai mică de 2 sau mai mic sau egal cu 1

638
00:52:33,610 --> 00:52:37,150
astfel că aceasta va lucra pentru orice matrice acum.

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

640
00:52:38,870 --> 00:52:42,740
Așa că e cazul nostru de bază.

641
00:52:42,740 --> 00:52:45,950
Acum, vrei să ne plimbe prin îmbinare?

642
00:52:45,950 --> 00:52:49,140
Ce înseamnă toate aceste cazuri?

643
00:52:49,140 --> 00:52:54,480
Până aici, facem doar aceeași idee, -

644
00:52:56,970 --> 00:53:02,470
[Elev] am nevoie pentru a fi trece dimensiunea cu toate apelurile mergeSortHelp.

645
00:53:02,470 --> 00:53:10,080
Am adăugat dimensiune ca un primar suplimentară și nu e acolo, cum ar fi dimensiunea / 2.

646
00:53:10,080 --> 00:53:16,210
[Bowden] Oh, mărimea / 2, marimea / 2. >> [Elev] Da, și, de asemenea, în funcție de mai sus, precum și.

647
00:53:16,210 --> 00:53:21,320
[Bowden] Aici? >> [Elev] Doar dimensiune. >> [Bowden] Oh. Dimensiune, dimensiunea? >> [Elev] Da.

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

649
00:53:23,010 --> 00:53:26,580
Lasă-mă să mă gândesc o secundă.

650
00:53:26,580 --> 00:53:28,780
Nu am alerga într-o problemă?

651
00:53:28,780 --> 00:53:33,690
Suntem mereu tratarea lăsat ca 0. >> [Elev] Nr

652
00:53:33,690 --> 00:53:36,340
Asta e bine prea. Scuze. Ar trebui să fie început. Da.

653
00:53:36,340 --> 00:53:39,230
[Bowden] Ok. Îmi place că o mai bună.

654
00:53:39,230 --> 00:53:43,880
Și sfârșitul. Bine.

655
00:53:43,880 --> 00:53:47,200
Deci, acum vrei să ne plimbe prin îmbinare? >> [Elev] Ok.

656
00:53:47,200 --> 00:53:52,150
Sunt doar de mers pe jos prin acest matrice nou pe care l-am creat.

657
00:53:52,150 --> 00:53:57,420
Dimensiunea acesteia este dimensiunea porțiunii de matrice pe care ne-o dorim să fie sortate

658
00:53:57,420 --> 00:54:03,460
și încercarea de a găsi elementul pe care ar trebui să pună în pasul matrice nou.

659
00:54:03,460 --> 00:54:10,140
Deci, pentru a face acest lucru, în primul rând mă verifica dacă jumătatea stângă a matrice continuă să aibă elemente de nici mai mult,

660
00:54:10,140 --> 00:54:14,260
si daca nu, atunci te duci la altcineva această condiție, care spune doar

661
00:54:14,260 --> 00:54:20,180
bine, trebuie să fie în matrice dreapta, și vom pune că, în indicele actual de newArray.

662
00:54:20,180 --> 00:54:27,620
>> Și apoi altfel, eu sunt de verificare în cazul în partea dreaptă a matrice este, de asemenea, terminat,

663
00:54:27,620 --> 00:54:30,630
caz în care am pus în stânga.

664
00:54:30,630 --> 00:54:34,180
Asta nu s-ar putea fi de fapt necesar. Nu sunt sigur.

665
00:54:34,180 --> 00:54:40,970
Dar oricum, celelalte două verificarea care dintre cele două este mai mic, în stânga sau dreapta.

666
00:54:40,970 --> 00:54:49,770
Și, de asemenea, în fiecare caz, în funcție de incrementare eu am substituent incrementa.

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

668
00:54:52,040 --> 00:54:53,840
Asta arată bine.

669
00:54:53,840 --> 00:54:58,800
Are cineva comentarii sau nelămuriri sau întrebări?

670
00:55:00,660 --> 00:55:07,720
Deci, cele patru cazuri pe care le avem pentru a aduce lucrurile în doar a fi - sau se pare ca cinci -

671
00:55:07,720 --> 00:55:13,100
dar trebuie să ia în considerare dacă matrice stânga a alerga afară de lucruri pe care trebuie să fuzioneze,

672
00:55:13,100 --> 00:55:16,390
dacă matrice dreptul de a alerga afară de lucruri pe care trebuie să fuzioneze -

673
00:55:16,390 --> 00:55:18,400
Mă îndreptat de la nimic.

674
00:55:18,400 --> 00:55:21,730
Deci, dacă matrice stânga a alerga afară de lucruri sau de matrice dreapta a alerga afară de lucruri.

675
00:55:21,730 --> 00:55:24,320
Acestea sunt două cazuri.

676
00:55:24,320 --> 00:55:30,920
Avem nevoie, de asemenea, cazul banal dacă chestia din stânga este mai mică decât un lucru bun.

677
00:55:30,920 --> 00:55:33,910
Apoi ne-am dori să alegeți ceva din stânga.

678
00:55:33,910 --> 00:55:37,630
Acestea sunt cazuri.

679
00:55:37,630 --> 00:55:40,990
Deci asta a avut dreptate, așa că e asta.

680
00:55:40,990 --> 00:55:46,760
Matrice a plecat. E 1, 2, 3. Bine. Deci da, acelea sunt cele patru lucruri pe care le-ar putea dori să facă.

681
00:55:50,350 --> 00:55:54,510
Și nu vom trece peste o soluție iterativ.

682
00:55:54,510 --> 00:55:55,980
Eu nu as recomanda -

683
00:55:55,980 --> 00:56:03,070
Merge fel este un exemplu de o funcție care este atât de coada nu recursiv,

684
00:56:03,070 --> 00:56:07,040
nu e ușor să-l facă coadă recursiv,

685
00:56:07,040 --> 00:56:13,450
dar, de asemenea, nu este foarte ușor de a face iterativ.

686
00:56:13,450 --> 00:56:16,910
Acest lucru este foarte ușor.

687
00:56:16,910 --> 00:56:19,170
Acest fel de punerea în aplicare a îmbinării,

688
00:56:19,170 --> 00:56:22,140
îmbinare, indiferent de ceea ce faci, te duci pentru a construi merge.

689
00:56:22,140 --> 00:56:29,170
>> Deci, îmbinare fel construit pe partea de sus a îmbinării recursiv este doar aceste trei linii.

690
00:56:29,170 --> 00:56:34,700
Iterativ, este mai enervant și mai greu să se gândească.

691
00:56:34,700 --> 00:56:41,860
Dar observați că nu e coadă recursiv deoarece mergeSortHelp - atunci când se solicită în sine -

692
00:56:41,860 --> 00:56:46,590
trebuie încă să facă lucruri după acest întoarce apelul recursiv.

693
00:56:46,590 --> 00:56:50,830
Deci, acest cadru trebuie să stiva continuă să existe chiar și după acest apel.

694
00:56:50,830 --> 00:56:54,170
Și apoi când apelați acest lucru, cadru stiva trebuie să continue să existe

695
00:56:54,170 --> 00:56:57,780
deoarece chiar și după acest apel, avem încă nevoie de a fuziona.

696
00:56:57,780 --> 00:57:01,920
Și este netrivial de a face acest coada recursiv.

697
00:57:04,070 --> 00:57:06,270
Întrebări?

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

699
00:57:09,860 --> 00:57:13,400
Deci, merge înapoi pentru a sorta - oh, sunt două lucruri pe care vreau să le arăt. Bine.

700
00:57:13,400 --> 00:57:17,840
Revenind la fel, vom face acest lucru rapid.

701
00:57:17,840 --> 00:57:21,030
Sau de căutare. Sortare? Sortare. Da.

702
00:57:21,030 --> 00:57:22,730
Revenind la începuturile fel.

703
00:57:22,730 --> 00:57:29,870
Dorim să creați un algoritm care sortează matrice folosind orice algoritm

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

705
00:57:33,660 --> 00:57:40,860
Deci, cum este posibil acest lucru? Are cineva orice fel de -

706
00:57:40,860 --> 00:57:44,300
Am sugerat mai sus la -

707
00:57:44,300 --> 00:57:48,300
Dacă suntem pe cale de a îmbunătăți de la n log n O din N,

708
00:57:48,300 --> 00:57:51,450
ne-am îmbunătățit algoritmul nostru de timp-înțelept,

709
00:57:51,450 --> 00:57:55,250
ceea ce înseamnă că ceea ce vom avea nevoie să facă pentru a compensa pentru asta?

710
00:57:55,250 --> 00:57:59,520
[Elev] Space. Da >>. Vom folosi mai mult spațiu.

711
00:57:59,520 --> 00:58:04,490
Și nici măcar nu doar de mai mult spațiu, e mai mult spațiu exponențial.

712
00:58:04,490 --> 00:58:14,320
Deci, eu cred că acest tip de algoritm este ceva pseudo, pseudo polynom -

713
00:58:14,320 --> 00:58:18,980
pseudo - nu mi le amintesc. Pseudo ceva.

714
00:58:18,980 --> 00:58:22,210
Dar e pentru că avem nevoie de a utiliza atât de mult spațiu

715
00:58:22,210 --> 00:58:28,610
că acest lucru este realizabil, dar nu este realist.

716
00:58:28,610 --> 00:58:31,220
>> Și cum putem realiza acest lucru?

717
00:58:31,220 --> 00:58:36,810
Putem realiza acest lucru, dacă putem garanta faptul că orice element special în matrice

718
00:58:36,810 --> 00:58:39,600
este sub o anumită dimensiune.

719
00:58:42,070 --> 00:58:44,500
Deci, hai să spunem că dimensiunea este de 200,

720
00:58:44,500 --> 00:58:48,130
orice element într-o matrice este sub dimensiunea 200.

721
00:58:48,130 --> 00:58:51,080
Și acest lucru este de fapt foarte realist.

722
00:58:51,080 --> 00:58:58,660
Puteți foarte ușor avea o matrice ca stii totul în ea

723
00:58:58,660 --> 00:59:00,570
va fi mai mică de un numar.

724
00:59:00,570 --> 00:59:07,400
Ca și în cazul în care aveți unele vector absolut masiv sau ceva de genul

725
00:59:07,400 --> 00:59:11,810
dar tu știi totul va fi între 0 și 5,

726
00:59:11,810 --> 00:59:14,790
atunci va fi mult mai rapid de a face acest lucru.

727
00:59:14,790 --> 00:59:17,930
Și legat pe oricare dintre elementele este de 5,

728
00:59:17,930 --> 00:59:21,980
Deci, acest legat, care este cât de mult de memorie ai de gând să fie folosind.

729
00:59:21,980 --> 00:59:26,300
Deci, legat este de 200.

730
00:59:26,300 --> 00:59:32,960
În teorie, există întotdeauna o legat, deoarece un număr întreg poate fi doar până la 4 miliarde de euro,

731
00:59:32,960 --> 00:59:40,600
dar asta e nerealist, deoarece atunci am fi folosind spațiul

732
00:59:40,600 --> 00:59:44,400
pe ordinea de 4 miliarde de euro. Deci asta e nerealist.

733
00:59:44,400 --> 00:59:47,060
Dar aici vom spune legat nostru este de 200.

734
00:59:47,060 --> 00:59:59,570
Trucul pentru a face-o în O a lui n este facem un alt array numit număr de dimensiuni legat.

735
00:59:59,570 --> 01:00:10,470
Deci, de fapt, aceasta este o scurtătură pentru - Eu de fapt nu știu dacă zăngănit face acest lucru.

736
01:00:11,150 --> 01:00:15,330
Dar, în CCG, cel puțin - zăngănit Sunt presupunând că nu prea -

737
01:00:15,330 --> 01:00:18,180
acest lucru va inițializa doar matrice întregul să fie 0s.

738
01:00:18,180 --> 01:00:25,320
Deci, dacă nu vreau să fac asta, atunci am putea face separat pentru (int i = 0;

739
01:00:25,320 --> 01:00:31,500
i <Bound; i + +) și a numărului de [i] = 0;

740
01:00:31,500 --> 01:00:35,260
Deci, acum totul este initializat cu 0.

741
01:00:35,260 --> 01:00:39,570
Am itera peste matrice mea,

742
01:00:39,570 --> 01:00:51,920
și ceea ce fac este Contez numărul fiecărui - Să mergem în jos aici.

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

744
01:00:55,480 --> 01:01:00,010
Ceea ce am de numărare este numărul de apariții ale fiecăruia dintre aceste elemente.

745
01:01:00,010 --> 01:01:03,470
Să adăugăm, de fapt un cuplu mai în aici cu unele repetă.

746
01:01:03,470 --> 01:01:11,070
Deci, valoarea avem aici, valoarea de care se va fi matrice [i].

747
01:01:11,070 --> 01:01:14,850
Deci val ar putea fi 4 sau 8 sau orice altceva.

748
01:01:14,850 --> 01:01:18,870
Și acum mă bazez cât de mulți dintre valoarea pe care le-am văzut,

749
01:01:18,870 --> 01:01:21,230
deci conteaza [val] + +;

750
01:01:21,230 --> 01:01:29,430
După ce se face acest lucru, numărul este de gând să arate ceva de genul 0001.

751
01:01:29,430 --> 01:01:42,190
Să facem conteaza [val] - RESPECTAȚI + 1.

752
01:01:42,190 --> 01:01:48,230
>> Acum, că e doar pentru a explica faptul că suntem incepand de la 0.

753
01:01:48,230 --> 01:01:50,850
Deci, în cazul în care 200 va fi cel mai mare număr noastră,

754
01:01:50,850 --> 01:01:54,720
apoi 0 la 200 este de 201 lucruri.

755
01:01:54,720 --> 01:02:01,540
Deci contează, o să arate ca și cum 00001 pentru că avem un 4.

756
01:02:01,540 --> 01:02:10,210
Apoi vom avea 0001 în cazul în care vom avea un 1 în indicele de 8 count.

757
01:02:10,210 --> 01:02:14,560
Vom avea un 2 în indexul 23 a numărului de.

758
01:02:14,560 --> 01:02:17,630
Vom avea un 2 în indicele a 42-a conta.

759
01:02:17,630 --> 01:02:21,670
Astfel încât să putem folosi numărătoarea.

760
01:02:34,270 --> 01:02:44,920
Deci, num_of_item = numărul [i].

761
01:02:44,920 --> 01:02:52,540
Și astfel, în cazul în care num_of_item este 2, ceea ce înseamnă că doriți să inserați 2 din numărul I

762
01:02:52,540 --> 01:02:55,290
în gama noastră sortate.

763
01:02:55,290 --> 01:03:02,000
Deci, avem nevoie pentru a urmări cât de departe suntem în matrice.

764
01:03:02,000 --> 01:03:05,470
Deci, indicele = 0.

765
01:03:05,470 --> 01:03:09,910
Array - Voi scrie doar.

766
01:03:16,660 --> 01:03:18,020
Numără -

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

768
01:03:28,580 --> 01:03:32,490
Asta e ceea ce vreau? Cred că e ceea ce vreau.

769
01:03:35,100 --> 01:03:38,290
Da, asta arata bine. Bine.

770
01:03:38,290 --> 01:03:43,050
Deci, nu toată lumea înțelege ce scopul de matrice mea contează este?

771
01:03:43,050 --> 01:03:48,140
Acesta este de numărare numărul de apariții ale fiecăruia dintre aceste numere.

772
01:03:48,140 --> 01:03:51,780
Apoi am iterarea peste asta contează matrice,

773
01:03:51,780 --> 01:03:57,190
și poziția lea în matrice contează

774
01:03:57,190 --> 01:04:01,930
este numărul de i e că ar trebui să apară în matrice mea sortate.

775
01:04:01,930 --> 01:04:06,840
De aceea, numărul de 4 va fi 1

776
01:04:06,840 --> 01:04:11,840
și capete de acuzare de 8 este de gând să fie de 1, 23 capete de acuzare de va fi 2.

777
01:04:11,840 --> 01:04:16,900
Deci, asta e modul în care mulți dintre ei doresc să inserați în matrice mea sortate.

778
01:04:16,900 --> 01:04:19,200
Apoi am făcut asta.

779
01:04:19,200 --> 01:04:28,960
Sunt inserarea num_of_item i e în matrice mea sortate.

780
01:04:28,960 --> 01:04:31,670
>> Întrebări?

781
01:04:32,460 --> 01:04:43,100
Și astfel, din nou, aceasta este timpul liniar, deoarece suntem doar iterarea peste această dată,

782
01:04:43,100 --> 01:04:47,470
dar este, de asemenea, liniară în ceea ce acest număr se întâmplă să fie,

783
01:04:47,470 --> 01:04:50,730
și așa mult depinde de ceea ce este legat.

784
01:04:50,730 --> 01:04:53,290
Cu o consolidat de 200, care nu e așa de rău.

785
01:04:53,290 --> 01:04:58,330
Dacă legat dumneavoastra va fi 10.000, atunci asta e un pic mai rău,

786
01:04:58,330 --> 01:05:01,360
dar daca legat dumneavoastră va fi de 4 miliarde de euro, care este complet nerealist

787
01:05:01,360 --> 01:05:07,720
și această matrice va trebui să fie de marimea 4 miliarde de euro, ceea ce este nerealist.

788
01:05:07,720 --> 01:05:10,860
Deci asta e. Întrebări?

789
01:05:10,860 --> 01:05:13,270
[Răspuns studentul nu pot fi auzite] >> Ok.

790
01:05:13,270 --> 01:05:15,710
Am realizat un lucru atunci când am trecut prin.

791
01:05:17,980 --> 01:05:23,720
Eu cred că problema a fost în Lucas lui și, probabil, fiecare dintre noi am văzut.

792
01:05:23,720 --> 01:05:26,330
Am uitat complet.

793
01:05:26,330 --> 01:05:31,040
Singurul lucru pe care am vrut să comenteze este că atunci când ai de a face cu lucruri cum ar fi indici,

794
01:05:31,040 --> 01:05:38,320
nu veți vedea niciodată cu adevărat acest lucru atunci când scrii un pentru buclă,

795
01:05:38,320 --> 01:05:41,120
dar punct de vedere tehnic, ori de câte ori ai de a face cu aceste indici,

796
01:05:41,120 --> 01:05:45,950
ar trebui să destul de mult întotdeauna a face cu numere întregi fără semn.

797
01:05:45,950 --> 01:05:53,850
Motivul pentru acest lucru este atunci când ai de a face cu numere întregi semnate,

798
01:05:53,850 --> 01:05:56,090
așa că, dacă ai 2 numere întregi semnate și le adăugați împreună

799
01:05:56,090 --> 01:06:00,640
și ei sfârșesc prea mare, atunci va termina cu un număr negativ.

800
01:06:00,640 --> 01:06:03,410
Deci, asta e ceea ce este de tip integer overflow.

801
01:06:03,410 --> 01:06:10,500
>> Dacă am adăuga 2 miliarde de 1 miliard, am termina cu negativ 1 miliard.

802
01:06:10,500 --> 01:06:15,480
Asta e modul în care întregi funcționează pe computere.

803
01:06:15,480 --> 01:06:17,510
Deci, problema cu ajutorul -

804
01:06:17,510 --> 01:06:23,500
Asta e bine, cu excepția, dacă se întâmplă să fie redusă 2 miliarde pana se întâmplă să fie 1 miliarde de euro,

805
01:06:23,500 --> 01:06:27,120
atunci aceasta va fi negativă 1 miliard și apoi vom împărți că la 2

806
01:06:27,120 --> 01:06:29,730
și se încheie cu negativ 500 de milioane.

807
01:06:29,730 --> 01:06:33,760
Deci, aceasta este doar o problemă în cazul în care se întâmplă să fie în căutarea printr-o matrice

808
01:06:33,760 --> 01:06:38,070
de miliarde de lucruri.

809
01:06:38,070 --> 01:06:44,050
Dar dacă se întâmplă + mic până la revărsare, atunci este o problemă.

810
01:06:44,050 --> 01:06:47,750
De îndată ce am să le facă nesemnate, apoi 2 miliarde și 1 miliard este de 3 miliarde de euro.

811
01:06:47,750 --> 01:06:51,960
3 miliarde împărțit la 2 este de 1,5 miliarde de euro.

812
01:06:51,960 --> 01:06:55,670
Asa ca imediat ce acestea sunt nesemnat, totul este perfect.

813
01:06:55,670 --> 01:06:59,900
Și așa e, de asemenea, o problemă atunci când scrii pentru bucle,

814
01:06:59,900 --> 01:07:03,940
si de fapt, probabil că o face în mod automat.

815
01:07:09,130 --> 01:07:12,330
Acesta va țipa de fapt, doar la tine.

816
01:07:12,330 --> 01:07:21,610
Deci, în cazul în care acest număr este prea mare pentru a fi în doar un întreg, dar s-ar potrivi într-un număr întreg fără semn,

817
01:07:21,610 --> 01:07:24,970
se va țipa la tine, asa ca asta e motivul pentru nu vă place foarte rula în cauză.

818
01:07:29,150 --> 01:07:34,820
Puteți vedea că un index nu este niciodată de gând să fie negativ,

819
01:07:34,820 --> 01:07:39,220
și așa că atunci când ești iterarea peste o matrice,

820
01:07:39,220 --> 01:07:43,970
poti spune aproape întotdeauna nesemnate int i, dar nu aveți cu adevărat să.

821
01:07:43,970 --> 01:07:47,110
Lucrurile sunt de gând să lucreze destul de mult la fel de bine.

822
01:07:48,740 --> 01:07:50,090
Bine. [Șoptește] Cât e ceasul?

823
01:07:50,090 --> 01:07:54,020
Ultimul lucru pe care am vrut să arate - și voi face doar o foarte repede.

824
01:07:54,020 --> 01:08:03,190
Știi cum ne-am # define astfel încât să putem defini # MAX ca 5 sau ceva?

825
01:08:03,190 --> 01:08:05,940
Să nu facem MAX. # Define RESPECTAȚI ca 200. Asta e ceea ce am făcut înainte.

826
01:08:05,940 --> 01:08:10,380
Care definește o constantă, care este doar de gând să fie copiat și inserat

827
01:08:10,380 --> 01:08:13,010
ori de câte ori se întâmplă să scrie legat.

828
01:08:13,010 --> 01:08:18,189
>> Astfel încât să putem face de fapt mai mult cu # definește.

829
01:08:18,189 --> 01:08:21,170
Putem defini # funcții.

830
01:08:21,170 --> 01:08:23,410
Ei nu sunt cu adevărat funcții, dar vom numi funcții.

831
01:08:23,410 --> 01:08:36,000
Un exemplu ar fi ceva de genul MAX (x, y) este definit ca (x <y y:? X). Bine.

832
01:08:36,000 --> 01:08:40,660
Deci, ar trebui să te obișnuiești cu sintaxa operatorul ternar,

833
01:08:40,660 --> 01:08:49,029
dar este mai mic decât y x? Întoarceți-y, x reveni altceva.

834
01:08:49,029 --> 01:08:54,390
Deci, puteți vedea puteți face această funcție separată,

835
01:08:54,390 --> 01:09:01,399
și funcția ar putea fi ca bool MAX are 2 argumente, returnați.

836
01:09:01,399 --> 01:09:08,340
Aceasta este una dintre cele mai comune pe care le văd făcut așa. Noi le numim macrocomenzi.

837
01:09:08,340 --> 01:09:11,790
Aceasta este o macrocomandă.

838
01:09:11,790 --> 01:09:15,859
Acesta este doar sintaxa pentru ea.

839
01:09:15,859 --> 01:09:18,740
Puteți scrie o macrocomandă pentru a face tot ce vrei.

840
01:09:18,740 --> 01:09:22,649
Veți vedea frecvent macro-uri pentru depanare printfs si alte chestii.

841
01:09:22,649 --> 01:09:29,410
Deci, un tip de printf, sunt constante speciale în C ca subliniere LINE subliniere,

842
01:09:29,410 --> 01:09:31,710
2 subliniază LINE subliniere,

843
01:09:31,710 --> 01:09:37,550
și nu există, de asemenea, cred ca 2 subliniaza FUNC. Asta ar putea fi ea. Ceva de genul asta.

844
01:09:37,550 --> 01:09:40,880
Aceste lucruri vor fi înlocuite cu denumirea funcției

845
01:09:40,880 --> 01:09:42,930
sau numărul liniei pe care esti pe.

846
01:09:42,930 --> 01:09:48,630
Cele mai frecvente, scrii printfs depanare că aici am putea apoi a scrie pur și simplu

847
01:09:48,630 --> 01:09:54,260
DEBUG și va imprima numărul de linie și funcția pe care I se întâmplă să fie în

848
01:09:54,260 --> 01:09:57,020
că a întâlnit această declarație DEBUG.

849
01:09:57,020 --> 01:09:59,550
Și puteți imprima, de asemenea, alte lucruri.

850
01:09:59,550 --> 01:10:05,990
Deci, un lucru pe care ar trebui să fiți atenți pentru este dacă se întâmplă să definească # DOUBLE_MAX

851
01:10:05,990 --> 01:10:11,380
ca ceva de genul 2 * 2 * y și x.

852
01:10:11,380 --> 01:10:14,310
Deci, pentru un motiv, se întâmplă să faci asta foarte mult.

853
01:10:14,310 --> 01:10:16,650
Deci, face o macrocomandă.

854
01:10:16,650 --> 01:10:18,680
Aceasta este de fapt rupt.

855
01:10:18,680 --> 01:10:23,050
Mi-ar numi de a face ceva de genul DOUBLE_MAX (3, 6).

856
01:10:23,050 --> 01:10:27,530
Deci, ce ar trebui să fie returnate?

857
01:10:28,840 --> 01:10:30,580
[Elev] 12.

858
01:10:30,580 --> 01:10:34,800
Da, ar trebui să fie returnate 12, și 12 este returnat.

859
01:10:34,800 --> 01:10:43,350
3 se înlocuiește pentru x, 6 se înlocuiește pentru y, și ne întoarcem 2 * 6, care este de 12.

860
01:10:43,350 --> 01:10:47,710
Acum, ce zici de asta? Ce ar trebui să fie returnate?

861
01:10:47,710 --> 01:10:50,330
[Elev] 14. În mod ideal >>, 14.

862
01:10:50,330 --> 01:10:55,290
Problema este că modul în care hash definește locul de muncă, nu uitați că este o copie literală și lipire

863
01:10:55,290 --> 01:11:00,160
de tot ceea ce destul de mult, deci ce acest lucru se întâmplă să fie interpretat în sensul că

864
01:11:00,160 --> 01:11:11,270
este de 3 mai puțin de 1 plus 6, de 2 ori 1 plus 6, 2 ori 3.

865
01:11:11,270 --> 01:11:19,780
>> Deci, pentru acest motiv aproape întotdeauna infasurati totul în paranteze.

866
01:11:22,180 --> 01:11:25,050
Orice variabilă, aproape întotdeauna înveliți în paranteze.

867
01:11:25,050 --> 01:11:29,570
Există cazuri în care nu trebuie să, așa cum știu că nu am nevoie să faci asta aici

868
01:11:29,570 --> 01:11:32,110
pentru că este mai puțin destul de mult întotdeauna doar de gând să lucreze,

869
01:11:32,110 --> 01:11:34,330
deși faptul că ar putea să nu fie chiar adevărat.

870
01:11:34,330 --> 01:11:41,870
Dacă există ceva ridicol ca DOUBLE_MAX (1 == 2),

871
01:11:41,870 --> 01:11:49,760
apoi că va fi înlocuit cu 3 mai puțin de 1 egal este egal cu 2,

872
01:11:49,760 --> 01:11:53,460
și așa mai departe, apoi se va face 3 mai puțin de 1, nu ca egal 2,

873
01:11:53,460 --> 01:11:55,620
care nu este ceea ce ne dorim.

874
01:11:55,620 --> 01:12:00,730
Deci, în scopul de a preveni orice probleme de operator de precedență,

875
01:12:00,730 --> 01:12:02,870
întotdeauna înveliți în paranteze.

876
01:12:03,290 --> 01:12:07,700
Bine. Și asta e tot, 5:30.

877
01:12:08,140 --> 01:12:12,470
Dacă aveți orice întrebări cu privire PSET, anunțați-ne.

878
01:12:12,470 --> 01:12:18,010
Ar trebui să fie distractiv, iar ediția hacker, de asemenea, este mult mai realist

879
01:12:18,010 --> 01:12:22,980
decât ediția hacker de anul trecut, așa că am speranța că o mulțime dintre voi încerca.

880
01:12:22,980 --> 01:12:26,460
Anul trecut a fost foarte copleșitoare.

881
01:12:28,370 --> 01:12:30,000
>> [CS50.TV]