1
00:00:00,000 --> 00:00:02,570
[Powered by Google Translate] [Kafli 3 - öruggari]

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

3
00:00:05,070 --> 00:00:07,310
>> [Þetta er CS50. - CS50.TV]

4
00:00:07,310 --> 00:00:12,700
>> Svo fyrsta spurningin er undarlega orðuð.

5
00:00:12,700 --> 00:00:17,480
GDB leyfir þér "kemba" forrit, en nánar tiltekið, hvað þýðir það að láta þig gera?

6
00:00:17,480 --> 00:00:22,590
Ég svara að einn, og ég veit ekki hvað er nákvæmlega gert ráð fyrir,

7
00:00:22,590 --> 00:00:27,910
þannig að ég ætla að giska á að það er eitthvað á sömu nótum og það leyfir þér skref fyrir skref

8
00:00:27,910 --> 00:00:31,540
ganga í gegnum the program, samskipti við það, breyting breytur, sem gjöri allt þetta -

9
00:00:31,540 --> 00:00:34,270
grundvallaratriðum alveg stjórna framkvæmd áætlunarinnar

10
00:00:34,270 --> 00:00:38,410
og skoða hverjum hluta framkvæmd áætlunarinnar.

11
00:00:38,410 --> 00:00:43,030
Svo þær aðgerðir láta þig kemba það.

12
00:00:43,030 --> 00:00:44,830
Allt í lagi.

13
00:00:44,830 --> 00:00:50,520
Hvers vegna tvöfaldur leita þurfa að fylki er að raða?

14
00:00:50,520 --> 00:00:53,360
Hver vill til að svara því?

15
00:00:56,120 --> 00:01:00,070
[Nemandi] Vegna þess að það virkar ekki ef það er ekki raðað. >> Já. [Hlátur]

16
00:01:00,070 --> 00:01:04,910
Ef það er ekki raðað, þá er það ómögulegt að skipta henni í tvennt

17
00:01:04,910 --> 00:01:07,850
og vita að allt til vinstri er minna og allt til hægri

18
00:01:07,850 --> 00:01:10,490
er meiri en miðju gildi.

19
00:01:10,490 --> 00:01:12,790
Þannig þarf það að vera flokkaður.

20
00:01:12,790 --> 00:01:14,170
Allt í lagi.

21
00:01:14,170 --> 00:01:17,570
Hvers vegna er kúla tegund í O í n veldi?

22
00:01:17,570 --> 00:01:23,230
Er einhver sem vill fyrst að gefa mjög fljótur hár-láréttur flötur yfirlit yfir hvaða kúla tegund er?

23
00:01:25,950 --> 00:01:33,020
[Nemandi] Þú ferð í grundvallaratriðum um hvert frumefni og þú skoðar fyrstu þætti.

24
00:01:33,020 --> 00:01:37,150
Ef þeir eru út af þar sem þú skipta þeim, svo þú stöðva næstu þætti og svo framvegis.

25
00:01:37,150 --> 00:01:40,770
Þegar þú nærð í lok, þá veistu að stærsti þátturinn er sett í lok,

26
00:01:40,770 --> 00:01:42,750
svo þú hunsa að einn þá þú halda áfram að fara í gegnum,

27
00:01:42,750 --> 00:01:48,490
og hvert skipti sem þú þarft að athuga einn minna þáttur þar til þú gera engar breytingar. >> Já.

28
00:01:48,490 --> 00:01:58,470
Það heitir kúla tegund vegna þess að ef þú flettir array á hlið svo það er upp og niður, lóðrétt,

29
00:01:58,470 --> 00:02:03,100
þá stóru gildin munu sökkva til botns og litlu gildi mun kúla upp á toppinn.

30
00:02:03,100 --> 00:02:05,210
Það er hvernig það fékk nafn sitt.

31
00:02:05,210 --> 00:02:08,220
Og já, þú ferð bara í gegnum.

32
00:02:08,220 --> 00:02:11,190
Þú halda að fara í gegnum fylking, skipta stærri gildi

33
00:02:11,190 --> 00:02:14,040
til að fá stærstu gildi til the botn.

34
00:02:14,040 --> 00:02:17,500
>> Hvers vegna er það O n veldi?

35
00:02:18,690 --> 00:02:24,620
Í fyrsta lagi er einhver langar að segja hvers vegna það er O n veldi?

36
00:02:24,620 --> 00:02:28,760
[Nemandi] Þar fyrir hvern tíma það fer n sinnum.

37
00:02:28,760 --> 00:02:32,100
Þú getur aðeins verið viss um að þú hafir tekið Stærsti parturinn alla leið niður,

38
00:02:32,100 --> 00:02:35,230
þá verður þú að endurtaka þetta fyrir eins mörgum þáttum. >> Já.

39
00:02:35,230 --> 00:02:41,800
Svo hafa í huga hvað stór O þýðir og hvað stór þýðir Omega.

40
00:02:41,800 --> 00:02:50,560
Stóri O er eins og efri mörk á hversu hægt það getur í raun keyrt.

41
00:02:50,560 --> 00:02:58,990
Svo með því að segja o Það er í n veldi, það er ekki O n annars það væri hægt að keyra

42
00:02:58,990 --> 00:03:02,640
í línulegum tíma, en það er O n cubed

43
00:03:02,640 --> 00:03:06,390
því það afmarkast af O í n cubed.

44
00:03:06,390 --> 00:03:12,300
Ef það er umlukin O á n veldi, þá er það takmarkast einnig af n cubed.

45
00:03:12,300 --> 00:03:20,280
Svo það er n veldi, og í hreinum versta tilfelli getur það ekki gert betur en n veldi,

46
00:03:20,280 --> 00:03:22,830
sem er hvers vegna það er O n veldi.

47
00:03:22,830 --> 00:03:31,200
Svo að sjá smá stærðfræði á hvernig það kemur út að vera N veldi,

48
00:03:31,200 --> 00:03:40,530
Ef við höfum fimm hluti á listanum okkar, í fyrsta sinn hversu margir samningar gætum við þurfum hugsanlega að

49
00:03:40,530 --> 00:03:47,170
í því skyni að fá þetta? Við skulum reyndar bara -

50
00:03:47,170 --> 00:03:52,040
Hversu margir skiptasamningar við erum að fara að gera í fyrsta hlaupa af tegund kúla gegnum fylki?

51
00:03:52,040 --> 00:03:53,540
[Nemandi] n - 1. >> Já.

52
00:03:53,540 --> 00:03:58,340
>> Ef það eru 5 þættir, við erum að fara að þurfa að gera n - 1.

53
00:03:58,340 --> 00:04:01,100
Síðan á seinni hversu margir skiptasamningar við erum að fara að gera?

54
00:04:01,100 --> 00:04:03,440
[Nemandi] n - 2. >> Já.

55
00:04:03,440 --> 00:04:11,640
Og þriðja er að fara að vera n - 3, og þá til þæginda mun ég skrifa síðustu tvær

56
00:04:11,640 --> 00:04:15,270
eins og þá sem við erum að fara að þurfa að gera 2 skiptasamninga og 1 Víxla.

57
00:04:15,270 --> 00:04:19,899
Ég held að síðasta mega eða mega ekki í raun að gerast.

58
00:04:19,899 --> 00:04:22,820
Er það skipti? Ég veit ekki.

59
00:04:22,820 --> 00:04:26,490
Svo þetta eru alls fjárhæðir skiptasamninga eða amk samanburður sem þú þarft að gera.

60
00:04:26,490 --> 00:04:29,910
Jafnvel ef þú skipta ekki, þú þarft samt að bera gildi.

61
00:04:29,910 --> 00:04:33,910
Þannig að það eru n - 1 samanburður á fyrsta hlaupa í gegnum array.

62
00:04:33,910 --> 00:04:42,050
Ef þú endurskipuleggja þetta, við skulum í raun að gera það sex hlutum svo það stafla upp fallega,

63
00:04:42,050 --> 00:04:44,790
og þá ég skal gera 3, 2, 1.

64
00:04:44,790 --> 00:04:49,910
Svo bara endurskipuleggja þessar upphæðir, við viljum að sjá hversu margir samanburð við tökum

65
00:04:49,910 --> 00:04:52,700
í öllu reiknirit.

66
00:04:52,700 --> 00:04:56,550
Þannig að ef við tökum þessar krakkar hérna,

67
00:04:56,550 --> 00:05:07,470
þá erum við samt bara að leggja saman þó margir samanburð voru.

68
00:05:07,470 --> 00:05:13,280
En ef við summa þetta og við summa þetta og við summa þetta,

69
00:05:13,280 --> 00:05:18,130
það er enn sama vandamál. Við summa bara þessum tiltekna hópa.

70
00:05:18,130 --> 00:05:22,400
>> Svo nú erum við að leggja saman 3 er n. Það er ekki bara 3 er n.

71
00:05:22,400 --> 00:05:27,650
Það er alltaf að fara að vera N / 2 er n.

72
00:05:27,650 --> 00:05:29,430
Svo hér við átt 6.

73
00:05:29,430 --> 00:05:34,830
Ef við hefðum 10 hlutum, svo við gætum gert þetta hópar í 5 mismunandi pör af hlutum

74
00:05:34,830 --> 00:05:37,180
og endar með n + n + n + n + n.

75
00:05:37,180 --> 00:05:45,840
Svo þú ert alltaf að fara að fá N / 2 er n, og svo þetta sem við munum hripa það út til n veldi / 2.

76
00:05:45,840 --> 00:05:48,890
Og svo jafnvel þó að það er þáttur í helming, sem gerist að koma í

77
00:05:48,890 --> 00:05:54,190
vegna þess að með hverri ítrun yfir fylki við saman 1 minna

78
00:05:54,190 --> 00:05:58,040
svo er það hvernig við fá yfir 2, en það er samt n veldi.

79
00:05:58,040 --> 00:06:01,650
Við sama um stöðugum þáttur um helming.

80
00:06:01,650 --> 00:06:07,760
Svo mikið af stór O efni eins og þetta byggir á bara góður að gera þessa tegund af stærðfræði,

81
00:06:07,760 --> 00:06:12,260
gera tölur fjárhæðir og geometrísk röð efni,

82
00:06:12,260 --> 00:06:17,750
en af ​​þeim á þessu námskeiði eru frekar einfalt.

83
00:06:17,750 --> 00:06:19,290
Allt í lagi.

84
00:06:19,290 --> 00:06:24,430
Hvers vegna er insertion sort í Omega í n? Hvað þýðir Omega meina?

85
00:06:24,430 --> 00:06:27,730
[Tveir nemendur tala í einu - óskiljanlegur] >> Já.

86
00:06:27,730 --> 00:06:30,630
Omega er hægt að hugsa um eins og neðri bundinn.

87
00:06:30,630 --> 00:06:36,550
>> Svo sama hversu duglegur insertion sort reiknirit er,

88
00:06:36,550 --> 00:06:41,810
burtséð frá listanum sem er samþykkt í, hefur það alltaf að bera að minnsta kosti n hluti

89
00:06:41,810 --> 00:06:44,620
eða það hefur að iterate yfir n hlutum.

90
00:06:44,620 --> 00:06:47,280
Hvers vegna er það?

91
00:06:47,280 --> 00:06:51,190
[Nemandi] Vegna þess að ef listinn er þegar raðað, þá í gegnum fyrsta endurtekning

92
00:06:51,190 --> 00:06:54,080
þú getur aðeins tryggt að fyrsta þáttur er minnst,

93
00:06:54,080 --> 00:06:56,490
og annað endurtekning þú getur aðeins ábyrgst fyrstu tvær eru

94
00:06:56,490 --> 00:07:00,010
vegna þess að þú veist ekki að restin af listanum er raðað. >> Já.

95
00:07:00,010 --> 00:07:08,910
Ef þú fara í algjörlega raðaða lista, á the mjög minnstur þú ert að fara yfir alla þætti

96
00:07:08,910 --> 00:07:12,180
til að sjá að ekkert þarf að vera flutt í kring.

97
00:07:12,180 --> 00:07:14,720
Svo farið yfir listann og segja ó, þetta er þegar raðað,

98
00:07:14,720 --> 00:07:18,240
það er ómögulegt fyrir þig að vita að það er raðað þar til þú athuga hvert frumefni

99
00:07:18,240 --> 00:07:20,660
til að sjá að þeir eru í raðað röð.

100
00:07:20,660 --> 00:07:25,290
Svo neðri bundinn á Innsetningarröðun er Omega í n.

101
00:07:25,290 --> 00:07:28,210
Hvað er það versta tilfelli í gangi tími Mergesort,

102
00:07:28,210 --> 00:07:31,390
versta tilfelli vera stór O aftur?

103
00:07:31,390 --> 00:07:37,660
Svo í versta falli, hvernig virkar Mergesort hlaupa?

104
00:07:42,170 --> 00:07:43,690
[Nemandi] N log n. >> Já.

105
00:07:43,690 --> 00:07:49,990
The Festa almenn reiknirit flokkun eru n log n. Þú getur ekki gert betur.

106
00:07:51,930 --> 00:07:55,130
>> Það eru sérstök tilfelli, og ef við höfum tíma í dag - en við won't líklega -

107
00:07:55,130 --> 00:07:59,330
við gátum séð sem virkar betur en n log n.

108
00:07:59,330 --> 00:08:04,050
En í almennu máli, getur þú ekki gert betur en n log n.

