1
00:00:00,000 --> 00:00:02,570
[Powered by Google Translate] [3. szakasz - További Kényelmes]

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

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

4
00:00:07,310 --> 00:00:12,700
>> Tehát az első kérdés furcsán hangzik.

5
00:00:12,700 --> 00:00:17,480
GDB lehetővé teszi, hogy "debug" egy program, de konkrétan mit jelent ez engedi csinálni?

6
00:00:17,480 --> 00:00:22,590
Fogok válaszolni, hogy az egyik, és nem tudom, hogy mi pontosan az várható volt,

7
00:00:22,590 --> 00:00:27,910
úgyhogy azt hiszem, hogy valami mentén ez lehetővé teszi, lépésről lépésre

8
00:00:27,910 --> 00:00:31,540
séta a program, kölcsönhatásba vele, váltással változók, tegyenek meg mindent ezek a dolgok -

9
00:00:31,540 --> 00:00:34,270
Alapvetően teljesen ellenőrzése a program végrehajtásának

10
00:00:34,270 --> 00:00:38,410
és vizsgáljuk meg egy adott részét a program végrehajtása.

11
00:00:38,410 --> 00:00:43,030
Tehát ezek a jellemzők teszik hibakeresés dolgokat.

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

13
00:00:44,830 --> 00:00:50,520
Miért bináris keresés előírják, hogy a tömb kell válogatni?

14
00:00:50,520 --> 00:00:53,360
Ki akar válaszolni?

15
00:00:56,120 --> 00:01:00,070
[Hallgató] Mert ez nem működik, ha nincs rendezve. >> Igen. [Nevetés]

16
00:01:00,070 --> 00:01:04,910
Ha ez nem válogatták szét, akkor lehetetlen osztott ketté

17
00:01:04,910 --> 00:01:07,850
és tudom, hogy mindent a bal kevésbé, és mindent a megfelelő

18
00:01:07,850 --> 00:01:10,490
nagyobb, mint a középső érték.

19
00:01:10,490 --> 00:01:12,790
Tehát meg kell rendezni.

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

21
00:01:14,170 --> 00:01:17,570
Miért van buborék egyfajta O n négyzetes?

22
00:01:17,570 --> 00:01:23,230
Valaki 1. akar adni egy nagyon gyors, magas szintű áttekintést, hogy mi buborék rendezés?

23
00:01:25,950 --> 00:01:33,020
[Hallgató] Ön alapvetően végig minden elem, és ellenőrizze az első néhány elemet.

24
00:01:33,020 --> 00:01:37,150
Ha ők ki hol cserélni őket, akkor ellenőrizze a következő néhány elemet, és így tovább.

25
00:01:37,150 --> 00:01:40,770
Amikor eléred a végén, akkor tudja, hogy a legnagyobb elem kerül a végén,

26
00:01:40,770 --> 00:01:42,750
így figyelmen kívül hagyja, hogy az egyik, akkor tovább megy keresztül,

27
00:01:42,750 --> 00:01:48,490
és minden egyes alkalommal meg kell ellenőrizni eggyel kevesebb elemet mindaddig, amíg nem történik változás. >> Igen.

28
00:01:48,490 --> 00:01:58,470
Úgy hívják bubble sort, mert ha megfordítja a tömb az oldalán, így ez felfelé és lefelé, függőleges,

29
00:01:58,470 --> 00:02:03,100
majd a nagy értékek aljára és a kis értékek buborék fel a csúcsra.

30
00:02:03,100 --> 00:02:05,210
Így kapta a nevét.

31
00:02:05,210 --> 00:02:08,220
És igen, csak megy keresztül.

32
00:02:08,220 --> 00:02:11,190
Folyton megy keresztül a tömb, csere a nagyobb érték

33
00:02:11,190 --> 00:02:14,040
hogy a legnagyobb értékeket az alján.

34
00:02:14,040 --> 00:02:17,500
>> Miért van az O n négyzetes?

35
00:02:18,690 --> 00:02:24,620
Először is, nem akárki azt akarom mondani, miért O n négyzetes?

36
00:02:24,620 --> 00:02:28,760
[Hallgató] Mert minden futam megy n-szer.

37
00:02:28,760 --> 00:02:32,100
Csak akkor lehetünk benne, hogy már megtette a legnagyobb elem egészen,

38
00:02:32,100 --> 00:02:35,230
akkor meg kell ismételni, hogy minél több elemet. >> Igen.

39
00:02:35,230 --> 00:02:41,800
Tehát ne feledje, milyen nagy O jelent, és milyen nagy Omega jelent.

40
00:02:41,800 --> 00:02:50,560
A nagy O olyan, mint a felső korlát milyen lassan tud ténylegesen futni.

41
00:02:50,560 --> 00:02:58,990
Tehát azzal, hogy a O n négyzetes, nem O n különben nem lenne képes futtatni

42
00:02:58,990 --> 00:03:02,640
lineáris időben, de O n-CubeD

43
00:03:02,640 --> 00:03:06,390
mert határolja O n-kocka.

44
00:03:06,390 --> 00:03:12,300
Ha ez által határolt O n négyzetes, akkor ez által is határolt n kocka.

45
00:03:12,300 --> 00:03:20,280
Így, ha n szögletes, és az abszolút legrosszabb esetben meg jobban, mint n négyzetnagyságrendű,

46
00:03:20,280 --> 00:03:22,830
ezért ez O n négyzeten.

47
00:03:22,830 --> 00:03:31,200
Tehát, ha csekély matematikai, hogyan jön ki, hogy n négyzetes,

48
00:03:31,200 --> 00:03:40,530
ha van öt dolog, ami a mi listán, az első alkalom, hogy hány swap lehetne esetleg kell tenni

49
00:03:40,530 --> 00:03:47,170
annak érdekében, hogy ezt? Nézzük valójában csak -

50
00:03:47,170 --> 00:03:52,040
Hány swap fogunk van, hogy az első távon a buborék sort a tömb?

51
00:03:52,040 --> 00:03:53,540
[Hallgató] n - 1. >> Igen.

52
00:03:53,540 --> 00:03:58,340
>> Ha van 5 elem, mi lesz szükség, hogy n - 1.

53
00:03:58,340 --> 00:04:01,100
Aztán a másik, hogy hány swap fogunk van, hogy?

54
00:04:01,100 --> 00:04:03,440
[Hallgató] n - 2. >> Igen.

55
00:04:03,440 --> 00:04:11,640
És a harmadik lesz n - 3, majd az egyszerűség kedvéért fogom írni az elmúlt két

56
00:04:11,640 --> 00:04:15,270
ahogy akkor lesz szükségünk, hogy a 2 és 1 swap swap.

57
00:04:15,270 --> 00:04:19,899
Azt hiszem, az utolsó lehet, hogy valójában nem kell, hogy megtörténjen.

58
00:04:19,899 --> 00:04:22,820
Ez a csere? Nem tudom.

59
00:04:22,820 --> 00:04:26,490
Tehát ezek teljes összege swap vagy legalább összehasonlításokat meg kell tenni.

60
00:04:26,490 --> 00:04:29,910
Még ha nem csere, akkor is kell összehasonlítani az értékeket.

61
00:04:29,910 --> 00:04:33,910
Tehát vannak n - 1 összehasonlítás az első távon a tömb.

62
00:04:33,910 --> 00:04:42,050
Ha rendezni ezeket a dolgokat, hadd valójában, hogy azt hat a dolgok így a dolgok verem szépen,

63
00:04:42,050 --> 00:04:44,790
majd én megteszem 3, 2, 1.

64
00:04:44,790 --> 00:04:49,910
Szóval csak átrendezése ezen összegek, szeretnénk látni, hogy hány összehasonlítást teszünk

65
00:04:49,910 --> 00:04:52,700
az egész algoritmus.

66
00:04:52,700 --> 00:04:56,550
Tehát ha ezek a srácok, hogy itt lenn,

67
00:04:56,550 --> 00:05:07,470
akkor még mindig csak összefoglalva azonban sok összehasonlítás volt.

68
00:05:07,470 --> 00:05:13,280
De ha összeadjuk ezeket, és összeadjuk ezeket és összeadjuk ezeket,

69
00:05:13,280 --> 00:05:18,130
ez még mindig ugyanaz a probléma. Csak Összefoglalva e bizonyos csoportok.

70
00:05:18,130 --> 00:05:22,400
>> Szóval most mi összeadásával 3 n években. Ez nem csak a 3 n.

71
00:05:22,400 --> 00:05:27,650
Ez mindig lesz n / 2 n években.

72
00:05:27,650 --> 00:05:29,430
Tehát itt történik, hogy 6.

73
00:05:29,430 --> 00:05:34,830
Ha lenne 10 dolog, akkor is ezt a csoportosítást 5 különböző pár dolog

74
00:05:34,830 --> 00:05:37,180
és a végén az n + n + n + n + n.

75
00:05:37,180 --> 00:05:45,840
Szóval mindig lesz, hogy n / 2 n-k, és így ez a mi jot ki, hogy n négyzetes / 2.

76
00:05:45,840 --> 00:05:48,890
És annak ellenére, hogy ez a tényező a fele, ami történik, hogy jöjjön

77
00:05:48,890 --> 00:05:54,190
mert az a tény, hogy az átmenő minden iterációs felett a tömb, amit összehasonlításba 1 kevésbé

78
00:05:54,190 --> 00:05:58,040
annak érdekében, hogy ez hogyan kap a több mint 2, de ez még mindig n faragva.

79
00:05:58,040 --> 00:06:01,650
Nem érdekel az állandó tényező fél.

80
00:06:01,650 --> 00:06:07,760
Szóval egy csomó nagy O dolgok, mint ez támaszkodik csak egyfajta ezt a fajta matematika,

81
00:06:07,760 --> 00:06:12,260
Ennek összegek számtani és mértani sorozat stuff,

82
00:06:12,260 --> 00:06:17,750
de a legtöbbjük a tanfolyam elég egyértelmű.

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

84
00:06:19,290 --> 00:06:24,430
Miért van beszúrási sort az Omega n? Mit jelent omega jelent?

85
00:06:24,430 --> 00:06:27,730
[Két diák beszél egyszerre - érthetetlen] >> Igen.

86
00:06:27,730 --> 00:06:30,630
Omega lehet gondolni, mint az alsó korlát.

87
00:06:30,630 --> 00:06:36,550
>> Tehát nem számít, mennyire hatékony a beszúrási sort algoritmus,

88
00:06:36,550 --> 00:06:41,810
függetlenül attól, hogy a lista, ami telt el, azt mindig meg összehasonlítandó legalább n dolgokat

89
00:06:41,810 --> 00:06:44,620
vagy nem iterációkhoz n dolgokat.

90
00:06:44,620 --> 00:06:47,280
Miért van ez?

91
00:06:47,280 --> 00:06:51,190
[Hallgató] Mert ha a lista már rendezve, akkor az első iterációs

92
00:06:51,190 --> 00:06:54,080
csak akkor tudjuk garantálni, hogy az első elem a sorban,

93
00:06:54,080 --> 00:06:56,490
és a második iteráció csak akkor lehet garantálni az első kettő

94
00:06:56,490 --> 00:07:00,010
azért, mert nem tudja, hogy a többi lista rendezésre. >> Igen.

95
00:07:00,010 --> 00:07:08,910
Ha át egy teljesen rendezett lista legalább van, hogy menjen át az összes elemet

96
00:07:08,910 --> 00:07:12,180
látni, hogy semmit sem kell mozgatni.

97
00:07:12,180 --> 00:07:14,720
Így halad át a listát, és azt mondja jaj, ezt már rendezve,

98
00:07:14,720 --> 00:07:18,240
lehetetlen, hogy tudja, ez rendezve amíg be nem minden elem

99
00:07:18,240 --> 00:07:20,660
látni, hogy vannak rendezve sorrendben.

100
00:07:20,660 --> 00:07:25,290
Tehát az alsó korlát elhelyezésének rendezés Omega n.

101
00:07:25,290 --> 00:07:28,210
Mi a legrosszabb futási ideje merge sort,

102
00:07:28,210 --> 00:07:31,390
legrosszabb esetben pedig nagy O megint?

103
00:07:31,390 --> 00:07:37,660
Így a legrosszabb forgatókönyv esetén hogyan merge sort futni?

104
00:07:42,170 --> 00:07:43,690
[Hallgató] N log n. >> Igen.

105
00:07:43,690 --> 00:07:49,990
A leggyorsabb általános rendezési algoritmusok n log n. Nem lehet jobban csinálni.

106
00:07:51,930 --> 00:07:55,130
>> Vannak speciális esetek, és ha van ideje ma - de mi talán won't -

107
00:07:55,130 --> 00:07:59,330
láttuk az egyik, hogy nem jobb, mint az n log n.

108
00:07:59,330 --> 00:08:04,050
De általános esetben, akkor nem jobb, mint n log n.

