1
00:00:00,000 --> 00:00:02,570
[Powered by Google Translate] [3. jagu - mugavam]

2
00:00:02,570 --> 00:00:05,070
[Rob Bowden - Harvardi Ülikool]

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

4
00:00:07,310 --> 00:00:12,700
>> Nii et esimene küsimus on kummaliselt sõnastatud.

5
00:00:12,700 --> 00:00:17,480
GDB saate "siluda" programm, kuid täpsemalt, mida see teile teha?

6
00:00:17,480 --> 00:00:22,590
Ma vastan, et üks, ja ma ei tea, mis täpselt oodatakse,

7
00:00:22,590 --> 00:00:27,910
nii et ma olen aim see on midagi eeskujul ta laseb teid samm-sammult

8
00:00:27,910 --> 00:00:31,540
kõndida läbi programmi, suhelda ta, muutus muutujaid, teha kõiki neid asju -

9
00:00:31,540 --> 00:00:34,270
põhimõtteliselt täielikult kontrolli täitmise programmi

10
00:00:34,270 --> 00:00:38,410
ja kontrollida mis tahes osa programmi täitmiseks.

11
00:00:38,410 --> 00:00:43,030
Nii et need funktsioonid võimaldavad teil siluda asju.

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

13
00:00:44,830 --> 00:00:50,520
Miks binaarne otsing nõuda, et massiiv sorteeritud?

14
00:00:50,520 --> 00:00:53,360
Kes tahab sellele vastata?

15
00:00:56,120 --> 00:01:00,070
[Üliõpilane] Sest see ei toimi, kui see ei järjestatud. >> Jah. [Naer]

16
00:01:00,070 --> 00:01:04,910
Kui see ei ole sorteeritud, siis on võimatu jagada see pooleks

17
00:01:04,910 --> 00:01:07,850
ja tean, et kõik vasakule on vähem ja kõike paremal

18
00:01:07,850 --> 00:01:10,490
on üle keskmise väärtuse.

19
00:01:10,490 --> 00:01:12,790
Seega tuleb välja sorteerida.

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

21
00:01:14,170 --> 00:01:17,570
Miks on mull sorteerida O n ruudus?

22
00:01:17,570 --> 00:01:23,230
Kas keegi kõigepealt tahan anda väga kiire kõrgetasemeline ülevaade sellest, mis mull sorteerida on?

23
00:01:25,950 --> 00:01:33,020
[Üliõpilane] Sa põhimõtteliselt läbida iga element ja teil vaadata esimese paari elemente.

24
00:01:33,020 --> 00:01:37,150
Kui nad välja, kus sa vahetada neid, siis vaadake järgmise paari elemente ja nii edasi.

25
00:01:37,150 --> 00:01:40,770
Kui jõuad lõpuks, siis sa tead, et suurim element on paigutatud lõpus,

26
00:01:40,770 --> 00:01:42,750
nii et sa ignoreerida, et üks siis hoida läheb läbi,

27
00:01:42,750 --> 00:01:48,490
ja iga kord, sa pead kontrollima üks vähem element, kuni te ei muudeta. >> Jah.

28
00:01:48,490 --> 00:01:58,470
Seda nimetatakse mull sorteerida, sest kui sa flip massiivi küljel nii et see on üles ja alla, vertikaalne,

29
00:01:58,470 --> 00:02:03,100
siis suur väärtused vajuvad põhja ja väikesed väärtused mulksuma üles.

30
00:02:03,100 --> 00:02:05,210
See, kuidas ta sai oma nime.

31
00:02:05,210 --> 00:02:08,220
Ja jaa, sa lihtsalt läbi minema.

32
00:02:08,220 --> 00:02:11,190
Hoiad läbimas massiivi, vahetades suuremat väärtust

33
00:02:11,190 --> 00:02:14,040
saada suurim väärtused alt.

34
00:02:14,040 --> 00:02:17,500
>> Miks on O n ruudus?

35
00:02:18,690 --> 00:02:24,620
Esiteks, keegi ei taha öelda, miks see O n ruudus?

36
00:02:24,620 --> 00:02:28,760
[Üliõpilane] Sest iga katse läheb n korda.

37
00:02:28,760 --> 00:02:32,100
Võite kindel olla vaid siis, kui olete võtnud suurima osa kogu tee alla,

38
00:02:32,100 --> 00:02:35,230
siis sa pead kordama, et nii palju elemente. >> Jah.

39
00:02:35,230 --> 00:02:41,800
Nii et pidage meeles, mida Big O tähendab ja mida suur Omega vahenditega.

40
00:02:41,800 --> 00:02:50,560
Big O on nagu ülemise kuidas aeglane see saab reaalselt sõita.

41
00:02:50,560 --> 00:02:58,990
Nii öeldes see O n ruudus, see ei ole O n muidu oleks võimelised sõitma

42
00:02:58,990 --> 00:03:02,640
üksteise aega, kuid see on O n kuubis

43
00:03:02,640 --> 00:03:06,390
sest see on piiratud O n kuubis.

44
00:03:06,390 --> 00:03:12,300
Kui see on piiratud O n ruudus, siis see on piiratud ka n kuubis.

45
00:03:12,300 --> 00:03:20,280
Nii et see on n ruudus, ja absoluutne halvimal juhul ei saa teha paremini kui n ruudus,

46
00:03:20,280 --> 00:03:22,830
mis on põhjus, miks see O n ruudus.

47
00:03:22,830 --> 00:03:31,200
Nii et näha kerget matemaatikat, kuidas asi välja tuleb n ruudus,

48
00:03:31,200 --> 00:03:40,530
kui meil on viis asju meie nimekirjas, esimest korda, kuidas paljud vahetustehingud võiks meil olla vaja teha

49
00:03:40,530 --> 00:03:47,170
et saada seda? Olgem tegelikult lihtsalt -

50
00:03:47,170 --> 00:03:52,040
Mitu vahetuslepingud me kavatseme peavad tegema, esimene sõit mull sorteerida läbi massiivi?

51
00:03:52,040 --> 00:03:53,540
[Üliõpilane] n - 1. >> Jah.

52
00:03:53,540 --> 00:03:58,340
>> Kui seal on 5 elementi, me ei kavatse vaja teha n - 1.

53
00:03:58,340 --> 00:04:01,100
Siis teine, kui palju vahetuslepingud me kavatseme tegema?

54
00:04:01,100 --> 00:04:03,440
[Üliõpilane] n - 2. >> Jah.

55
00:04:03,440 --> 00:04:11,640
Ja kolmas saab olema n - 3 ja seejärel lükitud ma kirjutan kahe viimase

56
00:04:11,640 --> 00:04:15,270
kui siis lähed vaja teha 2 vahetuslepingud ja 1 swap.

57
00:04:15,270 --> 00:04:19,899
Ma arvan, et viimane ei pruugi tegelikult vaja juhtuda.

58
00:04:19,899 --> 00:04:22,820
Kas see swap? Ma ei tea.

59
00:04:22,820 --> 00:04:26,490
Nii et need on kogusummad vahetuslepingud või vähemalt võrdlusi sa pead tegema.

60
00:04:26,490 --> 00:04:29,910
Isegi kui te ei vaheta, ikka on vaja võrrelda väärtusi.

61
00:04:29,910 --> 00:04:33,910
Nii on n - 1 võrdlust esietendus läbi massiivi.

62
00:04:33,910 --> 00:04:42,050
Kui teil ümber need asjad, olgem tegelikult teha seda kuus asjad nii asjad Kestab ilusti,

63
00:04:42,050 --> 00:04:44,790
ja siis ma teen 3, 2, 1.

64
00:04:44,790 --> 00:04:49,910
Nii lihtsalt ümber tõstes need summad, me tahame näha, kuidas paljud võrdlused teeme

65
00:04:49,910 --> 00:04:52,700
kogu algoritm.

66
00:04:52,700 --> 00:04:56,550
Nii et kui me toome need kutid siin all,

67
00:04:56,550 --> 00:05:07,470
siis me veel lihtsalt liidetakse siiski palju võrdlusi oli.

68
00:05:07,470 --> 00:05:13,280
Aga kui me kokku neid ja me Kokkuvõttes need ja me Kokkuvõttes need,

69
00:05:13,280 --> 00:05:18,130
see on ikka sama probleem. Me lihtsalt kokku nende konkreetsete rühmade.

70
00:05:18,130 --> 00:05:22,400
>> Nii et nüüd me liidetakse 3 n 's. See ei ole lihtsalt 3 n 's.

71
00:05:22,400 --> 00:05:27,650
See on alati saab olema n / 2 n 's.

72
00:05:27,650 --> 00:05:29,430
Nii et siin me juhtumisi on 6.

73
00:05:29,430 --> 00:05:34,830
Kui meil oleks 10 asja, siis võiks seda teha rühmituse 5 erinevat paari asja

74
00:05:34,830 --> 00:05:37,180
ja lõpuks n + n + n + n + n.

75
00:05:37,180 --> 00:05:45,840
Nii olete alati hakka n / 2 n on, ja nii see me kübeke see välja n ruudus / 2.

76
00:05:45,840 --> 00:05:48,890
Ja nii kuigi see on tegur poole, mis juhtub tulema

77
00:05:48,890 --> 00:05:54,190
sest asjaolu, et läbi iga iteratsiooni üle massiivi me võrdleme 1 vähem

78
00:05:54,190 --> 00:05:58,040
nii see on, kuidas me saame üle 2, aga see on ikkagi n ruudus.

79
00:05:58,040 --> 00:06:01,650
Me ei hooli pidev tegur poole.

80
00:06:01,650 --> 00:06:07,760
Nii palju suuri O selliseid asju toetub just selline seda selline matemaatika,

81
00:06:07,760 --> 00:06:12,260
tehes aritmeetika summad ja geomeetrilise jadana kraami,

82
00:06:12,260 --> 00:06:17,750
kuid enamik neist selles muidugi on üsna lihtne.

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

84
00:06:19,290 --> 00:06:24,430
Miks on sisestamise omamoodi Omega n? Mis omega tähendab?

85
00:06:24,430 --> 00:06:27,730
[Kaks üliõpilast rääkides korraga - arusaamatu] >> Jah.

86
00:06:27,730 --> 00:06:30,630
Omega sa ei mõtle nagu alampiir.

87
00:06:30,630 --> 00:06:36,550
>> Nii et ükskõik kui tõhus teie sisestamise omamoodi algoritm on,

88
00:06:36,550 --> 00:06:41,810
olenemata nimekirja, mis on vastu võetud, see on alati võrrelda vähemalt n asjad

89
00:06:41,810 --> 00:06:44,620
või peab ta itereerime n asju.

90
00:06:44,620 --> 00:06:47,280
Miks nii?

91
00:06:47,280 --> 00:06:51,190
[Üliõpilane] Sest kui nimekiri on juba sorteeritud, siis läbi esimese iteratsiooni

92
00:06:51,190 --> 00:06:54,080
saab ainult tagada, et kõige esimene element on vähim,

93
00:06:54,080 --> 00:06:56,490
ja teise iteratsiooni saab ainult tagada kaks esimest on

94
00:06:56,490 --> 00:07:00,010
sest sa ei tea, et ülejäänud nimekirja sorteeritakse. >> Jah.

95
00:07:00,010 --> 00:07:08,910
Kui te kaotate täiesti järjestatud nimekirja, vähemalt sa pead minema üle kõik elemendid

96
00:07:08,910 --> 00:07:12,180
näha, et midagi tuleb liigutada.

97
00:07:12,180 --> 00:07:14,720
Nii jooksevad üle nimekirja ja ütleb Oh, see on juba sorteeritud,

98
00:07:14,720 --> 00:07:18,240
see on võimatu, et sa teaksid seda inimest järjestatud kuni teil kontrollida iga element

99
00:07:18,240 --> 00:07:20,660
näha, et nad on järjestatud järjekorras.

100
00:07:20,660 --> 00:07:25,290
Nii alampiiri sisestamise sorteerida on Omega n.

101
00:07:25,290 --> 00:07:28,210
Mis halvimal juhul sõiduaega ühendamise sortida,

102
00:07:28,210 --> 00:07:31,390
Halvimal juhul on suur O uuesti?

103
00:07:31,390 --> 00:07:37,660
Nii et halvimal juhul kuidas ühendamise omamoodi joosta?

104
00:07:42,170 --> 00:07:43,690
[Üliõpilane] N log n. >> Jah.

105
00:07:43,690 --> 00:07:49,990
Kiireim üldine sortimine algoritmid on n log n. Sa ei saa teha paremini.

106
00:07:51,930 --> 00:07:55,130
>> On erijuhtudel, ja kui meil on aega täna - kuid me ilmselt won't -

107
00:07:55,130 --> 00:07:59,330
me ei näe sellist, mis ei parem kui n log n.

108
00:07:59,330 --> 00:08:04,050
Aga üldiselt juhul, ei saa te teha paremini kui n log n.