109
00:08:04,050 --> 00:08:09,680
Og sameina tegund verður að vera sá sem þú ættir að vita að þetta námskeið sem er n log n.

110
00:08:09,680 --> 00:08:13,260
Og svo munum við í raun að framkvæma það í dag.

111
00:08:13,260 --> 00:08:18,070
Og að lokum, í ekki meira en þrjár setningar, hvernig virkar val konar vinna?

112
00:08:18,070 --> 00:08:20,370
Hefur einhver vilja til að svara, og ég ætla að telja setningar þínar

113
00:08:20,370 --> 00:08:22,390
því ef þú ferð yfir 3 -

114
00:08:25,530 --> 00:08:28,330
Hefur einhver man val sort?

115
00:08:31,280 --> 00:08:37,809
Val tegund er yfirleitt mjög auðvelt að muna bara frá nafni.

116
00:08:37,809 --> 00:08:45,350
Þú iterate rúmlega array, finna hvað er stærsta gildi eða minnsta -

117
00:08:45,350 --> 00:08:47,290
hvað röð þú ert að flokka inn

118
00:08:47,290 --> 00:08:50,750
Svo skulum segja að við erum að flokka frá smæstu til stærstu.

119
00:08:50,750 --> 00:08:55,250
Þú iterate yfir fjölda, leita hvað lágmarks þáttur er,

120
00:08:55,250 --> 00:08:59,750
velja hana og síðan bara skipta henni hvað er í fyrsta sæti.

121
00:08:59,750 --> 00:09:04,090
Og þá á öðrum fara yfir fjölda, leita lágmarks frumefni aftur,

122
00:09:04,090 --> 00:09:07,490
velja það, og þá skipta um það með hvað er í annarri stöðu.

123
00:09:07,490 --> 00:09:10,650
Þannig að við erum bara að tína og velja Lágmarksgildi

124
00:09:10,650 --> 00:09:16,050
og setja þá inn í the andlit af the array þar til það er flokkað.

125
00:09:19,210 --> 00:09:21,560
Spurningar um það?

126
00:09:21,560 --> 00:09:25,710
>> Þetta virðist óhjákvæmilega í formi sem þú þarft að fylla út ef þú ert að skila inn pset.

127
00:09:29,010 --> 00:09:32,360
Þeir eru í grundvallaratriðum svör við þeim.

128
00:09:32,360 --> 00:09:34,230
Jæja, svo nú erfðaskrá vandamál.

129
00:09:34,230 --> 00:09:40,140
Ég sendi nú þegar út í tölvupósti - Var einhver ekki fá þessi email? Allt í lagi.

130
00:09:40,140 --> 00:09:46,630
Ég sendi nú þegar út í tölvupósti rými sem við erum að fara að vera með,

131
00:09:46,630 --> 00:09:52,120
og ef þú smellir á nafnið mitt - svo ég held að ég ætla að vera neðst

132
00:09:52,120 --> 00:09:57,170
vegna afturábak r - en ef þú smellir á nafnið mitt sérðu 2 endurskoðun.

133
00:09:57,170 --> 00:10:02,650
Útgáfa 1 er að fara að ég afritað og límt kóðann inn Spaces

134
00:10:02,650 --> 00:10:06,900
að leita hlutur þú ert að fara að framkvæma.

135
00:10:06,900 --> 00:10:10,540
Og Revision 2 verður eins konar hlutur sem við framkvæma eftir það.

136
00:10:10,540 --> 00:10:15,770
Svo er hægt að smella á Revision minn 1 og vinna þaðan.

137
00:10:17,350 --> 00:10:22,060
Og nú viljum við innleiða tvöfaldur leit.

138
00:10:22,060 --> 00:10:26,470
>> Er einhver sem vill bara gefa sauðakóðanum háttsettum skýringu

139
00:10:26,470 --> 00:10:31,440
af því sem við erum að fara að gera fyrir leit? Já.

140
00:10:31,440 --> 00:10:36,170
[Nemandi] Þú tekur bara miðju fylkisins og sjá hvort það sem þú ert að leita að

141
00:10:36,170 --> 00:10:38,650
er minna en eða meira en það.

142
00:10:38,650 --> 00:10:41,080
Og ef það er minna, þú ferð að hluta sem er minna,

143
00:10:41,080 --> 00:10:44,750
og ef það er meira, þú ferð að hluta sem er meira og þú endurtaka það þar til þú færð bara eitt.

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

145
00:10:46,570 --> 00:10:51,320
Takið eftir að númer array okkar er þegar raðað,

146
00:10:51,320 --> 00:10:57,190
og svo þýðir það að við getum nýtt sér það og við gátum fyrst að athuga,

147
00:10:57,190 --> 00:11:00,390
allt í lagi, ég er að leita að númer 50.

148
00:11:00,390 --> 00:11:03,720
Svo ég get farið inn á miðju.

149
00:11:03,720 --> 00:11:07,380
Miðjunni er erfitt að skilgreina hvenær það er slétt tala af hlutur,

150
00:11:07,380 --> 00:11:10,820
en við skulum bara segja að við munum alltaf HÃ við miðju.

151
00:11:10,820 --> 00:11:14,420
Svo hér höfum við 8 hlutum, þannig að miðja væri 16 ára.

152
00:11:14,420 --> 00:11:17,330
Ég er að leita að 50, svo 50 meiri en 16 ára.

153
00:11:17,330 --> 00:11:21,310
Svo nú get ég í raun meðhöndla array mitt sem þessum þáttum.

154
00:11:21,310 --> 00:11:23,450
Ég get henda allt frá 16 yfir.

155
00:11:23,450 --> 00:11:27,440
Nú er array minn bara þessir 4 þættir, og ég endurtek.

156
00:11:27,440 --> 00:11:31,910
Svo ég vil að finna miðju aftur, sem er að fara að vera 42.

157
00:11:31,910 --> 00:11:34,730
42 er minna en 50, þannig að ég get henda þessum tveimur þáttum.

158
00:11:34,730 --> 00:11:36,890
Þetta er eftir array mín.

159
00:11:36,890 --> 00:11:38,430
Ég ætla að finna miðju aftur.

160
00:11:38,430 --> 00:11:42,100
Ég giska á 50 var slæmt fordæmi vegna þess að ég var alltaf að henda burt það til vinstri,

161
00:11:42,100 --> 00:11:48,280
en með sömu mál, ef ég er að leita að einhverju

162
00:11:48,280 --> 00:11:52,100
og það er minna en frumefni Ég er nú að leita á,

163
00:11:52,100 --> 00:11:55,080
þá ætla ég að henda öllu til hægri.

164
00:11:55,080 --> 00:11:58,150
Svo nú þurfum við að framkvæma það.

165
00:11:58,150 --> 00:12:02,310
Takið eftir að við þurfum að fara að stærð.

166
00:12:02,310 --> 00:12:06,730
Við getum líka ekki að harða kóða stærð.

167
00:12:06,730 --> 00:12:11,640
Þannig að ef við losna við að # define -

168
00:12:19,630 --> 00:12:21,430
Allt í lagi.

169
00:12:21,430 --> 00:12:27,180
Hvernig get ég fundið fallega út hvað stærð númer array nú er?

170
00:12:27,180 --> 00:12:30,950
>> Hversu mörg frumefni eru í númer array?

171
00:12:30,950 --> 00:12:33,630
[Nemendur] Numbers, sviga,. Lengd?

172
00:12:33,630 --> 00:12:36,600
[Bowden] Það er ekki til í C.

173
00:12:36,600 --> 00:12:38,580
Þarftu. Lengd.

174
00:12:38,580 --> 00:12:42,010
Fylki hefur ekki eiginleika, svo það er engin lengd eign fylki

175
00:12:42,010 --> 00:12:45,650
það verður bara að gefa þér þó lengi það gerist að vera.

176
00:12:48,180 --> 00:12:51,620
[Nemandi] Sjá hversu mikið minni hún hefur og deila með hversu mikið - >> Já.

177
00:12:51,620 --> 00:12:55,810
Og hvernig getum við séð hversu mikið minni hún hefur? >> [Nemandi] sizeof. >> Já, sizeof.

178
00:12:55,810 --> 00:13:01,680
Sizeof er stjórnandi sem er að fara að skila stærð númer fylkisins.

179
00:13:01,680 --> 00:13:10,060
Og það er að fara að vera þó margar heiltölur eru sinnum the stærð af heiltölu

180
00:13:10,060 --> 00:13:14,050
Þar sem er hversu mikið minni það er í raun að taka upp.

181
00:13:14,050 --> 00:13:17,630
Svo ef ég vil ýmislegt í fylking,

182
00:13:17,630 --> 00:13:20,560
þá er ég að fara til að vilja skipta um stærð heiltala.

183
00:13:22,820 --> 00:13:26,010
Allt í lagi. Svo leyfir að mér að fara í stærð hér.

184
00:13:26,010 --> 00:13:29,430
Hvers vegna þarf ég að fara í stærð á öllum?

185
00:13:29,430 --> 00:13:38,570
Hvers vegna get ég ekki bara upp hér int size = sizeof (Haystack) / sizeof (int)?

186
00:13:38,570 --> 00:13:41,490
Hvers vegna virkar þetta ekki?

187
00:13:41,490 --> 00:13:44,470
[Nemandi] Það er ekki alþjóðlegt breytu.

188
00:13:44,470 --> 00:13:51,540
[Bowden] Haystack til og við erum sem liggur í tölum sem Heysátan,

189
00:13:51,540 --> 00:13:54,700
og þetta er góður af a foreshadowing um hvað er að koma. Já.

190
00:13:54,700 --> 00:14:00,170
[Nemandi] Haystack er bara tilvísun í það, þannig að það myndi koma aftur hversu stór sem tilvísun.

191
00:14:00,170 --> 00:14:02,150
Já.

192
00:14:02,150 --> 00:14:09,000
Ég efast í fyrirlestri sem þú hefur séð stafla enn í raun, ekki satt?

193
00:14:09,000 --> 00:14:11,270
Við höfum bara talað um það.

194
00:14:11,270 --> 00:14:16,090
Svo er stafla þar sem allar breytur eru að fara að geyma.

195
00:14:16,090 --> 00:14:19,960
>> Allir minni sem er úthlutað fyrir staðbundnum breytur er að fara í á mánudaginn,

196
00:14:19,960 --> 00:14:24,790
og hver aðgerð fær eigin rúm hennar á mánudaginn, eiga stafla ramma þess er hvað það er kallað.

197
00:14:24,790 --> 00:14:31,590
Svo helstu hefur stafla ramma þess, og inni í því er að fara að vera þetta númer array,

198
00:14:31,590 --> 00:14:34,270
og það er að fara að vera sizeof stærð (númer).

199
00:14:34,270 --> 00:14:38,180
Það er að fara að hafa stærð talna deilt með stærð þáttum,

200
00:14:38,180 --> 00:14:42,010
en alla ævi innan ramma stafla aðal.

201
00:14:42,010 --> 00:14:45,190
Þegar við köllum leit, fær eigin stafla ramma þess,

202
00:14:45,190 --> 00:14:48,840
eigin rúm til þess að geyma allar staðbundnar breytur hennar.

203
00:14:48,840 --> 00:14:56,420
En þessi rök - það er Heysátan ekki afrit af þessu öllu fylki.

204
00:14:56,420 --> 00:15:00,990
Við fara ekki í öllu fylkinu sem afrit í leit.

205
00:15:00,990 --> 00:15:04,030
Það fer bara tilvísun í það fylki.

206
00:15:04,030 --> 00:15:11,470
Svo leita aðgang þessar tölur gegnum þessa tilvísun.

207
00:15:11,470 --> 00:15:17,100
Það er enn að fá aðgang að hlutum sem lifa innan ramma stafla aðal,

208
00:15:17,100 --> 00:15:22,990
en í grundvallaratriðum, þegar við komum að ábendingum, sem ætti að vera fljótlega,

209
00:15:22,990 --> 00:15:24,980
þetta er það sem ábendingum er.

210
00:15:24,980 --> 00:15:29,400
Ábendingar eru bara tilvísanir í hluti, og þú getur notað ábendingum til aðgang hluti

211
00:15:29,400 --> 00:15:32,030
sem eru í ramma stafla annar hlutur.

212
00:15:32,030 --> 00:15:37,660
Svo jafnvel þótt númer er staðbundin að helstu, getum við samt í gegnum þetta músina.

213
00:15:37,660 --> 00:15:41,770
En þar sem það er bara músina og það er bara viðmið,

214
00:15:41,770 --> 00:15:45,040
sizeof (Haystack) skilar bara stærð tilvísun sjálft.

215
00:15:45,040 --> 00:15:47,950
Það þýðir ekki að skila stærð málið það bendir til.

216
00:15:47,950 --> 00:15:51,110
Það þýðir ekki að skila raunverulegri stærð af tölum.

217
00:15:51,110 --> 00:15:55,660
Og svo er þetta ekki að fara að vinna eins og við viljum það til.

218
00:15:55,660 --> 00:15:57,320
>> Spurningar um það?

219
00:15:57,320 --> 00:16:03,250
Ábendingum verður farið í í marktækt Gory smáatriðum í vikur til að koma.

220
00:16:06,750 --> 00:16:13,740
Og þetta er ástæðan fyrir a einhver fjöldi af hlutur sem þú sérð, the leita hlutum eða raða hlutum,