109
00:08:04,050 --> 00:08:09,680
És merge sort történik, hogy az, amit tudnia kell, erre a tanfolyamra, ami n log n.

110
00:08:09,680 --> 00:08:13,260
És így fogunk ténylegesen végrehajtó ma.

111
00:08:13,260 --> 00:08:18,070
És végül, az nem több, mint három mondatban, hogyan működik kiválasztási rendezési munkát?

112
00:08:18,070 --> 00:08:20,370
Vajon valaki akar válaszolni, és én számold össze a mondatok

113
00:08:20,370 --> 00:08:22,390
mert ha megy át 3 -

114
00:08:25,530 --> 00:08:28,330
Tudja valaki emlékszik kiválasztás sort?

115
00:08:31,280 --> 00:08:37,809
Selection sort általában elég könnyű emlékezni, csak a nevét.

116
00:08:37,809 --> 00:08:45,350
Csak iterációkhoz a tömb, megtalálja, amit a legnagyobb érték vagy a legkisebb -

117
00:08:45,350 --> 00:08:47,290
bármilyen sorrendben, amit válogatás be

118
00:08:47,290 --> 00:08:50,750
Tehát mondjuk mi válogatás a legkisebbtől a legnagyobb.

119
00:08:50,750 --> 00:08:55,250
Te iterációkhoz a tömb, keresve függetlenül minimum elem,

120
00:08:55,250 --> 00:08:59,750
válassza ki, és aztán csak csere azt bármi is van az első helyen.

121
00:08:59,750 --> 00:09:04,090
És aztán a második lépésben az array, keresse meg a minimális elem újra,

122
00:09:04,090 --> 00:09:07,490
jelölje ki, majd cserélni azt, hogy mi van a második pozíciót.

123
00:09:07,490 --> 00:09:10,650
Tehát csak a szedés és kiválasztja a minimális értékek

124
00:09:10,650 --> 00:09:16,050
, és helyezze azokat az első a tömb, amíg van rendezve.

125
00:09:19,210 --> 00:09:21,560
Kérdések az?

126
00:09:21,560 --> 00:09:25,710
>> Ezek elkerülhetetlenül megjelennek a formában van, hogy töltse ki, amikor benyújtásakor Pset.

127
00:09:29,010 --> 00:09:32,360
Ezek alapvetően a választ e.

128
00:09:32,360 --> 00:09:34,230
Oké, szóval most már kódolás problémákat.

129
00:09:34,230 --> 00:09:40,140
Már küldött e-mailben - Nem valaki nem kap, hogy az e-mailt? Oké.

130
00:09:40,140 --> 00:09:46,630
Már küldött e-mailben a teret, hogy mi fogunk használni,

131
00:09:46,630 --> 00:09:52,120
és ha rákattint a nevem - úgyhogy azt hiszem, leszek az alján

132
00:09:52,120 --> 00:09:57,170
mert a visszafelé r - de ha rákattint a nevemet látni fogod, 2 javítások.

133
00:09:57,170 --> 00:10:02,650
Felülvizsgálat 1 lesz már a vágólapra másolni a kódot Spaces

134
00:10:02,650 --> 00:10:06,900
a keresési dolgot fogsz végre kell hajtania.

135
00:10:06,900 --> 00:10:10,540
És Revision 2 lesz az a fajta dolog, hogy mi végre után.

136
00:10:10,540 --> 00:10:15,770
Szóval, akkor kattintson a Revision 1-es és az innen való munka.

137
00:10:17,350 --> 00:10:22,060
És most szeretnénk végrehajtani a bináris keresés.

138
00:10:22,060 --> 00:10:26,470
>> Akar valaki csak adni pszeudokód magas szintű magyarázat

139
00:10:26,470 --> 00:10:31,440
hogy mit fogunk tenni, hogy a keresés? Igen.

140
00:10:31,440 --> 00:10:36,170
[Hallgató] Csak vegye a közepén, a tömb, és nézd meg, hogy mit keres

141
00:10:36,170 --> 00:10:38,650
kevesebb, mint a, vagy annál több.

142
00:10:38,650 --> 00:10:41,080
És ha ez kevesebb, akkor menj a felét, ami kevesebb,

143
00:10:41,080 --> 00:10:44,750
és ha ez több, akkor menj a felére több, és megismétlem, hogy amíg csak kap egy dolog.

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

145
00:10:46,570 --> 00:10:51,320
Figyeljük meg, hogy a mi számok tömb már rendezett,

146
00:10:51,320 --> 00:10:57,190
és így ez azt jelenti, hogy mi is kihasználni ezt, és tudtunk először ellenőrizze,

147
00:10:57,190 --> 00:11:00,390
oké, én keresem a számot 50.

148
00:11:00,390 --> 00:11:03,720
Így tudok menni a középső.

149
00:11:03,720 --> 00:11:07,380
Közel nehéz meghatározni, ha ez még számos dolgot,

150
00:11:07,380 --> 00:11:10,820
de mondjuk mi mindig csonkolja a közepén.

151
00:11:10,820 --> 00:11:14,420
Tehát itt van 8 dolog, így a középső lenne 16.

152
00:11:14,420 --> 00:11:17,330
Ezt keresem: 50, így 50-16-nál nagyobb.

153
00:11:17,330 --> 00:11:21,310
Szóval most alapvetően kezelni a tömb mivel ezek az elemek.

154
00:11:21,310 --> 00:11:23,450
Tudok dobni mindent, 16-tól vége.

155
00:11:23,450 --> 00:11:27,440
Most a tömb csak a 4 elem, és ismételje meg.

156
00:11:27,440 --> 00:11:31,910
Így aztán szeretné megtalálni a középső újra, ami lesz 42.

157
00:11:31,910 --> 00:11:34,730
42 kevesebb, mint 50, így tudok dobni ezt a két elemet.

158
00:11:34,730 --> 00:11:36,890
Ez az én maradék tömb.

159
00:11:36,890 --> 00:11:38,430
Meg fogom találni a középső újra.

160
00:11:38,430 --> 00:11:42,100
Azt hiszem, 50 volt egy rossz példa, mert én mindig eldobni a dolgokat a baloldalt,

161
00:11:42,100 --> 00:11:48,280
de ugyanaz az intézkedés, ha én keresek valamit

162
00:11:48,280 --> 00:11:52,100
és ez kevesebb, mint az elem Én jelenleg vizsgálja,

163
00:11:52,100 --> 00:11:55,080
akkor fogom eldobni mindent jobbra.

164
00:11:55,080 --> 00:11:58,150
Tehát most kell végrehajtani, hogy a.

165
00:11:58,150 --> 00:12:02,310
Figyeljük meg, hogy át kell adni a méret.

166
00:12:02,310 --> 00:12:06,730
Azt is nem kell a kemény-kód méret.

167
00:12:06,730 --> 00:12:11,640
Tehát, ha megszabadulni a # define -

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

169
00:12:21,430 --> 00:12:27,180
Hogyan lehet szépen kitalálni, hogy mi a méret a számok tömb jelenleg?

170
00:12:27,180 --> 00:12:30,950
>> Hány eleme van a számok tömb?

171
00:12:30,950 --> 00:12:33,630
[Hallgató] Számok, konzolok,. Hossz?

172
00:12:33,630 --> 00:12:36,600
[Bowden] Ez nem létezik C.

173
00:12:36,600 --> 00:12:38,580
Szüksége. Hossza.

174
00:12:38,580 --> 00:12:42,010
Tömbök nincs tulajdonságai így nincs length tulajdonság tömbök

175
00:12:42,010 --> 00:12:45,650
hogy majd csak Önnek azonban sokáig ez történik lennie.

176
00:12:48,180 --> 00:12:51,620
[Hallgató] Lásd mennyi memória van, és osszuk el, hogy mennyi - >> Igen.

177
00:12:51,620 --> 00:12:55,810
Szóval, hogyan lehet látni, hogy mennyi memória van? >> [Hallgató] sizeof. >> Ja, sizeof.

178
00:12:55,810 --> 00:13:01,680
Sizeof az üzemeltető, hogy fogja vissza a méret a számok tömb.

179
00:13:01,680 --> 00:13:10,060
És ez lesz azonban sok egész szám van akkora értéke

180
00:13:10,060 --> 00:13:14,050
mivel ez mennyi memóriát ez ténylegesen munkába.

181
00:13:14,050 --> 00:13:17,630
Tehát, ha azt akarom, hogy néhány dolog a tömbben,

182
00:13:17,630 --> 00:13:20,560
akkor megyek ketté akarja osztani a méret egy egész szám.

183
00:13:22,820 --> 00:13:26,010
Oké. Annak érdekében, hogy lehetővé teszi számomra át méretben itt.

184
00:13:26,010 --> 00:13:29,430
Miért kell átadni a méret egyáltalán?

185
00:13:29,430 --> 00:13:38,570
Miért nem tudok csak tedd fel ide int size = sizeof (szénakazalban) / sizeof (int)?

186
00:13:38,570 --> 00:13:41,490
Miért ez nem működik?

187
00:13:41,490 --> 00:13:44,470
[Hallgató] Ez nem egy globális változót.

188
00:13:44,470 --> 00:13:51,540
[Bowden] Haystack létezik, és mi halad számok szénaboglya,

189
00:13:51,540 --> 00:13:54,700
és ez egyfajta előrevetítette, hogy mi jön. Igen.

190
00:13:54,700 --> 00:14:00,170
[Hallgató] Haystack csak az arra való utalás, így visszatér, hogy milyen nagy ez az utalás.

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

192
00:14:02,150 --> 00:14:09,000
Kétlem, előadás, hogy már látták a stack igazából még, ugye?

193
00:14:09,000 --> 00:14:11,270
Már most beszélt róla.

194
00:14:11,270 --> 00:14:16,090
Tehát a verem, ahol az összes változót fognak tárolni.

195
00:14:16,090 --> 00:14:19,960
>> Bármely memória van kiutalt lokális változók megy a stack,

196
00:14:19,960 --> 00:14:24,790
és minden funkciót kap saját helyet a stack, saját verem keret mi a neve.

197
00:14:24,790 --> 00:14:31,590
Tehát fő megvan a maga stack frame, és a benne lévő fog létezni e számok tömb,

198
00:14:31,590 --> 00:14:34,270
és ez lesz a mérete sizeof (szám).

199
00:14:34,270 --> 00:14:38,180
Ez megy, hogy a számok mérete osztva méretű elemek,

200
00:14:38,180 --> 00:14:42,010
de ez az összes életét tartozó fontosabb a stack frame.

201
00:14:42,010 --> 00:14:45,190
Mikor hívjuk keresés keressen kap saját stack frame,

202
00:14:45,190 --> 00:14:48,840
saját hely tárolni az összes helyi változók.

203
00:14:48,840 --> 00:14:56,420
De ezek az érvek - így szénakazalban nem másolatot a teljes tömb.

204
00:14:56,420 --> 00:15:00,990
Mi nem adja át az egész tömb egy példányt a keresést.

205
00:15:00,990 --> 00:15:04,030
Csak halad hivatkozást, hogy a tömb.

206
00:15:04,030 --> 00:15:11,470
Így search érhetik ezeket a számokat ezen keresztül referencia.

207
00:15:11,470 --> 00:15:17,100
Ez még mindig a dolgokat, hogy él benne a fő a stack frame,

208
00:15:17,100 --> 00:15:22,990
de alapvetően, ha eljutunk mutató, amely minden bizonnyal hamarosan,

209
00:15:22,990 --> 00:15:24,980
ez az, amit pointerek vannak.

210
00:15:24,980 --> 00:15:29,400
Mutatók csak hivatkozásokat a dolgokat, és tudod használni mutatókat elérni dolgokat

211
00:15:29,400 --> 00:15:32,030
, amelyek más dolgok "stack kereteket.

212
00:15:32,030 --> 00:15:37,660
Így, bár a számok helyi fő, akkor is elérheti keresztül ez a mutató.

213
00:15:37,660 --> 00:15:41,770
De mivel ez csak egy mutató, és ez csak egy referencia,

214
00:15:41,770 --> 00:15:45,040
sizeof (szénakazalban) éppen visszatérjen a méret a referencia is.

215
00:15:45,040 --> 00:15:47,950
Nem tér vissza a mérete a dolog, ez mutat.

216
00:15:47,950 --> 00:15:51,110
Nem tér vissza a tényleges mérete a számok.

217
00:15:51,110 --> 00:15:55,660
És így ez nem fog működni, ahogy jónak látja.

218
00:15:55,660 --> 00:15:57,320
>> Kérdések az?

219
00:15:57,320 --> 00:16:03,250
Mutatók fognak tűnni a jelentősen több véres részletesebben az elkövetkezendő hetek során.

220
00:16:06,750 --> 00:16:13,740
És ez az, amiért egy csomó dolog, amit látsz, a legtöbb keresési dolgokat, vagy rendezni a dolgokat,

221
00:16:13,740 --> 00:16:16,990
ők szinte minden lesz szüksége, hogy a tényleges mérete a tömb,