109
00:08:04,050 --> 00:08:09,680
Ja ühendada omamoodi juhtub olema üks sa peaksid teadma seda muidugi, et on n log n.

110
00:08:09,680 --> 00:08:13,260
Ja nii me tegelikult rakendatakse, et täna.

111
00:08:13,260 --> 00:08:18,070
Ja lõpuks, mitte rohkem kui kolm lauset, kuidas valik omamoodi töö?

112
00:08:18,070 --> 00:08:20,370
Kas keegi taha vastata, ja Ma loen oma lauseid

113
00:08:20,370 --> 00:08:22,390
sest kui te lähete üle 3 -

114
00:08:25,530 --> 00:08:28,330
Kas keegi mäletab valik omamoodi?

115
00:08:31,280 --> 00:08:37,809
Selection sort on tavaliselt üsna lihtne meeles pidada lihtsalt nimest.

116
00:08:37,809 --> 00:08:45,350
Sa lihtsalt kinnitada, üle massiivi, leida mida iganes suurim väärtus on või väikseim -

117
00:08:45,350 --> 00:08:47,290
mida iganes et sa sorteerimine sisse

118
00:08:47,290 --> 00:08:50,750
Ütleme, et me sorteerimine alates väiksemast suurim.

119
00:08:50,750 --> 00:08:55,250
Sa itereerime massiiv, otsin tahes minimaalne element on,

120
00:08:55,250 --> 00:08:59,750
valige see ja siis lihtsalt vahetada see kõik, mis on esimene koht.

121
00:08:59,750 --> 00:09:04,090
Ja siis teine ​​kiht üle massiivi, otsida minimaalne element uuesti

122
00:09:04,090 --> 00:09:07,490
valige see ja siis vahetada see, mida on teisel positsioonil.

123
00:09:07,490 --> 00:09:10,650
Nii et me lihtsalt korjamise ja valides miinimumväärtustest

124
00:09:10,650 --> 00:09:16,050
ja lisades need ees massiivi, kuni see on lahendatud.

125
00:09:19,210 --> 00:09:21,560
Küsimused, mis?

126
00:09:21,560 --> 00:09:25,710
>> Need paratamatult esinevad vormid pead täitma, kui sisestad pset.

127
00:09:29,010 --> 00:09:32,360
Need on põhiliselt vastused nendele.

128
00:09:32,360 --> 00:09:34,230
Okei, nii et nüüd kodeerimine probleeme.

129
00:09:34,230 --> 00:09:40,140
Ma juba välja saadetud e-posti kaudu - Kas keegi ei saa seda e-maili? Okei.

130
00:09:40,140 --> 00:09:46,630
Ma juba välja saadetud e-posti kaudu ruumi, et me ei kavatse olla kasutades,

131
00:09:46,630 --> 00:09:52,120
ja kui sa vajutad mu nime - nii et ma arvan, et ma lähen allosas

132
00:09:52,120 --> 00:09:57,170
sest tagurpidi r - aga kui klõpsate minu nimi näete 2 revisions.

133
00:09:57,170 --> 00:10:02,650
1. läbivaatamine läheb mul juba kopeeritud ja kleebitud kood Spaces

134
00:10:02,650 --> 00:10:06,900
otsingu asi, mida sa lähed on rakendada.

135
00:10:06,900 --> 00:10:10,540
Ja Revision 2 on omamoodi asi, mida me rakendada pärast seda.

136
00:10:10,540 --> 00:10:15,770
Nii et võite klõpsata minu muudatuse 1. ja tööd sealt.

137
00:10:17,350 --> 00:10:22,060
Ja nüüd me tahame ellu binaarne otsing.

138
00:10:22,060 --> 00:10:26,470
>> Kas keegi taha lihtsalt anda pseudokoodi kõrgetasemeline selgitus

139
00:10:26,470 --> 00:10:31,440
mida me lähed on teha otsingut? Jah.

140
00:10:31,440 --> 00:10:36,170
[Üliõpilane] Sa võta keset massiivi ja vaata, kas see, mida te otsite

141
00:10:36,170 --> 00:10:38,650
on väiksem kui või rohkem.

142
00:10:38,650 --> 00:10:41,080
Ja kui see on väiksem, kui minna pool on vähem,

143
00:10:41,080 --> 00:10:44,750
ja kui see on rohkem, kui minna pool on rohkem ja sa korrata, et kuni sa saad ühe asja.

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

145
00:10:46,570 --> 00:10:51,320
Pange tähele, et meie numbrid massiiv on juba sorteeritud,

146
00:10:51,320 --> 00:10:57,190
ja nii see tähendab, et me võime ära ja me võiks kõigepealt kontrollida,

147
00:10:57,190 --> 00:11:00,390
okei, ma otsin number 50.

148
00:11:00,390 --> 00:11:03,720
Nii et ma ei saa minna keset.

149
00:11:03,720 --> 00:11:07,380
Lähis on raske määratleda, kui see on isegi mitmeid asju,

150
00:11:07,380 --> 00:11:10,820
aga ütleme lihtsalt me ​​alati välja lülitada laeva keskel.

151
00:11:10,820 --> 00:11:14,420
Nii et siin on meil 8 asju, nii keskel oleks 16.

152
00:11:14,420 --> 00:11:17,330
Otsin 50, nii 50 on suurem kui 16.

153
00:11:17,330 --> 00:11:21,310
Nii et nüüd ma ei põhimõtteliselt ravida minu massiivi kui neid elemente.

154
00:11:21,310 --> 00:11:23,450
Ma ei visata kõik 16 üle.

155
00:11:23,450 --> 00:11:27,440
Nüüd on mu massiiv on lihtsalt need 4 elementi, ja ma kordan.

156
00:11:27,440 --> 00:11:31,910
Nii siis ma tahan leida uuesti keskel, mis saab olema 42.

157
00:11:31,910 --> 00:11:34,730
42 on alla 50, nii et ma ei viska need kaks elementi.

158
00:11:34,730 --> 00:11:36,890
See on minu ülejäänud massiiv.

159
00:11:36,890 --> 00:11:38,430
Ma lähen leida kuldset uuesti.

160
00:11:38,430 --> 00:11:42,100
Ma arvan, et 50 oli halb näide, sest olin alati visata ära asju vasakule,

161
00:11:42,100 --> 00:11:48,280
kuid sama meetme, kui ma otsin midagi

162
00:11:48,280 --> 00:11:52,100
ja see on väiksem kui element Ma olen praegu vaadates,

163
00:11:52,100 --> 00:11:55,080
siis ma lähen ära visata kõik paremale.

164
00:11:55,080 --> 00:11:58,150
Nii et nüüd me peame rakendama seda.

165
00:11:58,150 --> 00:12:02,310
Pange tähele, et meil on vaja läbida suurusega.

166
00:12:02,310 --> 00:12:06,730
Me võime ka ei pea raskesti koodi suurusest.

167
00:12:06,730 --> 00:12:11,640
Nii et kui me vabaneme sellest # define -

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

169
00:12:21,430 --> 00:12:27,180
Kuidas ma saan kenasti aru saada, mis suurust numbrid array praegu on?

170
00:12:27,180 --> 00:12:30,950
>> Mitu elemendid on numbrid massiivi?

171
00:12:30,950 --> 00:12:33,630
[Üliõpilane] Numbrid, sulgudes. Pikkus?

172
00:12:33,630 --> 00:12:36,600
[Bowden] See ei eksisteeri C.

173
00:12:36,600 --> 00:12:38,580
Vajad. Pikkus.

174
00:12:38,580 --> 00:12:42,010
Massiivid ei ole omadusi, mistõttu ei ole pikkus vara massiivid

175
00:12:42,010 --> 00:12:45,650
mis just teile kui kaua see juhtub olema.

176
00:12:48,180 --> 00:12:51,620
[Üliõpilane] Vaadake kui palju mälu on ja jagage kui palju - >> Jah.

177
00:12:51,620 --> 00:12:55,810
Niisiis, kuidas me saame näha, kui palju mälu tal on? >> [Üliõpilane] sizeof. >> Jah, sizeof.

178
00:12:55,810 --> 00:13:01,680
Sizeof on operaator, et läheb tagasi suurusest numbrid massiivi.

179
00:13:01,680 --> 00:13:10,060
Ja see saab olema siiski palju täisarvud on korda suurem täisarv

180
00:13:10,060 --> 00:13:14,050
kuna see, kui palju mälu see on tegelikult asumist.

181
00:13:14,050 --> 00:13:17,630
Nii et kui ma tahan palju asju on massiiv,

182
00:13:17,630 --> 00:13:20,560
siis ma lähen taha jagage suurus täisarv.

183
00:13:22,820 --> 00:13:26,010
Okei. Nii et laseb mul läbida suurus siin.

184
00:13:26,010 --> 00:13:29,430
Miks ma pean läbima suurus üldse?

185
00:13:29,430 --> 00:13:38,570
Miks ma ei saa lihtsalt teha siin int size = sizeof (heinakuhjas) / sizeof (int)?

186
00:13:38,570 --> 00:13:41,490
Miks see ei tööta?

187
00:13:41,490 --> 00:13:44,470
[Üliõpilane] See ei ole globaalne muutuja.

188
00:13:44,470 --> 00:13:51,540
[Bowden] heinakuhi olemas ja me läbivad numbrid nagu heinakuhi,

189
00:13:51,540 --> 00:13:54,700
ja see on selline foreshadowing Mis tulema. Jah.

190
00:13:54,700 --> 00:14:00,170
[Üliõpilane] heinakuhi on vaid viide sellele, et ta oleks tagasi, kui suur see viide.

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

192
00:14:02,150 --> 00:14:09,000
Ma kahtlen, loeng, et olete näinud korstnat veel tegelikult, eks?

193
00:14:09,000 --> 00:14:11,270
Me oleme lihtsalt rääkinud ta.

194
00:14:11,270 --> 00:14:16,090
Nii et korstnat on koht, kus kõik oma muutujad ei kavatse hoida.

195
00:14:16,090 --> 00:14:19,960
>> Iga mälu, mis on eraldatud kohalike muutujate läheb pakis,

196
00:14:19,960 --> 00:14:24,790
ja iga funktsiooni saab oma ruumi korstnat oma freimi on, kuidas seda nimetatakse.

197
00:14:24,790 --> 00:14:31,590
Nii et peamine on selle freimi, ja sees see saab eksisteerida see numbrite massiiv,

198
00:14:31,590 --> 00:14:34,270
ja see saab olema nende suurusest sizeof (numbrid).

199
00:14:34,270 --> 00:14:38,180
See saab olema suurus numbrid jagatud suurus elemendid,

200
00:14:38,180 --> 00:14:42,010
aga et kõik elu jooksul peamine on freimi.

201
00:14:42,010 --> 00:14:45,190
Kui me kutsume otsing, otsing sai oma freimi,

202
00:14:45,190 --> 00:14:48,840
oma ruumi, et salvestada kõik oma lokaalsed muutujad.

203
00:14:48,840 --> 00:14:56,420
Aga need argumendid - nii heinakuhjas ei ole koopia sellest kogu massiiv.

204
00:14:56,420 --> 00:15:00,990
Me ei liigu kogu massiivi koopia arvesse otsing.

205
00:15:00,990 --> 00:15:04,030
See lihtsalt läheb viidates, et massiivi.

206
00:15:04,030 --> 00:15:11,470
Nii et otsi pääseb need numbrid läbi see viide.

207
00:15:11,470 --> 00:15:17,100
See on ikka tutvumise asjad, mis elada sees peamine on freimi,

208
00:15:17,100 --> 00:15:22,990
aga põhimõtteliselt, kui saame vihjeid, mida tuleks kiiresti,

209
00:15:22,990 --> 00:15:24,980
see on see, mida osuti on.

210
00:15:24,980 --> 00:15:29,400
Näiturid on vaid viiteid asju, ja mida saab kasutada viiteid juurdepääsu asjad

211
00:15:29,400 --> 00:15:32,030
mis on muud asjad "korstnat raame.

212
00:15:32,030 --> 00:15:37,660
Nii et kuigi numbrid on kohaliku Otse me siiski võimalik seda läbi selle osuti.

213
00:15:37,660 --> 00:15:41,770
Aga kuna see on lihtsalt kursor ja see on lihtsalt viide,

214
00:15:41,770 --> 00:15:45,040
sizeof (heinakuhjas) lihtsalt tagastab suuruse viide ise.

215
00:15:45,040 --> 00:15:47,950
See ei tagasta suuruse asi see osutab.

216
00:15:47,950 --> 00:15:51,110
See ei tagasta tegeliku suuruse numbrid.

217
00:15:51,110 --> 00:15:55,660
Ja nii see ei lähe tööle, kui me tahame seda.

218
00:15:55,660 --> 00:15:57,320
>> Küsimused, mis?

219
00:15:57,320 --> 00:16:03,250
Näiturid on läinud oluliselt rohkem Verine üksikasjalikult lähinädalatel.

220
00:16:06,750 --> 00:16:13,740
Ja see on põhjus, miks paljud asjad, mis sa näed, kõige otsing asju või järjesta asju,