221
00:16:13,740 --> 00:16:16,990
þeir eru nánast allir að fara að þurfa að taka raunverulegan stærð fylkisins,

222
00:16:16,990 --> 00:16:20,440
því að í C, höfum við ekki hugmynd um hvað stærð fylkisins er.

223
00:16:20,440 --> 00:16:22,720
Þú þarft að höndunum gefa það inn

224
00:16:22,720 --> 00:16:27,190
Og þú getur ekki handvirkt að fara í öllu fylkinu vegna þess að þú ert bara farið í tilvísun

225
00:16:27,190 --> 00:16:30,390
og það er ekki hægt að fá stærð frá viðmiðunarverði.

226
00:16:30,390 --> 00:16:32,300
Allt í lagi.

227
00:16:32,300 --> 00:16:38,160
Svo nú viljum við að framkvæma það sem var lýst áður.

228
00:16:38,160 --> 00:16:41,530
Þú getur unnið á það í eina mínútu,

229
00:16:41,530 --> 00:16:45,250
og þú þarft ekki að hafa áhyggjur óður í getting allt fullkomlega 100% vinna.

230
00:16:45,250 --> 00:16:51,410
Bara skrifa upp hálfa sauðakóðanum því hvernig þú heldur að það ætti að virka.

231
00:16:52,000 --> 00:16:53,630
Allt í lagi.

232
00:16:53,630 --> 00:16:56,350
Engin þörf á að vera alveg búin með það enn.

233
00:16:56,350 --> 00:17:02,380
En er einhver líða vel með það sem þeir hafa svo langt,

234
00:17:02,380 --> 00:17:05,599
eins og eitthvað sem við getum unnið með saman?

235
00:17:05,599 --> 00:17:09,690
Er einhver sem vill sjálfboðaliða? Eða mun ég af handahófi velja.

236
00:17:12,680 --> 00:17:18,599
Það þarf ekki að vera rétt því hvaða mál en eitthvað Við getum breytt í starfshóp ástand.

237
00:17:18,599 --> 00:17:20,720
[Nemandi] Jú. >> Lagi.

238
00:17:20,720 --> 00:17:27,220
Svo er hægt að vista útgáfu með því að smella á litlu Vista táknið.

239
00:17:27,220 --> 00:17:29,950
Þú ert Ramya, ekki satt? >> [Nemandi] Já. >> [Bowden] lagi.

240
00:17:29,950 --> 00:17:35,140
Svo nú get ég skoðað endurskoðun og allir geta draga upp endurskoðun.

241
00:17:35,140 --> 00:17:38,600
Og hér höfum við - Allt í lagi.

242
00:17:38,600 --> 00:17:43,160
Svo Ramya fór með endurkvæma lausn, sem er ákveðið gild lausn.

243
00:17:43,160 --> 00:17:44,970
Það eru tvær leiðir sem þú getur gert þetta vandamál.

244
00:17:44,970 --> 00:17:48,060
Þú getur annað hvort gera það iteratively eða undirmöppum.

245
00:17:48,060 --> 00:17:53,860
Flest vandamál sem þú lendir það er hægt að gera endurkvæmt getur líka verið gert iteratively.

246
00:17:53,860 --> 00:17:58,510
Svo hér höfum við gert það í undirmöppum.

247
00:17:58,510 --> 00:18:03,730
>> Hefur einhver vilja til að skilgreina hvað það þýðir að gera fall endurkvæma?

248
00:18:07,210 --> 00:18:08,920
[Nemandi] Þegar þú ert með virka kalla sig

249
00:18:08,920 --> 00:18:13,470
og þá kalla sig þangað til það kemur út með rétt og satt. >> Já.

250
00:18:13,470 --> 00:18:17,680
A endurkvæma virka er bara fall sem kallar sig.

251
00:18:17,680 --> 00:18:24,140
Það eru þrjú stór atriði sem endurkvæma virka verður að hafa.

252
00:18:24,140 --> 00:18:27,310
Í fyrsta lagi er augljóslega, kallar það sig.

253
00:18:27,310 --> 00:18:29,650
Annað er undirstaða raunin.

254
00:18:29,650 --> 00:18:33,390
Svo á einhverjum tímapunkti fallið þarf að hætta að kalla sig,

255
00:18:33,390 --> 00:18:35,610
og það er það sem grunn tilfelli er fyrir.

256
00:18:35,610 --> 00:18:43,860
Svo hér við vitum að við ættum að hætta ætti við að gefast upp í leit okkar

257
00:18:43,860 --> 00:18:48,150
þegar byrja jafnt enda - og við munum fara yfir hvað þetta þýðir.

258
00:18:48,150 --> 00:18:52,130
En að lokum, the síðastur hlutur sem er mikilvægt fyrir endurkvæma virka:

259
00:18:52,130 --> 00:18:59,250
aðgerðir verða einhvern veginn nálgast grunn tilfelli.

260
00:18:59,250 --> 00:19:04,140
Eins ef þú ert í raun ekki að uppfæra neitt þegar þú annað endurkvæma hringja,

261
00:19:04,140 --> 00:19:07,880
Ef þú ert bókstaflega bara að hringja í virkni aftur með sömu rökum

262
00:19:07,880 --> 00:19:10,130
og engin global breytur hafa breyst eða eitthvað,

263
00:19:10,130 --> 00:19:14,430
þú munt aldrei ná stöð að ræða, í því tilviki sem er slæmt.

264
00:19:14,430 --> 00:19:17,950
Það mun vera óendanlega endurkvæmni og stafla flæða.

265
00:19:17,950 --> 00:19:24,330
En hér sjáum við að uppfæra er að gerast þar sem við erum að byrja að uppfæra + End / 2,

266
00:19:24,330 --> 00:19:28,180
Við erum að uppfæra á hætta rifrildi hér, við erum að uppfæra byrjun rök hér.

267
00:19:28,180 --> 00:19:32,860
Svo í öllum endurkvæma símtöl við erum að uppfæra eitthvað. Allt í lagi.

268
00:19:32,860 --> 00:19:38,110
Viltu ganga okkur í gegnum lausn þína? >> Jú.

269
00:19:38,110 --> 00:19:44,270
Ég er að nota SearchHelp þannig að í hvert skipti sem ég geri þetta virka símtalinu

270
00:19:44,270 --> 00:19:47,910
Ég hef upphaf þar sem ég er að leita að í fylkinu og í lok

271
00:19:47,910 --> 00:19:49,380
um þar sem ég er að leita að fylki.

272
00:19:49,380 --> 00:19:55,330
>> Við hvert skref sem það er að segja það er miðju þáttur sem er að byrja að + enda / 2,

273
00:19:55,330 --> 00:19:58,850
er miðaður við það sem við erum að leita að?

274
00:19:58,850 --> 00:20:04,650
Og ef það er, þá fundum við það, og ég held að fær liðið upp magn endurkvæmni.

275
00:20:04,650 --> 00:20:12,540
Og ef það er ekki satt, þá erum við að athuga hvort að miðju gildi fylkisins er of stór,

276
00:20:12,540 --> 00:20:19,320
í því tilviki við líta á vinstri hluta fylkisins með því að fara frá upphafi til miðju vísitölunni.

277
00:20:19,320 --> 00:20:22,710
Og annað sem við gerum á hætta helminginn.

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

279
00:20:24,740 --> 00:20:27,730
Það hljómar vel.

280
00:20:27,730 --> 00:20:36,640
Jæja, svo nokkra hluti, og í raun er þetta mjög háttsettum hlutur

281
00:20:36,640 --> 00:20:41,270
að þú munt aldrei þurfa að vita fyrir þetta námskeið, en það er satt.

282
00:20:41,270 --> 00:20:46,080
Endurkvæmar aðgerðir, heyrir þú alltaf að þær séu slæmur samningur

283
00:20:46,080 --> 00:20:51,160
því ef þú kallar endurkvæmt þig of oft, þá færðu stafla flæða

284
00:20:51,160 --> 00:20:54,990
síðan, eins og ég sagði áður, hvert hlutverk fær eigin stafla ramma þess.

285
00:20:54,990 --> 00:20:59,500
Þannig fær hvert símtal um endurkvæma virka eigin stafla ramma þess.

286
00:20:59,500 --> 00:21:04,140
Svo ef þú gerir 1000 endurkvæma símtöl, þá færðu 1.000 stakkur ramma,

287
00:21:04,140 --> 00:21:08,390
og fljótt þú leiða til að hafa of marga stafla ramma og svoleiðis bara brot.

288
00:21:08,390 --> 00:21:13,480
Svo er það hvers vegna endurkvæma virka almennt illa.

289
00:21:13,480 --> 00:21:19,370
En það er a ágætur hluti af endurkvæma virka kallað hali-endurkvæma virka,

290
00:21:19,370 --> 00:21:26,120
og þetta gerist að vera dæmi um einn þar ef þýðandinn tilkynningar þetta

291
00:21:26,120 --> 00:21:29,920
og það ætti, held ég - í Clang ef þú gefa það á-O2 merkja

292
00:21:29,920 --> 00:21:33,250
þá mun það taka þetta er hali endurkvæma og gera hlutina vel.

293
00:21:33,250 --> 00:21:40,050
>> Það mun endurnýta sömu stafla ramma aftur og aftur fyrir hvern endurkvæma hringja.

294
00:21:40,050 --> 00:21:47,010
Og svo þar sem þú ert að nota sömu stafla ramma, þú þarft ekki að hafa áhyggjur

295
00:21:47,010 --> 00:21:51,690
alltaf stafla barmafullur, og á sama tíma, eins og þú sagðir áður,

296
00:21:51,690 --> 00:21:56,380
þar þegar þú kemur aftur satt, þá hefur það að fara aftur upp öllum þessum stafla ramma

297
00:21:56,380 --> 00:22:01,740
og 10 kalla til SearchHelp að fara aftur í 9, þarf að fara aftur til 8..

298
00:22:01,740 --> 00:22:05,360
Svo þarf ekki að gerast þegar aðgerðir eru hali endurkvæma.

299
00:22:05,360 --> 00:22:13,740
Og svo er það sem gerir þessa aðgerð hali endurkvæma Athugið að í hverju símtali til searchHelp

300
00:22:13,740 --> 00:22:18,470
endurkvæma hringja að það er að gera er það sem það er að koma aftur.

301
00:22:18,470 --> 00:22:25,290
Svo í fyrstu kalla til SearchHelp, annaðhvort við strax aftur rangar,

302
00:22:25,290 --> 00:22:29,590
strax aftur satt, eða við tökum endurkvæma hringja til SearchHelp

303
00:22:29,590 --> 00:22:33,810
þar sem við erum að koma aftur er það sem kalla er að fara aftur.

304
00:22:33,810 --> 00:22:51,560
Og við gátum ekki gert þetta ef við gerðum eitthvað eins og int x = SearchHelp, skila X * 2,

305
00:22:51,560 --> 00:22:55,440
bara nokkrar af handahófi breyting.

306
00:22:55,440 --> 00:23:01,470
>> Svo nú þetta endurkvæma hringja, þetta int x = SearchHelp endurkvæma hringja,

307
00:23:01,470 --> 00:23:05,740
er ekki lengur hali endurkvæma vegna þess að það raunverulega hjartarskinn þurfa að snúa

308
00:23:05,740 --> 00:23:10,400
til baka í fyrri stafla ramma svo að fyrri hringja í aðgerð

309
00:23:10,400 --> 00:23:13,040
geta þá gert eitthvað með skilagildi.

310
00:23:13,040 --> 00:23:22,190
Svo er þetta ekki hali endurkvæma, en það sem við höfðum áður er fallega hali endurkvæma. Já.

311
00:23:22,190 --> 00:23:27,000
[Nemandi] Ætti ekki annað stöð mál að athuga fyrst

312
00:23:27,000 --> 00:23:30,640
vegna þess að það gæti verið aðstæður þar sem þegar þú standist það rök

313
00:23:30,640 --> 00:23:35,770
þú byrjar = enda, en þeir eru nál gildi.

314
00:23:35,770 --> 00:23:47,310
Spurningin var ekki hægt að hlaupa í málið þar enda er nálin gildi

315
00:23:47,310 --> 00:23:52,000
eða byrja = enda, viðeigandi, start = enda

316
00:23:52,000 --> 00:23:59,480
og þú hefur í raun ekki athugað þessa tilteknu gildi enn,

317
00:23:59,480 --> 00:24:03,910
þá byrja + End / 2 er bara að fara að vera á sama gildi.

318
00:24:03,910 --> 00:24:07,890
En við höfum nú þegar aftur rangar og við aldrei athugað gildi.

319
00:24:07,890 --> 00:24:14,240
Svo að minnsta kosti, í fyrsta símtali, ef stærð er 0, þá viljum við skila falskur.

320
00:24:14,240 --> 00:24:17,710
En ef stærð er 1, þá er að byrja er ekki að fara að jafna enda,

321
00:24:17,710 --> 00:24:19,820
og við munum að minnsta kosti athuga eitt frumefni.

322
00:24:19,820 --> 00:24:26,750
En ég held að þú ert rétt í því að við getum endað í máli þar byrja + End / 2,

323
00:24:26,750 --> 00:24:31,190
byrja endar að vera það sama og upphafi + End / 2,