222
00:16:16,990 --> 00:16:20,440
mert a C, fogalmunk sincs, hogy mi a mérete a tömb.

223
00:16:20,440 --> 00:16:22,720
Manuálisan kell átadni be!

224
00:16:22,720 --> 00:16:27,190
És nem lehet manuálisan át az egész tömb, mert te csak halad a referencia

225
00:16:27,190 --> 00:16:30,390
és nem kap a méretét a referencia.

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

227
00:16:32,300 --> 00:16:38,160
Tehát most azt akarjuk, hogy végre mi is magyarázta előtt.

228
00:16:38,160 --> 00:16:41,530
Lehet dolgozni rajta egy kicsit,

229
00:16:41,530 --> 00:16:45,250
és akkor nem kell aggódnia, mindent tökéletesen 100%-os dolgozik.

230
00:16:45,250 --> 00:16:51,410
Csak írd fel a fele pszeudokód, hogy hogyan gondolja, hogy működnie kell.

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

232
00:16:53,630 --> 00:16:56,350
Nem kell teljesen kész ezzel még.

233
00:16:56,350 --> 00:17:02,380
De nem mindenki érzi, kényelmes, amit eddig,

234
00:17:02,380 --> 00:17:05,599
mintha tudunk dolgozni együtt?

235
00:17:05,599 --> 00:17:09,690
Akar valaki önkéntes? Vagy véletlenszerűen felvenni.

236
00:17:12,680 --> 00:17:18,599
Nem kell, hogy jobbra minden olyan intézkedés, hanem valami, amit lehet módosítani egy működő állapotba.

237
00:17:18,599 --> 00:17:20,720
[Hallgató] Persze. >> Oké.

238
00:17:20,720 --> 00:17:27,220
Szóval lehet menteni a felülvizsgálat kattintva a kis Mentés ikonra.

239
00:17:27,220 --> 00:17:29,950
Igazad Ramya, ugye? >> [Hallgató] Igen. >> [Bowden] Oké.

240
00:17:29,950 --> 00:17:35,140
Szóval most megtekintheti felülvizsgálata és mindenki húzza fel a felülvizsgálatot.

241
00:17:35,140 --> 00:17:38,600
És itt van - Oké.

242
00:17:38,600 --> 00:17:43,160
Így Ramya elment a rekurzív megoldás, ami mindenképpen érvényes megoldás.

243
00:17:43,160 --> 00:17:44,970
Kétféle módon lehet ezt a problémát.

244
00:17:44,970 --> 00:17:48,060
Akkor sem csinálni iteratív vagy rekurzív.

245
00:17:48,060 --> 00:17:53,860
A legtöbb probléma a találkozás, hogy lehet tenni rekurzívan is elvégezhető iterációval.

246
00:17:53,860 --> 00:17:58,510
Tehát itt megcsináltuk rekurzívan.

247
00:17:58,510 --> 00:18:03,730
>> Vajon valaki akarja meghatározni, hogy mit jelent, hogy egy függvény rekurzív?

248
00:18:07,210 --> 00:18:08,920
[Hallgató] Ha van egy függvényhívás maga

249
00:18:08,920 --> 00:18:13,470
majd hívja magát, amíg ki nem jön a valódi és igaz. >> Igen.

250
00:18:13,470 --> 00:18:17,680
A rekurzív függvény csak olyan funkció, amely saját magát hívja meg.

251
00:18:17,680 --> 00:18:24,140
Van három nagy dolog, hogy egy rekurzív függvény kell.

252
00:18:24,140 --> 00:18:27,310
Az első természetesen, ez nevezi magát.

253
00:18:27,310 --> 00:18:29,650
A második az alapeset.

254
00:18:29,650 --> 00:18:33,390
Tehát egy bizonyos ponton a funkciót le kell állítania a nevezte magát,

255
00:18:33,390 --> 00:18:35,610
és ez az, amit az alap ügyben a.

256
00:18:35,610 --> 00:18:43,860
Tehát itt tudjuk, hogy le kell állítani, meg kell adja fel a keresést

257
00:18:43,860 --> 00:18:48,150
amikor a kezdő értéke end - és akkor megy át, hogy ez mit jelent.

258
00:18:48,150 --> 00:18:52,130
De végül, az utolsó dolog, ami fontos a rekurzív funkciók:

259
00:18:52,130 --> 00:18:59,250
a funkciókat kell valahogy megközelíteni az alapeset.

260
00:18:59,250 --> 00:19:04,140
Mint ha nem is naprakésszé semmit, ha csinál a második rekurzív hívás

261
00:19:04,140 --> 00:19:07,880
ha szó szerint csak a funkció meghívása újra ugyanazokat az érveket

262
00:19:07,880 --> 00:19:10,130
és nem globális változók megváltoztak, vagy ilyesmi,

263
00:19:10,130 --> 00:19:14,430
soha nem éri el az alap esetben, ebben az esetben, hogy ez rossz.

264
00:19:14,430 --> 00:19:17,950
Ez lesz egy végtelen rekurzió és verem túlcsordulás.

265
00:19:17,950 --> 00:19:24,330
De itt azt látjuk, hogy a frissítés történik, mivel mi frissítése kezdeni + end / 2,

266
00:19:24,330 --> 00:19:28,180
vagyunk frissítése vége érv itt vagyunk frissítése kezdetét érvet itt.

267
00:19:28,180 --> 00:19:32,860
Tehát minden rekurzív hívás vagyunk frissítése valamit. Oké.

268
00:19:32,860 --> 00:19:38,110
Szeretné járni hozzánk a megoldás? >> Persze.

269
00:19:38,110 --> 00:19:44,270
Én vagyok a SearchHelp úgy, hogy minden alkalommal, amikor ezt a funkciót felhívás

270
00:19:44,270 --> 00:19:47,910
Nekem van a kezdete, ahol én keresem a tömbben és a végén

271
00:19:47,910 --> 00:19:49,380
hol keresem a tömbben.

272
00:19:49,380 --> 00:19:55,330
>> Minden lépésnél, ahol mondja, hogy ez a középső elem, amely a kezdő + end / 2,

273
00:19:55,330 --> 00:19:58,850
, hogy azonos azzal, amit keresünk?

274
00:19:58,850 --> 00:20:04,650
És ha igen, akkor talált rá, és azt hiszem, hogy lesz telt ki a szint rekurzió.

275
00:20:04,650 --> 00:20:12,540
És ha ez nem igaz, akkor ellenőrizze, hogy a középső érték a tömb túl nagy,

276
00:20:12,540 --> 00:20:19,320
ebben az esetben nézzük a bal felén a tömböt fog kezdetétől a középső index.

277
00:20:19,320 --> 00:20:22,710
És egyébként mi a vége fele.

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

279
00:20:24,740 --> 00:20:27,730
Ez jól hangzik.

280
00:20:27,730 --> 00:20:36,640
Oké, egy pár dolgot, és valóban, ez egy nagyon magas szintű dolog

281
00:20:36,640 --> 00:20:41,270
hogy soha nem kell tudni, hogy a kurzus, de ez igaz.

282
00:20:41,270 --> 00:20:46,080
Rekurzív függvények, mindig hallani, hogy ők egy rossz üzlet

283
00:20:46,080 --> 00:20:51,160
mert ha rekurzívan nevezed magad túl sokszor, akkor kap verem túlcsordulás

284
00:20:51,160 --> 00:20:54,990
mert, mint már mondtam, minden funkciót kap a saját stack frame.

285
00:20:54,990 --> 00:20:59,500
Tehát minden egyes hívás a rekurzív függvény kap saját stack frame.

286
00:20:59,500 --> 00:21:04,140
Tehát, ha csinál 1.000 rekurzív hívásokat, akkor kap 1.000 stack keretek,

287
00:21:04,140 --> 00:21:08,390
és gyorsan vezetsz, hogy miután túl sok stack keretek és a dolgok csak megtörni.

288
00:21:08,390 --> 00:21:13,480
Szóval ezért rekurzív függvények általában rossz.

289
00:21:13,480 --> 00:21:19,370
De van egy szép részhalmaza rekurzív függvények úgynevezett tail-rekurzív függvények,

290
00:21:19,370 --> 00:21:26,120
és ez történetesen egy példát, ahol, ha a fordító észreveszi ezt

291
00:21:26,120 --> 00:21:29,920
és azt kell, azt hiszem - a csengés, ha átadja neki a-O2 flag

292
00:21:29,920 --> 00:21:33,250
akkor veszi észre ezt farok rekurzív, és a dolgok jó.

293
00:21:33,250 --> 00:21:40,050
>> Ez újra ugyanazt a stack frame újra és újra minden rekurzív hívást.

294
00:21:40,050 --> 00:21:47,010
És mivel te ugyanazt a verem keret, akkor nem kell aggódnia

295
00:21:47,010 --> 00:21:51,690
valaha verem túláradó, és ezzel egy időben, ahogy már korábban említettük,

296
00:21:51,690 --> 00:21:56,380
ha egyszer visszatér igaz, akkor vissza kell térnie az összes ilyen stack frame

297
00:21:56,380 --> 00:22:01,740
és a 10. hívás SearchHelp vissza kell térnie a 9., van, hogy visszatérjen a 8..

298
00:22:01,740 --> 00:22:05,360
Annak érdekében, hogy nem kell történni, ha a funkciók farok rekurzív.

299
00:22:05,360 --> 00:22:13,740
És mi teszi ezt a funkciót, farok rekurzív is vegyük észre, hogy az adott hívás searchHelp

300
00:22:13,740 --> 00:22:18,470
a rekurzív hívás, hogy ez így van, mi ez visszatér.

301
00:22:18,470 --> 00:22:25,290
Tehát az első hívás SearchHelp, akkor vagy azonnal vissza hamis,

302
00:22:25,290 --> 00:22:29,590
azonnal vissza igaz, vagy mi, hogy egy rekurzív hívás SearchHelp

303
00:22:29,590 --> 00:22:33,810
ahol mi vagyunk vissza, ami a hívás visszatér.

304
00:22:33,810 --> 00:22:51,560
És nem tudtuk ezt, ha csináltunk valami hasonlót int x = SearchHelp, return x * 2,

305
00:22:51,560 --> 00:22:55,440
Csak néhány véletlenszerű változás.

306
00:22:55,440 --> 00:23:01,470
>> Tehát most ez a rekurzív hívás ez int x = SearchHelp rekurzív hívás

307
00:23:01,470 --> 00:23:05,740
már nem farok rekurzív, mivel azt valóban kell vissza

308
00:23:05,740 --> 00:23:10,400
vissza az előző stack keretet annak érdekében, hogy, hogy a korábbi felhívását, hogy a funkció

309
00:23:10,400 --> 00:23:13,040
ezután csinálni valamit a visszatérési érték.

310
00:23:13,040 --> 00:23:22,190
Tehát ez nem farok rekurzív, de mi volt azelőtt szépen farok rekurzív. Igen.

311
00:23:22,190 --> 00:23:27,000
[Hallgató] Ha nem a második alapeset kell ellenőrizni 1.

312
00:23:27,000 --> 00:23:30,640
mert lehet olyan helyzet, amikor, amikor átadni azt az érvet,

313
00:23:30,640 --> 00:23:35,770
Ön start = end, de ők a tűt értéket.

314
00:23:35,770 --> 00:23:47,310
A kérdést nem tudjuk befut az esetben, ha vége a tű érték

315
00:23:47,310 --> 00:23:52,000
, vagy indítson = végén, megfelelő, start = end

316
00:23:52,000 --> 00:23:59,480
és még nem is ellenőrizték, hogy különös értéket még,

317
00:23:59,480 --> 00:24:03,910
majd indítsa + end / 2 csak lesz ugyanaz az értéke.

318
00:24:03,910 --> 00:24:07,890
De mi már vissza hamis, és mi soha nem ellenőrizték az értéket.

319
00:24:07,890 --> 00:24:14,240
Így legalábbis, az első hívást, ha a méret 0, akkor szeretnénk visszatérni hamis.

320
00:24:14,240 --> 00:24:17,710
De ha mérete 1, akkor indítás nem fog azonos célból

321
00:24:17,710 --> 00:24:19,820
és mi legalább megtekintéséhez egy eleme.

322
00:24:19,820 --> 00:24:26,750
De azt hiszem, igazad van, hogy mi is a végén egy olyan ügyben, ahol az induló + end / 2,

323
00:24:26,750 --> 00:24:31,190
indítás végül is ugyanaz, mint a kezdő + end / 2,

324
00:24:31,190 --> 00:24:35,350
de mi soha nem ellenőrizte, hogy elemet.

325
00:24:35,350 --> 00:24:44,740
>> Tehát ha először ellenőrzi a középső elem értéke keresünk,

326
00:24:44,740 --> 00:24:47,110
akkor azonnal vissza igaz.

327
00:24:47,110 --> 00:24:50,740
Különben ha ők egyenlő, akkor nincs értelme tovább