221
00:16:13,740 --> 00:16:16,990
Nad on peaaegu kõik läheb vaja võtta tegelikku suurust massiivi

222
00:16:16,990 --> 00:16:20,440
sest C, me ei tea, mis suurus massiiv on.

223
00:16:20,440 --> 00:16:22,720
Sa pead käsitsi andke seda sisse

224
00:16:22,720 --> 00:16:27,190
Ja sa ei saa käsitsi läbida kogu antennide massiivi, sest sa oled lihtsalt möödaminnes viide

225
00:16:27,190 --> 00:16:30,390
ja see ei saa suurus viide.

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

227
00:16:32,300 --> 00:16:38,160
Nii et nüüd me tahame rakendada, mida seletati varem.

228
00:16:38,160 --> 00:16:41,530
Võite töötada seda hetke,

229
00:16:41,530 --> 00:16:45,250
ja sa ei pea muretsema kõik täiesti 100% töökorras.

230
00:16:45,250 --> 00:16:51,410
Lihtsalt kirjutada üles poole pseudokoodi, kuidas sa arvad, et see peaks toimima.

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

232
00:16:53,630 --> 00:16:56,350
Pole vaja olla täiesti teha seda veel.

233
00:16:56,350 --> 00:17:02,380
Aga kas keegi on mugav, mida nad on seni

234
00:17:02,380 --> 00:17:05,599
nagu midagi saame teha koos?

235
00:17:05,599 --> 00:17:09,690
Kas keegi soovite vabatahtlikuna? Või ma juhuslikult kätte.

236
00:17:12,680 --> 00:17:18,599
See ei pea olema õigus mis tahes meede, kuid midagi saame muuta ühte toimivat riiki.

237
00:17:18,599 --> 00:17:20,720
[Üliõpilane] Muidugi. >> Okei.

238
00:17:20,720 --> 00:17:27,220
Nii saab säästa läbivaatamise klikkides vähe Save ikoonil.

239
00:17:27,220 --> 00:17:29,950
Sa oled Ramya, eks? >> [Üliõpilane] Jah. >> [Bowden] Okei.

240
00:17:29,950 --> 00:17:35,140
Nii et nüüd on mul võimalik näha oma läbivaatamine ning igaüks võib tõmba läbi vaadata.

241
00:17:35,140 --> 00:17:38,600
Ja siin on meil - Okei.

242
00:17:38,600 --> 00:17:43,160
Nii Ramya läks rekursiivne lahendus, mis on kindlasti kehtiv lahendus.

243
00:17:43,160 --> 00:17:44,970
On kaks võimalust, mida saate teha selle probleemiga.

244
00:17:44,970 --> 00:17:48,060
Võite teha seda korduvalt või rekursiivselt.

245
00:17:48,060 --> 00:17:53,860
Enamik probleeme sul tekib, mida saab teha rekursiivselt saab teha ka korduvalt.

246
00:17:53,860 --> 00:17:58,510
Nii et siin me oleme teinud seda rekursiivselt.

247
00:17:58,510 --> 00:18:03,730
>> Kas keegi soovite määratleda, mida tähendab teha funktsiooni rekursiivne?

248
00:18:07,210 --> 00:18:08,920
[Üliõpilane] Kui teil on funktsioon kõne ise

249
00:18:08,920 --> 00:18:13,470
ja siis helistada ise, kuni see väljub õige ja tõsi. >> Jah.

250
00:18:13,470 --> 00:18:17,680
Rekursiivne funktsioon on lihtsalt funktsioon, mis nimetab ennast.

251
00:18:17,680 --> 00:18:24,140
On kolm suurt asja, et rekursiivne funktsioon peab olema.

252
00:18:24,140 --> 00:18:27,310
Esimene on ilmselt see nõuab ise.

253
00:18:27,310 --> 00:18:29,650
Teine on tugipunkt.

254
00:18:29,650 --> 00:18:33,390
Nii et mingil hetkel funktsioon vajab lõpetada helistab ise,

255
00:18:33,390 --> 00:18:35,610
ja see on, mida tugipunkti on.

256
00:18:35,610 --> 00:18:43,860
Nii et siin me teame, et peaksime lõpetama, me peaksime loobuma oma otsing

257
00:18:43,860 --> 00:18:48,150
kui start võrdub lõppu - ja läheme üle, mida see tähendab.

258
00:18:48,150 --> 00:18:52,130
Aga lõpuks, viimane asi, mis on oluline rekursiivne funktsioone:

259
00:18:52,130 --> 00:18:59,250
funktsioonid tuleb kuidagi läheneda tugipunkti.

260
00:18:59,250 --> 00:19:04,140
Nagu kui sa ei ole tegelikult ajakohastamine midagi, kui teete teise rekursiivne kõne

261
00:19:04,140 --> 00:19:07,880
kui sa sõna otseses mõttes lihtsalt kutsutakse funktsioon uuesti samad argumendid

262
00:19:07,880 --> 00:19:10,130
ja ei globaalsed muutujad on muutunud või midagi,

263
00:19:10,130 --> 00:19:14,430
sa ei saavuta kunagi tugipunkti, mille puhul see on halb.

264
00:19:14,430 --> 00:19:17,950
See on lõpmatu rekursiooni ja korstnat ülevoolu.

265
00:19:17,950 --> 00:19:24,330
Aga siin me näeme, et uuendus toimub alates oleme ajakohastamine hakata + lõpp / 2,

266
00:19:24,330 --> 00:19:28,180
uuendame me lõpuks argumenti siin uuendame me alguses argument siin.

267
00:19:28,180 --> 00:19:32,860
Nii et kõik rekursiivne kõned me oleme parasjagu midagi. Okei.

268
00:19:32,860 --> 00:19:38,110
Kas soovite kõndida meid läbi sinu lahendus? >> Muidugi.

269
00:19:38,110 --> 00:19:44,270
Ma kasutan SearchHelp nii et iga kord kui ma seda funktsiooni kõne

270
00:19:44,270 --> 00:19:47,910
Mul on alguses, kus ma otsin on massiiv ja lõpuks

271
00:19:47,910 --> 00:19:49,380
kus ma otsin massiivi.

272
00:19:49,380 --> 00:19:55,330
>> Igal sammul, kus ta ütleb, et see on keset element, mis on algus + lõpp / 2,

273
00:19:55,330 --> 00:19:58,850
on võrdne sellega, mida me otsime?

274
00:19:58,850 --> 00:20:04,650
Ja kui on, siis me leidsime selle, ja ma arvan, et saab edasi kuni tase rekursioon.

275
00:20:04,650 --> 00:20:12,540
Ja kui see pole tõsi, siis me kontrollida, kas seda keset väärtuse massiivi on liiga suur,

276
00:20:12,540 --> 00:20:19,320
sel juhul me vaatame vasakul pool massiivi minnes algusest keskel indeks.

277
00:20:19,320 --> 00:20:22,710
Ja muidu me lõpuks poole võrra.

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

279
00:20:24,740 --> 00:20:27,730
See kõlab hästi.

280
00:20:27,730 --> 00:20:36,640
Okei, nii et paar asja, ja tegelikult on see väga kõrgel tasemel asi

281
00:20:36,640 --> 00:20:41,270
et sa ei pea kunagi teada selle käigus, kuid see on tõsi.

282
00:20:41,270 --> 00:20:46,080
Rekursiivne funktsioone, mida sa kuuled, et nad on halb asi

283
00:20:46,080 --> 00:20:51,160
sest kui sa rekursiivselt nimetad ennast liiga palju kordi, saad korstnat ülevoolu

284
00:20:51,160 --> 00:20:54,990
sest nagu ma enne ütlesin, iga funktsiooni saab oma freimi.

285
00:20:54,990 --> 00:20:59,500
Nii et iga kõne rekursiivne funktsioon sai oma freimi.

286
00:20:59,500 --> 00:21:04,140
Nii et kui teete 1000 rekursiivne kõned, saad 1000 korstnat raamid

287
00:21:04,140 --> 00:21:08,390
ja kiiresti sa kaasa liiga palju korstna raamid ja asjad lihtsalt murda.

288
00:21:08,390 --> 00:21:13,480
Nii et miks rekursiivne funktsioon on üldiselt halb.

289
00:21:13,480 --> 00:21:19,370
Aga seal on tore alagrupis rekursiivne funktsioone nimetatakse saba-rekursiivne funktsioone,

290
00:21:19,370 --> 00:21:26,120
ja see juhtub olema näide, kus kui kompilaator märkab seda

291
00:21:26,120 --> 00:21:29,920
ja see peaks, ma arvan - on rõkkama, kui te kaotate ta-O2 lipp

292
00:21:29,920 --> 00:21:33,250
siis märkad, et see on saba rekursiivne ja teha asju hea.

293
00:21:33,250 --> 00:21:40,050
>> See uuesti sama freimi ikka ja jälle iga rekursiivne kõne.

294
00:21:40,050 --> 00:21:47,010
Ja nii kuna sa kasutad sama freimi, sa ei pea muretsema

295
00:21:47,010 --> 00:21:51,690
kunagi korstnat täis, ja samal ajal, nagu sa ütlesid enne,

296
00:21:51,690 --> 00:21:56,380
kus kui sa tagasi true, siis peab tagastama kuni kõik need virna raamid

297
00:21:56,380 --> 00:22:01,740
ja 10. üleskutse SearchHelp on naasta 9., peab tagastama kuni 8..

298
00:22:01,740 --> 00:22:05,360
Nii et ei ole vaja juhtuda, kui funktsioonid on saba rekursiivne.

299
00:22:05,360 --> 00:22:13,740
Ja nii teebki seda funktsiooni saba rekursiivne on teada, et iga konkreetse kõne searchHelp

300
00:22:13,740 --> 00:22:18,470
rekursiivne kõne, et see teeb ja mida siis tagasi.

301
00:22:18,470 --> 00:22:25,290
Nii et esimene kõne SearchHelp, me kas kohe tagasi false,

302
00:22:25,290 --> 00:22:29,590
kohe tagasi true, või teeme rekursiivne kõne SearchHelp

303
00:22:29,590 --> 00:22:33,810
kus mida me tagasi just, et kõne on tagasi.

304
00:22:33,810 --> 00:22:51,560
Ja me ei saanud seda teha, kui me tegime midagi int x = SearchHelp, tagasi x * 2,

305
00:22:51,560 --> 00:22:55,440
lihtsalt mõne juhusliku muutuse.

306
00:22:55,440 --> 00:23:01,470
>> Nii et nüüd see rekursiivne kõne, see int x = SearchHelp rekursiivne kõne

307
00:23:01,470 --> 00:23:05,740
ei ole enam saba rekursiivne, sest tegelikult ei pea tagastama

308
00:23:05,740 --> 00:23:10,400
tagasi eelmise freimi nii, et eelmine kõne funktsioon

309
00:23:10,400 --> 00:23:13,040
saab siis teha midagi tagastatav väärtus.

310
00:23:13,040 --> 00:23:22,190
Nii et see ei ole saba rekursiivne, kuid mis meil oli enne on kenasti saba rekursiivne. Jah.

311
00:23:22,190 --> 00:23:27,000
[Üliõpilane] ei tohiks teise tugipunkti kontrollitakse 1.

312
00:23:27,000 --> 00:23:30,640
sest seal võib olla olukord, kus, kui te kaotate see argument

313
00:23:30,640 --> 00:23:35,770
olete start = lõpus, kuid nad on nõel väärtus.

314
00:23:35,770 --> 00:23:47,310
Küsimus ei ole meil tekib siis, kui lõpp on nõel väärtus

315
00:23:47,310 --> 00:23:52,000
või start = lõpus, asjakohaselt, start = lõpus

316
00:23:52,000 --> 00:23:59,480
ja sa ei ole tegelikult kontrollida, et erilist väärtust veel,

317
00:23:59,480 --> 00:24:03,910
siis alusta + lõpp / 2 on lihtsalt saab olema sama väärtusega.

318
00:24:03,910 --> 00:24:07,890
Aga me oleme juba tagasi vale ja me tegelikult ei kontrollinud väärtus.

319
00:24:07,890 --> 00:24:14,240
Nii et vähemalt esimeses kõne, kui suurus on 0, siis tahame tagasi false.

320
00:24:14,240 --> 00:24:17,710
Aga kui suurus on 1, siis alguses ei kavatse võrdne lõppu,

321
00:24:17,710 --> 00:24:19,820
ja me vähemalt kontrollida üks element.

322
00:24:19,820 --> 00:24:26,750
Aga ma arvan, teil on õigus, et saame lõpuks juhul, kui hakata + lõpp / 2,

323
00:24:26,750 --> 00:24:31,190
algus jõuab on sama algus + lõpp / 2,

324
00:24:31,190 --> 00:24:35,350
kuid me tegelikult kunagi kontrollinud, et element.

325
00:24:35,350 --> 00:24:44,740
>> Nii et kui me esimest korda vaadata on keset element väärtus me otsime,