324
00:24:31,190 --> 00:24:35,350
en við aldrei athugað að frumefni.

325
00:24:35,350 --> 00:24:44,740
>> Þannig að ef við athugum fyrst er miðja þáttur gildi sem við erum að leita að,

326
00:24:44,740 --> 00:24:47,110
þá getum við strax aftur satt.

327
00:24:47,110 --> 00:24:50,740
Annars ef þeir eru jafnir, þá er ekkert lið í að halda áfram

328
00:24:50,740 --> 00:24:58,440
þar sem við erum bara að fara að uppfæra í máli þar sem við erum á einum staka fylki.

329
00:24:58,440 --> 00:25:01,110
Ef að einn þáttur er ekki það sem við erum að leita að,

330
00:25:01,110 --> 00:25:03,530
þá er allt vitlaust. Já.

331
00:25:03,530 --> 00:25:08,900
[Nemandi] Málið er að þar sem stærð er í raun stærri en fjöldi staka í fylkinu,

332
00:25:08,900 --> 00:25:13,070
Það er nú þegar móti - >> Svo mun stærð -

333
00:25:13,070 --> 00:25:19,380
[Nemandi] Segja ef array var stærð 0, þá SearchHelp mun reyndar athuga Heysátan af 0

334
00:25:19,380 --> 00:25:21,490
á fyrsta símtali.

335
00:25:21,490 --> 00:25:25,300
Array er stærð 0, þannig að 0 er - >> Já.

336
00:25:25,300 --> 00:25:30,750
Það er annar hlutur sem - það gæti verið gott. Við skulum hugsa.

337
00:25:30,750 --> 00:25:40,120
Svo ef array hafði 10 þætti og miðja sem við erum að fara að athuga vísitölu 5,

338
00:25:40,120 --> 00:25:45,700
þannig að við erum að athuga 5, og við skulum segja að gildið er minna.

339
00:25:45,700 --> 00:25:50,720
Þannig að við erum að henda allt frá 5 áfram.

340
00:25:50,720 --> 00:25:54,030
Svo byrjar + endir / 2 er að fara að vera nýr enda okkar,

341
00:25:54,030 --> 00:25:57,450
svo já, það er alltaf að fara að vera út í lok fylkisins.

342
00:25:57,450 --> 00:26:03,570
Ef það er málið ef það væri jafnvel eða stakur, þá myndum við stöðva, segja, 4,

343
00:26:03,570 --> 00:26:05,770
en við erum enn að henda í burtu -

344
00:26:05,770 --> 00:26:13,500
Svo já, enda er alltaf að fara að vera út raunverulegan enda fylkisins.

345
00:26:13,500 --> 00:26:18,350
Svo þætti sem við erum með áherslu á, enda er alltaf að fara að vera einn eftir það.

346
00:26:18,350 --> 00:26:24,270
Og svo ef byrja er alltaf jafn enda erum við í fylki af stærð 0.

347
00:26:24,270 --> 00:26:35,600
>> The annar hlutur sem ég var að hugsa er að við erum að uppfæra byrja að byrja + enda / 2,

348
00:26:35,600 --> 00:26:44,020
þannig að þetta er raunin að ég er í vandræðum með, hvar byrja + End / 2

349
00:26:44,020 --> 00:26:46,820
er þáttur sem við erum að skoða.

350
00:26:46,820 --> 00:26:58,150
Við skulum segja að við höfðum þetta 10-þátturinn array. Whatever.

351
00:26:58,150 --> 00:27:03,250
Svo byrjar + endir / 2 er að fara að vera eitthvað eins og þessi,

352
00:27:03,250 --> 00:27:07,060
og ef það er ekki verðmæti, segjum við að uppfæra.

353
00:27:07,060 --> 00:27:10,060
Gildið er meiri, þannig að við viljum líta á þetta hluta fylkisins.

354
00:27:10,060 --> 00:27:15,910
Svo hvernig við erum að uppfæra byrja, við erum að uppfæra byrja að nú sé þetta þáttur.

355
00:27:15,910 --> 00:27:23,790
En þetta getur samt vinna, eða að minnsta kosti er hægt að byrja + endir / 2 + 1.

356
00:27:23,790 --> 00:27:27,850
[Nemandi] Þú þarft ekki að byrja + End [inaudible] >> Já.

357
00:27:27,850 --> 00:27:33,240
Við höfum þegar athugað þennan þátt og veit að það er ekki sá sem við erum að leita að.

358
00:27:33,240 --> 00:27:36,800
Þannig að við þurfum ekki að uppfæra byrja að vera svona þáttur.

359
00:27:36,800 --> 00:27:39,560
Við getum bara sleppt því og uppfæra byrja að vera svona þáttur.

360
00:27:39,560 --> 00:27:46,060
Og er það alltaf gott dæmi, við skulum segja, að þetta væri endir,

361
00:27:46,060 --> 00:27:53,140
svo þá byrja væri þetta, byrja + End / 2 væri þetta,

362
00:27:53,140 --> 00:28:00,580
byrja + End - Já, ég held að það getur endað í óendanlega endurkvæmni.

363
00:28:00,580 --> 00:28:12,690
Við skulum segja að það er bara fylki af stærð 2 eða fylki af stærð 1. Ég held að þetta muni virka.

364
00:28:12,690 --> 00:28:19,490
Svo nú, byrja að frumefni og enda er 1 utan það.

365
00:28:19,490 --> 00:28:24,110
Svo er þáttur sem við erum að fara að athuga þetta,

366
00:28:24,110 --> 00:28:29,400
og svo þegar við uppfærum byrja, við erum að uppfæra byrja að vera 0 + 1/2,

367
00:28:29,400 --> 00:28:33,160
sem er að fara að enda okkur aftur með því að vera að byrja á þessu atriði.

368
00:28:33,160 --> 00:28:36,210
>> Þannig að við erum að athuga sömu frumefni aftur og aftur.

369
00:28:36,210 --> 00:28:43,310
Svo er þetta málið þar sem hvert endurkvæma hringja þarf reyndar að uppfæra eitthvað.

370
00:28:43,310 --> 00:28:48,370
Þannig að við þurfum að byrja + End / 2 + 1, eða annað það er málið

371
00:28:48,370 --> 00:28:50,710
þar sem við erum í raun ekki að uppfæra byrjun.

372
00:28:50,710 --> 00:28:53,820
Allir sjá að?

373
00:28:53,820 --> 00:28:56,310
Allt í lagi.

374
00:28:56,310 --> 00:29:03,860
Hefur einhver hefur einhverjar spurningar um þessa lausn eða einhver fleiri athugasemdir?

375
00:29:05,220 --> 00:29:10,280
Allt í lagi. Hefur einhver hafa endurtekningu lausn sem við getum öll líta á?

376
00:29:17,400 --> 00:29:20,940
Gerði við gerum allt það undirmöppum?

377
00:29:20,940 --> 00:29:25,950
Eða líka að ég held ef þú opnað hennar, þá þú might hafa yfirkeyrt fyrri einn.

378
00:29:25,950 --> 00:29:28,810
Er það spara sjálfkrafa? Ég er ekki jákvæð.

379
00:29:35,090 --> 00:29:39,130
Hefur einhver hafa endurtekningu?

380
00:29:39,130 --> 00:29:42,430
Við getum gengið í gegnum það saman ef ekki.

381
00:29:46,080 --> 00:29:48,100
Hugmyndin er að fara til vera the sami.

382
00:30:00,260 --> 00:30:02,830
Endurtekningu lausn.

383
00:30:02,830 --> 00:30:07,140
Við erum að fara til að vilja grundvallaratriðum sömu hugmynd

384
00:30:07,140 --> 00:30:16,530
þar sem við viljum halda utan um nýju enda fylkisins og nýja byrjun í fylkinu

385
00:30:16,530 --> 00:30:18,510
og gera það aftur og aftur.

386
00:30:18,510 --> 00:30:22,430
Og ef það sem við erum að halda utan um eins og í upphafi og enda alltaf skerast,

387
00:30:22,430 --> 00:30:29,020
þá erum við ekki að finna hana og við getum aftur rangar.

388
00:30:29,020 --> 00:30:37,540
Svo hvernig á ég að gera það? Einhver hafa ábendingar eða kóða fyrir mig að draga upp?

389
00:30:42,190 --> 00:30:47,450
[Nemandi] Do a while lykkju. >> Já.

390
00:30:47,450 --> 00:30:49,450
Þú ert að fara til að vilja gera lykkju.

391
00:30:49,450 --> 00:30:51,830
>> Vissir þú hefur númerið ég gæti draga upp, eða hvað varstu að fara að stinga upp á?

392
00:30:51,830 --> 00:30:56,340
[Nemandi] Ég held það. >> Allt í lagi. Þetta gerir það auðveldara. Hvað var nafn þitt?

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

394
00:31:00,140 --> 00:31:04,190
Revision 1. Allt í lagi.

395
00:31:04,190 --> 00:31:13,200
Low er það sem við kallað byrja áður.

396
00:31:13,200 --> 00:31:17,080
Up er ekki alveg það sem við kallað enda áður.

397
00:31:17,080 --> 00:31:22,750
Reyndar, enda er nú innan fylkisins. Það er þáttur sem við ætti að íhuga.

398
00:31:22,750 --> 00:31:26,890
Svo lágt er 0, allt er the stærð af the array - 1,

399
00:31:26,890 --> 00:31:34,780
og nú erum við lykkja, og við erum að skoða -

400
00:31:34,780 --> 00:31:37,340
Ég giska á að þú getur gengið í gegnum það.

401
00:31:37,340 --> 00:31:41,420
Hver var að hugsa með þessu? Ganga okkur í gegnum kóðann þinn.

402
00:31:41,420 --> 00:31:49,940
[Nemandi] Jú. Horfðu á Haystack gildi í miðju og bera saman það til nál.

403
00:31:49,940 --> 00:31:58,520
Svo ef það er meira en nál, þá þú vilt - ó, í raun, það ætti að vera aftur á bak.

404
00:31:58,520 --> 00:32:05,180
Þú ert að fara til að vilja henda rétt hluta, og svo já, það ætti að vera leið.

405
00:32:05,180 --> 00:32:08,830
[Bowden] Þannig að þetta ætti að vera minna? Er það sem þú sagðir? >> [Nemandi] Já.

406
00:32:08,830 --> 00:32:10,390
[Bowden] lagi. Minna.

407
00:32:10,390 --> 00:32:15,700
Svo ef það sem við erum að horfa á er minni en það sem við viljum,

408
00:32:15,700 --> 00:32:19,410
þá já, viljum við henda vinstri hálfleik

409
00:32:19,410 --> 00:32:22,210
sem þýðir að við erum að uppfæra allt sem við erum að íhuga

410
00:32:22,210 --> 00:32:26,610
með því að færa lágmark til hægri fylkisins.

411
00:32:26,610 --> 00:32:30,130
Þetta lítur vel út.

412
00:32:30,130 --> 00:32:34,550
Ég held að það hafi sama mál sem við sögðum á undan,

413
00:32:34,550 --> 00:32:49,760
þar ef lítið er 0 og upp er 1, þá er lágmark + upp / 2 er að fara að setja upp til að vera það sama aftur.

414
00:32:49,760 --> 00:32:53,860
>> Og jafnvel ef það er ekki málið, það er enn skilvirkari minnsta kosti

415
00:32:53,860 --> 00:32:57,630
bara henda þáttur við litum bara á sem við vitum er rangt.

416
00:32:57,630 --> 00:33:03,240
Svo lág + upp / 2 + 1 - >> [nemandi] Það ætti að vera önnur leið.

417
00:33:03,240 --> 00:33:05,900
[Bowden] Eða það ætti að vera - 1 og hitt ætti að vera + 1.

418
00:33:05,900 --> 00:33:09,580
[Nemandi] Og það ætti að vera tvöfaldur jafn skilti. >> [Bowden] Já.

419
00:33:09,580 --> 00:33:11,340
[Nemandi] Já.

420
00:33:14,540 --> 00:33:15,910
Allt í lagi.

421
00:33:15,910 --> 00:33:21,280
Og að lokum, nú þegar við höfum þetta + 1 - 1 hlutur,

422
00:33:21,280 --> 00:33:31,520
er það - það gæti ekki verið - það er alltaf hægt að lágt til endir upp með a gildi sem er stærra en allt?

423
00:33:35,710 --> 00:33:40,320
Ég held að eina leiðin sem getur gerst - Er það mögulegt? >> [Nemandi] Ég veit ekki.

424
00:33:40,320 --> 00:33:45,220
En ef það gerist stytt og þá fær mínus að 1 og þá - >> Já.

425
00:33:45,220 --> 00:33:47,480
[Nemandi] Það myndi hugsanlega fá boðberi upp.

426
00:33:49,700 --> 00:33:53,940
Ég held að það ætti að vera góður bara af því

427
00:33:53,940 --> 00:33:58,800
fyrir það að enda minni að þeir myndu þurfa að vera jafnir, held ég.

428
00:33:58,800 --> 00:34:03,070
En ef þeir eru jafnir, þá myndum við ekki hafa gert meðan lykkja til að byrja með

429
00:34:03,070 --> 00:34:06,670
og við bara hefði aftur gildi. Þannig að ég held að við séum gott núna.

430
00:34:06,670 --> 00:34:11,530
Takið eftir að jafnvel þótt þetta vandamál er ekki lengur endurkvæma,