328
00:24:50,740 --> 00:24:58,440
hiszen mi csak fog frissíteni az esetben, ha mi egyetlen elemű tömb.

329
00:24:58,440 --> 00:25:01,110
Ha egyetlen elem nem az, amit keresünk,

330
00:25:01,110 --> 00:25:03,530
akkor minden rossz. Igen.

331
00:25:03,530 --> 00:25:08,900
[Hallgató] A lényeg az, hogy mivel a mérete valóban nagyobb, mint a tömb elemeinek,

332
00:25:08,900 --> 00:25:13,070
már van egy eltolás - >> Így lesz méret -

333
00:25:13,070 --> 00:25:19,380
[Hallgató] Mondja, ha a tömb mérete 0 volt, akkor a SearchHelp ténylegesen ellenőrzi szénaboglya a 0

334
00:25:19,380 --> 00:25:21,490
az első hívást.

335
00:25:21,490 --> 00:25:25,300
A tömb mérete 0, tehát a 0 jelentése - >> Igen.

336
00:25:25,300 --> 00:25:30,750
Van egy másik dolog, hogy - ez lehet jó. Gondoljuk.

337
00:25:30,750 --> 00:25:40,120
Tehát, ha a tömb volt 10 elemek és a középső fogjuk ellenőrizni a index 5,

338
00:25:40,120 --> 00:25:45,700
úgyhogy ellenőrzése 5, és tegyük fel, hogy az érték kisebb.

339
00:25:45,700 --> 00:25:50,720
Szóval dobott mindent idegenben 5-től kezdve.

340
00:25:50,720 --> 00:25:54,030
Így kezdődik + end / 2 lesz az új végén,

341
00:25:54,030 --> 00:25:57,450
Szóval igen, ez mindig fog maradni vége után a tömb.

342
00:25:57,450 --> 00:26:03,570
Ha ez a helyzet, ha ez páros vagy páratlan, akkor mi lenne ellenőrizni, mondjuk, 4,

343
00:26:03,570 --> 00:26:05,770
de még mindig eldobni -

344
00:26:05,770 --> 00:26:13,500
Szóval igen, vége mindig lesz túl tényleges végén a tömb.

345
00:26:13,500 --> 00:26:18,350
Tehát az elemeket mi összpontosítva, végén mindig lesz az egyik után.

346
00:26:18,350 --> 00:26:24,270
És ha az elején nem mindig egyenlő a célból vagyunk tömb mérete 0.

347
00:26:24,270 --> 00:26:35,600
>> A másik dolog, gondoltam is vagyunk frissítése kezdetét kell kezdeni + end / 2,

348
00:26:35,600 --> 00:26:44,020
így ez az eset áll fenn, hogy Gondjaim be, ahol az induló + end / 2

349
00:26:44,020 --> 00:26:46,820
az elem vagyunk ellenőrzés.

350
00:26:46,820 --> 00:26:58,150
Tegyük fel, hogy mi volt ez a 10-elem tömb. Mindegy.

351
00:26:58,150 --> 00:27:03,250
Így kezdődik + end / 2 lesz valami, mint ez,

352
00:27:03,250 --> 00:27:07,060
és ha ez nem az érték, mondjuk szeretnénk frissíteni.

353
00:27:07,060 --> 00:27:10,060
Az érték nagyobb, ezért szeretnénk, hogy nézd meg ezt a felét a tömbben.

354
00:27:10,060 --> 00:27:15,910
Szóval hogyan vagyunk frissítése kezdetét, mi frissítése kezdetétől most ezt az elemet.

355
00:27:15,910 --> 00:27:23,790
De ez még mindig működik, vagy legalábbis, meg tudod csinálni kezdő + end / 2 + 1.

356
00:27:23,790 --> 00:27:27,850
[Hallgató] Nem kell kezdeni + végét [hallhatatlan] >> Igen.

357
00:27:27,850 --> 00:27:33,240
Már ellenőrizte ezt az elemet, és tudom, hogy ez nem az, amit keresünk.

358
00:27:33,240 --> 00:27:36,800
Tehát nem kell frissíteni kezdetét, hogy ezt az elemet.

359
00:27:36,800 --> 00:27:39,560
Mi is csak hagyja ki és frissítse kezd, hogy ezt az elemet.

360
00:27:39,560 --> 00:27:46,060
És van még egy eset, mondjuk, hogy ez volt a célból

361
00:27:46,060 --> 00:27:53,140
így majd indítsa lenne ez, indítsa + end / 2 lesz ez,

362
00:27:53,140 --> 00:28:00,580
indul + end - Igen, azt hiszem, hogy végül a végtelen rekurziót.

363
00:28:00,580 --> 00:28:12,690
Tegyük fel, hogy ez csak egy tömb mérete 2 vagy tömb mérete 1. Azt hiszem, ez működni fog.

364
00:28:12,690 --> 00:28:19,490
Tehát jelenleg az, hogy a kezdő elem és vége 1 túl.

365
00:28:19,490 --> 00:28:24,110
Tehát az elem, hogy mi megyünk, hogy ellenőrizze ezt,

366
00:28:24,110 --> 00:28:29,400
majd amikor frissíti kezdete, mi frissítése kezdete legyen 0 + 1/2,

367
00:28:29,400 --> 00:28:33,160
amely a fog végződni minket vissza kezdetét, hogy ezt az elemet.

368
00:28:33,160 --> 00:28:36,210
>> Szóval ellenőrzésére azonos elem újra és újra.

369
00:28:36,210 --> 00:28:43,310
Szóval ez a helyzet, ha minden rekurzív hívás ténylegesen frissíteni valamit.

370
00:28:43,310 --> 00:28:48,370
Így kell tennünk kezdő + end / 2 + 1, vagy pedig van egy eset

371
00:28:48,370 --> 00:28:50,710
ha nem vagyunk valójában frissítés start.

372
00:28:50,710 --> 00:28:53,820
Mindenki látja, hogy?

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

374
00:28:56,310 --> 00:29:03,860
Van valakinek kérdése ez a megoldás, vagy bármilyen további megjegyzés?

375
00:29:05,220 --> 00:29:10,280
Oké. Tudja valaki, hogy egy iteratív megoldás, hogy mindannyian nézni?

376
00:29:17,400 --> 00:29:20,940
Vajon mindannyian csinálni rekurzívan?

377
00:29:20,940 --> 00:29:25,950
Vagy is, azt hiszem, ha nyitott az övé, akkor lehet, hogy felülírja az előző.

378
00:29:25,950 --> 00:29:28,810
Vajon automatikusan elmenti? Nem vagyok pozitív.

379
00:29:35,090 --> 00:29:39,130
Tudja valaki, hogy iteratív?

380
00:29:39,130 --> 00:29:42,430
Mi lehet járni rajta együtt, ha nem.

381
00:29:46,080 --> 00:29:48,100
Az ötlet lesz ugyanaz.

382
00:30:00,260 --> 00:30:02,830
Iteratív megoldás.

383
00:30:02,830 --> 00:30:07,140
Fogunk szeretnénk alapvetően nem ugyanaz a gondolat

384
00:30:07,140 --> 00:30:16,530
ahol szeretnénk nyomon követni az új végén a tömb és az új kezdete a tömb

385
00:30:16,530 --> 00:30:18,510
és nem, hogy újra és újra.

386
00:30:18,510 --> 00:30:22,430
És ha mi vagyunk nyomon követni, mint a kezdet és a vég mindig metszik egymást,

387
00:30:22,430 --> 00:30:29,020
akkor nem találtunk, és vissza tudjuk hamis.

388
00:30:29,020 --> 00:30:37,540
Szóval, hogyan tudom ezt? Bárki, aki javaslatokat vagy kód a számomra, hogy húzza fel?

389
00:30:42,190 --> 00:30:47,450
[Hallgató] Van egy darabig hurok. >> Igen.

390
00:30:47,450 --> 00:30:49,450
Fogsz szeretne csinálni egy hurok.

391
00:30:49,450 --> 00:30:51,830
>> Hasznosnak tekintette kódot tudtam felhúzni, vagy mit fog javasolni?

392
00:30:51,830 --> 00:30:56,340
[Hallgató] Azt hiszem, igen. >> Rendben. Ez megkönnyíti a dolgokat. Mi volt a neve?

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

394
00:31:00,140 --> 00:31:04,190
Felülvizsgálat 1. Oké.

395
00:31:04,190 --> 00:31:13,200
Olcsó az, amit az úgynevezett kezdeni előtt.

396
00:31:13,200 --> 00:31:17,080
Fel nem egészen, amit az úgynevezett vége előtt.

397
00:31:17,080 --> 00:31:22,750
Igazából, vége már a tömbben. Ez egy elemet is figyelembe kell vennie.

398
00:31:22,750 --> 00:31:26,890
Így alacsony 0, fel a méret a tömb - 1,

399
00:31:26,890 --> 00:31:34,780
és most looping, és ellenőrzik -

400
00:31:34,780 --> 00:31:37,340
Azt hiszem, lehet sétálni rajta.

401
00:31:37,340 --> 00:31:41,420
Mi volt a gondolkodás ezen keresztül? Sétáljon velünk a kódot.

402
00:31:41,420 --> 00:31:49,940
[Hallgató] Persze. Nézd meg a szénakazalban értéket a középső és hasonlítsa össze a tűt.

403
00:31:49,940 --> 00:31:58,520
Szóval, ha ez magasabb, mint a tű, akkor azt szeretnénk, hogy - ó, tényleg, hogy kell visszafelé.

404
00:31:58,520 --> 00:32:05,180
Fogsz szeretné eldobni a jobb felét, és így igen, hogy kell az utat.

405
00:32:05,180 --> 00:32:08,830
[Bowden] Szóval ez alacsonyabbnak kell lennie? Ez az, amit mondott? >> [Hallgató] Igen.

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

407
00:32:10,390 --> 00:32:15,700
Tehát, ha mi éppen a kisebb, mint amit akarunk,

408
00:32:15,700 --> 00:32:19,410
akkor igen, azt akarjuk, hogy dobja el a bal fele,

409
00:32:19,410 --> 00:32:22,210
ami azt jelenti, frissít mindent vagyunk tekintve

410
00:32:22,210 --> 00:32:26,610
mozgatásával alacsony jobbra a tömb.

411
00:32:26,610 --> 00:32:30,130
Ez jól néz ki.

412
00:32:30,130 --> 00:32:34,550
Azt hiszem, ez ugyanaz a kérdés, hogy azt mondtuk, az előző,

413
00:32:34,550 --> 00:32:49,760
ahol ha alacsony értéke 0 és legfeljebb 1, akkor az alacsony + fel / 2 fog létrehozni, hogy ugyanaz a dolog újra.

414
00:32:49,760 --> 00:32:53,860
>> És akkor is, ha nem ez a helyzet, akkor még hatékonyabb legalább

415
00:32:53,860 --> 00:32:57,630
hogy csak dobja az elemet már csak néztem amiről tudjuk, hogy rossz.

416
00:32:57,630 --> 00:33:03,240
Tehát alacsony + fel / 2 + 1 - >> [hallgató] Ez legyen a másik irányba.

417
00:33:03,240 --> 00:33:05,900
[Bowden] Vagy ezt kellene - 1 és a másik legyen + 1.

418
00:33:05,900 --> 00:33:09,580
[Hallgató] És legyen egy dupla egyenlőségjel. >> [Bowden] Igen.

419
00:33:09,580 --> 00:33:11,340
[Hallgató] Igen.

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

421
00:33:15,910 --> 00:33:21,280
És végül, most, hogy van ez a + 1 - 1 dolog,

422
00:33:21,280 --> 00:33:31,520
ez - talán nem is - ez mindig lehetséges alacsony ahhoz, hogy a végén egy-nél nagyobb értéket fel?

423
00:33:35,710 --> 00:33:40,320
Azt hiszem, az egyetlen módja, hogy megtörténhet - Lehetséges ez? >> [Hallgató] Nem tudom.

424
00:33:40,320 --> 00:33:45,220
De ha ez lesz csonkítva, majd kap mínusz, hogy az 1, majd a - >> Igen.

425
00:33:45,220 --> 00:33:47,480
[Hallgató] Ez valószínűleg kap elrontotta.

426
00:33:49,700 --> 00:33:53,940
Azt hiszem, jó lesz csak azért, mert

427
00:33:53,940 --> 00:33:58,800
mert a végén alacsonyabb kellett volna egyenlő, azt hiszem.

428
00:33:58,800 --> 00:34:03,070
De ha egyenlő, akkor nem tett volna a while ciklus kezdeni

429
00:34:03,070 --> 00:34:06,670
és mi csak volna vissza az értéket. Tehát úgy gondolom, jók vagyunk most.

430
00:34:06,670 --> 00:34:11,530
Figyeljük meg, hogy annak ellenére, hogy ez a probléma már nem rekurzív,

431
00:34:11,530 --> 00:34:17,400
ugyanolyan ötleteket kell alkalmazni, ha azt látjuk, hogy ez ilyen könnyen kínálkozik