326
00:24:44,740 --> 00:24:47,110
siis saame kohe tagasi true.

327
00:24:47,110 --> 00:24:50,740
Else kui nad võrdsed, siis pole mingit mõtet jätkata

328
00:24:50,740 --> 00:24:58,440
kuna me lihtsalt läheb uuendada juhul, kui me oleme ühe elemendi massiivist.

329
00:24:58,440 --> 00:25:01,110
Kui see ühe osa ei ole see, mida me otsime,

330
00:25:01,110 --> 00:25:03,530
siis on kõik vale. Jah.

331
00:25:03,530 --> 00:25:08,900
[Üliõpilane] Asi on selles, et kuna mõõtmed on tegelikult suurem kui elementide arv massiivis,

332
00:25:08,900 --> 00:25:13,070
on juba nihe - >> Nii on suurus -

333
00:25:13,070 --> 00:25:19,380
[Üliõpilane] Ütle kui massiivi oli suurus 0, siis SearchHelp tegelikult kontrollida heinakuhjas 0

334
00:25:19,380 --> 00:25:21,490
aasta esimese kõne.

335
00:25:21,490 --> 00:25:25,300
Massiiv on suurusega 0, seega 0 on - >> Jah.

336
00:25:25,300 --> 00:25:30,750
Seal on teine ​​asi - see võib olla hea. Mõtleme.

337
00:25:30,750 --> 00:25:40,120
Nii et kui massiivi oli 10 elementi ja keskmine me ei kavatse vaadata on punktid 5,

338
00:25:40,120 --> 00:25:45,700
nii me uurime 5, ja oletame, et väärtus on väiksem.

339
00:25:45,700 --> 00:25:50,720
Nii et me viskamine kõik ära 5 aastast.

340
00:25:50,720 --> 00:25:54,030
Nii algab + lõpp / 2 saab olema meie uus eesmärgil

341
00:25:54,030 --> 00:25:57,450
Nii et jah, see on alati jään kauem massiivi.

342
00:25:57,450 --> 00:26:03,570
Kui see on juhul, kui see oli paaris-või paaritu, siis me oleks vaadata, ütleme, 4,

343
00:26:03,570 --> 00:26:05,770
aga me peame veel minema visata -

344
00:26:05,770 --> 00:26:13,500
Nii et jah, lõpuks on alati saab olema lisaks tegelikule lõpuks massiiv.

345
00:26:13,500 --> 00:26:18,350
Nii elemente oleme keskendudes, lõpp on alati saab olema üks pärast seda.

346
00:26:18,350 --> 00:26:24,270
Ja nii kui alguses ei kunagi võrdne lõpuks oleme massiivi suurus 0.

347
00:26:24,270 --> 00:26:35,600
>> Teine asi, ma mõtlesin, et me oleme parasjagu algust tuleb hakata + lõpp / 2,

348
00:26:35,600 --> 00:26:44,020
nii see on nii, et mul on probleeme, kus hakata + lõpp / 2

349
00:26:44,020 --> 00:26:46,820
on element me uurime.

350
00:26:46,820 --> 00:26:58,150
Oletame, et meil oli see 10-element massiivi. Mida iganes.

351
00:26:58,150 --> 00:27:03,250
Nii algab + lõpp / 2 saab olema midagi nagu see üks,

352
00:27:03,250 --> 00:27:07,060
ja kui see ei ole väärtus, ütleme me tahame uuendada.

353
00:27:07,060 --> 00:27:10,060
Väärtus on suurem, nii et me tahame vaadata seda pool massiivi.

354
00:27:10,060 --> 00:27:15,910
Niisiis, kuidas me ajakohastamise algus uuendame me algusest nüüd selle elemendi.

355
00:27:15,910 --> 00:27:23,790
Aga see võib veel palju tööd, või vähemalt, mida saate teha algus + lõpp / 2 + 1.

356
00:27:23,790 --> 00:27:27,850
[Üliõpilane] Sa ei pea olema algus + lõpp [kuuldamatu] >> Jah.

357
00:27:27,850 --> 00:27:33,240
Oleme juba kontrollinud seda elementi ja tean, et see pole see, mida me otsime.

358
00:27:33,240 --> 00:27:36,800
Nii et me ei pea uuendama hakatakse selle elemendi.

359
00:27:36,800 --> 00:27:39,560
Saame vaid jätke see vahele ja ajakohastada hakkavad olema selle elemendi.

360
00:27:39,560 --> 00:27:46,060
Ja on seal kunagi juhul, oletame, et see oli lõpp,

361
00:27:46,060 --> 00:27:53,140
nii siis alustada oleks see, alusta + lõpp / 2 oleks see,

362
00:27:53,140 --> 00:28:00,580
algus + lõpp - Jah, ma arvan, et see võib sattuda lõpmatu rekursiooni.

363
00:28:00,580 --> 00:28:12,690
Oletame, et see on lihtsalt massiivi suurus 2 või massiivi suurus 1. Ma arvan, et see töötab.

364
00:28:12,690 --> 00:28:19,490
Nii et praegu, alguses on see, et element ja lõpuks on 1 väljaspool.

365
00:28:19,490 --> 00:28:24,110
Nii element, mis me kavatseme vaadata on see,

366
00:28:24,110 --> 00:28:29,400
ja siis kui me värskendame algus uuendame me hakatakse 0 + 1/2,

367
00:28:29,400 --> 00:28:33,160
mis läheb lõpuks meid tagasi alguses on see element.

368
00:28:33,160 --> 00:28:36,210
>> Nii et me kontrollida sama elemendi ikka ja jälle.

369
00:28:36,210 --> 00:28:43,310
Nii et see on nii, kui iga rekursiivne kõne peab tegelikult uuendada midagi.

370
00:28:43,310 --> 00:28:48,370
Nii et me peame tegema algus + lõpp / 2 + 1, muidu seal on juhtum

371
00:28:48,370 --> 00:28:50,710
kuhu me tegelikult ei ajakohastamise algus.

372
00:28:50,710 --> 00:28:53,820
Igaüks näed seda?

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

374
00:28:56,310 --> 00:29:03,860
Kas kellelgi on küsimusi selle lahendus või enam kommenteerida?

375
00:29:05,220 --> 00:29:10,280
Okei. Kas keegi on iteratiivne lahendus, et me kõik saame vaadata?

376
00:29:17,400 --> 00:29:20,940
Kas me kõik teeme seda rekursiivselt?

377
00:29:20,940 --> 00:29:25,950
Või ka ma arvan, kui sa avada päralt, siis võib-olla kaalu oma eelmist.

378
00:29:25,950 --> 00:29:28,810
See automaatselt salvestada? Ma ei ole kindel.

379
00:29:35,090 --> 00:29:39,130
Kas keegi on iteratiivne?

380
00:29:39,130 --> 00:29:42,430
Me võime minna läbi see, kui ei saa.

381
00:29:46,080 --> 00:29:48,100
Idee saab olema sama.

382
00:30:00,260 --> 00:30:02,830
Iteratiivsed lahendus.

383
00:30:02,830 --> 00:30:07,140
Me läheme taha põhimõtteliselt teha sama mõte

384
00:30:07,140 --> 00:30:16,530
kuhu me tahame jälgida uute lõpus massiivi ja uue algust massiivi

385
00:30:16,530 --> 00:30:18,510
ja seda ikka ja jälle.

386
00:30:18,510 --> 00:30:22,430
Ja kui see, mida me jälgida, kui algus ja lõpp kunagi ristuvad,

387
00:30:22,430 --> 00:30:29,020
siis me ei leidnud seda ja me saame tagasi false.

388
00:30:29,020 --> 00:30:37,540
Niisiis, kuidas ma seda teen? Igaüks on ettepanekuid või kood, et ma tõmba?

389
00:30:42,190 --> 00:30:47,450
[Üliõpilane] Kas samas silmus. >> Jah.

390
00:30:47,450 --> 00:30:49,450
Sa ei kavatse teha tahad silmus.

391
00:30:49,450 --> 00:30:51,830
>> Kas teil on kood Ma ei tõmba, või mida sa lähed soovitate?

392
00:30:51,830 --> 00:30:56,340
[Üliõpilane] Ma arvan küll. >> Olgu. See teeb asjad lihtsamaks. Mis su nimi oligi?

393
00:30:56,340 --> 00:30:57,890
[Üliõpilane] Lucas.

394
00:31:00,140 --> 00:31:04,190
1. läbivaatamine. Okei.

395
00:31:04,190 --> 00:31:13,200
Madal on see, mida me kutsusime alustada enne.

396
00:31:13,200 --> 00:31:17,080
Kuni ei ole päris see, mida me kutsusime end enne.

397
00:31:17,080 --> 00:31:22,750
Tegelikult lõpp on nüüd jooksul massiivi. See on element peaksime kaaluma.

398
00:31:22,750 --> 00:31:26,890
Nii madal on 0, kuni on suurus array - 1

399
00:31:26,890 --> 00:31:34,780
ja nüüd oleme silmuspõletamise, ja me kontroll -

400
00:31:34,780 --> 00:31:37,340
Ma arvan, et saab kõndida läbi.

401
00:31:37,340 --> 00:31:41,420
Milline oli teie mõtlemise kaudu? Kõnni meid läbi oma kood.

402
00:31:41,420 --> 00:31:49,940
[Üliõpilane] Muidugi. Vaata heinakuhjas väärtus keskel ja võrrelda seda nõela.

403
00:31:49,940 --> 00:31:58,520
Nii et kui see on suurem kui nõela, siis tahad, et - oh, tegelikult, et peaks olema tagurpidi.

404
00:31:58,520 --> 00:32:05,180
Sa lähed tahan visata paremal pool, ja nii jah, et tuleks tee.

405
00:32:05,180 --> 00:32:08,830
[Bowden] Nii et see peaks olema väiksem? Kas see, mida sa ütlesid? >> [Üliõpilane] Jah.

406
00:32:08,830 --> 00:32:10,390
[Bowden] Okei. Vähem.

407
00:32:10,390 --> 00:32:15,700
Nii et kui see, mida me vaatame on väiksem kui see, mida me tahame,

408
00:32:15,700 --> 00:32:19,410
siis jah, me tahame visata vasakule poole

409
00:32:19,410 --> 00:32:22,210
mis tähendab, et me oleme parasjagu kõike me arvestades

410
00:32:22,210 --> 00:32:26,610
liigutades madal paremal massiivi.

411
00:32:26,610 --> 00:32:30,130
See näeb hea välja.

412
00:32:30,130 --> 00:32:34,550
Ma arvan, et see on sama teema, et me ütles eelmine,

413
00:32:34,550 --> 00:32:49,760
kus, kui madal on 0 ja üles on 1, siis madala + üles / 2 kavatse luua üks ja sama asi jälle.

414
00:32:49,760 --> 00:32:53,860
>> Ja isegi kui see nii ei ole, see on veelgi tõhusam, vähemalt

415
00:32:53,860 --> 00:32:57,630
lihtsalt visata element me just vaatasin, mis me teame, on vale.

416
00:32:57,630 --> 00:33:03,240
Nii madal + üles / 2 + 1 - >> [üliõpilane] See peaks olema teistpidi.

417
00:33:03,240 --> 00:33:05,900
[Bowden] Või peaks see olema - 1 ja teine ​​peaks olema + 1.

418
00:33:05,900 --> 00:33:09,580
[Üliõpilane] Ja seal peaks olema topelt võrdusmärk. >> [Bowden] Jah.

419
00:33:09,580 --> 00:33:11,340
[Üliõpilane] Jah.

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

421
00:33:15,910 --> 00:33:21,280
Ja lõpuks, nüüd, et meil on see + 1 - 1 asi,

422
00:33:21,280 --> 00:33:31,520
on see - see ei pruugi olla - kas see on kunagi võimalik madal, et lõpuks suurem väärtus on?

423
00:33:35,710 --> 00:33:40,320
Ma arvan, et ainus viis, mis võib juhtuda - Kas on võimalik? >> [Üliõpilane] Ma ei tea.

424
00:33:40,320 --> 00:33:45,220
Aga kui ta saab kärbitud ja siis läheb miinus, et 1 ja siis - >> Jah.

425
00:33:45,220 --> 00:33:47,480
[Üliõpilane] Oleks võimalik saada messed up.

426
00:33:49,700 --> 00:33:53,940
Ma arvan, et see peaks olema hea ainult sellepärast

427
00:33:53,940 --> 00:33:58,800
see, et lõpuks madalam neil oleks võrdne, ma arvan.

428
00:33:58,800 --> 00:34:03,070
Aga kui nad on võrdsed, siis me poleks seda teinud samas silmus alustada

429
00:34:03,070 --> 00:34:06,670
ja me lihtsalt oleks tagastatud väärtus. Nii et ma arvan, et me oleme head nüüd.

430
00:34:06,670 --> 00:34:11,530
Pange tähele, et kuigi see probleem ei ole enam rekursiivne,

431
00:34:11,530 --> 00:34:17,400
sama laadi ideid kohaldata, kui näeme, kuidas seda nii lihtsalt sobiv