431
00:34:11,530 --> 00:34:17,400
sams konar hugmyndir um hvar við getum séð hvernig þetta svo auðveldlega lánar sig

432
00:34:17,400 --> 00:34:23,659
í endurkvæma lausn af því að við erum bara að uppfæra vísitölur aftur og aftur,

433
00:34:23,659 --> 00:34:29,960
við erum að gera vandamál minni og minni, við erum með áherslu á hlutmengi fylkisins.

434
00:34:29,960 --> 00:34:40,860
[Nemandi] Ef lágt er 0 og upp er 1, myndu þeir báðir vera 0 + 1/2, sem myndi fara til 0,

435
00:34:40,860 --> 00:34:44,429
og þá mætti ​​vera + 1, vildi einn vera - 1.

436
00:34:47,000 --> 00:34:50,870
[Nemandi] Hvar erum við að skoða jafnrétti?

437
00:34:50,870 --> 00:34:55,100
Eins ef miðju einn er í raun nál?

438
00:34:55,100 --> 00:34:58,590
Við erum ekki eins og að gera það? Oh!

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

440
00:35:05,340 --> 00:35:13,740
Já. Við getum ekki bara að gera prófið hérna því Segjum að fyrsta miðju -

441
00:35:13,740 --> 00:35:16,430
[Nemandi] Það er í raun ekki eins og henda bundið.

442
00:35:16,430 --> 00:35:20,220
Svo ef þú henda bundið, þú þarft að athuga það fyrst eða hvað.

443
00:35:20,220 --> 00:35:23,350
Ah. Já. >> [Nemandi] Já.

444
00:35:23,350 --> 00:35:29,650
Svo nú höfum við hent einn við litum nú á,

445
00:35:29,650 --> 00:35:33,260
sem þýðir að við þurfum nú að hafa einnig

446
00:35:33,260 --> 00:35:44,810
if (Haystack [(lítil + allt) / 2] == nál), þá getum við aftur satt.

447
00:35:44,810 --> 00:35:52,070
Og hvort ég setti annað eða bara ef það þýðir bókstaflega það sama

448
00:35:52,070 --> 00:35:57,110
vegna þess að þetta hefði skilað satt.

449
00:35:57,110 --> 00:36:01,450
Svo ég ætla að setja annað hvort, en það skiptir ekki máli.

450
00:36:01,450 --> 00:36:10,440
>> Svo annað ef þetta, annars þetta og þetta er algengt sem ég geri

451
00:36:10,440 --> 00:36:14,340
þar sem jafnvel ef það er raunin þar sem allt er gott hér,

452
00:36:14,340 --> 00:36:22,780
eins lágt getur aldrei verið meiri en allt, það er ekki þess virði að rök um það hvort það er satt.

453
00:36:22,780 --> 00:36:28,010
Svo þú getur svo að segja á meðan lítið er minna en eða jafnt og

454
00:36:28,010 --> 00:36:30,720
eða á meðan lágt er minni en

455
00:36:30,720 --> 00:36:35,300
svo gerist ef þeir eru alltaf jafn eða lágt til að fara upp,

456
00:36:35,300 --> 00:36:40,130
þá getum við brjótast út úr þessari lykkju.

457
00:36:41,410 --> 00:36:44,630
Spurningum, áhyggjur, athugasemdir?

458
00:36:47,080 --> 00:36:49,270
Allt í lagi. Þetta lítur vel út.

459
00:36:49,270 --> 00:36:52,230
Nú viljum við að gera svoleiðis.

460
00:36:52,230 --> 00:37:04,030
Ef við förum í seinni endurskoðun minn, sjáum við þessar sömu tölur,

461
00:37:04,030 --> 00:37:07,550
en nú eru þeir ekki lengur í raðað röð.

462
00:37:07,550 --> 00:37:12,840
Og við viljum að innleiða konar nota hvaða reiknirit í O í n log n.

463
00:37:12,840 --> 00:37:17,240
Svo sem reiknirit finnst þér að við ættum að innleiða hér? >> [Nemandi] Mergesort.

464
00:37:17,240 --> 00:37:23,810
[Bowden] Já. Mergesort er O (n log n), svo það er það sem við erum að fara að gera.

465
00:37:23,810 --> 00:37:26,680
Og vandamálið er að fara að vera mjög svipuð,

466
00:37:26,680 --> 00:37:31,920
þar sem það lánar auðveldlega sig við endurkvæma lausn.

467
00:37:31,920 --> 00:37:35,580
Við getum einnig að koma upp með endurtekningu lausn ef við viljum,

468
00:37:35,580 --> 00:37:42,540
en endurkvæmni verður auðveldara hér og við ættum að gera endurkvæmni.

469
00:37:45,120 --> 00:37:49,530
Ég held að við munum ganga í gegnum Mergesort fyrst,

470
00:37:49,530 --> 00:37:54,280
þó það er yndisleg vídeó á Mergesort þegar. [Hlátur]

471
00:37:54,280 --> 00:37:59,780
Svo Mergesort það eru - ég er að eyða svo mikið af þessum pappír.

472
00:37:59,780 --> 00:38:02,080
Ó, það er aðeins einn eftir.

473
00:38:02,080 --> 00:38:03,630
Svo sameinast.

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

475
00:38:26,090 --> 00:38:27,440
Allt í lagi.

476
00:38:29,910 --> 00:38:33,460
Merge tekur tvö aðskilin fylki.

477
00:38:33,460 --> 00:38:36,780
Sig þessi tvö fylki eru bæði flokkað.

478
00:38:36,780 --> 00:38:40,970
Þannig að þetta fylki, 1, 3, 5, raðað. Þessi fylki, 0, 2, 4, flokkað.

479
00:38:40,970 --> 00:38:46,710
Nú er það sameinast ætti að gera sameina þær í eina fylkingu sem er sjálf raðað.

480
00:38:46,710 --> 00:38:57,130
Þannig að við viljum á fjölbreytta stærð 6 sem er að fara að hafa þessi atriði inni í því

481
00:38:57,130 --> 00:38:59,390
í raðað röð.

482
00:38:59,390 --> 00:39:03,390
>> Og svo við getum nýta þá staðreynd að þessi tvö fylki eru flokkuð

483
00:39:03,390 --> 00:39:06,800
að gera þetta í línulegum tíma,

484
00:39:06,800 --> 00:39:13,510
línuleg sinn sem þýðir að ef þetta fylki er stærð x og þetta er stærð y,

485
00:39:13,510 --> 00:39:20,970
þá alls reiknirit að vera O (x + y). Allt í lagi.

486
00:39:20,970 --> 00:39:23,150
Svo tillögur.

487
00:39:23,150 --> 00:39:26,030
[Nemandi] Gat við byrjum frá vinstri?

488
00:39:26,030 --> 00:39:30,150
Svo þú munt setja 0 niður fyrst og síðan 1 og þá hér þú ert á 2.

489
00:39:30,150 --> 00:39:33,320
Svo það er góður af eins og þú hafa a flipi sem er að flytja til hægri. >> [Bowden] Já.

490
00:39:33,320 --> 00:39:41,070
Fyrir bæði þessi fylki ef við einbeitum okkur bara á lengst frumefni.

491
00:39:41,070 --> 00:39:43,530
Vegna bæði fylki eru flokkuð, vitum við að þessir 2 þættir

492
00:39:43,530 --> 00:39:46,920
eru minnstu einingar í hvoru fylki.

493
00:39:46,920 --> 00:39:53,500
Svo þýðir að 1 af þessum 2 þáttum verður að vera minnsti þáttur í sameinaða fylking okkar.

494
00:39:53,500 --> 00:39:58,190
Það bara gerist þannig að minnsti er einn á hægri og er.

495
00:39:58,190 --> 00:40:02,580
Svo við tökum 0, setja það á vinstri því 0 er minna en 1,

496
00:40:02,580 --> 00:40:08,210
þannig að 0, setja það inn í efstu stöðu okkar, og þá erum við að uppfæra þetta

497
00:40:08,210 --> 00:40:12,070
að nú áherslu á fyrstu frumefni.

498
00:40:12,070 --> 00:40:14,570
Og nú erum við að endurtaka.

499
00:40:14,570 --> 00:40:20,670
Svo nú erum við að bera saman 2 og 1. 1 er minni, þannig að við munum setja inn 1.

500
00:40:20,670 --> 00:40:25,300
Við uppfæra músina til að benda á þennan gaur.

501
00:40:25,300 --> 00:40:33,160
Nú erum við að gera það aftur, svo 2. Þetta mun uppfæra og bera saman þessar 2, 3.

502
00:40:33,160 --> 00:40:37,770
Þetta uppfærslur, síðan 4 og 5.

503
00:40:37,770 --> 00:40:42,110
Svo er að sameinast.

504
00:40:42,110 --> 00:40:49,010
>> Það ætti að vera nokkuð augljóst að það er línuleg tími þar sem við förum bara yfir hvert frumefni einu.

505
00:40:49,010 --> 00:40:55,980
Og það er stærsta skrefið til að innleiða Mergesort er að gera þetta.

506
00:40:55,980 --> 00:40:59,330
Og það er ekki það erfitt.

507
00:40:59,330 --> 00:41:15,020
Tveimur atriði til að hafa áhyggjur óður í er við skulum segja að við vorum að sameina 1, 2, 3, 4, 5, 6.

508
00:41:15,020 --> 00:41:30,930
Í þessu tilfelli erum við að enda í atburðarás þar sem þetta er að fara að vera minni,

509
00:41:30,930 --> 00:41:36,160
þá erum við að uppfæra músina, þetta er að fara að vera minni, uppfæra þetta,

510
00:41:36,160 --> 00:41:41,280
þetta er minni, og nú þú ert að viðurkenna

511
00:41:41,280 --> 00:41:44,220
þegar þú hefur keyrt í raun út af þáttum til að bera saman við.

512
00:41:44,220 --> 00:41:49,400
Þar sem við höfum nú þegar að nota þetta allt array,

513
00:41:49,400 --> 00:41:55,190
allt í þessu fylki er nú bara sett inn hér.

514
00:41:55,190 --> 00:42:02,040
Þannig að ef við hlaupa alltaf í stað þar sem eitt fylki okkar er alveg sameinast nú þegar,

515
00:42:02,040 --> 00:42:06,510
þá erum við að taka bara alla þætti hins array og setja þá í lok fylkisins.

516
00:42:06,510 --> 00:42:13,630
Þannig að við getum bara setja 4, 5, 6. Allt í lagi.

517
00:42:13,630 --> 00:42:18,070
Það er eitt að horfa út fyrir.

518
00:42:22,080 --> 00:42:26,120
Framkvæmd sem ætti að vera skref 1.

519
00:42:26,120 --> 00:42:32,600
Sameina raða þá byggt á því, er það 2 skref, 2 kjánalegt skref.

520
00:42:38,800 --> 00:42:42,090
Við skulum gefa bara þetta fylki.

521
00:42:57,920 --> 00:43:05,680
Svo Mergesort, skref 1 er að endurkvæmt brjóta fylki í helminga.

522
00:43:05,680 --> 00:43:09,350
Svo skipta þessu fylki í helminga.

523
00:43:09,350 --> 00:43:22,920
Við höfum nú 4, 15, 16, 50 og 8, 23, 42, 108.

524
00:43:22,920 --> 00:43:25,800
Og nú erum við að gera það aftur og við hættu þessir í helminga.

525
00:43:25,800 --> 00:43:27,530
Ég ætla bara að gera það á þessari hlið.

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

527
00:43:34,790 --> 00:43:37,440
Við viljum gera það sama hérna.

528
00:43:37,440 --> 00:43:40,340
Og nú erum við skipt því í helminga aftur.

529
00:43:40,340 --> 00:43:51,080
Og við höfum 4, 15, 16, 50.

530
00:43:51,080 --> 00:43:53,170
Svo er þessi stöð mál okkar.

531
00:43:53,170 --> 00:44:00,540
Þegar fylki eru stærð 1, þá erum við að hætta við að skipta í helminga.

532
00:44:00,540 --> 00:44:03,190
>> Nú hvað gerum við við þetta?

533
00:44:03,190 --> 00:44:15,730
Við á endanum mun þetta einnig brjóta niður í 8, 23, 42, og 108.

534
00:44:15,730 --> 00:44:24,000
Svo nú er að við erum á þessum tímapunkti, nú stíga tveir Mergesort er bara að sameina pör á listum.

535
00:44:24,000 --> 00:44:27,610
Þannig að við viljum að sameina þá. Við köllum bara steypa.

536
00:44:27,610 --> 00:44:31,410
Við vitum sameinast aftur þetta í raðað röð.

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

538
00:44:33,920 --> 00:44:41,440
Nú viljum við að sameina þetta, og það mun skila lista með þeim í raðað röð,

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

540
00:44:44,160 --> 00:44:57,380
Við sameina þá - ég get ekki skrifað - 8, 23 og 42, 108.

541
00:44:57,380 --> 00:45:02,890
Þannig að við höfum sameinað par einu sinni.

542
00:45:02,890 --> 00:45:05,140
Nú erum við að sameinast bara aftur.

543
00:45:05,140 --> 00:45:10,130
Takið eftir því hver af þessum listum er raðað í sjálfu sér,

544
00:45:10,130 --> 00:45:15,220
og þá getum við bara sameinast þessum listum til að fá lista af stærð 4, sem er raðað