432
00:34:17,400 --> 00:34:23,659
a rekurzív megoldás az, hogy mi csak frissítésével indexek újra és újra,

433
00:34:23,659 --> 00:34:29,960
tesszük a problémát, egyre kisebb és kisebb, mi összpontosítva egy részhalmaza a tömb.

434
00:34:29,960 --> 00:34:40,860
[Hallgató] Ha alacsony jelentése 0 és fel jelentése 1, akkor mindketten 0 + 1/2, ami menne 0-ra,

435
00:34:40,860 --> 00:34:44,429
és akkor sem lenne + 1, az egyik a - 1.

436
00:34:47,000 --> 00:34:50,870
[Hallgató] Hol vagyunk ellenőrzési egyenlőség?

437
00:34:50,870 --> 00:34:55,100
Mint ha a középső valójában tű?

438
00:34:55,100 --> 00:34:58,590
Mi jelenleg nem csinálja ezt? Oh!

439
00:35:00,610 --> 00:35:02,460
Ha ez -

440
00:35:05,340 --> 00:35:13,740
Igen. Nem csak ezt a vizsgálatot le ide, mert mondjuk az első közép -

441
00:35:13,740 --> 00:35:16,430
[Hallgató] Ez tulajdonképpen tetszik nem dobja el a kötött.

442
00:35:16,430 --> 00:35:20,220
Tehát, ha dobja a kötött, akkor ellenőrizze, hogy az első vagy bármi.

443
00:35:20,220 --> 00:35:23,350
Ah. Igen. >> [Hallgató] Igen.

444
00:35:23,350 --> 00:35:29,650
Tehát most már dobni az egyik jelenleg nézett,

445
00:35:29,650 --> 00:35:33,260
ami azt jelenti, hogy most kell is

446
00:35:33,260 --> 00:35:44,810
if (szénakazalban [(low +-ig) / 2] == tű), akkor mi is vissza igaz.

447
00:35:44,810 --> 00:35:52,070
És akár tettem mást, vagy csak, ha ez azt jelenti, szó szerint ugyanaz a dolog

448
00:35:52,070 --> 00:35:57,110
mert ez volna vissza igaz.

449
00:35:57,110 --> 00:36:01,450
Így fogok tenni, ha mást, de ez nem számít.

450
00:36:01,450 --> 00:36:10,440
>> Tehát még ha ez, más ez, és ez egy közös dolog, amit csinálni

451
00:36:10,440 --> 00:36:14,340
ahol még ha ez a helyzet, ha minden jó itt,

452
00:36:14,340 --> 00:36:22,780
mint az alacsony soha nem lehet nagyobb, mint felfelé, nem érdemes érvelést arról, hogy ez igaz.

453
00:36:22,780 --> 00:36:28,010
Szóval, akkor is azt mondják, míg az alacsony kisebb vagy egyenlő, mint

454
00:36:28,010 --> 00:36:30,720
vagy az olyan, kis kisebb, mint

455
00:36:30,720 --> 00:36:35,300
így ha valaha is azonos vagy alacsony lesz, hogy lemondjunk róluk,

456
00:36:35,300 --> 00:36:40,130
akkor lehet kitörni a hurok.

457
00:36:41,410 --> 00:36:44,630
Kérdések, aggályok, észrevétel?

458
00:36:47,080 --> 00:36:49,270
Oké. Ez jól néz ki.

459
00:36:49,270 --> 00:36:52,230
Most szeretnénk csinálni sort.

460
00:36:52,230 --> 00:37:04,030
Ha elmegyünk a második felülvizsgálat, azt látjuk, ezek ugyanazt a számot,

461
00:37:04,030 --> 00:37:07,550
de most már nem rendezetten.

462
00:37:07,550 --> 00:37:12,840
És azt akarjuk, hogy végre sort tetszőleges algoritmus O n log n.

463
00:37:12,840 --> 00:37:17,240
Tehát melyik algoritmus mit kéne végre itt? >> [Hallgató] Merge sort.

464
00:37:17,240 --> 00:37:23,810
[Bowden] Igen. Merge rendezés O (n log n), úgy, hogy az, amit mi fogunk csinálni.

465
00:37:23,810 --> 00:37:26,680
És a probléma lesz nagyon hasonló,

466
00:37:26,680 --> 00:37:31,920
ahol könnyen alkalmas arra, hogy egy rekurzív megoldást.

467
00:37:31,920 --> 00:37:35,580
Mi is felér egy iteratív megoldás, ha azt akarjuk,

468
00:37:35,580 --> 00:37:42,540
de a rekurzió könnyebb lesz itt, és meg kell tennünk a rekurziót.

469
00:37:45,120 --> 00:37:49,530
Azt hiszem, majd séta a merge sort az első,

470
00:37:49,530 --> 00:37:54,280
bár van egy szép videót merge sort már. [Nevetés]

471
00:37:54,280 --> 00:37:59,780
Tehát merge sort vannak - Én pazarlás ennyi e papír.

472
00:37:59,780 --> 00:38:02,080
Ó, már csak egy maradt.

473
00:38:02,080 --> 00:38:03,630
Szóval egyesítése.

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

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

476
00:38:29,910 --> 00:38:33,460
Merge vesz két külön tömböket.

477
00:38:33,460 --> 00:38:36,780
Egyénileg a két tömb egyaránt rendezve.

478
00:38:36,780 --> 00:38:40,970
Szóval ez a tömb, 1, 3, 5, rendezve. Ez a tömb, 0, 2, 4, rendezve.

479
00:38:40,970 --> 00:38:46,710
Most mit kell tennie, egyesítés egyesíteni őket egy tömb, amely maga rendezve.

480
00:38:46,710 --> 00:38:57,130
Tehát szeretnénk egy sor mérete 6, ami megy, hogy ezek az elemek belsejében

481
00:38:57,130 --> 00:38:59,390
rendezetten.

482
00:38:59,390 --> 00:39:03,390
>> És így tudjuk kihasználni azt a tényt, hogy ez a két tömb rendezése

483
00:39:03,390 --> 00:39:06,800
hogy ezt a lineáris időben,

484
00:39:06,800 --> 00:39:13,510
lineáris idő értelme, ha ez a tömb mérete x és ez a méret y,

485
00:39:13,510 --> 00:39:20,970
akkor a teljes algoritmus legyen O (x + y). Oké.

486
00:39:20,970 --> 00:39:23,150
Szóval javaslatokat.

487
00:39:23,150 --> 00:39:26,030
[Hallgató] tudnánk kezdeni a bal?

488
00:39:26,030 --> 00:39:30,150
Szóval, akkor tegye a 0 le először, majd az 1-es és akkor itt te vagy a 2.

489
00:39:30,150 --> 00:39:33,320
Szóval ez olyan, mint hogy van egy fül, ami mozog jobbra. >> [Bowden] Igen.

490
00:39:33,320 --> 00:39:41,070
A mindkét tömbök ha csak összpontosítani a bal szélső elem.

491
00:39:41,070 --> 00:39:43,530
Mivel mindkét tömbök vannak rendezve, tudjuk, hogy ezek 2 elem

492
00:39:43,530 --> 00:39:46,920
a legkisebb elem egyik tömbben.

493
00:39:46,920 --> 00:39:53,500
Ez azt jelenti, hogy 1 e 2 elem kell, hogy legyen a legkisebb eleme a egyesített tömbben.

494
00:39:53,500 --> 00:39:58,190
Ez csak azért történik, hogy a legkisebb az egyik a jobb ebben az időben.

495
00:39:58,190 --> 00:40:02,580
Úgyhogy veszünk 0, tegye rá a baloldali mivel 0 kisebb, mint 1,

496
00:40:02,580 --> 00:40:08,210
hogy vegye 0, helyezze be az első helyre, majd mi frissíti ezt

497
00:40:08,210 --> 00:40:12,070
hogy most összpontosítani az első elemet.

498
00:40:12,070 --> 00:40:14,570
És most megismételjük.

499
00:40:14,570 --> 00:40:20,670
Tehát most összehasonlítjuk 2 és 1. 1 kisebb, úgyhogy be 1.

500
00:40:20,670 --> 00:40:25,300
Frissítjük ezt a mutatót, hogy pont ez a fickó.

501
00:40:25,300 --> 00:40:33,160
Most csináld újra, így a 2. Ez frissíteni fogja, hasonlítsa össze ezeket a 2, 3.

502
00:40:33,160 --> 00:40:37,770
Ezt frissítéseket, majd a 4 és 5.

503
00:40:37,770 --> 00:40:42,110
Ez tehát merge.

504
00:40:42,110 --> 00:40:49,010
>> Meg kell elég nyilvánvaló, hogy a lineáris idő óta megyünk át minden elem egyszer.

505
00:40:49,010 --> 00:40:55,980
És ez a legnagyobb lépés a végrehajtási összevonási rendezés ezt.

506
00:40:55,980 --> 00:40:59,330
És ez nem olyan nehéz.

507
00:40:59,330 --> 00:41:15,020
Egy pár dolog aggódni a mondjuk voltunk egyesülő 1, 2, 3, 4, 5, 6.

508
00:41:15,020 --> 00:41:30,930
Ebben az esetben a végén a forgatókönyv, ahol ez lesz kisebb,

509
00:41:30,930 --> 00:41:36,160
akkor frissíti a mutató, ez lesz kisebb, frissíti a,

510
00:41:36,160 --> 00:41:41,280
ez már kisebb, és most fel kell ismernie

511
00:41:41,280 --> 00:41:44,220
ha már tényleg elfogyott elemek összehasonlítani.

512
00:41:44,220 --> 00:41:49,400
Mivel már használnak az egész tömb,

513
00:41:49,400 --> 00:41:55,190
mindent a tömb már csak beilleszteni ide.

514
00:41:55,190 --> 00:42:02,040
Szóval, ha valaha is befut a ponton, ahol az egyik tömbök teljesen összeolvadt már,

515
00:42:02,040 --> 00:42:06,510
akkor csak hogy minden elemét a többi tömb, és helyezze őket a végén a tömb.

516
00:42:06,510 --> 00:42:13,630
Így tudjuk csak helyezze 4, 5, 6. Oké.

517
00:42:13,630 --> 00:42:18,070
Ez az egyik dolog, hogy néz ki.

518
00:42:22,080 --> 00:42:26,120
Végrehajtási, hogy kell az 1. lépést.

519
00:42:26,120 --> 00:42:32,600
Merge rendezni, akkor ennek alapján, ez 2 lépésben, 2 buta lépéseket.

520
00:42:38,800 --> 00:42:42,090
Nézzük csak hogy ezt a tömböt.

521
00:42:57,920 --> 00:43:05,680
Szóval merge sort, az 1. lépés az, hogy rekurzív törni a tömb a félidőt.

522
00:43:05,680 --> 00:43:09,350
Szóval szét ezt a tömböt a félidőt.

523
00:43:09,350 --> 00:43:22,920
Most már 4, 15, 16, 50 és 8, 23, 42, 108.

524
00:43:22,920 --> 00:43:25,800
És most újra meg újra, és szét ezeket a félidőt.

525
00:43:25,800 --> 00:43:27,530
Én csak csinálni ezen az oldalon.

526
00:43:27,530 --> 00:43:34,790
Így 4, 15 és 16, 50.

527
00:43:34,790 --> 00:43:37,440
Azt nem ugyanaz a dolog itt.

528
00:43:37,440 --> 00:43:40,340
És most osztott be félbe ismét.

529
00:43:40,340 --> 00:43:51,080
És van 4, 15, 16, 50.

530
00:43:51,080 --> 00:43:53,170
Annak érdekében, hogy a mi alapeset.

531
00:43:53,170 --> 00:44:00,540
Ha a tömbök mérete 1, akkor hagyja abba a hasítási a félidőt.

532
00:44:00,540 --> 00:44:03,190
>> Most mit csináljunk ezzel?

533
00:44:03,190 --> 00:44:15,730
A végén ez is lebontják a 8, 23, 42, és 108.

534
00:44:15,730 --> 00:44:24,000
Tehát most, hogy vagyunk ezen a ponton, most lépjen kettő merge sort éppen egyesülő párok a listákra.

535
00:44:24,000 --> 00:44:27,610
Tehát szeretnénk egyesíteni ezeket. Csak hívjon összeolvad.

536
00:44:27,610 --> 00:44:31,410
Tudjuk, hogy merge visszatér ezeket rendezett sorrendben.

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

538
00:44:33,920 --> 00:44:41,440
Most szeretnénk egyesíteni ezeket, és hogy vissza fog térni a listát azokkal, rendezetten,

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

540
00:44:44,160 --> 00:44:57,380
Mi egyesíteni azokat - nem tudok írni - 8, 23 és 42, 108.

541
00:44:57,380 --> 00:45:02,890
Tehát létrejött pár egyszer.

542
00:45:02,890 --> 00:45:05,140
Most már csak egyesíteni újra.