432
00:34:17,400 --> 00:34:23,659
et rekursiivne lahendus see, et me lihtsalt ajakohastamine indeksite ikka ja jälle,

433
00:34:23,659 --> 00:34:29,960
teeme probleemi väiksemaks ja väiksemaks, me keskendudes alagrupis massiivi.

434
00:34:29,960 --> 00:34:40,860
[Üliõpilane] Kui madal on 0 ja üles on 1, nad oleksid mõlemad 0 + 1/2, mis läheks 0,

435
00:34:40,860 --> 00:34:44,429
ja siis üks oleks + 1, üks oleks - 1.

436
00:34:47,000 --> 00:34:50,870
[Üliõpilane] Kuhu me kontrollida võrdõiguslikkuse?

437
00:34:50,870 --> 00:34:55,100
Nagu siis, kui keskmisel on tegelikult nõela?

438
00:34:55,100 --> 00:34:58,590
Me ei ole praegu seda teeb? Oh!

439
00:35:00,610 --> 00:35:02,460
Kui see on -

440
00:35:05,340 --> 00:35:13,740
Jah. Me ei saa lihtsalt teha katse siia alla, sest oletame, et esimene Lähis -

441
00:35:13,740 --> 00:35:16,430
[Üliõpilane] See on tegelikult nagu ei visata seotud.

442
00:35:16,430 --> 00:35:20,220
Nii et kui sa visata seotud, sa pead kontrollima seda esimesena või mis iganes.

443
00:35:20,220 --> 00:35:23,350
Ah. Jah. >> [Üliõpilane] Jah.

444
00:35:23,350 --> 00:35:29,650
Nii et nüüd oleme visata üks me praegu vaatasin,

445
00:35:29,650 --> 00:35:33,260
mis tähendab, me peame nüüd ka

446
00:35:33,260 --> 00:35:44,810
if (heinakuhjas [(madal + up) / 2] == nõel), siis saame tagasi true.

447
00:35:44,810 --> 00:35:52,070
Ja kas ma panen mujale või lihtsalt kui, siis tähendab see sõna-sõnalt sama asi

448
00:35:52,070 --> 00:35:57,110
kuna see oleks tagastatud tõsi.

449
00:35:57,110 --> 00:36:01,450
Ma panen muidu kui, kuid see ei ole oluline.

450
00:36:01,450 --> 00:36:10,440
>> Nii teine ​​kui see, siis see, ja see on ühine asi, mida ma teha

451
00:36:10,440 --> 00:36:14,340
kus isegi kui see on nii, kui kõik on hea siin,

452
00:36:14,340 --> 00:36:22,780
nagu madal saa kunagi olla suurem kui üleval, see ei ole väärt arutluskäik selle kohta, kas see on tõsi.

453
00:36:22,780 --> 00:36:28,010
Nii et võite ka öelda, et kui madal on väiksem või võrdne

454
00:36:28,010 --> 00:36:30,720
või kui madal on alla

455
00:36:30,720 --> 00:36:35,300
nii et kui nad on kunagi võrdne või madal juhtub mööda üles,

456
00:36:35,300 --> 00:36:40,130
siis saame murda läbi selle aasa.

457
00:36:41,410 --> 00:36:44,630
Küsimused, mured, kommentaare?

458
00:36:47,080 --> 00:36:49,270
Okei. See näeb hea välja.

459
00:36:49,270 --> 00:36:52,230
Nüüd me tahame teha omamoodi.

460
00:36:52,230 --> 00:37:04,030
Kui läheme minu teine ​​läbivaatamine, me näeme neid samu numbreid,

461
00:37:04,030 --> 00:37:07,550
aga nüüd nad enam ei järjestatud järjekorras.

462
00:37:07,550 --> 00:37:12,840
Ja me tahame ellu omamoodi kasutades algoritmi O n log n.

463
00:37:12,840 --> 00:37:17,240
Nii et mis algoritmi sa arvad, et peaksime rakendama siin? >> [Üliõpilane] Merge omamoodi.

464
00:37:17,240 --> 00:37:23,810
[Bowden] Jah. Merge sorteerida on O (n log n), nii see on, mida me teeme.

465
00:37:23,810 --> 00:37:26,680
Ja probleem saab olema üsna sarnane,

466
00:37:26,680 --> 00:37:31,920
kus see lihtsalt väärib rekursiivne lahendus.

467
00:37:31,920 --> 00:37:35,580
Me võime ka tulla iteratiivne lahendus, kui me tahame,

468
00:37:35,580 --> 00:37:42,540
kuid rekursioon on lihtsam siin ja me peaksime tegema rekursioon.

469
00:37:45,120 --> 00:37:49,530
Ma arvan, et me kõnnime läbi ühendamise omamoodi esimene,

470
00:37:49,530 --> 00:37:54,280
kuigi on armas video on märk omamoodi juba. [Naer]

471
00:37:54,280 --> 00:37:59,780
Nii et ühendada omamoodi on - ma raiskan nii palju seda paberit.

472
00:37:59,780 --> 00:38:02,080
Oh, seal on ainult üks vasakule.

473
00:38:02,080 --> 00:38:03,630
Nii ühendada.

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

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

476
00:38:29,910 --> 00:38:33,460
Merge võtab kaks eraldi massiivid.

477
00:38:33,460 --> 00:38:36,780
Eraldi nende kahe massiivid on nii järjestatud.

478
00:38:36,780 --> 00:38:40,970
Nii et see massiiv, 1, 3, 5, järjestatud. See massiiv, 0, 2, 4, järjestatud.

479
00:38:40,970 --> 00:38:46,710
Nüüd mida ühendamise peaks tegema, on ühendada need ühtsesse massiivi ise sorteerida.

480
00:38:46,710 --> 00:38:57,130
Nii et me tahame massiivi suurus 6, mis läheb on need elemendid sees on

481
00:38:57,130 --> 00:38:59,390
aastal sorteeritud järjekorras.

482
00:38:59,390 --> 00:39:03,390
>> Ja nii saame ära kasutada asjaolu, et need kaks massiivid on järjestatud

483
00:39:03,390 --> 00:39:06,800
teha seda lineaarset aega

484
00:39:06,800 --> 00:39:13,510
lineaarse aja tähenduses, kui see massiiv on suurus x ja see on suurus y,

485
00:39:13,510 --> 00:39:20,970
Seejärel kogu algoritm peaks olema O (x + y). Okei.

486
00:39:20,970 --> 00:39:23,150
Nii ettepanekuid.

487
00:39:23,150 --> 00:39:26,030
[Üliõpilane] Kas hakkame vasakult?

488
00:39:26,030 --> 00:39:30,150
Nii saad panna 0 alla ja siis 1 ja siis siin sa oled 2.

489
00:39:30,150 --> 00:39:33,320
Nii et see on selline nagu teil on kaart, mis liigub paremale. >> [Bowden] Jah.

490
00:39:33,320 --> 00:39:41,070
Sest mõlemad massiivid kui me keskenduda ainult kõige vasakpoolsem element.

491
00:39:41,070 --> 00:39:43,530
Kuna mõlemad massiivid on järjestatud, me teame, et need 2 elementi

492
00:39:43,530 --> 00:39:46,920
on väikseim elemendid kas massiiv.

493
00:39:46,920 --> 00:39:53,500
Nii et see tähendab, et 1 neist 2 elementi peab olema väikseim element meie ühinenud massiivi.

494
00:39:53,500 --> 00:39:58,190
See lihtsalt nii juhtub, et väikseim on üks paremal seekord.

495
00:39:58,190 --> 00:40:02,580
Nii et me võtame 0, sisesta see vasakul sest 0 on väiksem kui 1,

496
00:40:02,580 --> 00:40:08,210
nii et võta 0, sisestage see meie esimesel kohal ja siis me uuendada seda

497
00:40:08,210 --> 00:40:12,070
et nüüd keskenduda esimese osaga.

498
00:40:12,070 --> 00:40:14,570
Ja nüüd me kordame.

499
00:40:14,570 --> 00:40:20,670
Nii et nüüd me võrdleme 2 ja 1. 1 on väiksem, nii me lisada 1.

500
00:40:20,670 --> 00:40:25,300
Me värskenduse see pointer juhtida selle kutiga.

501
00:40:25,300 --> 00:40:33,160
Nüüd teeme uuesti, nii et 2. See uuendab, võrrelda neid 2, 3.

502
00:40:33,160 --> 00:40:37,770
See uudiseid, siis 4 ja 5.

503
00:40:37,770 --> 00:40:42,110
Nii et on ühendamisega.

504
00:40:42,110 --> 00:40:49,010
>> See peaks olema üsna selge, et see on lineaarne aega, sest me lihtsalt minna üle iga element ühe korra.

505
00:40:49,010 --> 00:40:55,980
Ja see on suurim samm rakendamisel ühendamise omamoodi teeb seda.

506
00:40:55,980 --> 00:40:59,330
Ja see ei ole nii raske.

507
00:40:59,330 --> 00:41:15,020
Paar asja muretsema, oletame, et me ühinevad 1, 2, 3, 4, 5, 6.

508
00:41:15,020 --> 00:41:30,930
Sel juhul me sattuda olukorda, kus see saab olema väiksem,

509
00:41:30,930 --> 00:41:36,160
siis me uuendada see pointer, see saab olema väiksem, ajakohastab seda,

510
00:41:36,160 --> 00:41:41,280
see on väiksem, ja nüüd sa pead tunnistama

511
00:41:41,280 --> 00:41:44,220
kui olete tegelikult otsa elemente võrrelda.

512
00:41:44,220 --> 00:41:49,400
Kuna me oleme juba kasutanud seda kogu antennide massiivi,

513
00:41:49,400 --> 00:41:55,190
kõik see massiiv on nüüd lihtsalt lisada siia.

514
00:41:55,190 --> 00:42:02,040
Nii et kui me kunagi joosta, kus üks meie massiivid on täielikult segunenud juba,

515
00:42:02,040 --> 00:42:06,510
siis me lihtsalt võtame kõik elemendid teiste massiivi ja lisada need lõpuks massiiv.

516
00:42:06,510 --> 00:42:13,630
Nii saame lihtsalt sisestada 4, 5, 6. Okei.

517
00:42:13,630 --> 00:42:18,070
See on üks asi, et olge.

518
00:42:22,080 --> 00:42:26,120
Rakendamine, mis peaks olema 1. etapp.

519
00:42:26,120 --> 00:42:32,600
Merge sortida siis põhineb sellel, et see on 2 sammu, 2 rumal samme.

520
00:42:38,800 --> 00:42:42,090
Ütleme lihtsalt annan selle massiivi.

521
00:42:57,920 --> 00:43:05,680
Nii et ühendada sorteerida, 1.etapp on rekursiivselt murda massiivi pooleks.

522
00:43:05,680 --> 00:43:09,350
Nii et jagada seda massiivi pooleks.

523
00:43:09,350 --> 00:43:22,920
Meil on nüüd 4, 15, 16, 50 ja 8, 23, 42, 108.

524
00:43:22,920 --> 00:43:25,800
Ja nüüd teeme uuesti ja me jagada need pooleks.

525
00:43:25,800 --> 00:43:27,530
Ma lihtsalt teen seda siinpool.

526
00:43:27,530 --> 00:43:34,790
Nii et 4, 15 ja 16, 50.

527
00:43:34,790 --> 00:43:37,440
Me teeks sama asi siin.

528
00:43:37,440 --> 00:43:40,340
Ja nüüd me jagame pooleks uuesti.

529
00:43:40,340 --> 00:43:51,080
Ja meil on 4, 15, 16, 50.

530
00:43:51,080 --> 00:43:53,170
Nii et see on meie tugipunkt.

531
00:43:53,170 --> 00:44:00,540
Kui massiivid on suurus 1, siis me lõpetame koos jagamine pooleks.

532
00:44:00,540 --> 00:44:03,190
>> Nüüd, mida me teeme seda?

533
00:44:03,190 --> 00:44:15,730
Me lõpuks see ka lagunenud 8, 23, 42 ja 108.

534
00:44:15,730 --> 00:44:24,000
Nüüd, et me oleme selles punktis, nüüd samm kaks Tarkvaraprojekteerimise on lihtsalt ühinevad paari nimekirju.

535
00:44:24,000 --> 00:44:27,610
Nii et me tahame ühendada need. Me lihtsalt helistada ühendada.

536
00:44:27,610 --> 00:44:31,410
Me teame ühendamise naaseb need sorteeritakse järjekorras.

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

538
00:44:33,920 --> 00:44:41,440
Nüüd tahame koondada need, ja et tagasi nimekirja omadega sorteeritud järjekorras

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

540
00:44:44,160 --> 00:44:57,380
Me ühendada need - ma ei saa kirjutada - 8, 23 ja 42, 108.

541
00:44:57,380 --> 00:45:02,890
Nii et meil on tekkinud paari korraga.

542
00:45:02,890 --> 00:45:05,140
Nüüd me lihtsalt ühendada uuesti.