545
00:45:15,220 --> 00:45:19,990
og sameina þessa tvo lista til að fá lista af stærð 4 það er flokkað.

546
00:45:19,990 --> 00:45:25,710
Og að lokum, getum við sameinast þessir tveir listar stærð 4 til fá einn lista yfir stærð 8 sem er raðað.

547
00:45:25,710 --> 00:45:34,030
Svo til að sjá að þetta er almennt N log n, sáum við þegar það sameinast er línuleg,

548
00:45:34,030 --> 00:45:40,390
svo þegar við erum að fást við sameiningu, svo eins og heildarkostnað af sameiningu

549
00:45:40,390 --> 00:45:43,410
fyrir þessar tvær lista er bara 2 af því -

550
00:45:43,410 --> 00:45:49,610
Eða vel, það er O n, en N hér er bara þessir 2 þættir, svo það er 2.

551
00:45:49,610 --> 00:45:52,850
Og þessir 2 verða 2 og þessir 2 verða 2 og þessir 2 verða 2,

552
00:45:52,850 --> 00:45:58,820
svo yfir öll sameinast um að við þurfum að gera, enda við upp að gera n.

553
00:45:58,820 --> 00:46:03,210
Eins og 2 + 2 + 2 + 2 er 8, sem er n,

554
00:46:03,210 --> 00:46:08,060
þannig að kostnaður við sameiningu í þessu mengi er n.

555
00:46:08,060 --> 00:46:10,810
Og þá það sama hér.

556
00:46:10,810 --> 00:46:16,980
Við munum sameina þá 2, þá eru þessir 2, og sérstaklega þetta sameinast mun taka fjórar aðgerðir,

557
00:46:16,980 --> 00:46:23,610
þetta sameinast mun taka fjórar aðgerðir, en enn og aftur, milli allra þeirra,

558
00:46:23,610 --> 00:46:29,030
við á endanum sameina N samtals hlutir, og svo tekur þetta skref n.

559
00:46:29,030 --> 00:46:33,670
Og svo tekur hvert stig n þætti verið sameinuð.

560
00:46:33,670 --> 00:46:36,110
>> Og hve mörg borð eru?

561
00:46:36,110 --> 00:46:40,160
Á hverju stigi, array okkar vex með stærð 2.

562
00:46:40,160 --> 00:46:44,590
Hér fylki okkar eru stærð 1, hér að þeir eru í stærð 2, hér að þeir eru í stærð 4,

563
00:46:44,590 --> 00:46:46,470
og að lokum, þá eru þeir í stærð 8.

564
00:46:46,470 --> 00:46:56,450
Svo þar sem það er tvöföldun, eru að fara að vera alls log n af þessum liðum.

565
00:46:56,450 --> 00:47:02,090
Svo með log n stig, hvert stig að taka N samtals starfsemi,

566
00:47:02,090 --> 00:47:05,720
fáum við n log n reiknirit.

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

568
00:47:08,940 --> 00:47:13,320
Hefur fólk gert þegar framfarir á hvernig á að framkvæma þetta?

569
00:47:13,320 --> 00:47:18,260
Er einhver sem þegar í ríki þar sem ég get bara draga upp kóðann þeirra?

570
00:47:20,320 --> 00:47:22,260
Ég get gefið eina mínútu.

571
00:47:24,770 --> 00:47:27,470
Þetta er að fara að vera lengur.

572
00:47:27,470 --> 00:47:28,730
Ég mæli aftur fram -

573
00:47:28,730 --> 00:47:30,510
Þú þarft ekki að gera endurkvæmni fyrir sameiningu

574
00:47:30,510 --> 00:47:33,750
því að gera endurkvæmni fyrir sameiningu, ætlar þú að fara til verða að standast fullt af mismunandi stærðum.

575
00:47:33,750 --> 00:47:37,150
Þú getur, en það er pirrandi.

576
00:47:37,150 --> 00:47:43,720
En endurkvæmni fyrir tegund sjálft er laglegur þægilegur.

577
00:47:43,720 --> 00:47:49,190
Þú bara bókstaflega kalla svoleiðis á vinstri helmingi, flokka á hægri hluta. Allt í lagi.

578
00:47:51,770 --> 00:47:54,860
Einhver hefur eitthvað sem ég get draga upp enn?

579
00:47:54,860 --> 00:47:57,540
Eða annað sem ég ætla að gefa eina mínútu.

580
00:47:58,210 --> 00:47:59,900
Allt í lagi.

581
00:47:59,900 --> 00:48:02,970
Einhver með eitthvað sem við getum að vinna með?

582
00:48:05,450 --> 00:48:09,680
Eða annað sem við verðum bara að vinna við þetta og þá þenja út þaðan.

583
00:48:09,680 --> 00:48:14,050
>> Einhver hafa meira en þetta sem ég get draga upp?

584
00:48:14,050 --> 00:48:17,770
[Nemandi] Já. Þú getur draga upp minn. >> Allt í lagi.

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

586
00:48:22,170 --> 00:48:25,280
[Nemandi] Það voru fullt skilyrði. >> Ó, skjóta. Getur þú -

587
00:48:25,280 --> 00:48:28,110
[Nemandi] Ég verð að vista hana. >> Já.

588
00:48:32,420 --> 00:48:35,730
Þannig að við gerðum ekki sameiningu sérstaklega.

589
00:48:35,730 --> 00:48:38,570
Ó, en það er ekki svo slæmt.

590
00:48:39,790 --> 00:48:41,650
Allt í lagi.

591
00:48:41,650 --> 00:48:47,080
Svo er tegund sig bara að hringja mergeSortHelp.

592
00:48:47,080 --> 00:48:49,530
Útskýrðu fyrir okkur hvað mergeSortHelp gerir.

593
00:48:49,530 --> 00:48:55,700
[Nemandi] MergeSortHelp ansi er mikill tvo liði,

594
00:48:55,700 --> 00:49:01,270
sem er að raða hverjum helming fylkisins og síðan að sameina bæði.

595
00:49:04,960 --> 00:49:08,050
[Bowden] Jæja, svo gefa mér annað.

596
00:49:10,850 --> 00:49:13,210
Ég held að þetta - >> [nemandi] ég þarf að -

597
00:49:17,100 --> 00:49:19,400
Já. Ég vantar eitthvað.

598
00:49:19,400 --> 00:49:23,100
Í sameiningu, við gerum ég að ég þarf að búa til nýtt array

599
00:49:23,100 --> 00:49:26,530
vegna þess að ég gat ekki gert það í stað. >> Já. Þú getur ekki. Rétt.

600
00:49:26,530 --> 00:49:28,170
[Nemandi] Svo ég að búa til nýtt array.

601
00:49:28,170 --> 00:49:31,510
Ég gleymdi í lok sameinast við aftur breyta.

602
00:49:31,510 --> 00:49:34,490
Allt í lagi. Við þurfum nýtt fylki.

603
00:49:34,490 --> 00:49:41,000
Í Mergesort, þetta er næstum alltaf satt.

604
00:49:41,000 --> 00:49:44,340
Hluti af kostnaði við betri reiknirit tíma-vitur

605
00:49:44,340 --> 00:49:47,310
er nánast alltaf þurfa að nota aðeins meira minni.

606
00:49:47,310 --> 00:49:51,570
Svo hér, sama hvernig þú sameina konar,

607
00:49:51,570 --> 00:49:54,780
þú myndi óhjákvæmilega þurfa að nota nokkrar auka minni.

608
00:49:54,780 --> 00:49:58,240
Hann eða hún skapaði nýja fylki.

609
00:49:58,240 --> 00:50:03,400
Og þá segir þú í lok við þurfum bara að afrita nýtt array í upprunalegu fylkisins.

610
00:50:03,400 --> 00:50:04,830
[Nemandi] Ég held það, já.

611
00:50:04,830 --> 00:50:08,210
Ég veit ekki hvort það virkar í skilmálar af að telja með tilvísun eða hvað -

612
00:50:08,210 --> 00:50:11,650
Já, það mun virka. >> [Nemandi] lagi.

613
00:50:20,620 --> 00:50:24,480
Vissir þú reynir að keyra þetta? >> [Nemandi] Nei, ekki enn. >> Lagi.

614
00:50:24,480 --> 00:50:28,880
Prófaðu að keyra það, og svo skal ég tala um það fyrir a second.

615
00:50:28,880 --> 00:50:35,200
[Nemandi] Ég þarf að hafa alla virka frumútgáfur og allt, þó, ekki satt?

616
00:50:37,640 --> 00:50:40,840
The virka frumútgáfur. Ó, að þú eins - Já.

617
00:50:40,840 --> 00:50:43,040
Raða kallar mergeSortHelp.

618
00:50:43,040 --> 00:50:47,390
>> Svo í röð til að raða að hringja mergeSortHelp verður mergeSortHelp annaðhvort hafa verið skilgreind

619
00:50:47,390 --> 00:50:56,370
fyrir tegund eða þurfum við bara frumgerð. Bara afrita og líma það.

620
00:50:56,370 --> 00:50:59,490
Og sömuleiðis, mergeSortHelp kallar sameinast

621
00:50:59,490 --> 00:51:03,830
en sameinast hefur ekki verið skilgreint enn, svo að við getum bara látið mergeSortHelp vita

622
00:51:03,830 --> 00:51:08,700
að það er það sem sameinast er að fara að líta út eins og það er það.

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

624
00:51:22,770 --> 00:51:32,660
Við höfum málefni hér þar sem við höfum ekki grunn tilfelli.

625
00:51:32,660 --> 00:51:38,110
MergeSortHelp er endurkvæma, svo allir endurkvæma virka

626
00:51:38,110 --> 00:51:42,610
er að fara að þurfa einhvers konar tilfelli stöð til að vita hvenær á að hætta endurkvæmt kalla sig.

627
00:51:42,610 --> 00:51:45,590
Hvað er undirstaða okkar tilviki að fara að vera hér? Já.

628
00:51:45,590 --> 00:51:49,110
[Nemandi] Ef stærð er 1? >> [Bowden] Já.

629
00:51:49,110 --> 00:51:56,220
Svo eins og við sáum þarna, hætt við skerandi fylki

630
00:51:56,220 --> 00:52:01,850
þegar við fengum inn fylki af stærð 1, sem óhjákvæmilega eru flokkuð sig.

631
00:52:01,850 --> 00:52:09,530
Svo ef stærð er 1, vitum við fylki er þegar raðað,

632
00:52:09,530 --> 00:52:12,970
þannig að við getum bara aftur.

633
00:52:12,970 --> 00:52:16,880
>> Takið eftir það er tóm, svo að við ekki aftur neitt sérstaklega, aftur við bara.

634
00:52:16,880 --> 00:52:19,580
Allt í lagi. Svo það er undirstaða okkar tilviki.

635
00:52:19,580 --> 00:52:27,440
Ég held að byggja mál okkar gæti líka verið ef við gerast að sameina óákveðinn greinir í ensku fylking af stærð 0,

636
00:52:27,440 --> 00:52:30,030
við viljum líklega að hætta á einhverjum tímapunkti,

637
00:52:30,030 --> 00:52:33,610
þannig að við getum bara sagt stærð minna en 2 eða minna en eða jafnt og 1

638
00:52:33,610 --> 00:52:37,150
þannig að þetta mun virka fyrir hvaða fylking nú.

639
00:52:37,150 --> 00:52:38,870
Allt í lagi.

640
00:52:38,870 --> 00:52:42,740
Svo það er undirstaða okkar tilviki.

641
00:52:42,740 --> 00:52:45,950
Nú þú vilt að ganga okkur í gegnum sameiningu?

642
00:52:45,950 --> 00:52:49,140
Hvað öll þessi tilfelli þýða?

643
00:52:49,140 --> 00:52:54,480
Up hér, við erum bara að gera sömu hugmynd, að -

644
00:52:56,970 --> 00:53:02,470
[Nemandi] Ég þarf að brottför stærð með öllum mergeSortHelp símtöl.

645
00:53:02,470 --> 00:53:10,080
Ég bætti stærð sem viðbótar aðal og það er ekki þar, eins og stærð / 2.

646
00:53:10,080 --> 00:53:16,210
[Bowden] Ó, stærð / 2, stærð / 2. >> [Nemandi] Já, og einnig í ofangreindum virka eins og heilbrigður.

647
00:53:16,210 --> 00:53:21,320
[Bowden] Hér? >> [Nemandi] Bara stærð. >> [Bowden] Ó. Stærð, stærð? >> [Nemandi] Já.

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

649
00:53:23,010 --> 00:53:26,580
Leyfðu mér að hugsa um annað.

650
00:53:26,580 --> 00:53:28,780
Eigum við að keyra inn í málið?

651
00:53:28,780 --> 00:53:33,690
Við erum alltaf að meðhöndla vinstri sem 0. >> [Nemandi] Nei

652
00:53:33,690 --> 00:53:36,340
Það er rangt líka. Því miður. Það ætti að vera upphafið. Já.

653
00:53:36,340 --> 00:53:39,230
[Bowden] lagi. Mér finnst það betra.

654
00:53:39,230 --> 00:53:43,880
Og enda. Allt í lagi.

655
00:53:43,880 --> 00:53:47,200
Svo nú þú vilt að ganga okkur í gegnum sameiningu? >> [Nemandi] lagi.