543
00:45:05,140 --> 00:45:10,130
Figyeljük meg, hogy minden egyes ilyen listák rendezve önmagában,

544
00:45:10,130 --> 00:45:15,220
és akkor is csak egyesíteni ezeket a listákat, hogy kap egy listát a 4-es méretű, amely rendezve

545
00:45:15,220 --> 00:45:19,990
és egyesíti a két listát kap egy listát a 4-es méretű, ami rendezve.

546
00:45:19,990 --> 00:45:25,710
És végül, tudjuk egyesíteni e két listáját 4-es méretű, hogy kap egy listát, hogy a 8-as méret van rendezve.

547
00:45:25,710 --> 00:45:34,030
Tehát látható, hogy ez az általános n log n, már láttuk, hogy merge lineáris,

548
00:45:34,030 --> 00:45:40,390
így amikor dolgunk egyesülő e, így például a teljes költsége merge

549
00:45:40,390 --> 00:45:43,410
e két lista csak 2, mert -

550
00:45:43,410 --> 00:45:49,610
Vagy jól, ez O n, de n itt csak ezeket a 2 elem, így 2.

551
00:45:49,610 --> 00:45:52,850
És ezek a 2 lesz 2 és e 2 lesz 2, és ezek 2 lesz 2,

552
00:45:52,850 --> 00:45:58,820
így minden a összevonta, hogy meg kell csinálni, amit a végén csinál n.

553
00:45:58,820 --> 00:46:03,210
Mint a 2 + 2 + 2 + 2 8 közül az N,

554
00:46:03,210 --> 00:46:08,060
így a költsége egyesülő erre a halmazra n.

555
00:46:08,060 --> 00:46:10,810
És ugyanaz a dolog itt.

556
00:46:10,810 --> 00:46:16,980
Majd eleget a 2, majd ezeket a 2, és egyénileg ezen engedmény lesz 4 műveletek,

557
00:46:16,980 --> 00:46:23,610
ezen engedmény lesz 4 műveleteket, de még egyszer, az összes ilyen,

558
00:46:23,610 --> 00:46:29,030
a végén egyesülő n át a dolgokat, és így ezt a lépést tart n.

559
00:46:29,030 --> 00:46:33,670
És így minden szinten előnyben n elem egyesítették.

560
00:46:33,670 --> 00:46:36,110
>> És hány szint van?

561
00:46:36,110 --> 00:46:40,160
Minden egyes szinten a tömb növekszik 2-es méret.

562
00:46:40,160 --> 00:46:44,590
Íme a tömbök mérete 1, itt ők a 2-es méret, itt ők a 4-es méretű,

563
00:46:44,590 --> 00:46:46,470
és végül, ők a 8-as méret.

564
00:46:46,470 --> 00:46:56,450
Tehát mivel duplájára, ott lesznek összesen log n ezeket a szinteket.

565
00:46:56,450 --> 00:47:02,090
Tehát log n szint, minden egyes szinten figyelembe n összesen műveletek,

566
00:47:02,090 --> 00:47:05,720
kapunk egy n log n algoritmus.

567
00:47:05,720 --> 00:47:07,790
Kérdései vannak?

568
00:47:08,940 --> 00:47:13,320
Az emberek már haladást ért el, hogyan hajtsák végre ezt?

569
00:47:13,320 --> 00:47:18,260
Van valaki már egy olyan államban, ahol tudok csak húzza fel a kódot?

570
00:47:20,320 --> 00:47:22,260
Tudok adni egy percet.

571
00:47:24,770 --> 00:47:27,470
Ez lesz hosszabb.

572
00:47:27,470 --> 00:47:28,730
Én nagyon ajánlom kiújulnak -

573
00:47:28,730 --> 00:47:30,510
Nem kell tennie rekurziót a merge

574
00:47:30,510 --> 00:47:33,750
mert tenni rekurziót az egyesítés fogsz át kell adni egy csomó különböző méretű.

575
00:47:33,750 --> 00:47:37,150
Tudod, de ez bosszantó.

576
00:47:37,150 --> 00:47:43,720
De rekurzió a sort maga nagyon egyszerű.

577
00:47:43,720 --> 00:47:49,190
Te csak a szó szoros értelmében szükséges sort a bal fele, sort a jobb felét. Oké.

578
00:47:51,770 --> 00:47:54,860
Bárki bármit tudok húzni még fel?

579
00:47:54,860 --> 00:47:57,540
Vagy Adok egy percet.

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

581
00:47:59,900 --> 00:48:02,970
Bárki, aki valamit tudunk dolgozni?

582
00:48:05,450 --> 00:48:09,680
Vagy akkor csak dolgozni ezzel majd bontsa ki onnan.

583
00:48:09,680 --> 00:48:14,050
>> Bárki, aki több, mint ez, hogy én is húzza fel?

584
00:48:14,050 --> 00:48:17,770
[Hallgató] Igen. Akkor húzza fel az enyémet. >> Rendben.

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

586
00:48:22,170 --> 00:48:25,280
[Hallgató] Volt egy csomó feltételeket. >> Ó, a francba. Can you -

587
00:48:25,280 --> 00:48:28,110
[Hallgató] Meg kell menteni. >> Igen.

588
00:48:32,420 --> 00:48:35,730
Így tettük ezt az egyesítés külön-külön.

589
00:48:35,730 --> 00:48:38,570
Ó, de ez nem olyan rossz.

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

591
00:48:41,650 --> 00:48:47,080
Szóval sort maga csak hívás mergeSortHelp.

592
00:48:47,080 --> 00:48:49,530
Magyarázd el, mi mergeSortHelp csinál.

593
00:48:49,530 --> 00:48:55,700
[Hallgató] MergeSortHelp nagyjából működik a két fő lépésben,

594
00:48:55,700 --> 00:49:01,270
amely rendezni mindkét felét a tömb, majd egyesíteni mind a ketten.

595
00:49:04,960 --> 00:49:08,050
[Bowden] Oké, adj egy percet.

596
00:49:10,850 --> 00:49:13,210
Azt hiszem, ez - >> [hallgató] Meg kell -

597
00:49:17,100 --> 00:49:19,400
Igen. Én valami hiányzik.

598
00:49:19,400 --> 00:49:23,100
Az egyesítés, rájöttem, hogy szükségem van egy új tömböt

599
00:49:23,100 --> 00:49:26,530
mert nem tudtam csinálni a helyén. >> Igen. Nem lehet. Helyes.

600
00:49:26,530 --> 00:49:28,170
[Hallgató] Szóval hozzon létre egy új tömböt.

601
00:49:28,170 --> 00:49:31,510
Elfelejtettem végén egyesítés újbóli-változás.

602
00:49:31,510 --> 00:49:34,490
Oké. Szükségünk van egy új tömböt.

603
00:49:34,490 --> 00:49:41,000
A merge sort, ez szinte mindig igaz.

604
00:49:41,000 --> 00:49:44,340
Része a költségek egy jobb algoritmust idő-bölcs

605
00:49:44,340 --> 00:49:47,310
szinte mindig szüksége, hogy egy kicsit több memóriát igényel.

606
00:49:47,310 --> 00:49:51,570
Tehát itt nem számít, hogyan csinálod egyesítése sort,

607
00:49:51,570 --> 00:49:54,780
akkor elkerülhetetlenül kell használni egy kis extra memóriát.

608
00:49:54,780 --> 00:49:58,240
Ő létrehozott egy új tömböt.

609
00:49:58,240 --> 00:50:03,400
És akkor azt mondja a végén már csak be kell másolni az új tömb az eredeti tömb.

610
00:50:03,400 --> 00:50:04,830
[Hallgató] Azt hiszem, igen.

611
00:50:04,830 --> 00:50:08,210
Én nem tudom, hogy működik szempontjából számolás történő hivatkozással, vagy bármi -

612
00:50:08,210 --> 00:50:11,650
Igen, ez működni fog. >> [Hallgató] Oké.

613
00:50:20,620 --> 00:50:24,480
Próbáltad futó ezt? >> [Hallgató] Nem, még nem. >> Oké.

614
00:50:24,480 --> 00:50:28,880
Próbálja futtatni, és aztán majd beszélünk róla egy kicsit.

615
00:50:28,880 --> 00:50:35,200
[Hallgató] Azt kell, hogy az összes funkció prototípusok és mindent, igaz?

616
00:50:37,640 --> 00:50:40,840
A függvény prototípusok. Úgy érted, mint a - Igen.

617
00:50:40,840 --> 00:50:43,040
Sort hívja mergeSortHelp.

618
00:50:43,040 --> 00:50:47,390
>> Így ahhoz, hogy a sort, hogy hívja mergeSortHelp, mergeSortHelp kell vagy már meghatározták

619
00:50:47,390 --> 00:50:56,370
mielőtt sort, vagy már csak be kell a prototípus. Csak másolja be azt.

620
00:50:56,370 --> 00:50:59,490
És hasonlóképpen, mergeSortHelp hív összeolvad,

621
00:50:59,490 --> 00:51:03,830
de merge még nem határozták még meg, így tudjuk csak hadd mergeSortHelp tudom

622
00:51:03,830 --> 00:51:08,700
hogy az, amit egyesíteni fog kinézni, és ennyi.

623
00:51:09,950 --> 00:51:15,730
Szóval mergeSortHelp.

624
00:51:22,770 --> 00:51:32,660
Van olyan kérdés van, ahol nincs az alapeset.

625
00:51:32,660 --> 00:51:38,110
MergeSortHelp rekurzív, így minden rekurzív függvény

626
00:51:38,110 --> 00:51:42,610
lesz szüksége valamilyen alapeset tudni, hogy mikor kell abbahagyni rekurzívan hívja magát.

627
00:51:42,610 --> 00:51:45,590
Mi a alapeset lesz itt? Igen.

628
00:51:45,590 --> 00:51:49,110
[Hallgató] Ha a méret 1? >> [Bowden] Igen.

629
00:51:49,110 --> 00:51:56,220
Szóval, mint láttuk ott, álltunk hasító tömbök

630
00:51:56,220 --> 00:52:01,850
ha egyszer bekerült tömbök mérete 1, ami elkerülhetetlenül vannak rendezve magukat.

631
00:52:01,850 --> 00:52:09,530
Tehát, ha mérete értéke 1, tudjuk, hogy a tömb már rendezett,

632
00:52:09,530 --> 00:52:12,970
így tudjuk csak vissza.

633
00:52:12,970 --> 00:52:16,880
>> Figyeljük meg, hogy az érvénytelen, így nem adott vissza semmit, csak vissza.

634
00:52:16,880 --> 00:52:19,580
Oké. Szóval ez a mi alapeset.

635
00:52:19,580 --> 00:52:27,440
Azt hiszem, a mi az alapeset is lehetne, ha történetesen egyesülő tömb mérete 0,

636
00:52:27,440 --> 00:52:30,030
akkor valószínűleg szeretne állni egy bizonyos ponton,

637
00:52:30,030 --> 00:52:33,610
így tudjuk csak mondjuk méret kisebb, mint 2 vagy kisebb, mint vagy egyenlő 1

638
00:52:33,610 --> 00:52:37,150
annak érdekében, hogy ez működni fog bármilyen tömb most.

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

640
00:52:38,870 --> 00:52:42,740
Szóval ez a mi alapeset.

641
00:52:42,740 --> 00:52:45,950
Most akarsz járni hozzánk merge?

642
00:52:45,950 --> 00:52:49,140
Mit jelentenek ezek az esetekben jelent?

643
00:52:49,140 --> 00:52:54,480
Akár itt, csak most ugyanezt teszi ötlet, a -

644
00:52:56,970 --> 00:53:02,470
[Hallgató] I kell áthaladó méret minden mergeSortHelp hívást.

645
00:53:02,470 --> 00:53:10,080
Én hozzá méretű kiegészítő elsődleges, és nem ott, mint például a méret / 2.

646
00:53:10,080 --> 00:53:16,210
[Bowden] Oh, méret / 2, méret / 2. >> [Hallgató] Ja, és szintén a fenti funkció is.

647
00:53:16,210 --> 00:53:21,320
[Bowden] Itt? >> [Hallgató] Csak méretét. >> [Bowden] Oh. Méret, méret? >> [Hallgató] Igen.

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

649
00:53:23,010 --> 00:53:26,580
Hadd gondolkozzam egy kicsit.

650
00:53:26,580 --> 00:53:28,780
Vajon befut egy kérdés?

651
00:53:28,780 --> 00:53:33,690
Mindig kezeljük a bal oldali 0-ként. >> [Hallgató] Nem

652
00:53:33,690 --> 00:53:36,340
Ez rossz is. Bocsánat. Meg kell kezdeni. Igen.

653
00:53:36,340 --> 00:53:39,230
[Bowden] Oké. Szeretem, hogy a jobb.

654
00:53:39,230 --> 00:53:43,880
És a végén. Oké.

655
00:53:43,880 --> 00:53:47,200
Tehát most nem akarsz járni hozzánk merge? >> [Hallgató] Oké.