543
00:45:05,140 --> 00:45:10,130
Pange tähele, et kõik need nimekirjad on sorteeritud iseenesest

544
00:45:10,130 --> 00:45:15,220
ja siis saame lihtsalt ühendada need nimekirjad saada nimekirja suurus 4, mis on järjestatud

545
00:45:15,220 --> 00:45:19,990
ja ühendada need kaks nimekirja, et saada nimekirja suurus 4, mis on järjestatud.

546
00:45:19,990 --> 00:45:25,710
Ja lõpuks, me võime ühendada need kaks nimekirja suurus 4, et saada üks nimekiri suurus 8, mis on järjestatud.

547
00:45:25,710 --> 00:45:34,030
Nii et näete, et see on üldine n log n, me juba nägime, et ühendamine on lineaarne,

548
00:45:34,030 --> 00:45:40,390
nii et kui me tegeleme nende ühendamine, nii nagu üldkuludest ühendamise

549
00:45:40,390 --> 00:45:43,410
Nende kahe nimekirja on vaid 2, sest -

550
00:45:43,410 --> 00:45:49,610
Või noh, see on O n, kuid n siin on lihtsalt need 2 elementi, nii et see on 2.

551
00:45:49,610 --> 00:45:52,850
Ja need 2 on 2 ja need 2 on 2 ja need 2 on 2,

552
00:45:52,850 --> 00:45:58,820
nii üle kõik sulab, et me peame tegema, me lõpuks teeme n.

553
00:45:58,820 --> 00:46:03,210
Nagu 2 + 2 + 2 + 2 on 8, mis on n

554
00:46:03,210 --> 00:46:08,060
nii et kulud ühinevad selle komplekti on n.

555
00:46:08,060 --> 00:46:10,810
Ja siis sama asi siin.

556
00:46:10,810 --> 00:46:16,980
Me ühendada need 2, siis need 2, ja eraldi kõnealust ühendamist võtab neli operatsiooni,

557
00:46:16,980 --> 00:46:23,610
kõnealust ühendamist võtab neli operatsiooni, kuid taas, vahel kõik need,

558
00:46:23,610 --> 00:46:29,030
me lõpuks ühinevad n kokku asju, ja nii see toiming n.

559
00:46:29,030 --> 00:46:33,670
Ja nii igal tasandil võtab n elementi liitmisega.

560
00:46:33,670 --> 00:46:36,110
>> Ja kui palju tasanditel on olemas?

561
00:46:36,110 --> 00:46:40,160
Igal tasandil meie massiivi kasvab suurus 2.

562
00:46:40,160 --> 00:46:44,590
Siin meie massiivid on suurus 1, siin nad on suurus 2, siin nad on suurus 4,

563
00:46:44,590 --> 00:46:46,470
ja lõpuks, nad on suurus 8.

564
00:46:46,470 --> 00:46:56,450
Nii et kuna ta on kahekordne, seal saab olema kokku log n nendest tasanditest.

565
00:46:56,450 --> 00:47:02,090
Nii log n taset, iga tase, võttes n kogu tegevus,

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

567
00:47:05,720 --> 00:47:07,790
Küsimused?

568
00:47:08,940 --> 00:47:13,320
Kas inimesed on juba saavutanud edu kohta, kuidas rakendada seda?

569
00:47:13,320 --> 00:47:18,260
Kas keegi juba riigis, kus ma saan lihtsalt tõmba oma koodi?

570
00:47:20,320 --> 00:47:22,260
Võin anda minut.

571
00:47:24,770 --> 00:47:27,470
See üks läheb kauem.

572
00:47:27,470 --> 00:47:28,730
Ma väga soovitada kordu -

573
00:47:28,730 --> 00:47:30,510
Sa ei pea tegema rekursiooni jaoks ühendamise

574
00:47:30,510 --> 00:47:33,750
sest teha rekursiooni jaoks ühinevad, sa lähed on läbida hunnik erinevaid suurusi.

575
00:47:33,750 --> 00:47:37,150
Sa saad, aga see on tüütu.

576
00:47:37,150 --> 00:47:43,720
Aga rekursiooni jaoks omamoodi ise on üsna lihtne.

577
00:47:43,720 --> 00:47:49,190
Sa lihtsalt sõna otseses mõttes helistada omamoodi vasakul pool, sorteerida paremal pool. Okei.

578
00:47:51,770 --> 00:47:54,860
Igaüks on midagi ma ei tõmba veel?

579
00:47:54,860 --> 00:47:57,540
Või muidu ma annan minut.

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

581
00:47:59,900 --> 00:48:02,970
Igaüks on midagi, mida me saame töötada koos?

582
00:48:05,450 --> 00:48:09,680
Või muidu me lihtsalt töötada selle ja seejärel laiendage sealt.

583
00:48:09,680 --> 00:48:14,050
>> Igaüks on rohkem kui see, et ma ei tõmba?

584
00:48:14,050 --> 00:48:17,770
[Üliõpilane] Jah. Võite tõmba minu. >> Olgu.

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

586
00:48:22,170 --> 00:48:25,280
[Üliõpilane] Oli palju tingimusi. >> Oh, tulistada. Kas sa -

587
00:48:25,280 --> 00:48:28,110
[Üliõpilane] Ma pean salvestage see. >> Jah.

588
00:48:32,420 --> 00:48:35,730
Nii et me tegime seda ühendamise eraldi.

589
00:48:35,730 --> 00:48:38,570
Oh, aga see ei ole nii halb.

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

591
00:48:41,650 --> 00:48:47,080
Nii et omamoodi on ise lihtsalt helistades mergeSortHelp.

592
00:48:47,080 --> 00:48:49,530
Selgitage meile, mida mergeSortHelp teeb.

593
00:48:49,530 --> 00:48:55,700
[Üliõpilane] MergeSortHelp päris palju maksab kaks peamist etappi,

594
00:48:55,700 --> 00:49:01,270
mis on sorteerida iga poole massiiv ja seejärel ühendada mõlemad.

595
00:49:04,960 --> 00:49:08,050
[Bowden] Okei, nii et andke mulle teine.

596
00:49:10,850 --> 00:49:13,210
Ma arvan, et see - >> [üliõpilane] mul on vaja -

597
00:49:17,100 --> 00:49:19,400
Jah. Ma olen midagi puudu.

598
00:49:19,400 --> 00:49:23,100
Aastal ühinevad, ma mõistan, et mul on vaja luua uus massiiv

599
00:49:23,100 --> 00:49:26,530
sest ma ei suutnud seda teha paigas. >> Jah. Sa ei saa. Õige.

600
00:49:26,530 --> 00:49:28,170
[Üliõpilane] Nii saan luua uue massiivi.

601
00:49:28,170 --> 00:49:31,510
Ma unustasin lõpus ühendada uuesti muuta.

602
00:49:31,510 --> 00:49:34,490
Okei. Me vajame uut massiivi.

603
00:49:34,490 --> 00:49:41,000
Aastal ühendamise omamoodi, see on peaaegu alati tõsi.

604
00:49:41,000 --> 00:49:44,340
Osa kuludest parem algoritm ajaliselt

605
00:49:44,340 --> 00:49:47,310
on peaaegu alati vaja kasutada natuke rohkem mälu.

606
00:49:47,310 --> 00:49:51,570
Nii et siin, ükskõik kuidas sa seda ühendada sorteerida,

607
00:49:51,570 --> 00:49:54,780
sa paratamatult vaja kasutada mõned ekstra mälu.

608
00:49:54,780 --> 00:49:58,240
Ta lõi uue massiivi.

609
00:49:58,240 --> 00:50:03,400
Ja siis lõpus öelda, me lihtsalt vaja kopeerida uue massiivi algsesse massiivi.

610
00:50:03,400 --> 00:50:04,830
[Üliõpilane] Ma arvan küll, jah.

611
00:50:04,830 --> 00:50:08,210
Ma ei tea, kas see töötab nii lugedes viitega või mis iganes -

612
00:50:08,210 --> 00:50:11,650
Jah, see töötab. >> [Üliõpilane] Okei.

613
00:50:20,620 --> 00:50:24,480
Kas sa proovisid töötab see? >> [Üliõpilane] Ei, veel mitte. >> Okei.

614
00:50:24,480 --> 00:50:28,880
Proovige käivitada see ja siis räägin seda teist.

615
00:50:28,880 --> 00:50:35,200
[Üliõpilane] mul on vaja, et kõik funktsiooni prototüüpe ja kõik, eks?

616
00:50:37,640 --> 00:50:40,840
Funktsiooni prototüüpe. Oh, sa mõtled nagu - Jah.

617
00:50:40,840 --> 00:50:43,040
Sorteeri helistatakse mergeSortHelp.

618
00:50:43,040 --> 00:50:47,390
>> Nii et omamoodi helistada mergeSortHelp, mergeSortHelp peavad kas on määratletud

619
00:50:47,390 --> 00:50:56,370
enne sorteeri või me lihtsalt vaja prototüüp. Lihtsalt kopeeri ja kleebi see.

620
00:50:56,370 --> 00:50:59,490
Ja samamoodi, mergeSortHelp helistatakse ühinevad,

621
00:50:59,490 --> 00:51:03,830
kuid ühendamise ei ole veel kindlaks määratud, et saaksime lihtsalt lasta mergeSortHelp tea

622
00:51:03,830 --> 00:51:08,700
et see, mida ühendada saab välja nägema, ja nii ongi.

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

624
00:51:22,770 --> 00:51:32,660
Meil on küsimus siin, kus meil ei ole tugipunkti.

625
00:51:32,660 --> 00:51:38,110
MergeSortHelp on rekursiivne, nii et kõik rekursiivne funktsioon

626
00:51:38,110 --> 00:51:42,610
läheb vaja mingi tugipunkti teada, millal lõpetada rekursiivselt kutsutakse ise.

627
00:51:42,610 --> 00:51:45,590
Mis on meie tugipunkt saab olema siin? Jah.

628
00:51:45,590 --> 00:51:49,110
[Üliõpilane] Kui suurus on 1? >> [Bowden] Jah.

629
00:51:49,110 --> 00:51:56,220
Nii nagu me nägime seal, me lõpetasime jagamine massiivid

630
00:51:56,220 --> 00:52:01,850
kui me sattus massiive suurus 1, mis paratamatult on järjestatud ise.

631
00:52:01,850 --> 00:52:09,530
Nii et kui suurus võrdub 1, me teame massiiv on juba sorteeritud,

632
00:52:09,530 --> 00:52:12,970
nii et me saame lihtsalt tagasi.

633
00:52:12,970 --> 00:52:16,880
>> Pange tähele, et on tühine, nii et me ei tule midagi erilist, me lihtsalt tagasi.

634
00:52:16,880 --> 00:52:19,580
Okei. Nii et meie tugipunkt.

635
00:52:19,580 --> 00:52:27,440
Ma arvan, et meie baasi Võib ka juhtuda, kui me juhtumisi ühinevad massiivi suurus 0,

636
00:52:27,440 --> 00:52:30,030
me ilmselt tahad lõpetada mingil hetkel,

637
00:52:30,030 --> 00:52:33,610
nii et me võiks lihtsalt öelda suurus väiksem kui 2 või väiksem või võrdne 1

638
00:52:33,610 --> 00:52:37,150
nii et see töötab iga massiivi nüüd.

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

640
00:52:38,870 --> 00:52:42,740
Nii et meie tugipunkt.

641
00:52:42,740 --> 00:52:45,950
Nüüd sa tahad kõndida meid ühendada?

642
00:52:45,950 --> 00:52:49,140
Mida kõik need juhtumid tähendab?

643
00:52:49,140 --> 00:52:54,480
Siin üleval, me teeme lihtsalt sama mõte, -

644
00:52:56,970 --> 00:53:02,470
[Üliõpilane] Ma pean mööda sõitma suurus kõik mergeSortHelp kõned.

645
00:53:02,470 --> 00:53:10,080
Lisasin suurus täiendava esmane ja see ei ole seal, nagu suurus / 2.

646
00:53:10,080 --> 00:53:16,210
[Bowden] Oh, suurus / 2, suurus / 2. >> [Üliõpilane] Jah, ja ka eespool funktsioon samuti.

647
00:53:16,210 --> 00:53:21,320
[Bowden] Siin? >> [Üliõpilane] Lihtsalt suurus. >> [Bowden] Oh. Suurus, suurus? >> [Üliõpilane] Jah.

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

649
00:53:23,010 --> 00:53:26,580
Las ma mõtlen teist.

650
00:53:26,580 --> 00:53:28,780
Kas me joosta küsimus?

651
00:53:28,780 --> 00:53:33,690
Me oleme alati ravivad vasakule kui 0. >> [Üliõpilane] nr

652
00:53:33,690 --> 00:53:36,340
See on vale ka. Vabandust. See peaks olema algus. Jah.

653
00:53:36,340 --> 00:53:39,230
[Bowden] Okei. Mulle meeldib, et parem.