656
00:53:47,200 --> 00:53:52,150
Ég er bara að ganga í gegnum þetta nýja fylkingu sem ég hef búið til.

657
00:53:52,150 --> 00:53:57,420
Stærð hennar er á stærð við hluta fylkisins sem við viljum að vera flokkaður

658
00:53:57,420 --> 00:54:03,460
og reyna að finna hluti sem ég ætti að setja í nýju array skref.

659
00:54:03,460 --> 00:54:10,140
Svo til að gera það, fyrst ég er að athuga hvort að vinstri helmingur í fylkinu heldur áfram að hafa neitt fleiri þætti,

660
00:54:10,140 --> 00:54:14,260
og ef það virkar ekki, þá fara niður til að annað ástand, sem bara segir

661
00:54:14,260 --> 00:54:20,180
allt í lagi, það verður að vera í rétta fylking, og við munum setja það í núverandi vísitölu newArray.

662
00:54:20,180 --> 00:54:27,620
>> Og svo annað, ég er að athuga hvort hægra megin í fylkinu er einnig lokið,

663
00:54:27,620 --> 00:54:30,630
þar sem ef ég setti bara í vinstri.

664
00:54:30,630 --> 00:54:34,180
Það gæti í raun ekki verið nauðsynlegt. Ég er ekki viss.

665
00:54:34,180 --> 00:54:40,970
En engu að síður, eru hinir tveir stöðva hvaða tvær minni í vinstri eða hægri.

666
00:54:40,970 --> 00:54:49,770
Og einnig í hverju tilfelli, ég incrementing hvort tákn ég hækka.

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

668
00:54:52,040 --> 00:54:53,840
Það lítur vel út.

669
00:54:53,840 --> 00:54:58,800
Hefur einhver hafa athugasemdir eða áhyggjur eða spurningar?

670
00:55:00,660 --> 00:55:07,720
Svo fjórum tilvikum sem við höfum til að koma hlutum í bara að vera - eða það lítur út eins og fimm -

671
00:55:07,720 --> 00:55:13,100
en við verðum að íhuga hvort vinstri array hefur keyrt út af hlutum sem við þurfum að sameinast,

672
00:55:13,100 --> 00:55:16,390
hvort rétt array hefur keyrt út af hlutum sem við þurfum að sameinast -

673
00:55:16,390 --> 00:55:18,400
Ég er að benda á neitt.

674
00:55:18,400 --> 00:55:21,730
Svo hvort vinstri array hefur keyrt út af hlutum eða rétt array hefur keyrt út af hlutum.

675
00:55:21,730 --> 00:55:24,320
Þeir eru tvö tilvik.

676
00:55:24,320 --> 00:55:30,920
Við þurfum einnig léttvæg ræða hvort vinstri sem er minna en the réttur hlutur.

677
00:55:30,920 --> 00:55:33,910
Þá viljum við að velja vinstri hlutur.

678
00:55:33,910 --> 00:55:37,630
Þeir eru dæmi.

679
00:55:37,630 --> 00:55:40,990
Svo þetta var rétt, svo það er það.

680
00:55:40,990 --> 00:55:46,760
Array vinstri. Það er 1, 2, 3. Allt í lagi. Svo já, eru þeir fjórir hlutir sem við gætum vilja til að gera.

681
00:55:50,350 --> 00:55:54,510
Og við munum ekki fara yfir endurtekningu lausn.

682
00:55:54,510 --> 00:55:55,980
Ég myndi ekki mæla með -

683
00:55:55,980 --> 00:56:03,070
Mergesort er dæmi um fall sem er bæði ekki hali endurkvæma,

684
00:56:03,070 --> 00:56:07,040
það er ekki auðvelt að gera það hali endurkvæma,

685
00:56:07,040 --> 00:56:13,450
en einnig er það ekki mjög auðvelt að gera það endurtekningu.

686
00:56:13,450 --> 00:56:16,910
Þetta er mjög auðvelt.

687
00:56:16,910 --> 00:56:19,170
Þessi framkvæmd Mergesort,

688
00:56:19,170 --> 00:56:22,140
sameinast, það er sama hvað þú gerir, þú ert að fara að byggja sameinast.

689
00:56:22,140 --> 00:56:29,170
>> Svo Mergesort byggt ofan á sameiningu endurkvæmt er bara þessar þrjár línur.

690
00:56:29,170 --> 00:56:34,700
Iteratively er það meira pirrandi og erfiðara að hugsa um.

691
00:56:34,700 --> 00:56:41,860
En eftir að það er ekki hali endurkvæma síðan mergeSortHelp - þegar það kallar sig -

692
00:56:41,860 --> 00:56:46,590
það þarf samt að gera það eftir þetta endurkvæma skilar hringja.

693
00:56:46,590 --> 00:56:50,830
Þannig að þetta stafla ramma verður að halda áfram að vera til jafnvel eftir að kalla þetta.

694
00:56:50,830 --> 00:56:54,170
Og svo þegar þú kallar þetta, stafla ramma verður að halda áfram að vera til

695
00:56:54,170 --> 00:56:57,780
því jafnvel eftir að hringja, þurfum við enn að sameinast.

696
00:56:57,780 --> 00:57:01,920
Og það er nontrivial að þetta hali endurkvæma.

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

698
00:57:08,300 --> 00:57:09,860
Allt í lagi.

699
00:57:09,860 --> 00:57:13,400
Svo að fara til baka til að flokka - ó, það er tvennt sem ég vil sýna. Allt í lagi.

700
00:57:13,400 --> 00:57:17,840
Fara aftur til að flokka, við munum gera það fljótt.

701
00:57:17,840 --> 00:57:21,030
Eða leita. Raða? Tagi. Já.

702
00:57:21,030 --> 00:57:22,730
Fara aftur til upphaf tagi.

703
00:57:22,730 --> 00:57:29,870
Við viljum búa til reiknirit sem flokkar fylki með hvaða reiknirit

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

705
00:57:33,660 --> 00:57:40,860
Svo hvernig er þetta hægt? Hefur einhver hefur einhverjar tegund af -

706
00:57:40,860 --> 00:57:44,300
Ég gefið í skyn áður á -

707
00:57:44,300 --> 00:57:48,300
Ef við erum að fara að bæta úr n log n O á n,

708
00:57:48,300 --> 00:57:51,450
Við höfum bætt reiknirit okkar tími-vitur,

709
00:57:51,450 --> 00:57:55,250
sem þýðir hvað við erum að fara að þurfa að gera til að bæta upp fyrir það?

710
00:57:55,250 --> 00:57:59,520
[Nemandi] Space. >> Já. Við ætlum að vera með meira pláss.

711
00:57:59,520 --> 00:58:04,490
Og ekki einu sinni bara meira pláss, það veldishraða meira pláss.

712
00:58:04,490 --> 00:58:14,320
Þannig að ég held að þessi tegund af reiknirit er falsaður eitthvað gervi polynom -

713
00:58:14,320 --> 00:58:18,980
gervi - Ég man það ekki. Gervi eitthvað.

714
00:58:18,980 --> 00:58:22,210
En það er vegna þess að við þurfum að nota svo mikið pláss

715
00:58:22,210 --> 00:58:28,610
að þetta sé náð en ekki raunhæf.

716
00:58:28,610 --> 00:58:31,220
>> Og hvernig ná við þetta?

717
00:58:31,220 --> 00:58:36,810
Við getum ná þessu ef við tryggjum að allir einkum þáttur í fylkinu

718
00:58:36,810 --> 00:58:39,600
er undir ákveðinni stærð.

719
00:58:42,070 --> 00:58:44,500
Svo við skulum bara segja að stærð er 200,

720
00:58:44,500 --> 00:58:48,130
hvaða þáttur í fylki er undir stærð 200.

721
00:58:48,130 --> 00:58:51,080
Og þetta er í raun mjög raunhæf.

722
00:58:51,080 --> 00:58:58,660
Þú getur mjög auðveldlega hafa fylki sem þú veist allt í það

723
00:58:58,660 --> 00:59:00,570
er að fara að vera minna en sumir tala.

724
00:59:00,570 --> 00:59:07,400
Eins ef þið hafið einhverjar algerlega gegnheill vektor eða eitthvað

725
00:59:07,400 --> 00:59:11,810
en þú veist allt er að fara að vera á milli 0 og 5,

726
00:59:11,810 --> 00:59:14,790
þá er það að fara að vera verulega hraðar til að gera þetta.

727
00:59:14,790 --> 00:59:17,930
Og bundið um einhver þeirra atriða er 5,

728
00:59:17,930 --> 00:59:21,980
þannig að þetta bundið, það er hversu mikið minni þú ert að fara að nota.

729
00:59:21,980 --> 00:59:26,300
Svo er bundið 200.

730
00:59:26,300 --> 00:59:32,960
Fræðilega er alltaf bundið þar heiltala getur aðeins verið allt að 4 milljarða króna,

731
00:59:32,960 --> 00:59:40,600
en það er óraunhæft síðan við myndum vera með rúm

732
00:59:40,600 --> 00:59:44,400
á röð 4 milljörðum króna. Svo er það óraunhæft.

733
00:59:44,400 --> 00:59:47,060
En hér munum við segja bundið okkar er 200.

734
00:59:47,060 --> 00:59:59,570
The bragð til að gera það í O á n við að gera annað fylki kallast telja stærð bundinn.

735
00:59:59,570 --> 01:00:10,470
Svo í raun, þetta er flýtileið fyrir - ég reyndar veit ekki hvort Clang gerir þetta.

736
01:00:11,150 --> 01:00:15,330
En í GCC minnsta kosti - Ég er miðað Clang gerir það líka -

737
01:00:15,330 --> 01:00:18,180
þetta mun bara frumstilla alla array að vera 0s.

738
01:00:18,180 --> 01:00:25,320
Svo ef ég vil ekki að gera það, þá gæti ég sérstaklega gert fyrir (int i = 0;

739
01:00:25,320 --> 01:00:31,500
i <bundið, i + +) og telja [i] = 0;

740
01:00:31,500 --> 01:00:35,260
Svo nú er allt frumstilla í 0.

741
01:00:35,260 --> 01:00:39,570
Ég iterate yfir fylking minn,

742
01:00:39,570 --> 01:00:51,920
og hvað ég er að gera er að ég er að telja fjölda hvers - Við skulum fara niður hér.

743
01:00:51,920 --> 01:00:55,480
Við höfum 4, 15, 16, 50, 8, 23, 42, 108.

744
01:00:55,480 --> 01:01:00,010
Það sem ég er að telja er fjöldi atvika af hverjum þessara þátta.

745
01:01:00,010 --> 01:01:03,470
Skulum raunverulega bæta nokkrum fleiri hér með nokkrum endurtekningar.

746
01:01:03,470 --> 01:01:11,070
Þannig að verðmæti við höfum hér, gildi sem er að fara að vera array [i].

747
01:01:11,070 --> 01:01:14,850
Svo Val gæti verið 4 eða 8 eða hvað sem er.

748
01:01:14,850 --> 01:01:18,870
Og núna er ég að telja hversu margir af þeim gildi sem ég hef séð,

749
01:01:18,870 --> 01:01:21,230
svo telja [Val] + +;

750
01:01:21,230 --> 01:01:29,430
Eftir það er gert, gildir er að fara að líta eitthvað eins og 0001.

751
01:01:29,430 --> 01:01:42,190
Gerum telja [Val] - bundinn + 1.

752
01:01:42,190 --> 01:01:48,230
>> Nú er það bara að gera grein fyrir því að við erum að byrja frá 0.

753
01:01:48,230 --> 01:01:50,850
Svo ef 200 er að fara að vera stærsta númerið okkar,

754
01:01:50,850 --> 01:01:54,720
þá er 0-200 201 hlutir.

755
01:01:54,720 --> 01:02:01,540
Svo telja, mun það líta út eins og 00.001 því við höfum eitt 4.

756
01:02:01,540 --> 01:02:10,210
Síðan munum við hafa 0001 þar sem við munum hafa 1 í 8. vísitölu telja.

757
01:02:10,210 --> 01:02:14,560
Við munum hafa 2 í 23 vísitölu telja.

758
01:02:14,560 --> 01:02:17,630
Við munum hafa 2 í 42 vísitölu telja.

759
01:02:17,630 --> 01:02:21,670
Svo getum við notað telja.

760
01:02:34,270 --> 01:02:44,920
Svo num_of_item = máli [i].

761
01:02:44,920 --> 01:02:52,540
Og svo ef num_of_item er 2, sem þýðir að við viljum að setja 2 í fjölda i

762
01:02:52,540 --> 01:02:55,290
í raðað array okkar.

763
01:02:55,290 --> 01:03:02,000
Þannig að við þurfum að halda utan um hversu langt við erum í array.

764
01:03:02,000 --> 01:03:05,470
Svo vísitölu = 0.

765
01:03:05,470 --> 01:03:09,910
Array - Ég verð bara að skrifa það.

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

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

768
01:03:28,580 --> 01:03:32,490
Er það það sem ég vil? Ég held að það er það sem ég vil.

769
01:03:35,100 --> 01:03:38,290
Já, þetta lítur vel út. Allt í lagi.

770
01:03:38,290 --> 01:03:43,050
Svo er allir skilja hvað varðar telja fylki minn er?

771
01:03:43,050 --> 01:03:48,140
Það er að telja fjölda atvika af öllum þessum tölum.