656
00:53:47,200 --> 00:53:52,150
Én csak séta az új tömb, hogy én már létre.

657
00:53:52,150 --> 00:53:57,420
Mérete a méret a részét a tömb, hogy szeretnénk kell válogatni

658
00:53:57,420 --> 00:54:03,460
és megpróbálja megtalálni az elemet, amit meg kell oldania az új tömb lépést.

659
00:54:03,460 --> 00:54:10,140
Így kell csinálni, hogy először én ellenőrzése, amikor a bal fele a tömb továbbra is többé elemet,

660
00:54:10,140 --> 00:54:14,260
és ha nem, akkor menj le, hogy más feltétel, amely szerint csak a

661
00:54:14,260 --> 00:54:20,180
rendben kell, hogy legyen a megfelelő tömb, és mi fel, hogy a jelenlegi index newArray.

662
00:54:20,180 --> 00:54:27,620
>> És aztán különben én ellenőrzése, ha a jobb oldalon a tömb is befejeződött,

663
00:54:27,620 --> 00:54:30,630
ebben az esetben én csak fel a bal oldalon.

664
00:54:30,630 --> 00:54:34,180
Ez talán nem is lesz szükség. Nem vagyok benne biztos.

665
00:54:34,180 --> 00:54:40,970
De egyébként is, a másik két ellenőrzést, hogy a két kisebb, a bal vagy a jobb.

666
00:54:40,970 --> 00:54:49,770
És azt is minden esetben, én növelésének amelyik placeholder I növelni.

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

668
00:54:52,040 --> 00:54:53,840
Jól néz ki.

669
00:54:53,840 --> 00:54:58,800
Van valakinek megjegyzése vagy problémája vagy kérdése?

670
00:55:00,660 --> 00:55:07,720
Így a négy eset, hogy meg kell hozni a dolgokat csak, hogy - vagy úgy néz ki, 5 -

671
00:55:07,720 --> 00:55:13,100
de meg kell vizsgálni, hogy a bal oldali tömb kifogy a dolog, amit meg kell egyesíteni,

672
00:55:13,100 --> 00:55:16,390
arról, hogy a megfelelő tömb kifogy a dolog, amit meg kell egyesíteni -

673
00:55:16,390 --> 00:55:18,400
Én mutatott semmit.

674
00:55:18,400 --> 00:55:21,730
Szóval, hogy a bal oldali tömb elfogyott a dolgok, vagy a megfelelő tömb kifogyott a dolgokat.

675
00:55:21,730 --> 00:55:24,320
E két esetben.

676
00:55:24,320 --> 00:55:30,920
Azt is meg kell triviális eset, hogy a bal oldali dolog, kevesebb, mint a helyes dolog.

677
00:55:30,920 --> 00:55:33,910
Aztán akarjuk választani a bal dolog.

678
00:55:33,910 --> 00:55:37,630
Azok az esetek.

679
00:55:37,630 --> 00:55:40,990
Szóval ez volt a helyes, hogy ez az.

680
00:55:40,990 --> 00:55:46,760
Array maradt. Ez 1, 2, 3. Oké. Szóval igen, ezek a négy dolog, amit érdemes csinálni.

681
00:55:50,350 --> 00:55:54,510
És mi nem megy át egy iteratív megoldást.

682
00:55:54,510 --> 00:55:55,980
Én nem ajánlom -

683
00:55:55,980 --> 00:56:03,070
Merge rendezés egy példa egy függvény, amely egyszerre nem farok rekurzív,

684
00:56:03,070 --> 00:56:07,040
ez nem könnyű, hogy ez farok rekurzív,

685
00:56:07,040 --> 00:56:13,450
de ez nem könnyű, hogy ez iteratív.

686
00:56:13,450 --> 00:56:16,910
Ez nagyon egyszerű.

687
00:56:16,910 --> 00:56:19,170
Ez a végrehajtása merge sort,

688
00:56:19,170 --> 00:56:22,140
egyesítése, nem számít, mit teszel, fogsz építeni merge.

689
00:56:22,140 --> 00:56:29,170
>> Szóval merge sort épülő egyesítés rekurzívan mindössze három sorokat.

690
00:56:29,170 --> 00:56:34,700
Iteratív, ez több bosszantó és nehezebb gondolkodni.

691
00:56:34,700 --> 00:56:41,860
De észre, hogy ez nem farok rekurzív kezdete mergeSortHelp - ha nevezi magát -

692
00:56:41,860 --> 00:56:46,590
meg kell még csinálni a dolgokat után rekurzív hívás visszatér.

693
00:56:46,590 --> 00:56:50,830
Tehát ez a stack frame továbbra is fennállnak után is hívja ezt.

694
00:56:50,830 --> 00:56:54,170
És akkor, amikor hívja ezt, a verem keretet kell továbbra is fennállnak

695
00:56:54,170 --> 00:56:57,780
mert még azután is, hogy a hívást, még mindig meg kell egyesíteni.

696
00:56:57,780 --> 00:57:01,920
És ez triviális, hogy ez a farok rekurzív.

697
00:57:04,070 --> 00:57:06,270
Kérdései vannak?

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

699
00:57:09,860 --> 00:57:13,400
Szóval, megy vissza a rendezéshez - ó, ott két dolgot szeretnék mutatni. Oké.

700
00:57:13,400 --> 00:57:17,840
Visszatérve a sort, akkor ezt gyorsan.

701
00:57:17,840 --> 00:57:21,030
Vagy keressen. Sort? Sort. Igen.

702
00:57:21,030 --> 00:57:22,730
Visszatérve a kezdetekhez a sort.

703
00:57:22,730 --> 00:57:29,870
Szeretnénk létrehozni egy olyan algoritmus, amely rendezi a tömb bármely algoritmus

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

705
00:57:33,660 --> 00:57:40,860
Hogy lehetséges ez? Van valakinek bármilyen -

706
00:57:40,860 --> 00:57:44,300
Én utalt mielőtt azt -

707
00:57:44,300 --> 00:57:48,300
Ha mindjárt javul n log n O n,

708
00:57:48,300 --> 00:57:51,450
már javult a algoritmus idő-bölcs,

709
00:57:51,450 --> 00:57:55,250
ami azt jelenti, hogy mit fogunk csinálni kell pótolni ezt?

710
00:57:55,250 --> 00:57:59,520
[Hallgató] Space. >> Igen. Fogunk használni több helyet.

711
00:57:59,520 --> 00:58:04,490
És nem is csak több helyet, hanem exponenciálisan nagyobb teret.

712
00:58:04,490 --> 00:58:14,320
Úgy gondolom, ez a fajta algoritmus pszeudo valami pszeudo polinom -

713
00:58:14,320 --> 00:58:18,980
pszeudo - Nem emlékszem. Pszeudo valamit.

714
00:58:18,980 --> 00:58:22,210
De ez azért van, mert meg kell használni, így sok helyet

715
00:58:22,210 --> 00:58:28,610
, hogy ez megvalósítható, de nem reális.

716
00:58:28,610 --> 00:58:31,220
>> És hogyan érhetjük el ezt?

717
00:58:31,220 --> 00:58:36,810
Mi lehet ennek elérésére, ha garantáljuk, hogy egy adott elem a tömbben

718
00:58:36,810 --> 00:58:39,600
ér el egy meghatározott méret.

719
00:58:42,070 --> 00:58:44,500
Akkor mondjuk, hogy a mérete 200,

720
00:58:44,500 --> 00:58:48,130
bármely elem egy tömb alatt van méret 200.

721
00:58:48,130 --> 00:58:51,080
És ez valóban nagyon reális.

722
00:58:51,080 --> 00:58:58,660
Akkor nagyon könnyen van egy tömb, hogy tudod, mindent, ami benne

723
00:58:58,660 --> 00:59:00,570
lesz kisebb, mint néhány szám.

724
00:59:00,570 --> 00:59:07,400
Mint ha van néhány teljesen masszív vektort vagy valami

725
00:59:07,400 --> 00:59:11,810
de tudod, minden rendben van, hogy 0 és 5 között,

726
00:59:11,810 --> 00:59:14,790
akkor lesz jelentősen gyorsabb erre.

727
00:59:14,790 --> 00:59:17,930
És a kötődött bármelyik az elemek 5,

728
00:59:17,930 --> 00:59:21,980
így ez a korlát, azaz mennyi memóriát fogsz használni.

729
00:59:21,980 --> 00:59:26,300
Tehát a korlát 200-at.

730
00:59:26,300 --> 00:59:32,960
Elméletileg van mindig egy kötött mert értéke csak legfeljebb 4 milliárd

731
00:59:32,960 --> 00:59:40,600
de ez reális cél, mivel akkor lenne a tér

732
00:59:40,600 --> 00:59:44,400
a sorrendben a 4 milliárdot. Szóval ez irreális.

733
00:59:44,400 --> 00:59:47,060
De itt mi mondjuk a korlát 200.

734
00:59:47,060 --> 00:59:59,570
A trükk az, hogy csinálja az O n teszünk egy sor úgynevezett rendbeli méretű kötve.

735
00:59:59,570 --> 01:00:10,470
Tehát tulajdonképpen ez egy parancsikont - Igazából nem tudom, ha csenget teszi ezt.

736
01:00:11,150 --> 01:00:15,330
De GCC legalább - Én feltételezve csenget csinálja is -

737
01:00:15,330 --> 01:00:18,180
ez csak inicializálja az egész tömb legyen 0s.

738
01:00:18,180 --> 01:00:25,320
Szóval, ha én nem akarom, hogy akkor én is külön-külön do for (int i = 0;

739
01:00:25,320 --> 01:00:31,500
i <BOUND; i + +) és számít [i] = 0;

740
01:00:31,500 --> 01:00:35,260
Tehát most mindent inicializálva 0-ra.

741
01:00:35,260 --> 01:00:39,570
Én iterációkhoz a tömb,

742
01:00:39,570 --> 01:00:51,920
és mit csinálok én számlálás a számát az egyes - Menjünk le ide.

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

744
01:00:55,480 --> 01:01:00,010
Amit én számolva ez az előfordulások számát az egyes elemei.

745
01:01:00,010 --> 01:01:03,470
Nézzünk ténylegesen hozzá még egy pár itt néhány ismétlődik.

746
01:01:03,470 --> 01:01:11,070
Tehát ez az érték van itt, az értékét a lesz array [i].

747
01:01:11,070 --> 01:01:14,850
Így val lehet 4 vagy 8, vagy bármi.

748
01:01:14,850 --> 01:01:18,870
És most számít, hogy hány az értéket láttam,

749
01:01:18,870 --> 01:01:21,230
így számít [val] + +;

750
01:01:21,230 --> 01:01:29,430
Miután ez megtörtént, számít fog kinézni 0001.

751
01:01:29,430 --> 01:01:42,190
Csináljuk számít [val] - KÖTELEZŐ + 1.

752
01:01:42,190 --> 01:01:48,230
>> Most, hogy csak azért, hogy figyelembe azt a tényt, hogy mi kezdődően 0.

753
01:01:48,230 --> 01:01:50,850
Tehát ha 200 lesz a legnagyobb számú,

754
01:01:50,850 --> 01:01:54,720
majd 0-200 jelentése 201 dolgok.

755
01:01:54,720 --> 01:02:01,540
Tehát számít, úgy fogsz kinézni, mint 00001, mert van egy 4.

756
01:02:01,540 --> 01:02:10,210
Akkor mi lesz, ha 0001 lesz egy 1-8-án index száma.

757
01:02:10,210 --> 01:02:14,560
Lesz egy 2-23-index száma.

758
01:02:14,560 --> 01:02:17,630
Mi lesz a 2 a 42. index száma.

759
01:02:17,630 --> 01:02:21,670
Így tudjuk használni száma.

760
01:02:34,270 --> 01:02:44,920
Szóval num_of_item = számít [i].

761
01:02:44,920 --> 01:02:52,540
És így ha num_of_item 2, ez azt jelenti, hogy szeretné szúrni 2-i száma

762
01:02:52,540 --> 01:02:55,290
a mi rendezett tömbben.

763
01:02:55,290 --> 01:03:02,000
Tehát meg kell nyomon követni, hogy milyen messze vagyunk a tömb.

764
01:03:02,000 --> 01:03:05,470
Tehát index = 0.

765
01:03:05,470 --> 01:03:09,910
Array - Én csak írni.

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

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

768
01:03:28,580 --> 01:03:32,490
Ez az, amit akarok? Azt hiszem, ez az, amit akarok.

769
01:03:35,100 --> 01:03:38,290
Igen, ez jól néz ki. Oké.

770
01:03:38,290 --> 01:03:43,050
Tehát nem mindenki érti, mi a célja az én számít tömb?

771
01:03:43,050 --> 01:03:48,140
Ez számít az előfordulások számát minden egyes ilyen számok.

772
01:03:48,140 --> 01:03:51,780
Akkor vagyok iterációjával felett számít tömb,