654
00:53:39,230 --> 00:53:43,880
Ja lõpuks. Okei.

655
00:53:43,880 --> 00:53:47,200
Nii et nüüd sa tahad kõndida meid ühendada? >> [Üliõpilane] Okei.

656
00:53:47,200 --> 00:53:52,150
Ma lihtsalt jalgsi läbi uue massiivi Olen loonud.

657
00:53:52,150 --> 00:53:57,420
Selle suurus on suurus osa massiiv, et me tahame välja sorteerida

658
00:53:57,420 --> 00:54:03,460
ja püüab leida element, mis ma peaks tegema uue massiivi samm.

659
00:54:03,460 --> 00:54:10,140
Nii et mida teha, et esiteks Ma kontrollin, kas vasakul pool massiiv on jätkuvalt enam elemente,

660
00:54:10,140 --> 00:54:14,260
ja kui seda ei juhtu, siis minna, et teine ​​tingimus, mis lihtsalt ütleb

661
00:54:14,260 --> 00:54:20,180
okei, see peab olema õiges massiiv, ja me paneme, et praeguses indeks newArray.

662
00:54:20,180 --> 00:54:27,620
>> Ja siis muidu, ma kontrollin, kas paremal pool massiiv on samuti lõpetatud,

663
00:54:27,620 --> 00:54:30,630
sel juhul ma lihtsalt panna vasakule.

664
00:54:30,630 --> 00:54:34,180
See ei pruugi tegelikult olla vajalik. Ma pole kindel.

665
00:54:34,180 --> 00:54:40,970
Aga ikkagi, aga teised kaks kontroll kumb on väiksema vasakule või paremale.

666
00:54:40,970 --> 00:54:49,770
Ja ka iga kord, ma incrementing kumb kohatäide ma juurdekasvu.

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

668
00:54:52,040 --> 00:54:53,840
See näeb hea välja.

669
00:54:53,840 --> 00:54:58,800
Kas kellelgi on kommentaare või muresid või küsimusi?

670
00:55:00,660 --> 00:55:07,720
Nii et neli juhtumit, et me peame tooma asjad lihtsalt on - või tundub 5 -

671
00:55:07,720 --> 00:55:13,100
kuid me peame kaaluma, kas vasakul massiiv on otsa asjad peame ühinema,

672
00:55:13,100 --> 00:55:16,390
kas õigus massiiv on otsa asjad peame ühendada -

673
00:55:16,390 --> 00:55:18,400
Ma osutavad midagi.

674
00:55:18,400 --> 00:55:21,730
Nii et kas vasakul massiiv on otsa asjad või paremale massiiv on otsa asjad.

675
00:55:21,730 --> 00:55:24,320
Need on kaks juhtumit.

676
00:55:24,320 --> 00:55:30,920
Samuti peame triviaalne puhul kas vasakule asi on väiksem kui õige asi.

677
00:55:30,920 --> 00:55:33,910
Siis tahame valida vasakul asi.

678
00:55:33,910 --> 00:55:37,630
Need on juhtumid.

679
00:55:37,630 --> 00:55:40,990
Nii et see oli õige, et see on.

680
00:55:40,990 --> 00:55:46,760
Array jäänud. See on 1, 2, 3. Okei. Nii et jah, need on neli asju, mida me võiksite teha.

681
00:55:50,350 --> 00:55:54,510
Ja me ei lähe üle iteratiivne lahendus.

682
00:55:54,510 --> 00:55:55,980
Ma ei soovitaks -

683
00:55:55,980 --> 00:56:03,070
Merge omamoodi on näide funktsioon, mis on nii mitte saba rekursiivne,

684
00:56:03,070 --> 00:56:07,040
see ei ole kerge teha seda saba rekursiivne,

685
00:56:07,040 --> 00:56:13,450
kuid ka see ei ole väga lihtne teha seda iteratiivne.

686
00:56:13,450 --> 00:56:16,910
See on väga lihtne.

687
00:56:16,910 --> 00:56:19,170
See rakendamist ühendamise sortida,

688
00:56:19,170 --> 00:56:22,140
ühendada, ükskõik mida sa teed, sa lähed ehitada ühendamisega.

689
00:56:22,140 --> 00:56:29,170
>> Nii et ühendada omamoodi ehitatud peal ühendamise rekursiivselt on vaid need kolm rida.

690
00:56:29,170 --> 00:56:34,700
Iteratiivselt, see on rohkem tüütu ja raske mõelda.

691
00:56:34,700 --> 00:56:41,860
Aga teate, et see ei ole saba rekursiivne alates mergeSortHelp - kui ta nimetab ennast -

692
00:56:41,860 --> 00:56:46,590
see vajab veel teha asju pärast seda rekursiivne kõne tulu.

693
00:56:46,590 --> 00:56:50,830
Nii et see freimi peab püsima isegi pärast nõuab see.

694
00:56:50,830 --> 00:56:54,170
Ja siis kui te nimetate seda, freimi peab püsima

695
00:56:54,170 --> 00:56:57,780
sest isegi pärast seda kõnet, peame siiski ühendada.

696
00:56:57,780 --> 00:57:01,920
Ja see on mittetriviaalsed teha seda saba rekursiivne.

697
00:57:04,070 --> 00:57:06,270
Küsimused?

698
00:57:08,300 --> 00:57:09,860
Hea küll.

699
00:57:09,860 --> 00:57:13,400
Nii läheb tagasi sortida - oh, seal on kaks asja, ma tahan näidata. Okei.

700
00:57:13,400 --> 00:57:17,840
Tulles tagasi sorteerida, me teeme seda kiiresti.

701
00:57:17,840 --> 00:57:21,030
Või leidke. Sorteeri? Sordi. Jah.

702
00:57:21,030 --> 00:57:22,730
Tulles tagasi alguse omamoodi.

703
00:57:22,730 --> 00:57:29,870
Me tahame luua algoritm, mis sorteerib massiivi kasutades algoritmi

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

705
00:57:33,660 --> 00:57:40,860
Niisiis, kuidas on see võimalik? Kas kellelgi on mingit -

706
00:57:40,860 --> 00:57:44,300
Ma vihjanud enne kell -

707
00:57:44,300 --> 00:57:48,300
Kui me parasjagu paranema n log n-O n,

708
00:57:48,300 --> 00:57:51,450
oleme parem meie algoritm aeg-tark,

709
00:57:51,450 --> 00:57:55,250
mis tähendab, mida me kavatseme vaja teha, et korvata seda?

710
00:57:55,250 --> 00:57:59,520
[Üliõpilane] Space. >> Jah. Me ei kavatse kasutama rohkem ruumi.

711
00:57:59,520 --> 00:58:04,490
Ja isegi mitte lihtsalt rohkem ruumi, see on hüppeliselt rohkem ruumi.

712
00:58:04,490 --> 00:58:14,320
Nii et ma arvan seda tüüpi algoritm on pseudo midagi, pseudo polünoom -

713
00:58:14,320 --> 00:58:18,980
pseudo - ma ei mäleta. Pseudo midagi.

714
00:58:18,980 --> 00:58:22,210
Aga sellepärast, et me peame kasutama nii palju ruumi

715
00:58:22,210 --> 00:58:28,610
et see on saavutatav, kuid mitte realistlik.

716
00:58:28,610 --> 00:58:31,220
>> Ja kuidas me seda saavutada?

717
00:58:31,220 --> 00:58:36,810
Me suudame seda saavutada, kui me garanteerida ühegi element massiivi

718
00:58:36,810 --> 00:58:39,600
on alla teatud suurust.

719
00:58:42,070 --> 00:58:44,500
Nii et ütleme lihtsalt, et suurus on 200,

720
00:58:44,500 --> 00:58:48,130
tahes osa massiiv on allpool suurus 200.

721
00:58:48,130 --> 00:58:51,080
Ja see on tegelikult väga realistlik.

722
00:58:51,080 --> 00:58:58,660
Te saate väga lihtsalt on massiiv, et sa tead kõike seda

723
00:58:58,660 --> 00:59:00,570
saab olema väiksem kui mõned number.

724
00:59:00,570 --> 00:59:07,400
Nagu kui teil on mõned täiesti massiivne vektor või midagi

725
00:59:07,400 --> 00:59:11,810
kuid sa tead kõike saab olema vahemikus 0 kuni 5,

726
00:59:11,810 --> 00:59:14,790
siis see saab olema tunduvalt kiiremini seda teha.

727
00:59:14,790 --> 00:59:17,930
Ja seotud mis tahes elemente on 5,

728
00:59:17,930 --> 00:59:21,980
nii see seotud, et kui palju mälu sa kavatsed kasutada.

729
00:59:21,980 --> 00:59:26,300
Nii köidetud on 200.

730
00:59:26,300 --> 00:59:32,960
Teoreetiliselt on alati seotud kuna täisarv võib olla ainult kuni 4 miljardit,

731
00:59:32,960 --> 00:59:40,600
aga see on ebareaalne, sest siis me tahaks olla kasutades ruumi

732
00:59:40,600 --> 00:59:44,400
tellimisel 4 miljardit eurot. Nii et on ebareaalne.

733
00:59:44,400 --> 00:59:47,060
Aga siin me ütleme meie köidetud on 200.

734
00:59:47,060 --> 00:59:59,570
Trikk teeb seda O n teeme teise massiivi nimega loeb suurus seotud.

735
00:59:59,570 --> 01:00:10,470
Nii et tegelikult on see otsetee - ma tegelikult ei tea, kas rõkkama teeb seda.

736
01:00:11,150 --> 01:00:15,330
Aga GCC vähemalt - Ma eeldades rõkkama see liiga -

737
01:00:15,330 --> 01:00:18,180
see lihtsalt initsialiseerida kogu massiiv olla 0..