772
01:03:48,140 --> 01:03:51,780
Og ég er iterating á að telja fjölda,

773
01:03:51,780 --> 01:03:57,190
og ith stöðu á telja fylki

774
01:03:57,190 --> 01:04:01,930
er fjöldi i er sem ætti að birtast í raðað array mínu.

775
01:04:01,930 --> 01:04:06,840
Þess vegna telja 4 er að fara að vera 1

776
01:04:06,840 --> 01:04:11,840
og telja 8 er að fara að vera 1, telja 23 er að fara að vera 2.

777
01:04:11,840 --> 01:04:16,900
Svo er það hversu margir af þeim sem ég vil setja inn raðað array minn.

778
01:04:16,900 --> 01:04:19,200
Og ég bara það.

779
01:04:19,200 --> 01:04:28,960
Ég er að setja num_of_item ég er í raðað array minn.

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

781
01:04:32,460 --> 01:04:43,100
Og svo aftur, þetta er línuleg tími þar sem við erum bara að iterating yfir þetta einu sinni,

782
01:04:43,100 --> 01:04:47,470
en það er líka línuleg í hvað þessi tala verður að vera,

783
01:04:47,470 --> 01:04:50,730
og svo fer það að miklu leyti á því sem bundið er.

784
01:04:50,730 --> 01:04:53,290
Með bundið af 200, sem er ekki svo slæmt.

785
01:04:53,290 --> 01:04:58,330
Ef bundið er að fara að vera 10.000, þá er það aðeins verra,

786
01:04:58,330 --> 01:05:01,360
en ef bundið er að fara að vera 4 milljarðar það er alveg óraunhæft

787
01:05:01,360 --> 01:05:07,720
og þetta fylki er að fara til verða að vera af stærð 4 milljarða, sem er óraunhæft.

788
01:05:07,720 --> 01:05:10,860
Svo er það það. Spurningar?

789
01:05:10,860 --> 01:05:13,270
[Inaudible nemandi svar] >> lagi.

790
01:05:13,270 --> 01:05:15,710
Ég áttaði mig á eitt annað hlutur þegar við vorum að fara í gegnum.

791
01:05:17,980 --> 01:05:23,720
Ég held að vandamálið var í er Lucas og sennilega hvert einasta sem við höfum séð.

792
01:05:23,720 --> 01:05:26,330
Ég gleymdi alveg.

793
01:05:26,330 --> 01:05:31,040
Það eina sem ég vildi gera athugasemd við er að þegar þú ert að takast á við hluti eins og vísitalna,

794
01:05:31,040 --> 01:05:38,320
þú aldrei raunverulega séð þetta þegar þú ert að skrifa a for lykkju,

795
01:05:38,320 --> 01:05:41,120
en tæknilega, þegar þú ert að takast á við þessar vísitölur

796
01:05:41,120 --> 01:05:45,950
þú ættir nánast alltaf að takast á við óundirritaður heiltölur.

797
01:05:45,950 --> 01:05:53,850
Ástæðan fyrir þessu er þegar þú ert að takast á við undirrituð heiltölur

798
01:05:53,850 --> 01:05:56,090
þannig að ef þú ert með 2 undirritað heiltölur og þú bætir við þeim saman

799
01:05:56,090 --> 01:06:00,640
og þeir á endanum of stór, þá endar með neikvæða tölu.

800
01:06:00,640 --> 01:06:03,410
Svo það er það sem heiltala flæða er.

801
01:06:03,410 --> 01:06:10,500
>> Ef ég bæta 2 milljörðum og 1 milljarður, enda ég upp með neikvæðum 1 milljarð.

802
01:06:10,500 --> 01:06:15,480
Það er hvernig heiltölur vinna á tölvur.

803
01:06:15,480 --> 01:06:17,510
Þannig að vandamálið með því að nota -

804
01:06:17,510 --> 01:06:23,500
Það er allt í lagi nema lítið gerist að 2 milljarðar og allt verður að vera 1 milljarður,

805
01:06:23,500 --> 01:06:27,120
þá er þetta að fara að vera neikvæð 1 milljarð og þá erum við að fara að deila því með 2

806
01:06:27,120 --> 01:06:29,730
og endað með neikvæðum 500 milljónir.

807
01:06:29,730 --> 01:06:33,760
Svo er þetta bara vandamál ef þú skyldir vera að leita í gegnum fylki

808
01:06:33,760 --> 01:06:38,070
milljarða hluta.

809
01:06:38,070 --> 01:06:44,050
En ef lítið + allt gerist að flæða, þá er það vandamál.

810
01:06:44,050 --> 01:06:47,750
Um leið og við tökum þá óundirritaður, þá er 2 milljörðum plús 1 milljarð 3 milljarðar.

811
01:06:47,750 --> 01:06:51,960
3 milljarðar deilt með 2 er 1,5 milljarðar króna.

812
01:06:51,960 --> 01:06:55,670
Svo um leið og þeir eru án undirritunar, allt er fullkomið.

813
01:06:55,670 --> 01:06:59,900
Og svo er það líka málið þegar þú ert að skrifa þína fyrir lykkjur,

814
01:06:59,900 --> 01:07:03,940
og í raun er það sennilega það sjálfkrafa.

815
01:07:09,130 --> 01:07:12,330
Það verður í raun bara að æpa á þig.

816
01:07:12,330 --> 01:07:21,610
Þannig að ef þessi tala er of stór til að vera í bara heiltala en það myndi passa að óundirritaður heiltölu,

817
01:07:21,610 --> 01:07:24,970
það mun æpa á þig, svo það er hvers vegna þú aldrei hlaupa inn í málið.

818
01:07:29,150 --> 01:07:34,820
Þú getur séð að vísitala er aldrei að fara að vera neikvæð,

819
01:07:34,820 --> 01:07:39,220
og svo þegar þú ert iterating yfir fjölda,

820
01:07:39,220 --> 01:07:43,970
þú getur nánast alltaf sagt óundirritaður int i, en þú í raun ekki til.

821
01:07:43,970 --> 01:07:47,110
Hlutirnir eru að fara að vinna ansi mikið eins og heilbrigður.

822
01:07:48,740 --> 01:07:50,090
Allt í lagi. [Hvíslar] Hvað er klukkan?

823
01:07:50,090 --> 01:07:54,020
Það síðasta sem ég vildi sýna - og ég verð bara að gera það mjög fljótur.

824
01:07:54,020 --> 01:08:03,190
Þú veist hvernig við höfum skilgreint # svo við getum # define MAX sem 5 eða eitthvað?

825
01:08:03,190 --> 01:08:05,940
Við skulum ekki Max. # Define bundinn eins og 200. Það er það sem við gerðum áður.

826
01:08:05,940 --> 01:08:10,380
Það skilgreinir stöðug, sem er bara að fara að afrita og líma

827
01:08:10,380 --> 01:08:13,010
hvar sem við gerast að skrifa bundinn.

828
01:08:13,010 --> 01:08:18,189
>> Þannig að við getum í raun gert meira með # skilgreinir.

829
01:08:18,189 --> 01:08:21,170
Við getum # skilgreina aðgerðir.

830
01:08:21,170 --> 01:08:23,410
Þeir eru í raun ekki virka, en við munum kalla þá virka.

831
01:08:23,410 --> 01:08:36,000
Dæmi væri eitthvað eins og Max (x, y) er skilgreind sem (x <Y y:? X). Allt í lagi.

832
01:08:36,000 --> 01:08:40,660
Svo þú ættir að venjast ternary rekstraraðila setningafræði,

833
01:08:40,660 --> 01:08:49,029
en er x minna en y? Return y, annars aftur x.

834
01:08:49,029 --> 01:08:54,390
Svo þú sérð að þú getur gert þetta sér aðgerð,

835
01:08:54,390 --> 01:09:01,399
og virka gæti verið eins bool MAX tekur 2 rök, skila þessu.

836
01:09:01,399 --> 01:09:08,340
Þetta er einn af the sameiginlegur sjálfur sé ég gert svona. Við köllum þá Fjölvi.

837
01:09:08,340 --> 01:09:11,790
Þetta er þjóðhagsleg.

838
01:09:11,790 --> 01:09:15,859
Þetta er bara setningafræði fyrir það.

839
01:09:15,859 --> 01:09:18,740
Þú getur skrifað Fjölvi til að gera hvað sem þú vilt.

840
01:09:18,740 --> 01:09:22,649
Þú sérð oft Fjölvi fyrir kembiforrit printfs og efni.

841
01:09:22,649 --> 01:09:29,410
Svo gerð printf eru sérstakar fastar í C ​​eins og undirstrik LINE undirstrika,

842
01:09:29,410 --> 01:09:31,710
2 undirstrikar LINE undirstrika,

843
01:09:31,710 --> 01:09:37,550
og það er líka að ég held 2 undirstrikar störf. Það gæti verið það. Eitthvað eins og þessi.

844
01:09:37,550 --> 01:09:40,880
Þessir hlutir verða skipt út með nafni virka

845
01:09:40,880 --> 01:09:42,930
eða númer línu sem þú ert á.

846
01:09:42,930 --> 01:09:48,630
Oft, skrifa kembiforrit printfs sem hérna ég gæti þá bara skrifa

847
01:09:48,630 --> 01:09:54,260
Kemba og það mun prenta línu númer og aðgerð sem ég gerst að vera í

848
01:09:54,260 --> 01:09:57,020
að fundur þessi Debug yfirlýsingu.

849
01:09:57,020 --> 01:09:59,550
Og þú getur líka prentað út annað.

850
01:09:59,550 --> 01:10:05,990
Svo er einn hlutur sem þú ættir að horfa út fyrir ef ég gerst að # define DOUBLE_MAX

851
01:10:05,990 --> 01:10:11,380
sem eitthvað eins og 2 * y og 2 * x.

852
01:10:11,380 --> 01:10:14,310
Svo fyrir ástæðu hvað, gerast þú að gera það mikið.

853
01:10:14,310 --> 01:10:16,650
Svo gera það þjóðhagsleg.

854
01:10:16,650 --> 01:10:18,680
Þetta er í raun brotinn.

855
01:10:18,680 --> 01:10:23,050
Ég myndi kalla það með því að gera eitthvað eins og DOUBLE_MAX (3, 6).

856
01:10:23,050 --> 01:10:27,530
Svo hvað ætti að vera aftur?

857
01:10:28,840 --> 01:10:30,580
[Nemandi] 12.

858
01:10:30,580 --> 01:10:34,800
Já, ætti 12 að vera aftur, og 12 er skilað.

859
01:10:34,800 --> 01:10:43,350
3 er skipt út fyrir X, fær 6 í stað fyrir y, og við aftur 2 * 6, sem er 12.

860
01:10:43,350 --> 01:10:47,710
Nú hvað um það? Hvað ætti að vera aftur?

861
01:10:47,710 --> 01:10:50,330
[Nemandi] 14. >> Helst 14.

862
01:10:50,330 --> 01:10:55,290
Málið er að hvernig kjötkássa skilgreinir vinna, muna að það er bókstaflega afrita og líma

863
01:10:55,290 --> 01:11:00,160
á nánast allt, svo það þetta er að fara að túlka sem

864
01:11:00,160 --> 01:11:11,270
er 3 minna en 1 plús 6, 2 sinnum 1 plús 6, 2 sinnum 3.

865
01:11:11,270 --> 01:11:19,780
>> Svo þess vegna er sett næstum alltaf allt í sviga.

866
01:11:22,180 --> 01:11:25,050
Hvaða breyta er sett nánast alltaf í sviga.

867
01:11:25,050 --> 01:11:29,570
Það eru tilvik þar sem þú þarft ekki að, eins og ég veit að ég þarf ekki að gera það hér

868
01:11:29,570 --> 01:11:32,110
því minna en nánast alltaf bara að fara að vinna,

869
01:11:32,110 --> 01:11:34,330
þó að það gæti ekki einu sinni að vera satt.

870
01:11:34,330 --> 01:11:41,870
Ef það er eitthvað fáránlegt eins DOUBLE_MAX (1 == 2),

871
01:11:41,870 --> 01:11:49,760
þá er að fara að fá stað með 3 minna en 1 er jafnt 2,

872
01:11:49,760 --> 01:11:53,460
og svo þá það er að fara að gera 3 minna en 1, er að jafn 2,

873
01:11:53,460 --> 01:11:55,620
sem er ekki það sem við viljum.

874
01:11:55,620 --> 01:12:00,730
Svo í því skyni að koma í veg fyrir rekstraraðila forgang vandamál,

875
01:12:00,730 --> 01:12:02,870
alltaf sett í sviga.

876
01:12:03,290 --> 01:12:07,700
Allt í lagi. Og það er það, 5:30.

877
01:12:08,140 --> 01:12:12,470
Ef þú hefur einhverjar spurningar um pset, láttu okkur vita.

878
01:12:12,470 --> 01:12:18,010
Það ætti að vera gaman, og tölvusnápur útgáfa einnig er miklu raunsærri

879
01:12:18,010 --> 01:12:22,980
en spjallþráð útgáfa af síðasta ári, þannig að við vonum að mikið af þú ert að reyna það.

880
01:12:22,980 --> 01:12:26,460
Á síðasta ári var mjög yfirþyrmandi.

881
01:12:28,370 --> 01:12:30,000
>> [CS50.TV]