773
01:03:51,780 --> 01:03:57,190
és az i-edik pozícióját a szám tömb

774
01:03:57,190 --> 01:04:01,930
a szám az i ez jelenjen meg a rendezett tömbben.

775
01:04:01,930 --> 01:04:06,840
Ezért számít a 4 lesz 1

776
01:04:06,840 --> 01:04:11,840
és számít a 8 lesz 1, számuk 23 lesz 2.

777
01:04:11,840 --> 01:04:16,900
Szóval így sokan szeretnék illeszteni a rendezett tömbben.

778
01:04:16,900 --> 01:04:19,200
Aztán csak csinálni.

779
01:04:19,200 --> 01:04:28,960
Én behelyezése num_of_item i-az én rendezett tömbben.

780
01:04:28,960 --> 01:04:31,670
>> Kérdései vannak?

781
01:04:32,460 --> 01:04:43,100
És újra, ez a lineáris idő óta mi csak iterációjával át ezt egyszer,

782
01:04:43,100 --> 01:04:47,470
de ez is lineáris, mi ez a szám történetesen,

783
01:04:47,470 --> 01:04:50,730
és így nagymértékben attól függ, hogy mi a korlát.

784
01:04:50,730 --> 01:04:53,290
A kötött, 200, ez nem is olyan rossz.

785
01:04:53,290 --> 01:04:58,330
Ha a kötött lesz 10.000, akkor ez egy kicsit rosszabb,

786
01:04:58,330 --> 01:05:01,360
de ha a rögzített lesz 4 milliárd ez teljesen irreális

787
01:05:01,360 --> 01:05:07,720
és ez a tömb lesz, hogy legyen a méret 4 milliárd, ami irreális.

788
01:05:07,720 --> 01:05:10,860
Szóval ennyi. Kérdései vannak?

789
01:05:10,860 --> 01:05:13,270
[Hallhatatlan diák válasza] >> Oké.

790
01:05:13,270 --> 01:05:15,710
Rájöttem, egy másik dolog, ha megyünk keresztül.

791
01:05:17,980 --> 01:05:23,720
Azt hiszem, a probléma az volt, a Lucas és valószínűleg minden egyes ember láttunk.

792
01:05:23,720 --> 01:05:26,330
Teljesen elfelejtettem.

793
01:05:26,330 --> 01:05:31,040
Az egyetlen dolog, amit szerettem volna, hogy mondjon véleményt, hogy ha van dolgunk, dolgok, mint indexek,

794
01:05:31,040 --> 01:05:38,320
Ön soha nem látni ezt, ha írsz egy for ciklus,

795
01:05:38,320 --> 01:05:41,120
de technikailag, ha van dolgunk, ezek a mutatók,

796
01:05:41,120 --> 01:05:45,950
akkor nagyjából mindig foglalkozik előjel nélküli egészek.

797
01:05:45,950 --> 01:05:53,850
Ennek oka az, amikor dolgunk aláírt egészek,

798
01:05:53,850 --> 01:05:56,090
így ha van 2 aláírt egészek, és felveszi őket

799
01:05:56,090 --> 01:06:00,640
és a végén túl nagy, akkor a végén egy negatív szám.

800
01:06:00,640 --> 01:06:03,410
Szóval ez az, amit egész túlcsordulás.

801
01:06:03,410 --> 01:06:10,500
>> Ha hozzá 2 milliárd 1 milliárd I végén negatív 1 milliárd euró.

802
01:06:10,500 --> 01:06:15,480
Így egész munka számítógépeken.

803
01:06:15,480 --> 01:06:17,510
Tehát a probléma a -

804
01:06:17,510 --> 01:06:23,500
Ez rendben van, kivéve, ha az alacsony történik, hogy 2 milliárd legfeljebb történetesen 1 milliárd

805
01:06:23,500 --> 01:06:27,120
akkor ez lesz a negatív 1 milliárd és akkor fogjuk osztani, hogy a 2-

806
01:06:27,120 --> 01:06:29,730
és a végén a negatív 500 millió EUR.

807
01:06:29,730 --> 01:06:33,760
Tehát ez csak egy kérdés, ha történetesen kereső segítségével egy tömb

808
01:06:33,760 --> 01:06:38,070
milliárd a dolgokat.

809
01:06:38,070 --> 01:06:44,050
De ha kis +-ig történik túlcsordulás, akkor ez a probléma.

810
01:06:44,050 --> 01:06:47,750
Amint teszik aláíratlan, majd 2000000000 plusz 1 milliárd 3 milliárdot.

811
01:06:47,750 --> 01:06:51,960
3000000000 osztva 2 pedig 1,5 milliárd euró.

812
01:06:51,960 --> 01:06:55,670
Szóval, amint ők aláíratlan, minden tökéletes.

813
01:06:55,670 --> 01:06:59,900
És ez is egy olyan kérdés, amikor írsz be a hurkok,

814
01:06:59,900 --> 01:07:03,940
és valóban, ez valószínűleg nem teszi meg automatikusan.

815
01:07:09,130 --> 01:07:12,330
Ez valójában csak kiabálni veled.

816
01:07:12,330 --> 01:07:21,610
Tehát, ha ez a szám túl nagy lenni csak egy integer, de ez illik egy előjel nélküli egész,

817
01:07:21,610 --> 01:07:24,970
fog kiabálni, úgyhogy ez az, amiért soha nem befut a kérdést.

818
01:07:29,150 --> 01:07:34,820
Láthatjuk, hogy az index soha nem lesz negatív,

819
01:07:34,820 --> 01:07:39,220
és így, amikor iterációjával át egy tömb,

820
01:07:39,220 --> 01:07:43,970
akkor szinte mindig azt mondják, unsigned int i, de nem igazán kell.

821
01:07:43,970 --> 01:07:47,110
Dolgok mennek dolgozni nagyjából ugyanúgy.

822
01:07:48,740 --> 01:07:50,090
Oké. [Suttog] Mi van most?

823
01:07:50,090 --> 01:07:54,020
Az utolsó dolog, amit meg akartam mutatni - és én csak csinálni nagyon gyors.

824
01:07:54,020 --> 01:08:03,190
Tudod, hogy mi # define így tudjuk # define MAX mint 5, vagy valami?

825
01:08:03,190 --> 01:08:05,940
Ne tegye MAX. # Define KÖTELEZŐ, mint 200-at. Ez az, amit mi korábban.

826
01:08:05,940 --> 01:08:10,380
Ez határozza meg a konstans, ami csak megy a vágólapra másolni

827
01:08:10,380 --> 01:08:13,010
bárhol is történik, hogy írjon rá nézve kötelező.

828
01:08:13,010 --> 01:08:18,189
>> Tehát valójában többre # definiálja.

829
01:08:18,189 --> 01:08:21,170
Mi lehet a # define funkciókat.

830
01:08:21,170 --> 01:08:23,410
Ők nem igazán funkcióját, de fogjuk hívni őket funkciókat.

831
01:08:23,410 --> 01:08:36,000
Egy példa lenne, valami hasonlót MAX (x, y) meghatározása (x <y? Y: x). Oké.

832
01:08:36,000 --> 01:08:40,660
Szóval meg kell szokni hármas operátor szintaxisa,

833
01:08:40,660 --> 01:08:49,029
de x kisebb mint y? Vissza y, különben vissza x.

834
01:08:49,029 --> 01:08:54,390
Így látni lehet, hogy ez egy külön funkció,

835
01:08:54,390 --> 01:09:01,399
és a funkció lehet, mint bool MAX úgy 2 érvek vissza ezt.

836
01:09:01,399 --> 01:09:08,340
Ez az egyik a leggyakoribbak látom kész így. Hívjuk őket makrókat.

837
01:09:08,340 --> 01:09:11,790
Ez egy makrót.

838
01:09:11,790 --> 01:09:15,859
Ez csak a szintaxis is.

839
01:09:15,859 --> 01:09:18,740
Írhat makrót csinálsz, amit akarsz.

840
01:09:18,740 --> 01:09:22,649
Ön gyakran látni makrók hibakeresési printfs, meg ilyesmi.

841
01:09:22,649 --> 01:09:29,410
Tehát egyfajta printf, vannak speciális állandók C mint aláhúzás LINE aláhúzás,

842
01:09:29,410 --> 01:09:31,710
2 aláhúzás LINE aláhúzás,

843
01:09:31,710 --> 01:09:37,550
és ott is azt hiszem 2 aláhúzás FUNC. Lehet, hogy azt. Valami ilyesmi.

844
01:09:37,550 --> 01:09:40,880
Azok a dolgok váltják fel a nevét, a funkció

845
01:09:40,880 --> 01:09:42,930
vagy a számot a sor, hogy te vagy az.

846
01:09:42,930 --> 01:09:48,630
Gyakran írsz hibakeresés printfs, hogy ide tudok majd csak írni

847
01:09:48,630 --> 01:09:54,260
DEBUG, és kiírja a sor számát és a funkció, hogy én történetesen

848
01:09:54,260 --> 01:09:57,020
hogy felmerült, hogy DEBUG nyilatkozatot.

849
01:09:57,020 --> 01:09:59,550
És te is nyomtathatja más dolog.

850
01:09:59,550 --> 01:10:05,990
Tehát az egyik dolog, amit meg kell nézni ki, ha én történetesen # define DOUBLE_MAX

851
01:10:05,990 --> 01:10:11,380
valami, mint a 2 * 2 * y és x.

852
01:10:11,380 --> 01:10:14,310
Tehát bármilyen okból, véletlenül csinálni, hogy egy csomó.

853
01:10:14,310 --> 01:10:16,650
Tehát, hogy ez egy makrót.

854
01:10:16,650 --> 01:10:18,680
Ez ténylegesen sérült.

855
01:10:18,680 --> 01:10:23,050
Hívnám azt csinál valami ilyesmi DOUBLE_MAX (3, 6).

856
01:10:23,050 --> 01:10:27,530
Szóval mit kell visszaküldeni?

857
01:10:28,840 --> 01:10:30,580
[Hallgató] 12.

858
01:10:30,580 --> 01:10:34,800
Igen, 12 vissza kell küldeni, és 12 van vissza.

859
01:10:34,800 --> 01:10:43,350
3 kap helyébe az x, 6 lesz helyettesíteni y, és mi vissza 2 * 6, amely a 12.

860
01:10:43,350 --> 01:10:47,710
Most mi van ezzel? Mit kell vissza?

861
01:10:47,710 --> 01:10:50,330
[Hallgató] 14. >> Ideális esetben 14.

862
01:10:50,330 --> 01:10:55,290
A kérdés az, hogy mennyire hash meghatározza a munka, ne feledje, ez egy szó szerinti másolás és beillesztés

863
01:10:55,290 --> 01:11:00,160
Az elég sok mindent, akkor mi ez lesz kell értelmezni,

864
01:11:00,160 --> 01:11:11,270
3 kisebb, mint 1 és 6, 2-szer 1 és 6, 2-szer 3.

865
01:11:11,270 --> 01:11:19,780
>> Szóval ezért szinte mindig mindent betakar zárójelben.

866
01:11:22,180 --> 01:11:25,050
Minden változó, szinte mindig csomagolja zárójelben.

867
01:11:25,050 --> 01:11:29,570
Vannak olyan esetek, amikor nem kell, mint tudom, hogy nem kell csinálni, hogy itt

868
01:11:29,570 --> 01:11:32,110
mert kevesebb, mint nagyjából mindig csak működni fog,

869
01:11:32,110 --> 01:11:34,330
annak ellenére, hogy talán nem is igaz.

870
01:11:34,330 --> 01:11:41,870
Ha van valami nevetséges, mint DOUBLE_MAX (1 == 2),

871
01:11:41,870 --> 01:11:49,760
akkor ez fog kap helyett 3 kevesebb, mint 1 egyenlő értéke 2,

872
01:11:49,760 --> 01:11:53,460
és így akkor fog csinálni 3 kevesebb, mint 1, nem, hogy az egyenlő 2,

873
01:11:53,460 --> 01:11:55,620
ami nem az, amit akarunk.

874
01:11:55,620 --> 01:12:00,730
Így annak érdekében, hogy megakadályozza operátor precedencia problémákat,

875
01:12:00,730 --> 01:12:02,870
Mindig csomagolja zárójelben.

876
01:12:03,290 --> 01:12:07,700
Oké. És ez az, 5:30.

877
01:12:08,140 --> 01:12:12,470
Ha bármilyen kérdése van a Pset, tudassa velünk.

878
01:12:12,470 --> 01:12:18,010
Meg lehet szórakoztató, és a hacker kiadás is sokkal reálisabb

879
01:12:18,010 --> 01:12:22,980
mint a hacker kiadása a tavalyi, ezért reméljük, hogy sok nem próbálja meg.

880
01:12:22,980 --> 01:12:26,460
A tavalyi nagyon nyomasztó.

881
01:12:28,370 --> 01:12:30,000
>> [CS50.TV]