738
01:00:18,180 --> 01:00:25,320
Nii et kui ma ei taha seda teha, siis ma võiks eraldi teha jaoks (int i = 0;

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

740
01:00:31,500 --> 01:00:35,260
Nii et nüüd on kõik käivitub kuni 0.

741
01:00:35,260 --> 01:00:39,570
Ma itereerime minu massiiv,

742
01:00:39,570 --> 01:00:51,920
ja mida ma teen on ma loendades iga - lähme alla siit.

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

744
01:00:55,480 --> 01:01:00,010
Mida ma loendan on sündmuste arv kõikidel osadel.

745
01:01:00,010 --> 01:01:03,470
Olgem tegelikult lisada veel paar siin mõned kordub.

746
01:01:03,470 --> 01:01:11,070
Nii et raha on meil siin, väärtus, mis saab olema massiiv [i].

747
01:01:11,070 --> 01:01:14,850
Nii Val võiks olla 4 või 8 või mis iganes.

748
01:01:14,850 --> 01:01:18,870
Ja nüüd ma loen, kui palju selle väärtus Olen näinud,

749
01:01:18,870 --> 01:01:21,230
nii loeb [Val] + +;

750
01:01:21,230 --> 01:01:29,430
Kui see on tehtud, loeb läheb otsima midagi 0001.

751
01:01:29,430 --> 01:01:42,190
Teeme loeb [Val] - JÄRGIMA + 1.

752
01:01:42,190 --> 01:01:48,230
>> Nüüd ongi lihtsalt arvestada asjaolu, et me alates 0.

753
01:01:48,230 --> 01:01:50,850
Nii et kui 200 saab olema meie suurim arv,

754
01:01:50,850 --> 01:01:54,720
siis 0-200 on 201 asja.

755
01:01:54,720 --> 01:02:01,540
Nii loeb, see näeb välja nagu 00001, sest meil on üks 4.

756
01:02:01,540 --> 01:02:10,210
Siis me peame 0001, kus me peame 1 8. indeks loota.

757
01:02:10,210 --> 01:02:14,560
Me peame 2 23. indeksi arvu.

758
01:02:14,560 --> 01:02:17,630
Me peame 2 42. indeksi arvu.

759
01:02:17,630 --> 01:02:21,670
Nii saame kasutada loota.

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

761
01:02:44,920 --> 01:02:52,540
Ja nii kui num_of_item on 2, mis tähendab, et me tahame lisada 2 numbrit i

762
01:02:52,540 --> 01:02:55,290
meie järjestatud massiivist.

763
01:02:55,290 --> 01:03:02,000
Seega on meil vaja jälgida, kui kaugele oleme arvesse massiivi.

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

765
01:03:05,470 --> 01:03:09,910
Array - ma lihtsalt kirjutan selle.

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

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

768
01:03:28,580 --> 01:03:32,490
Kas see, mida ma tahan? Ma arvan, et see, mida ma tahan.

769
01:03:35,100 --> 01:03:38,290
Jah, see näeb hea välja. Okei.

770
01:03:38,290 --> 01:03:43,050
Nii ei igaüks aru, mida eesmärgil minu loeb massiiv on?

771
01:03:43,050 --> 01:03:48,140
On loendades esinemistest kõik need numbrid.

772
01:03:48,140 --> 01:03:51,780
Siis ma itereerimise üle, mis loeb massiivi

773
01:03:51,780 --> 01:03:57,190
ja-nda positsiooni loeb massiivi

774
01:03:57,190 --> 01:04:01,930
on mitmeid i on, et peaks ilmuma minu sorteeritud massiiv.

775
01:04:01,930 --> 01:04:06,840
Sellepärast loeb 4 saab olema 1

776
01:04:06,840 --> 01:04:11,840
ja loeb 8 saab olema 1, loeb 23. saab olema 2.

777
01:04:11,840 --> 01:04:16,900
Nii see on, kuidas paljud neist Tahan lisada oma sorteeritud massiiv.

778
01:04:16,900 --> 01:04:19,200
Siis ma lihtsalt teha.

779
01:04:19,200 --> 01:04:28,960
Olen sisestamist num_of_item i on minu sorteeritud massiiv.

780
01:04:28,960 --> 01:04:31,670
>> Küsimused?

781
01:04:32,460 --> 01:04:43,100
Ja nii jälle, see on lineaarne aega, sest me lihtsalt itereerimise üle seekord,

782
01:04:43,100 --> 01:04:47,470
aga see on ka lineaarne mida see number juhtub olema,

783
01:04:47,470 --> 01:04:50,730
ja nii see suuresti sõltub sellest, mida teie seotud on.

784
01:04:50,730 --> 01:04:53,290
Mis köidetud 200, see pole nii hull.

785
01:04:53,290 --> 01:04:58,330
Kui oma köidetud saab olema 10000, siis see on natuke hullem,

786
01:04:58,330 --> 01:05:01,360
aga kui oma köidetud saab olema 4 miljardit, mis on täiesti ebareaalne

787
01:05:01,360 --> 01:05:07,720
ja see massiiv läheb pea olema suurus 4 miljardit eurot, mis on ebareaalne.

788
01:05:07,720 --> 01:05:10,860
Nii et see on. Küsimused?

789
01:05:10,860 --> 01:05:13,270
[Kuuldamatu õpilase vastus] >> Okei.

790
01:05:13,270 --> 01:05:15,710
Ma sain aru, üks teine ​​asi, kui me läksime mööda.

791
01:05:17,980 --> 01:05:23,720
Ma arvan, et probleem oli Lucase ja ilmselt iga üks oleme näinud.

792
01:05:23,720 --> 01:05:26,330
Ma täitsa unustasin.

793
01:05:26,330 --> 01:05:31,040
Ainuke asi, ma tahtsin kommenteerida, et kui olete tegelevad asju nagu indeksite,

794
01:05:31,040 --> 01:05:38,320
sa kunagi näha seda, kui olete kirjalikult jaoks silmus,

795
01:05:38,320 --> 01:05:41,120
kuid tehniliselt, kui olete tegelevad need indeksid,

796
01:05:41,120 --> 01:05:45,950
siis peaks päris palju alati käsitleda allkirjastamata täisarvud.

797
01:05:45,950 --> 01:05:53,850
Selle põhjuseks on see, kui olete tegelevad allkirjastatud täisarvud,

798
01:05:53,850 --> 01:05:56,090
nii et kui sul on 2 logis täisarvud ja sa lisage need koos

799
01:05:56,090 --> 01:06:00,640
ja nad lõpuks liiga suur, siis sa lõpuks koos negatiivse numbriga.

800
01:06:00,640 --> 01:06:03,410
Nii see on, mida Integer overflow on.

801
01:06:03,410 --> 01:06:10,500
>> Kui ma lisan 2 miljardit ja 1 miljard ma lõpuks negatiivne 1 miljard eurot.

802
01:06:10,500 --> 01:06:15,480
Nii täisarvud tööd arvutitega.

803
01:06:15,480 --> 01:06:17,510
Nii et probleem kasutades -

804
01:06:17,510 --> 01:06:23,500
See on hea, välja arvatud juhul, kui madal juhtub olema 2 miljardit ja kuni juhtub olema 1 miljard

805
01:06:23,500 --> 01:06:27,120
siis see saab olema negatiivne 1000000000 ja siis me hakkame jagama, et 2

806
01:06:27,120 --> 01:06:29,730
ja lõpuks negatiivne 500 miljonit eurot.

807
01:06:29,730 --> 01:06:33,760
Nii et see on ainult küsimus, kui teil juhtub olema otsivad läbi massiivi

808
01:06:33,760 --> 01:06:38,070
miljardeid asju.

809
01:06:38,070 --> 01:06:44,050
Aga kui madal + kuni juhtub ülevoolu, siis see on probleem.

810
01:06:44,050 --> 01:06:47,750
Niipea kui me need allkirjastamata, siis 2 miljardit pluss 1 miljard 3000000000.

811
01:06:47,750 --> 01:06:51,960
3000000000 jagatud 2 on 1,5 miljardit eurot.

812
01:06:51,960 --> 01:06:55,670
Nii et niipea kui nad on allkirjastamata, kõik on täiuslik.

813
01:06:55,670 --> 01:06:59,900
Ja nii see on ka küsimus, kui olete kirjalikult oma jaoks silmuseid,

814
01:06:59,900 --> 01:07:03,940
ja tegelikult, siis ilmselt teeb seda automaatselt.

815
01:07:09,130 --> 01:07:12,330
See tegelikult lihtsalt karjuda sulle.

816
01:07:12,330 --> 01:07:21,610
Nii et kui see arv on liiga suur, et olla lihtsalt täisarv, kuid see sobiks allkirjastamata täisarv,

817
01:07:21,610 --> 01:07:24,970
see ütleb teile, nii et miks sa kunagi tekib küsimus.

818
01:07:29,150 --> 01:07:34,820
Te näete, et indeks on kunagi saab olema negatiivne,

819
01:07:34,820 --> 01:07:39,220
ja nii kui sa itereerimise üle massiiv,

820
01:07:39,220 --> 01:07:43,970
saate peaaegu alati öelda allkirjastamata int i, kuid sa tõesti ei pea.

821
01:07:43,970 --> 01:07:47,110
Asjad lähevad tööle päris palju sama hästi.

822
01:07:48,740 --> 01:07:50,090
Okei. [Sosistab] Mis kell on?

823
01:07:50,090 --> 01:07:54,020
Viimane asi, mida ma tahtsin näidata - ja ma just seda teha väga kiiresti.

824
01:07:54,020 --> 01:08:03,190
Sa tead, kuidas oleme # define et saaksime # define MAX kui 5 või midagi?

825
01:08:03,190 --> 01:08:05,940
Ärme teeme MAX. # Define tema kui 200-le. See, mida me tegime enne.

826
01:08:05,940 --> 01:08:10,380
See määratleb konstant, mis on lihtsalt läheb kopeerida ja kleepida

827
01:08:10,380 --> 01:08:13,010
kus iganes me juhtumisi kirjutan seotud.

828
01:08:13,010 --> 01:08:18,189
>> Nii saame tegelikult teha rohkem # määratleb.

829
01:08:18,189 --> 01:08:21,170
Saame # define funktsioone.

830
01:08:21,170 --> 01:08:23,410
Nad pole tõesti toimib, kuid me kutsume neid funktsioone.

831
01:08:23,410 --> 01:08:36,000
Näiteks oleks midagi MAX (x, y) on defineeritud kui (x <y? Y: x). Okei.

832
01:08:36,000 --> 01:08:40,660
Nii et sa peaksid harjuma kolmekomponentsete operaator süntaks,

833
01:08:40,660 --> 01:08:49,029
kuid on x vähem kui y? Tagasi y, teine ​​tagasi x.

834
01:08:49,029 --> 01:08:54,390
Nii et näete, saate teha seda eraldi funktsioon,

835
01:08:54,390 --> 01:09:01,399
ja funktsioon võiks olla nagu bool MAX kestab 2 argumente, tagastab.

836
01:09:01,399 --> 01:09:08,340
See on üks enim levinud näen teinud niimoodi. Me nimetame neid makrosid.

837
01:09:08,340 --> 01:09:11,790
See on makro.

838
01:09:11,790 --> 01:09:15,859
See on lihtsalt süntaks ta.

839
01:09:15,859 --> 01:09:18,740
Võite kirjutada makro teha mida iganes sa tahad.

840
01:09:18,740 --> 01:09:22,649
Sa sageli näha makrosid silumiseks printfs ja värki.

841
01:09:22,649 --> 01:09:29,410
Nii tüüpi printf on olemas spetsiaalsed konstandid C nagu rõhutavad LINE rõhutada,

842
01:09:29,410 --> 01:09:31,710
2 rõhutatakse LINE rõhutada,

843
01:09:31,710 --> 01:09:37,550
ja seal on ka minu arvates 2 rõhutatakse FUNC. See võib olla see. Midagi sellist.

844
01:09:37,550 --> 01:09:40,880
Need asjad tuleb asendada funktsiooni nimi

845
01:09:40,880 --> 01:09:42,930
või mitu liini, mis sa oled.

846
01:09:42,930 --> 01:09:48,630
Sageli kirjutad silumine printfs et siin all ma võiksin siis lihtsalt kirjutada

847
01:09:48,630 --> 01:09:54,260
Debug ja see print line number ja funktsioon, et ma juhtun olema

848
01:09:54,260 --> 01:09:57,020
et tal tekkisid selle DEBUG avalduse.

849
01:09:57,020 --> 01:09:59,550
Ja saate printida ka muid asju.

850
01:09:59,550 --> 01:10:05,990
Nii et üks asi, mida sa peaksid olge on, kui ma juhtun # define DOUBLE_MAX

851
01:10:05,990 --> 01:10:11,380
kui midagi 2 * y ja 2 * x.

852
01:10:11,380 --> 01:10:14,310
Nii et mingil põhjusel juhtub, et teha palju.

853
01:10:14,310 --> 01:10:16,650
Nii et see makro.

854
01:10:16,650 --> 01:10:18,680
See on tegelikult katki.

855
01:10:18,680 --> 01:10:23,050
Ma nimetaksin seda tehes midagi DOUBLE_MAX (3, 6).

856
01:10:23,050 --> 01:10:27,530
Mida tuleks tagasi?

857
01:10:28,840 --> 01:10:30,580
[Üliõpilane] 12.

858
01:10:30,580 --> 01:10:34,800
Jah, 12 tuleb tagasi, ja 12 tagastatud.

859
01:10:34,800 --> 01:10:43,350
3 saab asendada x, 6 saab asendada y, ja me läheme tagasi 2 * 6, mis on 12.

860
01:10:43,350 --> 01:10:47,710
Nüüd mis sellest? Mida tuleks tagasi?

861
01:10:47,710 --> 01:10:50,330
[Üliõpilane] 14. >> Ideaalis, 14.

862
01:10:50,330 --> 01:10:55,290
Küsimus on, et kuidas hash määratleb töö, pidage meeles see on sõnasõnaline kopeeri ja kleebi

863
01:10:55,290 --> 01:11:00,160
ja päris palju kõike, mis siis, et see saab tõlgendada

864
01:11:00,160 --> 01:11:11,270
on 3 alla 1 pluss 6, 2 korda 1 pluss 6, 2 korda 3.

865
01:11:11,270 --> 01:11:19,780
>> Nii et sel põhjusel sa peaaegu alati wrap kõike sulgudes.

866
01:11:22,180 --> 01:11:25,050
Iga muutuja sa peaaegu alati wrap sulgudes.

867
01:11:25,050 --> 01:11:29,570
On juhtumeid, kus sa ei pea, nagu ma tean, et ma ei pea seda tegema siin

868
01:11:29,570 --> 01:11:32,110
sest vähem kui on päris palju alati lihtsalt läheb tööle,

869
01:11:32,110 --> 01:11:34,330
kuigi see ei pruugi isegi olla tõsi.

870
01:11:34,330 --> 01:11:41,870
Kui midagi on naeruväärne nagu DOUBLE_MAX (1 == 2)

871
01:11:41,870 --> 01:11:49,760
siis see on hakka asendatakse 3 vähem kui 1 võrdub võrdub 2,

872
01:11:49,760 --> 01:11:53,460
ja nii siis see läheb teha 3 alla 1, siis kas see võrdub 2,

873
01:11:53,460 --> 01:11:55,620
mis pole see, mida me tahame.

874
01:11:55,620 --> 01:12:00,730
Nii et vältida operaatori tähtsam probleeme,

875
01:12:00,730 --> 01:12:02,870
alati wrap sulgudes.

876
01:12:03,290 --> 01:12:07,700
Okei. Ja ongi kõik, 5:30.

877
01:12:08,140 --> 01:12:12,470
Kui teil on küsimusi pset, andke meile teada.

878
01:12:12,470 --> 01:12:18,010
See peaks olema lõbus, ja häkker väljaanne ka on palju realistlikum

879
01:12:18,010 --> 01:12:22,980
kui häkker väljaanne eelmise aasta, seega loodame, et palju teil seda proovida.

880
01:12:22,980 --> 01:12:26,460
Eelmisel aastal oli väga suur.

881
01:12:28,370 --> 01:12:30,000
>> [CS50.TV]