[Powered by Google Translate] [Seksyon 3 - plis konfòtab]
[Rob Bowden - Inivèsite Harvard]
>> [Sa a se CS50. - CS50.TV]
>> Se konsa, se premye kesyon an etranj remak bwèf.
Gdb pèmèt ou "dbug" yon pwogram, men, plis espesyalman, ki sa li fè ou fè?
Mwen pral reponn ke yon moun, epi mwen pa konnen sa ki egzakteman espere,
Se konsa, mwen ap devine yon bagay li a sou liy ki an li pèmèt ou etap pa etap
mache nan pwogram nan, kominike avèk li, varyab chanjman, fè tout bagay sa yo -
fondamantalman konplètman kontwole ekzekisyon nan yon pwogram
ak enspekte nenpòt ki pati yo bay nan ekzekisyon an nan pwogram nan.
Se konsa, sa yo karakteristik kite ou dbug bagay sa yo.
Oke.
Poukisa rechèch binè egzije pou yo yon etalaj Ranje?
Ki moun ki vle reponn sa?
[Elèv] Paske li pa travay si li pa nan Klase. >> Yeah. [Ri]
Si li pa nan Ranje, lè sa a li nan enposib fann l 'nan mwatye
ak konnen ke tout bagay sa yo bò gòch la ki pi piti a ak tout bagay sa yo dwa pou
se pi gran pase valè mitan an.
Se konsa, li bezwen yo dwe klase.
Oke.
Poukisa se sòt jarèt nan O nan okib n?
nenpòt moun ki premye vle bay yon trè rapid BECA wo nivo nan sa ki sòt jarèt se?
[Elèv] Ou fondamantalman ale nan chak eleman ak ou tcheke premye eleman yo kèk.
Si yo ap soti nan kote ou swap yo, Lè sa a, ou tcheke pwochen eleman yo kèk ak sou sa.
Lè ou rive nan fen a, Lè sa a, ou konnen ke se eleman ki pi gwo mete nan fen a,
konsa ou inyore ke youn Lè sa a, w kenbe sou ale atravè tout,
ak chak fwa ou gen yo tcheke yon sèl mwens eleman jiskaske ou fè pa gen okenn chanjman. >> Yeah.
Yo rele li sòt jarèt paske si ou baskile etalaj la sou bò li yo Se konsa li leve, li desann, vètikal,
Lè sa a, valè yo gwo ap plonje anba a ak valè yo ti pral jarèt moute sou tèt la.
Sa a se li montre kouman li te resevwa non li yo.
Ak yeah, ou jis ale nan.
Ou kenbe ale nan etalaj la, échanjé valè ki pi gwo a
jwenn valè yo pi gwo jouk anba a.
>> Poukisa se li O nan okib n?
Premyèman, nenpòt moun ki vle di poukisa li a O nan n okib?
[Elèv] Paske pou chak kouri li ale fwa n.
Ou kapab sèlman asire w ke ou te pran eleman nan pi gwo tout wout la desann,
Lè sa a, ou gen repete sa pou kòm eleman anpil moun. >> Yeah.
Se konsa, kenbe nan tèt ou ki sa gwo O vle di ak sa vle di Omega gwo.
O nan gwo, se tankou anwo a mare l 'sou ki jan ralanti li ka aktyèlman kouri.
Se konsa, lè li di O li a nan okib n, se pa O nan n oswa lòt moun li ta kapab kouri
nan tan lineyè, men li se O nan n Gleason
paske li se bòne pa O nan n Gleason.
Si li la bòne pa O nan okib n, Lè sa a, li la limite tou pa n Gleason.
Se konsa, li se n okib, ak nan ka a absoli pi move li pa ka fè pi bon pase okib n,
ki se poukisa li a O nan n okib.
Se konsa, yo wè ti tay matematik nan li montre kouman li vini soti nan gen n okib,
si nou gen senk bagay sa yo nan lis nou an, premye fwa a ki jan anpil echanj nou ta ka potansyèlman bezwen fè
yo nan lòd jwenn sa a? Se pou nou aktyèlman jis -
Konbyen echanj nou pral gen fè nan kouri nan premye nan kalite jarèt nan etalaj la?
[Elèv] n - 1. >> Yeah.
>> Si gen 5 eleman, nou ap ale nan bezwen fè n - 1.
Lè sa a, sou yon sèl nan dezyèm konbyen echanj nou pral gen a fè?
[Elèv] n - 2. >> Yeah.
, Twazyèm lan a pwal n - 3, ak Lè sa a, pou konvenyans Mwen pral ekri de nan dènye
Lè sa a, kòm nou ap ale nan bezwen fè 2 echanj ak swap 1.
Mwen devine yon sèl nan dènye ka oswa ka pa aktyèlman bezwen rive.
Èske se yon swap? Mwen pa konnen.
Se konsa, sa yo, se kantite lajan total ki nan echanj oswa omwen konparezon ou gen fè a.
Menm si ou pa boukante, ou toujou bezwen konpare salè valè yo.
Se konsa, gen n - 1 konparezon an kouri nan premye nan etalaj la.
Si ou ordonne bagay sa yo, se pou yo aktyèlman fè li sis bagay konsa bagay sa yo pile joliman,
ak Lè sa a, mwen pral fè 3, 2, 1.
Se konsa, jis ranplase sa yo sòm total, nou vle wè kòman anpil konparezon nou fè
nan algorithm a tout antye.
Se konsa, si nou pote mesye sa yo desann isit la,
Lè sa a, nou toujou ap jis adisyon konparezon sepandan anpil, te gen.
Men, si nou rapò kantite sa yo ak nou rapò kantite sa yo ak nou rapò kantite sa yo,
li la toujou menm pwoblèm nan. Nou jis rapò kantite moun ki gwoup an patikilye.
>> Se konsa, kounye a nou ap adisyon 3 nan n. Li pa jis 3 an n.
Li nan toujou pral fè n / 2 nan n.
Se konsa, isit la nou rive gen 6.
Si nou te gen 10 bagay sa yo, Lè sa a, nou te kapab fè sa a gwoupman pou 5 pè diferan de bagay sa yo
ak fini ak n + n + n + n n +.
Se konsa, ou toujou ap pral jwenn n / 2 nan n, ak kidonk sa a nou pral bout li soti nan n okib / 2.
Se konsa, menm si li nan faktè a nan mwatye, ki k ap pase nan vini nan
paske nan lefèt ke nan chak iterasyon sou etalaj la nou konpare 1 mwens
pou ki nan ki jan nou jwenn sou la 2, men li la toujou N okib.
Nou pa pran swen sou faktè a konstan nan yon mwatye.
Se konsa, yon anpil nan bagay gwo O tankou sa a rpoz sou jis kalite ap fè sa a sòt de matematik,
fè sòm total aritmetik ak jewometrik bagay seri yo,
men pi fò nan yo nan kou sa a se trè dwat.
Oke.
Poukisa se sòt ensèsyon nan Omega nan n? Ki sa ki Omega vle di?
[De elèv ki pale nan yon fwa - enkonpreansibl] >> Yeah.
Omega ou ka panse a kòm pi ba mare l 'la.
>> Se konsa, pa gen pwoblèm konbyen efikas algorithm ensèsyon sòt ou ye, se
kèlkeswa lis la ki nan te pase nan, li toujou gen yo konpare omwen n bagay sa yo
oswa li te repekte sou bagay sa yo n.
Poukisa se sa?
[Elèv] Paske si se lis la deja klase, lè sa a nan iterasyon nan premye
ou ka sèlman garanti ke eleman an trè premye ki pi piti a,
ak iterasyon nan dezyèm ou ka sèlman garanti de a an premye yo se
paske ou pa konnen ki rès la nan lis la Ranje. >> Yeah.
Si w pase nan yon lis konplètman Ranje, nan omwen nan anpil ou gen ale sou tout eleman ki
yo wè ke pa gen anyen bezwen yo dwe te deplase alantou.
Se konsa, pase sou lis la epi yo di oh, sa a se deja klase,
li nan enposib pou ou pou w konnen li nan Ranje jiskaske ou tcheke chak eleman
yo wè yo ke yo se nan Ranje lòd.
Se konsa, pi ba a mare l 'sou sòt ensèsyon se Omega n.
Kisa ki ka ki pi mal la kouri lè nan sòt fizyone,
pi move ka ke yo te O gwo ankò?
Se konsa, nan senaryo a ka pi mal, ki jan unifye sòt kouri?
[Elèv] N boutèy demi lit n. >> Yeah.
Pi rapid algoritm yo klasman jeneral se yon, n boutèy demi lit n. Ou pa ka fè pi byen.
>> Gen ka espesyal, epi si nou gen tan jodi a - men nou pwobableman won't -
nou te ka wè youn ki fè sa ki pi bon pase n boutèy demi lit n.
Men, nan ka la an jeneral, ou pa kapab fè pi bon pase n boutèy demi lit n.
Ak rantre sòt k ap pase yo dwe youn nan ou ta dwe konnen pou kou sa a ki se n boutèy demi lit n.
Se konsa, nou pral aktyèlman ap mete ann aplikasyon sa jodi an.
Epi finalman, nan pa plis ke twa fraz, ki jan fè travay sòt seleksyon?
yon moun vle reponn, epi mwen pral konte fraz ou
paske si w ale sou 3 -
nenpòt moun ki sonje sòt seleksyon?
Sòt seleksyon se nòmalman trè fasil a sonje jis nan non la.
Ou jis repekte sou etalaj la, jwenn tou sa valè a pi gwo se oswa pi piti -
kèlkeswa sa lòd w ap Fouye pous
Se konsa, kite a di n ap Fouye soti nan pi piti pi gwo a.
Ou repekte sou etalaj la, kap chèche kèlkeswa sa eleman minimòm-nan se,
chwazi l ', li Lè sa a, jis boukante l' tou sa se nan plas an premye.
Lè sa a, sou pas dezyèm sou etalaj la, gade pou eleman minimòm-nan ankò,
chwazi l ', li Lè sa a, boukante l' ak sa ki nan nan yon pozisyon nan dezyèm fwa.
Se konsa, nou jis davwa epi chwazi valè yo minimòm
ak mete yo nan devan nan etalaj la jiskaske li se Klase.
Kesyon sou sa?
>> Sa yo inevitableman parèt nan fòm sa yo ou bezwen ranpli lè w ap soumèt pset la.
Moun sa yo se fondamantalman repons yo bay moun.
Oke, kidonk kounye a kodaj pwoblèm.
Mwen deja voye soti sou imel - Eske yon moun pa jwenn ki imel? Oke.
Mwen deja voye soti sou imel espas la ke nou ap pral lè l sèvi avèk,
epi si ou klike sou non mwen - Se konsa, mwen panse mwen pral yo dwe nan pati anba a
paske yo te r nan bak - men si ou klike sou non mwen ou pral wè 2 revizyon.
Revizyon 1 yo pral mwen deja kopye ak kole kòd la nan Espas
pou bagay la rechèch w ap ale nan gen a aplike.
Ak Revizyon 2 yo pral bagay la sòt ke nou aplike apre sa.
Se konsa, ou ka klike sou Revizyon mwen 1 ak travay apati de la.
Epi, koulye a nou vle aplike rechèch binè.
>> nenpòt moun ki vle jis bay yon eksplikasyon pseudocode wo nivo
nan ki sa nou pwal gen pou fè pou rechèch? Yeah.
[Elèv] Ou jis pran mitan an nan etalaj la ak wè si sa w ap chèche pou
se mwens pase sa oswa plis pase sa.
Men, si li nan mwens, ou ale nan mwatye a ki nan mwens,
epi si li nan plis, ou ale nan mwatye a ki an plis, epi ou repete sa jiskaske ou jis jwenn yon sèl bagay.
[Bowden] Yeah.
Remake se etalaj nimewo nou an deja klase,
Pou fè sa ki vle di ke nou kapab pran avantaj de sa ki epi nou te ka premye chèk,
oke, mwen kap chèche nimewo a 50.
Se konsa, mwen ka ale nan mitan yo.
Mwayen se difisil defini a lè li yon nimewo menm de bagay sa yo,
men kite yo jis di nou pral toujou tronke nan mitan an.
Se konsa, isit la nou gen 8 bagay sa yo, se konsa mitan an ta dwe 16.
Mwen kap chèche 50, se konsa 50 se pi gran pase 16.
Se konsa, koulye a, mwen ka fondamantalman trete etalaj mwen kòm eleman sa yo.
Mwen ka jete tout bagay soti nan 16 sou.
Koulye a, etalaj mwen se jis eleman sa yo 4, epi mwen repete.
Se konsa, Lè sa a, mwen vle jwenn mitan an ankò, ki a pwal 42.
42 se mwens pase 50, se konsa mwen ka jete eleman sa yo de.
Sa a se etalaj rete m 'yo.
Mwen pral jwenn mwayen an ankò.
Mwen devine 50 se te yon egzanp move paske mwen te toujou jete bagay sa yo nan bò gòch lan,
men pa menm mezi, si mwen chèche pou yon bagay
ak li a mwens pase eleman nan mwen kounye a chèche a,
Lè sa a, mwen pral jete tout bagay sa yo bò dwat la.
Se konsa, kounye a nou bezwen aplike sa.
Remake ke nou bezwen pase nan gwosè.
Nou kapab tou pa bezwen difisil-kòd gwosè.
Se konsa, si nou debarase m de ki # defini -
Oke.
Kouman mwen ka joliman konnen sa ki gwosè a nan etalaj la nimewo kounye a se?
>> Konbyen eleman yo nan etalaj la nimewo?
[Elèv] Numbers, parantèz,. Longè?
[Bowden] ki pa egziste nan C.
Bezwen. Longè.
Matris pa gen pwopriyete yo, kidonk pa genyen okenn pwopriyete longè ranje
ki pral jis ba ou sepandan tan li k ap pase yo.
[Elèv] Gade jan memwa li gen epi divize pa kantite lajan - >> Yeah.
Se konsa, ki jan nou ka wè ki kantite memwa li gen? >> [Elèv] sizof. >> Yeah, sizof.
Sizof se operatè a ki nan ale nan retounen gwosè a nan etalaj la nimewo yo.
E se te pral fè sepandan anpil nonm antye relatif, gen fwa gwosè a nan yon nonb antye relatif
depi lè sa a konbyen lajan memwa li la aktyèlman ap pran yo.
Se konsa, si mwen vle ki kantite bagay sa yo nan etalaj la,
Lè sa a, mwen pral vle divize pa gwosè a nan yon nonb antye relatif.
Oke. Se konsa, ki pèmèt m 'pase nan gwosè isit la.
Poukisa mwen bezwen pase nan gwosè nan tout?
Poukisa nou pa mwen ka jis fè moute isit la int gwosè = sizof (gwo pile zèb) / sizof (Int)?
Poukisa sa a pa travay?
[Elèv] Se pa yon varyab mondyal.
[Bowden] gwo pile zèb egziste e nou ap pase nan nimewo kòm gwo pile zèb
ak sa a se kalite yon prefigurasyon nan sa ki nan ap vini yo. Yeah.
[Elèv] gwo pile zèb se jis referans nan li, se konsa li ta retounen ki jan gwo ke referans se.
Yeah.
Mwen gen dout nan konferans ke ou te wè chemine a ankò vrèman, dwa?
Nou te jis pale sou li.
Se konsa, chemine a se kote tout nan varyab ou yo ale nan dwe estoke.
>> Nenpòt memwa ki nan resevwa lajan pou varyab lokal ki pral nan chemine a,
epi chak fonksyon vin espas pwòp li yo sou chemine a, ankadreman chemine pwòp li yo se sa ki sa yo rele.
Se konsa, prensipal la gen ankadreman chemine li yo, ak andedan nan li ki pral egziste sa a etalaj nonb,
epi li pral fè nan sizof gwosè (nimewo).
Li nan pral gen gwosè nan nimewo divize pa gwosè nan eleman,
men sa ki tout lavi nan lespas ankadreman chemine prensipal la.
Lè nou rele rechèch, rechèch vin ankadreman chemine pwòp li yo,
espas pwòp li yo nan magazen tout nan varyab lokal li yo.
Men, sa yo agiman - pou gwo pile zèb se pa yon kopi sa a etalaj tout antye.
Nou pa pase nan etalaj nan tout kòm yon kopi nan rechèch.
Li jis pase yon referans ak sa yo ki etalaj.
Se konsa, rechèch kapab jwenn aksè nan nimewo sa yo nan sa a referans.
Li nan toujou gen aksè nan bagay sa yo ke ap viv andedan nan ankadreman chemine prensipal la,
men fondamantalman, lè nou jwenn yo endikasyon yo, ki ta dwe byento,
sa a se sa endikasyon yo ye.
Endikasyon yo se jis referans sou bagay sa yo, epi ou ka sèvi ak bagèt gen aksè a bagay sa yo
yo ki nan ankadreman chemine lòt bagay '.
Se konsa, menm si nimewo se lokal yo prensipal yo, nou ka toujou jwenn aksè li nan sa a konsèy.
Men, depi li nan jis yon konsèy ak li nan jis yon referans,
sizof (gwo pile zèb) jis retounen gwosè a nan referans nan tèt li.
Li pa retounen gwosè a nan bagay la li nan lonje dwèt yo.
Li pa retounen gwosè aktyèl la nan nimewo yo.
Se konsa, sa a pa ale nan travay kòm nou vle l 'bay.
>> Kesyon sou sa?
Endikasyon pral fè wout nou nan an detay siyifikativman plis esyon nan semèn kap vini yo.
Ak sa a se poukisa yon anpil nan bagay sa yo ke ou wè, ki pi bagay sa yo rechèch oswa bagay sa yo sòt,
yo ap prèske tout pral bezwen pran gwosè aktyèl la nan etalaj la,
paske se nan C, nou pa gen okenn lide ki sa gwosè a nan etalaj la se.
Ou bezwen manuelman pase l pous
Epi ou pa ka manuelman pase nan etalaj nan tout paske w ap sèlman pase nan referans a
epi li pa ka jwenn gwosè a nan referans a.
Oke.
Se konsa, kounye a nou vle aplike sa ki te eksplike anvan.
Ou ka travay sou li pou yon minit,
epi ou pa gen enkyete sou jwenn tout bagay parfe 100% ap travay.
Jis ekri moute pseudocode a mwatye pou ki jan ou panse ke li ta dwe travay.
Oke.
Pa gen bezwen konplètman fè ak sa a ankò.
Men, nenpòt moun ki santi yo konfòtab avèk sa yo gen twò lwen,
tankou yon bagay nou ka travay avèk ansanm?
nenpòt moun ki vle travay kòm volontè? Oswa mwen pral owaza chwazi.
Li pa gen yo dwe gen dwa nan nenpòt ki mezi men yon bagay nou ka modifye nan yon eta k ap travay.
[Elèv] Sure. >> Okay.
Se konsa, ou ka sove dat revizyon an pa klike sou icon an ti Save.
Ou se Ramya, dwa? >> [Elèv] Yeah. >> [Bowden] Okay.
Se konsa, koulye a, mwen kapab wè revizyon ou yo ak tout moun ka rale moute dat revizyon an.
Ak isit la nou genyen - Okay.
Se konsa, Ramya ale avèk solisyon an repetitif, ki se definitivman yon solisyon ki valid.
Gen de fason ou ka fè pwoblèm sa a.
Ou kapab swa fè li iterativman oswa recursive.
Pifò pwoblèm ou rankontre ke yo ka fè recursive kapab tou gen pou fè iterativman.
Se konsa, isit la nou te fè l 'recursive.
>> yon moun vle defini sa li vle di fè yon fonksyon repetitif?
[Elèv] Lè ou gen yon fonksyon rele tèt li
ak Lè sa a, rele tèt li jouk li rive soti ak vrè ak vre. >> Yeah.
Yon fonksyon repetitif se jis yon fonksyon ki fè apèl tèt li.
Gen twa bagay sa yo gwo ke yon fonksyon repetitif yo dwe gen.
Premye a se evidamman, li rele tèt li.
Dezyèm la se ka a baz.
Se konsa, nan kèk pwen fonksyon a bezwen sispann rele tèt li,
ak se sa ki ka a baz se pou.
Se konsa, isit la nou konnen ke nou ta dwe sispann, nou ta dwe bay moute nan rechèch nou an
lè kòmansman egal fen - epi nou pral ale sou ki sa sa vle di.
Men, finalman, bagay la pase sa a, se enpòtan pou fonksyon repetitif:
fonksyon yo dwe yon jan kanmenm apwoche ka a baz.
Renmen si ou pa ap aktyèlman mete ajou anyen lè ou fè dezyèm apèl la repetitif,
si w ap literalman jis rele fonksyon nan ankò avèk agiman yo menm
e pa gen varyab mondyal te chanje oswa yon lòt bagay,
ou pa janm pral rive nan ka a baz, nan ka sa a ki nan move.
Li pral yon rkursyon enfini ak yon debòde chemine.
Men, isit la nou wè ke update la k ap pase depi nou ap mete ajou kòmanse + fen / 2,
n ap mete ajou agiman nan fen isit la, nou ap mete ajou agiman an kòmanse isit la.
Se konsa, nan tout apèl yo avèk repetitif nou ap mete ajou yon bagay. Oke.
ou vle mache nou nan solisyon ou a? >> Sure.
Mwen sèvi ak SearchHelp pou ke chak fwa mwen fè sa a rele fonksyon
Mwen gen nan kòmansman an nan kote mwen kap chèche nan etalaj la ak fen an
nan kote m ap gade etalaj la.
>> Nan chak etap ki kote l ye li di li nan eleman nan mitan, ki se kòmansman + fen / 2,
se ke egal a ki sa nou ap chèche pou?
Men, si li se, Lè sa a, nou jwenn li, e mwen devine ki vin pase moute nivo yo nan rkursyon.
Men, si ke se pa vre, lè sa a nou tcheke si ke valè mitan nan etalaj la se twò gwo,
nan ka sa a nou gade nan mwatye a gòch nan etalaj la pa pral soti nan kòmansman endèks mitan an.
Ak otreman nou fè mwatye nan fen.
[Bowden] Okay.
Ki sanble bon.
Oke, kidonk yon koup bagay sa yo, ak aktyèlman, sa a se yon bagay trè wo nivo
ke ou pa janm pral bezwen konnen pou kou sa a, men li se vre.
Fonksyon repetitif, ou toujou tande yo ke yo se yon kontra move
paske si w recursive rele tèt ou twòp fwa, ou jwenn debòde chemine
depi, jan mwen te di anvan, chak fonksyon vin ankadreman chemine pwòp li yo.
Se konsa, chak apèl nan fonksyon an repetitif vin ankadreman chemine pwòp li yo.
Se konsa, si ou fè apèl 1,000 repetitif, ou jwenn 1,000 ankadreman chemine,
epi byen vit ou mennen nan ki gen twò anpil ankadreman chemine ak bagay sa yo jis kraze.
Se konsa, Se poutèt sa fonksyon repetitif yo jeneralman move.
Men, gen yon sou bèl nan fonksyon repetitif rele fonksyon ke-repetitif,
ak sa a k ap pase yo yon egzanp sou yon sèl kote si du a remake sa a
epi li ta dwe, mwen panse ke - nan sonnen si w pase li-O2 a drapo
Lè sa a, li ap remake sa a se ke repetitif ak fè bagay sa yo bon.
>> Li pral jam itilize ankadreman an pil menm sou yo ak sou ankò pou chak apèl repetitif.
Se konsa, depi w ap itilize ankadreman an pil menm, ou pa bezwen enkyete sou
janm chemine debòde, ak nan menm tan an, tankou ou te di anvan,
kote yon fwa ou retounen vre, Lè sa a, li gen retounen moute tout moun sa yo ankadreman chemine
ak apèl la 10yèm SearchHelp gen pou l retounen 9yèm a, gen pou l retounen 8yèm la.
Se konsa, ki pa bezwen rive lè fonksyon yo se ke repetitif.
Se konsa, sa ki fè sa a ke fonksyon repetitif se pre-avi ke pou nenpòt ki rele yo bay searchHelp
rele nan repetitif ke li nan fè a se sa ki li nan retounen.
Se konsa, nan rele nan premye SearchHelp, nou swa imedyatman retounen fo,
imedyatman retounen vre, oswa nou fè yon apèl repetitif SearchHelp
kote sa n ap retounen se sa ki ki rele ki retounen.
Epi nou pa ta ka fè sa a si nou te fè yon bagay tankou int x = SearchHelp, retounen x 2 *,
sèlman kèk chanjman o aza.
>> Se konsa, kounye a sa a rele repetitif, sa a int x = SearchHelp repetitif rele,
li gen plis ke repetitif paske li gen aktyèlman retounen
tounen nan yon ankadreman chemine anvan pou ke ki rele anvan fonksyon an
ka Lè sa a, fè yon bagay ki gen valè lè li retounen.
Se konsa, sa a se pa ke repetitif, men ki sa nou te genyen anvan se joliman ke repetitif. Yeah.
[Elèv] pa ta dwe ka a dezyèm baz tcheke premye
paske se la te kapab fè yon sitiyasyon kote lè ou pase l agiman an
ou te kòmanse = fen, men yo se valè a zegwi.
Kesyon an pa te nou ka kouri antre nan ka a kote fen se valè a zegwi
oswa kòmanse = fen, kòmsadwa, kòmanse = fen
epi ou pa gen aktyèlman tcheke ke valè patikilye ankò,
Lè sa a, kòmanse + fen / 2 se jis pral fè menm valè a.
Men, nou te deja tounen fo e nou pa janm aktyèlman tcheke valè an.
Se konsa, omwen nan anpil, nan rele an premye, si gwosè se 0, lè sa a nou vle tounen fo.
Men, si gwosè se 1, lè sa a kòmanse pa pral nan fen egal,
epi n ap omwen tcheke eleman nan yon sèl.
Men mwen panse ke ou se dwa nan ke nou ka fini nan yon ka kote kòmanse + fen / 2,
kòmansman fini moute yo te menm bagay la kòm kòmansman + fen / 2,
men nou pa janm aktyèlman tcheke ke eleman.
>> Se konsa, si nou premye tcheke se eleman nan mitan valè a nou ap chèche pou yo,
Lè sa a, nou ka imedyatman retounen vre.
Lòt Bagay yo si yo ap egal, Lè sa a, gen nan pa gen pwen nan kontinye
depi nou ap jis pral mete ajou nan yon ka kote nou yo se sou yon etalaj sèl-eleman.
Si se sa ki eleman sèl se pa yon sèl an ke nou ap chèche pou yo,
Lè sa a, tout bagay se sa ki mal. Yeah.
[Elèv] bagay la se ke depi gwosè se aktyèlman pi gwo pase ki kantite eleman nan etalaj la,
gen deja yon kourbur - >> Se konsa, pral gwosè -
[Elèv] Di si etalaj la te gwosè 0, Lè sa a, SearchHelp a pral aktyèlman tcheke gwo pile zèb nan 0
sou apèl la an premye.
Etalaj la gen gwosè 0, se konsa 0 a se - >> Yeah.
Genyen yon lòt bagay ki - li ta ka bon. Se pou nou panse.
Se konsa, si etalaj la te gen 10 eleman ak yon sèl nan mitan nou ap ale nan tcheke se endèks 5,
se konsa nou ap tcheke 5, epi kite pou yo di ke valè a se mwens.
Se konsa, nou ap voye tout bagay lwen 5 pati.
Se konsa, kòmanse + fen / 2 a pwal fen nouvo nou an,
Se konsa wi, li te toujou ale nan rete pi lwen pase nan fen etalaj la.
Si li nan yon ka si li te menm oswa enpè, alò nou ta tcheke, di, 4,
men nou toujou ap jete -
Se konsa, yeah, fen se toujou pral fè pi lwen pase fen aktyèl la nan etalaj la.
Se konsa, eleman sa yo nou ap konsantre sou, fen a toujou ale nan fè yon sèl la apre sa.
Se konsa, si kòmansman fè sa ki janm fen egal, nou se nan yon etalaj de gwosè 0.
>> Bagay a lòt mwen te panse se nou ap mete ajou kòmansman yo dwe kòmanse + fen / 2,
kidonk sa a se ka a ke mwen gen pwoblèm ak travay, ki kote kòmanse + fen / 2
se eleman ki nou ap tcheke.
Se pou nou di nou te gen sa a etalaj 10-eleman. Kèlkeswa.
Se konsa, kòmanse + fen / 2 a pwal yon bagay tankou sa a yon sèl,
epi si sa a pa valè a, di nou vle mete ajou.
Valè a se pi gwo, se konsa nou vle fè yon gade nan sa a mwatye nan etalaj la.
Se konsa, kouman nou ap mete ajou kòmanse, nou ap mete ajou kòmansman kounye a gen sa a eleman.
Men, sa a ka toujou travay, oswa omwen nan anpil, ou kapab fè kòmansman + fen / 2 + 1.
[Elèv] Ou pa bezwen yo dwe kòmanse + fen [fèbl] >> Yeah.
Nou te deja tcheke sa a eleman ak konnen li pa yon sèl la nou ap chèche pou.
Se konsa, nou pa bezwen mete ajou kòmansman yo dwe sa a eleman.
Nou ka jis sote li epi mete ajou kòmanse yo dwe sa a eleman.
¶ Eske gen tout tan yon ka, kite la di, ke sa a te fen,
se konsa Lè sa a, kòmanse ta dwe sa a, kòmanse + fen / 2 ta dwe sa a,
kòmanse + fen - Yeah, mwen panse ke li ka fini nan rkursyon enfini.
Se pou nou di li nan jis yon etalaj de gwosè 2 oswa yon etalaj de gwosè 1. Mwen panse ke sa a ap travay.
Se konsa, kounye a, kòmanse se ke eleman ak fen se 1 apre li.
Se konsa, eleman a ke nou ap ale nan tcheke se yon sèl sa a,
ak Lè sa a, lè nou mete ajou kòmanse, nou ap mete ajou kòmansman yo dwe 0 + 1/2,
ki se ale nan fini nou tounen ak kòmansman yo te sa a eleman.
>> Se konsa, nou ap tcheke eleman an menm sou yo ak sou ankò.
Se konsa, sa a se ka a kote tout apèl repetitif dwe aktyèlman mete ajou yon bagay.
Se konsa, nou bezwen fè kòmansman + fen / 2 + 1, oswa lòt moun gen nan yon ka
kote nou pa ap aktyèlman mete ajou kòmanse.
Tout moun wè sa?
Oke.
nenpòt moun ki gen kesyon sou sa a solisyon an oswa kòmantè nenpòt ki plis?
Oke. nenpòt moun ki gen yon repete solisyon ki nou kapab tout gade nan?
Èske nou tout nou fè l 'recursive?
Oswa tou Mwen devine si ou louvri fanm lan, Lè sa a, ou ka gen écrase youn anvan ou yo.
li otomatikman sove? Mwen pa pozitif.
nenpòt moun ki te repete?
Nou ka mache atravè li ansanm si se pa.
Lide a a pwal menm bagay la.
Repete solisyon an.
Nou pwal vle fondamantalman fè lide a menm
kote nou vle kenbe tras nan fen a nouvo sou etalaj la ak nan kòmansman an nouvo sou etalaj la
ak fè sa sou yo ak sou.
Men, si sa n ap kenbe tras de kòm kòmansman ak nan fen a tout tan kwaze,
Lè sa a, nou pa t 'jwenn li epi nou ka retounen fo.
Se konsa, kouman mwen fè sa? Nenpòt moun ki gen sijesyon, oswa kòd postal pou m 'nan rale moute?
[Elèv] Eske yon riban pandan y ap. >> Yeah.
Ou yo ale nan vle fè yon riban.
>> Eske ou te gen kòd mwen te kapab rale moute a, oswa sa yo te ou pral sijere?
[Elèv] mwen panse sa. >> Tout dwa. Sa fè bagay sa yo pi fasil. Ki sa ki te ou rele?
[Elèv] Lucas.
Revizyon 1. Oke.
Ba se ki sa nou rele kòmanse anvan.
Up se pa byen ki sa nou rele fen anvan.
Aktyèlman, fen se kounye a nan etalaj la. Li nan yon eleman nou ta dwe konsidere.
Se konsa, ba se 0, moute se gwosè a nan etalaj la - 1,
e kounye a, nou ap loupin, epi n ap tcheke -
Mwen devine ou ka mache atravè li.
Ki sa ki te panse ou nan sa a? Mache nou nan kòd ou a.
[Elèv] Sure. Gade nan valè a gwo pile zèb nan mitan an ak li konpare l ak zegwi.
Se konsa, si li nan pi gran pase zegwi ou a, Lè sa a, ou vle - oh, aktyèlman, ki ta dwe fè bak.
W ap ale nan vle jete mwatye nan dwa, epi konsa yeah, ki ta dwe wout la.
[Bowden] Se konsa, sa a ta dwe mwens? Se ke sa ou te di? >> [Elèv] Yeah.
[Bowden] Okay. Mwens.
Se konsa, si sa nou ap chèche a se ki pi piti pase ki sa nou vle,
Lè sa a, yeah, nou vle jete mwatye nan bò gòch,
ki vle di nou ap mete ajou tout sa nou ap konsidere
pa deplase ba a dwat a etalaj la.
Sa a sanble bon.
Mwen panse ke li gen pwoblèm nan menm ke nou te di sou yon sèl anvan an,
kote si ba se 0 ak moute se 1, lè sa a ba + moute / 2 ki pral mete kanpe yo dwe menm bagay la ankò.
>> E menm si sa a pa ka a, li se toujou pi efikas omwen nan anpil
jis jete eleman nan nou jis te gade, nou konnen sa ki mal.
Se konsa, ba + moute / 2 + 1 - >> [elèv] Ki ta dwe nan lòt fason.
[Bowden] Oswa sa a yo ta dwe - 1 ak youn nan lòt yo ta dwe + 1.
[Elèv] Lè ta dwe gen yon doub egal siy. >> [Bowden] Yeah.
[Elèv] Yeah.
Oke.
Epi finalman, kounye a ke nou gen sa a 1 + - 1 bagay,
se li - li pa ta ka - se li tout tan posib pou ba fini ak yon valè ki pi konsekan pase a?
Mwen panse ke fason a sèlman ki ka rive - Eske li posib? >> [Elèv] Mwen pa konnen.
Men, si li vin twonke ak Lè sa a, vin mwens ke 1 ak Lè sa a, - >> Yeah.
[Elèv] Li ta pètèt jwenn messed yo.
Mwen panse ke li ta dwe bon sèlman paske
pou l 'bay fini pi ba yo ta dwe fè egal, mwen panse ke.
Men, si yo yo egal, lè sa a nou pa ta fè riban a pandan y ap yo kòmanse avèk yo
ak nou jis ta yo te retounen valè la. Se konsa, mwen panse ke nou ap bon kounye an.
Remake menm si pwoblèm sa a se pa repetitif,
kalite la menm nan lide aplike kote nou kapab wè ki jan sa a pou fasil prèt tèt li
a yon solisyon repetitif pa lefèt ke nou ap jis mete ajou endis yo sou yo ak sou ankò,
nou ap fè pwoblèm nan pi piti ak pi piti, nou ap konsantre sou yon gwoup ki sot nan etalaj la.
[Elèv] Si ba se 0 ak moute se 1, yo ta tou de gen 0 + 1/2, ki ta ale nan 0,
ak Lè sa a, yon sèl ta dwe + 1, youn ta dwe - 1.
[Elèv] Kote nou tcheke egalite?
Renmen si yon sèl nan mitan an se aktyèlman zegwi?
Nou pa kounye a ap fè sa? Oh!
Si it's -
Wi. Nou pa ka jis fè tès la desann isit la paske kite a di mitan an premye -
[Elèv] Li nan aktyèlman renmen pa jete mare an.
Se konsa, si ou jete mare a, ou gen yo tcheke li premye oswa kèlkeswa sa.
Ah. Yeah. >> [Elèv] Yeah.
Se konsa, kounye a nou te jete lwen youn nan nou kounye a gade,
ki vle di nou koulye a bezwen yo te genyen tou
si (gwo pile zèb [(ba + moute) / 2] == zegwi), Lè sa a, nou ka retounen vre.
Epi si mwen mete lòt bagay oswa jis si, sa vle di literalman menm bagay la
paske sa a ta yo te retounen vre.
Se konsa, mwen pral mete lòt bagay si, men li pa gen pwoblèm.
>> Se konsa, lòt bagay si sa a lòt bagay, sa a, e sa se yon bagay ki komen m 'fè
kote menm si li se ka a kote tout bagay se yon bon bagay isit la,
tankou ki ba kapab pa janm dwe pi gran pase moute, li pa rezònman vo sou si sa a, se vre.
Se konsa, ou ka byen jan ou di pandan y ap ba se mwens pase oswa egal a
oswa pandan y ap ba se mwens pase
Se konsa, si yo se tout tan egal oswa ki ba k ap pase nan pase moute,
Lè sa a, nou ka kraze soti nan sa a riban.
Adrese kesyon, enkyetid, kòmantè?
Oke. Sa a sanble bon.
Koulye a, nou vle fè zèl.
Si nou ale nan revizyon dezyèm m 'yo, nou wè nimewo sa yo menm,
Men, koulye a, yo pa ankò nan Ranje lòd.
E nou vle aplike sòt lè l sèvi avèk nenpòt ki algorithm nan O nan n boutèy demi lit n.
Se konsa, ki algorithm ou panse nou ta dwe aplike isit la? >> [Elèv] fuzyone zèl.
[Bowden] Yeah. Rantre sòt se O (n boutèy demi lit n), se konsa sa a, se sa n ap pral fè a.
Ak pwoblèm nan a pwal trè sanblab,
kote li fasil prèt tèt li nan yon solisyon repetitif.
Nou kapab tou vini ak yon solisyon repete si nou vle,
men rkursyon pral pi fasil isit la epi nou dwe fè rkursyon.
Mwen devine nou pral mache nan sòt unifye an premye,
byenke gen yon videyo bèl sou sòt unifye deja. [Ri]
Se konsa, rantre sòt gen - Mwen gaspiye anpil nan papye sa a.
Oh, gen nan yon sèl bò gòch.
Se konsa, rantre.
Oh, 1, 3, 5.
Oke.
Unifye pran de ranje ki apa a.
Endividyèlman sa yo ranje de yo tou de Ranje.
Se konsa, sa a etalaj, 1, 3, 5, Klase. Sa a etalaj, 0, 2, 4, Klase.
Kounye a ki sa unifye ta dwe fè se konbine yo nan yon etalaj yon sèl ki se pwòp tèt li Ranje.
Se konsa, nou vle yon etalaj de gwosè 6 ki pral gen eleman sa yo andedan nan li
nan Ranje lòd.
>> Se konsa, nou ka pran avantaj de lefèt ke sa yo ranje de yo Ranje
fè sa nan tan lineyè,
lineyè siyifikasyon tan si sa a etalaj se x gwosè ak sa a se y gwosè,
Lè sa a, algorithm nan total yo ta dwe O (x + y). Oke.
Se konsa, sijesyon.
[Elèv] t 'kapab nou kòmanse sou bò goch la?
Se konsa, ou pral mete 0 a desann premye ak Lè sa a, 1 an ak Lè sa a, isit la ou se nan 2 a.
Se konsa, li kalite tankou ou gen yon tab ki nan k ap deplase a dwat la. >> [Bowden] Yeah.
Pou toude, ni nan sa yo ranje si nou jis konsantre sou eleman ki leftmost.
Paske tou de ranje yo Ranje, nou konnen ke eleman sa yo 2
yo se eleman ki pi piti nan swa etalaj.
Se konsa, ki vle di ke 1 nan 2 sa yo eleman yo dwe eleman ki pi piti a nan etalaj uni nou an.
Li jis konsa k ap pase ki pi piti a se youn nan sou tan an dwa sa a.
Se konsa, nou pran 0, insert li sou bò gòch la paske 0 se mwens pase 1,
pou pran 0, insert l 'nan pozisyon premye nou an, epi Lè sa a, nou mete ajou sa a
kounye a konsantre sou eleman la an premye.
Epi, koulye a nou repete.
Se konsa, kounye a nou konpare 2 ak 1. 1 se pi piti, se konsa nou pral insert 1.
Nou mete ajou sa a konsèy nan pwen sa a nèg.
Koulye a, nou fè l 'ankò, se konsa 2. Sa a pral mete ajou, konpare sa yo 2, 3.
Sa a dènye nouvèl yo, Lè sa a, 4 ak 5.
Se konsa, ki se unifye.
>> Li ta dwe trè klè ke li se tan lineyè depi nou jis ale atravè chak eleman yon fwa.
E ke se etap nan pi gwo nan aplikasyon unifye sòt ap fè sa a.
Epi li pa ki difisil.
Yon bagay koup enkyete sou se nan kite l 'di nou te Fusion 1, 2, 3, 4, 5, 6.
Nan ka sa a nou fini nan senaryo a kote sa a yon sèl ki pral yo dwe pi piti,
Lè sa a, nou mete ajou sa a konsèy, sa a yon sèl ki pral yo dwe pi piti, mete ajou sa a,
yon sèl sa a nan pi piti, e kounye a, ou gen yo rekonèt
lè ou te aktyèlman kouri soti nan eleman yo konpare avèk yo.
Depi nou deja itilize sa a etalaj antye,
tout bagay nan sa a etalaj kounye a jis mete nan isit la.
Se konsa, si nou janm kouri antre nan pwen kote yonn nan ranje nou an, ap konplètman fizyone deja,
Lè sa a, nou jis pran tout eleman ki nan etalaj nan lòt epi antre yo nan nan fen etalaj la.
Se konsa, nou ka jis insert 4, 5, 6. Oke.
Sa a se yon sèl bagay yo gade soti pou li a.
Aplike ki ta dwe etap 1.
Rantre sòt Lè sa a, ki baze sou ki, li nan 2 etap, 2 etap timoun.
Se pou nou jis bay sa a etalaj.
Se konsa, rantre sòt, etap 1 se recursive kraze etalaj la nan mwatye.
Se konsa, fann sa a etalaj nan mwatye.
Nou kounye a gen 4, 15, 16, 50 ak 8, 23, 42, 108.
Epi, koulye a nou fè l 'ankò epi nou fann sa yo nan mwatye.
Mwen te jis pral fè l 'sou bò sa a.
Se konsa, 4, 15 ak 16, 50.
Nou ta fè menm bagay la sou isit la.
Epi, koulye a nou fann l 'nan mwatye ankò.
E nou gen 4, 15, 16, 50.
Se konsa, ki se ka baz nou an.
Yon fwa ranje yo se nan gwosè 1, Lè sa a, nou sispann ak division a nan mwatye.
>> Kounye a ki sa nou fè ak sa a?
Nou fini sa a pral tou kraze desann nan 8, 23, 42, ak 108.
Se konsa, kounye a ke nou ap nan pwen sa a, kounye a etap de nan sòt unifye se jis fusion pè sou lis yo.
Se konsa, nou vle rantre sa yo. Nou jis rele rantre.
Nou konnen unifye ap retounen sa yo nan Ranje lòd.
4, 15.
Koulye a, nou vle rantre sa yo, li ki pral retounen yon lis ki gen sa yo ki nan Ranje lòd,
16, 50.
Nou rantre sa yo - Mwen pa ka ekri - 8, 23 ak 42, 108.
Se konsa, nou gen pè uni yon fwa.
Koulye a, nou jis rantre ankò.
Remake chak nan sa yo bay lis se Klase nan tèt li,
ak Lè sa a, nou ka jis rantre sa yo bay lis yo ka resevwa yon lis ki gen yon gwosè 4 ki se Klase
ak rantre sa yo bay lis de yo ka resevwa yon lis ki gen yon gwosè 4 ki se Klase.
Epi finalman, nou ka rantre sa yo bay lis de nan gwosè 4 yo jwenn youn lis ki gen yon gwosè 8 ki se Klase.
Se konsa, yo wè ke sa a se an jeneral n n boutèy demi lit, nou deja wè unifye se lineyè,
Se konsa, lè nou ap fè fas ak fusion sa yo, se konsa tankou pri an jeneral nan unifye
pou de sa yo bay lis se jis 2 paske -
Oswa byen, li la O nan n, men n isit la se jis eleman sa yo 2, kidonk li a 2.
Ak sa yo 2 yo pral 2 ak sa yo 2 yo pral 2 ak sa yo 2 yo pral 2,
se konsa atravè tout nan melanje sa yo ke nou bezwen fè, nou fini fè n.
Tankou 2 + 2 + 2 + 2 se 8, ki se n,
Se konsa se pri a Fusion nan sa a seri n.
Lè sa a, menm bagay la isit la.
Nou pral rantre sa yo 2, Lè sa a, sa yo 2, ak endividyèlman sa a unifye pral pran kat operasyon yo,
sa a unifye pral pran kat operasyon yo, men yon lòt fwa ankò, ant tout sa yo,
nou fini Fusion n bagay total, e konsa etap sa a pran n.
Se konsa, chak nivo pran eleman n ap fizyone.
>> Ak konbyen nivo ki genyen?
Nan chak nivo, etalaj nou ap grandi pa gwosè 2.
Mwen ranje nou yo se nan gwosè 1, isit la yo ap nan gwosè 2, isit la yo ap nan gwosè 4,
epi finalman, yo ap nan gwosè 8.
Se konsa, depi li double pwensip, gen pwal gen yon total de boutèy demi lit n nan nivo sa yo.
Se konsa, avèk boutèy demi lit n nivo, chak nivo endividyèl pran n operasyon total,
nou jwenn yon boutèy demi lit n n algorithm.
Kesyon?
Èske moun deja fè pwogrè sou kòman yo aplike sa a?
Èske nenpòt moun ki deja nan yon eta kote mwen ka jis rale moute kòd yo?
Mwen ka bay yon minit.
Sa a yon sèl ki pral yo dwe dire pi lontan.
Mwen trè rekòmande rive ankò -
Ou pa oblije fè rkursyon pou unifye
paske yo fè rkursyon pou fizyone, w ap ale nan dwe pase yon pakèt moun sou gwosè diferan.
Ou kapab, men li la anmèdan.
Men, rkursyon pou sòt tèt li se trè fasil.
Ou jis literalman rele sòt sou mwatye agoch, sòt sou mwatye dwat. Oke.
Nenpòt moun ki gen bagay mwen ka rale moute ankò?
Oswa lòt moun Mwen pral ba yon minit.
Oke.
Nenpòt moun ki gen yon bagay nou ka travay avèk?
Oswa lòt moun nou pral jis travay avèk sa a ak Lè sa a, elaji soti nan la.
>> Nenpòt moun ki gen plis pase sa a ke mwen ka rale moute?
[Elèv] Yeah. Ou ka rale moute m '. >> Tout dwa.
Wi!
[Elèv] Te gen yon anpil nan kondisyon yo. >> Oh, tire. Èske ou ka -
[Elèv] mwen gen pou konsève pou li. >> Yeah.
Se konsa, nou te fè sa fè unifye la separeman.
Oh, men li la pa tèlman move.
Oke.
Se konsa, sòt se tèt li jis rele mergeSortHelp.
Eksplike nou kisa mergeSortHelp fè.
[Elèv] MergeSortHelp bèl anpil fè de etap sa yo prensipal yo,
ki se yo sòt chak mwatye nan etalaj la epi lè sa a rantre tou de peyi yo.
[Bowden] Oke, kidonk, ban m 'yon dezyèm fwa.
Mwen panse ke sa a - >> [elèv] mwen bezwen -
Yeah. Mwen manke yon bagay.
Nan fizyone, Mwen reyalize ke mwen bezwen yo kreye yon etalaj nouvo
paske mwen pa ta ka fè l 'nan plas. >> Wi. Ou pa kapab. Kòrèk.
[Elèv] Se konsa, mwen kreye yon etalaj nouvo.
Mwen bliye nan fen rantre re chanje-.
Oke. Nou bezwen yon etalaj nouvo.
Nan sòt fizyone, sa a se prèske toujou vrè.
Yon pati nan pri a nan yon algorithm pi bon tan-ki gen bon konprann
se prèske toujou ki bezwen sèvi ak yon ti jan pi plis memwa.
Se konsa, isit la, pa gen pwoblèm ki jan ou fè rantre sòt,
ou ta inevitableman bezwen sèvi ak kèk memwa siplemantè.
Li oswa li te kreye yon etalaj nouvo.
Lè sa a, ou di nan fen a nou jis bezwen yon kopi nouvo etalaj nan etalaj orijinal la.
[Elèv] Mwen panse ke se konsa, yeah.
Mwen pa konnen si ki travay an tèm de konte pa referans oswa kèlkeswa sa -
Yeah, li pral travay. >> [Elèv] Okay.
Eske ou te eseye kouri sa a? >> [Elèv] Non, pa ankò. >> Okay.
Eseye kouri l ', li Lè sa a, mwen pral pale sou sa pou yon dezyèm fwa.
[Elèv] mwen bezwen gen tout prototip yo fonksyon ak tout bagay, menm si, dwa?
Fonksyon prototip yo. Oh, ou vle di tankou - Wi.
Triye ap rele mergeSortHelp.
>> Se konsa, nan lòd pou sòt yo rele mergeSortHelp, mergeSortHelp yo dwe swa yo te defini
anvan sòt oswa nou jis bezwen pwototip la. Jis kopye epi keratin sa.
Ak Menm jan tou, mergeSortHelp ap rele fizyone,
men unifye pa te defini ankò, pou nou ka jis kite mergeSortHelp konnen
ki se sa ki rantre ki pral sanble, epi ki nan sa.
Se konsa, mergeSortHelp.
Nou gen yon pwoblèm isit la kote nou pa gen okenn ka baz.
MergeSortHelp se repetitif, se konsa nenpòt fonksyon repetitif
ki pral bezwen kèk sòt de ka baz konnen kilè pou w sispann recursive rele tèt li.
Ki sa ki ka baz nou an pral fè isit la? Yeah.
[Elèv] Si gwosè a se 1 an? >> [Bowden] Wi.
Se konsa, tankou nou te wè dwa a, nou te sispann ranje divize
yon fwa nou ale nan ranje nan gwosè 1, ki inevitableman yo Ranje tèt yo.
Se konsa, si gwosè egal 1, nou konnen se etalaj la deja klase,
pou nou ka jis retounen.
>> Avi sa a, se anile, donk nou pa retounen anyen patikilye, nou jis retounen.
Oke. Se konsa, sa a, se ka baz nou an.
Mwen devine ka baz nou an ta ka tou si nou rive yo dwe fusion yon etalaj de gwosè 0,
nou pwobableman vle sispann nan kèk pwen,
pou nou ka jis di gwosè mwens pase 2 oswa mwens pase oswa egal a 1
pou ke sa a ap travay pou nenpòt ki etalaj kounye a.
Oke.
Se konsa, sa a, se ka baz nou an.
Koulye a, ou vle mache nou nan unifye?
Ki sa tout ka sa yo vle di?
Up isit la, nou ap jis ap fè lide la menm, - nan
[Elèv] mwen bezwen yo dwe pase gwosè ak tout apèl yo avèk yo mergeSortHelp.
Mwen te ajoute gwosè kòm yon prensipal plis epi li pa la, tankou gwosè / 2.
[Bowden] Oh, gwosè / 2, gwosè / 2. >> [Elèv] Yeah, epi tou li nan fonksyon ki pi wo a kòm byen.
[Bowden] isit la? >> [Elèv] Jis gwosè. >> [Bowden] Oh. Size, gwosè? >> [Elèv] Yeah.
[Bowden] Okay.
Kite m 'panse ke pou yon dezyèm fwa.
nou kouri antre nan yon pwoblèm?
Nou toujou ap trete bò gòch la kòm 0. >> [Elèv] No
Sa a se sa ki mal tou. Sorry. Li ta dwe kòmanse. Yeah.
[Bowden] Okay. Mwen renmen sa pi byen.
Ak yon fen. Oke.
Se konsa, kounye a ou vle mache nou nan unifye? >> [Elèv] Okay.
Mwen jis mache nan sa a etalaj nouvo ke mwen te kreye.
Gwosè li se gwosè a nan pòsyon ki pou etalaj la ke nou vle yo Ranje
ak ap eseye jwenn eleman a ke mwen ta dwe mete nan etap la etalaj nouvo.
Se konsa, fè sa, premye mwen tcheke si mwatye nan gòch nan etalaj la kontinye ap gen nenpòt ki plis eleman,
epi si li fè sa pa, Lè sa a, ou ale desann nan ki kondisyon lòt moun, ki jis di
oke, sa yo dwe nan etalaj nan dwa yo, epi nou pral mete sa nan endèks la aktyèl la newArray.
>> Lè sa a, otreman, mwen tcheke si yo bò dwat la etalaj la tou fini,
nan ka sa a mwen jis mete nan bò gòch li.
Sa pa ta ka aktyèlman ap nesesè. Mwen pa si.
Men, de tout fason, de lòt chèk la Kilès nan de a ki pi piti nan bò gòch la oswa dwa a.
Epi tou li nan chak ka, mwen incrementing kèlkeswa sa ki kontneur mwen kantite.
[Bowden] Okay.
Ki sanble bon.
nenpòt moun ki gen kòmantè oswa enkyetid oswa kesyon?
Se konsa, kat ka yo ke nou gen yo pote bagay sa yo nan jis ke yo te - oswa li sanble senk -
men nou dwe konsidere si gen etalaj gòch la kouri soti nan bagay sa yo nou bezwen fizyone,
si etalaj nan dwa kouri soti nan bagay sa yo nou bezwen rantre -
Mwen lonje dwèt nan pa gen anyen.
Se konsa, si etalaj gòch la kouri soti nan bagay sa yo oswa yo te etalaj nan dwa kouri soti nan bagay sa yo.
Moun sa yo ki se de ka.
Nou menm tou nou bezwen ka a trivial nan si wi ou non bagay la bò gòch se mwens pase sa ki dwat.
Lè sa a, nou vle chwazi bagay la bò gòch.
Moun sa yo se ka yo.
Se konsa, sa a te dwat, pou ki nan sa.
Etalaj kite. Li nan 1, 2, 3. Oke. Se konsa, yeah, sa yo se bagay sa yo kat nou ta ka vle fè.
Epi nou pa pral ale sou plis pase yon repete solisyon an.
Mwen pa ta rekòmande -
Rantre sòt ki se yon egzanp yon fonksyon ki se tou de se pa ke repetitif,
li pa fasil fè li ke repetitif,
men tou li pa trè fasil a fè li repete.
Sa a se trè fasil.
Sa a egzekisyon sòt fizyone,
fizyone, pa gen pwoblèm sa ou fè sa, w ap ale nan bati unifye.
>> Se konsa, rantre sòt bati sou tèt unifye recursive se jis liy sa yo twa.
Iterativman, li se plis annwiyeu e plis difisil yo reflechi sou.
Men, remake ke se pa ke repetitif depi mergeSortHelp - lè li rele tèt li -
li toujou bezwen fè bagay sa yo apre sa a retounen apèl repetitif.
Se konsa, sa a ankadreman chemine yo dwe kontinye egziste menm apre w rele sa a.
Lè sa a, lè w rele sa a, ankadreman an chemine yo dwe kontinye egziste
paske menm apre sa rele, nou toujou bezwen rantre.
Epi li se nontrivial fè sa-a ke repetitif.
Kesyon?
Tout dwa.
Se konsa, pral tounen nan sòt - oh, gen nan de bagay sa yo mwen vle montre. Oke.
Ale tounen nan sòt, nou pral fè sa byen vit.
Oswa rechèch. Triye? Triye. Yeah.
Ale tounen nan kòmansman yo nan zèl.
Nou vle kreye yon algorithm ki kalite etalaj la lè l sèvi avèk nenpòt ki algorithm
nan O n.
Se konsa, kouman sa a posib? nenpòt moun ki gen nenpòt ki sòt de -
Mwen te diskite anvan an -
Si nou ap sou yo amelyore, sòti n boutèy demi lit n O nan n,
nou yo te amelyore algorithm nou an tan-gen bon konprann,
ki vle di ki sa nou pral bezwen fè pou fè moute pou sa?
[Elèv] Espas. >> Yeah. Nou ap pral lè l sèvi avèk plis espas.
Epi li pa menm jis plis espas, li nan espas exponentielle plis.
Se konsa, mwen panse ke sa a ki kalite algorithm se yon bagay pseudo, pseudo polynom -
pseudo - Mwen pa ka sonje. Pseudo yon bagay.
Men, li la paske nou bezwen sèvi ak espas tèlman
ke sa a se possible, men se pa reyalis.
>> Ak ki jan nou reyalize sa a?
Nou ka reyalize sa a si nou garanti ke nenpòt eleman patikilye nan etalaj la
se pi ba a yon gwosè a sèten.
Se konsa, kite yo jis di ke gwosè se 200,
nenpòt eleman nan yon etalaj se pi ba a gwosè 200.
Ak sa a se aktyèlman trè reyalis.
Ou ka trè fasil gen yon etalaj ke ou konnen tout bagay nan li
a pwal mwens pase kèk nimewo.
Renmen si w gen kèk vektè absoliman masiv oswa yon bagay
men ou konnen tout bagay a pwal ant 0 ak 5,
Lè sa a, li la pral fè siyifikativman pi vit fè sa.
Apre yo fin mare a sou nenpòt ki nan eleman yo se 5,
kidonk sa a mare, se sa ki konbyen memwa w ap ale nan dwe lè l sèvi avèk.
Se konsa, mare la se 200.
Nan teyori gen se toujou yon mare depi yon nonb antye relatif kapab fèt sèlman jiska 4 milya dola,
men sa a ireyèl depi lè sa a nou ta dwe lè l sèvi avèk espas
sou lòd la nan 4 milya dola. Se konsa, ke a ireyèl.
Men, isit la nou pral di mare nou an, se 200.
Jwe fent la ap fè l 'nan O nan n se nou fè yon lòt etalaj rele nan yo konsidere gwosè mare l'.
Se konsa, aktyèlman, sa a se yon chemen kout pou - Mwen aktyèlman pa konnen si rezone sa a.
Men, nan GCC omwen nan anpil - rezone I'm asepte fè li twò -
sa a pral jis inisyalize etalaj nan tout yo dwe 0s.
Se konsa, si mwen pa vle fè sa, Lè sa a, mwen te kapab fè pou separeman (Int mwen = 0;
mwen <'mare, mwen + +) ak konte [mwen] = 0;
Se konsa, kounye a tout bagay se inisyalizèd a 0.
Mwen repekte sou etalaj m 'yo,
ak sa m ap fè la a mwen konte kantite chak - Ann al desann isit la.
Nou gen 4, 15, 16, 50, 8, 23, 42, 108.
Sa mwen ap konte se nimewo a nan evènman nan chak nan sa yo eleman.
Se pou nou aktyèlman ajoute yon koup plis nan isit la ak kèk either.
Se konsa, valè a nou gen isit la, valè sa a nan a pwal etalaj [mwen].
Se konsa, Val te kapab 4 oswa 8 oswa kèlkeswa sa.
Epi, koulye a mwen konte konbyen nan ki valè mwen te wè,
Se konsa konte [Val] + +;
Apre sa, konte a pral sanble yon bagay tankou 0001.
Se pou nou fè konte [Val] - mare l '+ 1.
>> Koulye a, sa se sèlman nan kont pou lefèt ke nou ap kòmanse soti nan 0.
Se konsa, si 200 a pwal nimewo pi gwo nou an,
Lè sa a, 0 a 200 se 201 bagay sa yo.
Se konsa, konte, li pral gade tankou 00001 paske nou gen yon sèl 4.
Lè sa a, n ap gen 0001 kote nou pral gen yon 1 nan endèks la 8yèm nan konte.
Nou pwal genyen yon 2 nan endèks la 23rd nan konte.
Nou pwal genyen yon 2 nan endèks la 42nd nan konte.
Se konsa, nou ka sèvi ak konte.
Se konsa, num_of_item = konte [mwen].
Se konsa, si num_of_item se 2, sa vle di nou vle insert 2 nan nimewo a mwen
nan Ranje etalaj nou an.
Se konsa, nou bezwen kenbe tras nan ki jan lwen nou se nan etalaj la.
Se konsa, = endèks 0.
Etalaj - Mwen pral jis ekri li.
Counts -
etalaj [endèks + +] = mwen;
Se ke sa m 'vle? Mwen panse ke sa a, se sa m 'vle.
Wi, sa a sanble bon. Oke.
Se konsa, tout moun konprann ki sa bi pou yo etalaj konte mwen, se yon?
Li se konte kantite evènman nan chak nan nimewo sa yo.
Lè sa a, mwen iteration sou ki etalaj konte,
ak pozisyon nan on nan etalaj la konte
se nimewo a nan mwen an ki ta dwe parèt nan Ranje etalaj m 'yo.
Se poutèt sa konte nan 4 a pwal 1
ak konte nan 8 a pwal 1, konte nan 23 a pwal 2.
Se konsa, lè sa a jan anpil nan yo mwen vle insert nan Ranje etalaj m 'yo.
Lè sa a, mwen jis fè sa.
Mwen mete num_of_item mwen an nan Ranje etalaj m 'yo.
>> Kesyon?
Se konsa, ankò, sa a se tan lineyè depi nou yo se jis iteration sou sa a yon fwa,
men li la tou lineyè nan sa ki nan nimewo sa a k ap pase yo,
ak se konsa li lou depann de sa ki mare-w la.
Ak yon mare nan 200, ki nan pa tèlman move.
Si mare ou a pwal 10,000, Lè sa a, sa a, se yon ti kras pi mal,
Men, si mare ou a pral nan gen 4 milya dola, ki nan konplètman ireyèl
ak sa a etalaj ki pral gen yo dwe nan gwosè 4 milya dola, ki se ireyèl.
Se konsa, sa a, se sa. Kesyon?
[Fèbl repons elèv] >> Okay.
Mwen reyalize yon lòt bagay lè nou te ale atravè tout.
Mwen panse ke pwoblèm nan te nan a Lucas ak pwobableman chak yon sèl nou te wè.
Mwen konplètman bliye.
Bagay la sèlman mwen te vle fè kòmantè sou se ke lè w ap fè fas ak bagay sa yo tankou endis yo,
ou pa janm reyèlman wè sa a lè w ap ekri yon pou riban,
men teknikman, nenpòt lè w ap fè fas ak sa yo endis yo,
ou ta dwe bèl anpil toujou fè fas ak nonm antye relatif siye.
Rezon ki fè la pou sa a se lè w ap fè fas ak siyen nonm antye yo,
pou si ou gen 2 siyen nonm antye relatif, epi ou ajoute yo ansanm
ak yo fini twò gwo, lè sa a ou fini ak yon chif negatif.
Se konsa, se sa ki debòde nonb antye relatif se.
>> Si m 'ajoute 2 milya dola ak 1 milya dola, mwen fini ak milya dola negatif 1.
Sa a ki jan nonm antye relatif travay sou òdinatè.
Se konsa, pwoblèm nan ak lè l sèvi avèk -
Sa a se amann eksepte si ba k ap pase yo 2 milya dola ak moute k ap pase yo 1 milya dola,
Lè sa a, sa a se pral negatif 1 milya dola ak Lè sa a, nou pral divize ki pa 2
ak fini ak milyon dola negatif 500.
Se konsa, sa a se sèlman yon pwoblèm si ou rive dwe chèche nan yon etalaj
nan dè milya de bagay sa yo.
Men, si + ba moute k ap pase nan debòde, lè sa a sa a, se yon pwoblèm.
Osito ke nou fè yo siye, lè sa a 2 milya dola plis 1 milya dola se 3 milya dola.
3 milya dola divize pa 2 se 1.5 milya dola.
Se konsa, le pli vit ke yo ap siye, tout bagay la bon nèt.
Se konsa, ki la tou yon pwoblèm lè w ap ekri ou pou pasan,
ak aktyèlman, li pwobableman fè li otomatikman.
Li pral aktyèlman jis rele nan ou.
Se konsa, si nimewo sa a se twò gwo yo dwe nan jis nonb antye relatif yon men li ta anfòm nan yon nonb antye relatif siye,
li pral rele nan ou, se konsa ke poutèt sa ou pa janm reyèlman kouri antre nan pwoblèm nan.
Ou ka wè yon endèks pa janm a pwal negatif,
epi konsa lè w ap iteration sou plis pase yon etalaj,
ou ka prèske toujou di siye int mwen, men ou pa vrèman gen a.
Tout bagay ap mache nan travay bèl anpil jis kòm byen.
Oke. [Murmura] Ki sa ki lè li ye?
Bagay la pase mwen te vle montre - epi mwen pral jis fè li vrèman rapid.
Ou konnen ki jan nou te # defini pou nou ka # defini MAX kòm 5 oswa yon bagay?
Pa kite nan fè MAX. # Defini mare l 'kòm 200. Sa a ki sa nou te fè sa anvan.
Ki defini yon konstan, ki se jis pral dwe kopye ak kole
tout kote nou rive ekri mare l '.
>> Se konsa, nou ka aktyèlman fè plis ak # defini.
Nou ka # defini fonksyon.
Yo ap pa reyèlman fonksyon, men nou pwal rele yo fonksyon.
Yon egzanp ta kapab yon bagay tankou MAX (x, y) defini kòm (x <y y:? X). Oke.
Se konsa, ou ta dwe jwenn itilize sentaks operatè tèrsyèr,
men se x mwens pase y? Retounen y, lòt bagay retounen x.
Se konsa, ou ka wè ou ka fè sa a yon separe fonksyon,
ak fonksyon an ta ka tankou bouleen MAX pran 2 agiman, retounen sa a.
Sa a se youn nan yo menm ki mwen wè ki pi komen fè tankou sa a. Nou rele yo makro.
Sa a se yon macro.
Sa a se jis sentaks la pou li.
Ou ka ekri yon macro fè tou sa ou vle.
Ou souvan wè makro pou debogaj printfs ak lòt bagay.
Se konsa, yon kalite printf, gen konstan espesyal nan C tankou souliye LINE souliye,
2 insist LINE souliye,
ak gen nan tou mwen panse ke 2 insist fonksyone. Ke sa ta kapab li. Yon bagay tankou sa.
Moun sa yo ki bagay sa yo pral ranplase ak non an nan fonksyon an
oswa nimewo a nan liy lan ke w ap sou.
Anpil fwa, ou ekri debogaj printfs ki desann isit la mwen te kapab Lè sa a, jis ekri
Dbug epi li pral enprime nimewo a liy ak fonksyon ke mwen rive yo dwe nan
ke li rankontre ki deklarasyon dbug.
Epi ou ka tou enprime lòt bagay.
Se konsa, yon sèl bagay ou ta dwe gade deyò pou se si mwen rive # defini DOUBLE_MAX
kòm yon bagay tankou 2 * y ak 2 * x.
Se konsa, pou rezon sa a, ou rive fè sa anpil.
Se konsa, fè l 'yon macro.
Sa a se aktyèlman kase.
Mwen ta rele l 'pa fè yon bagay tankou DOUBLE_MAX (3, 6).
Se konsa, sa yo dwe retounen?
[Elèv] 12.
Wi, 12 yo ta dwe tounen, ak 12 yo voye li tounen.
3 vin ranplase pou x, 6 vin ranplase pou y, epi nou retounen 2 * 6, ki se 12.
Kounye a ki sa sou sa a? Kisa yo ta dwe tounen?
[Elèv] 14. >> Idealman, 14.
Pwoblèm lan se ke kouman regle defini travay, sonje ke se byen yon kopi literal ak keratin
nan tout bagay bèl anpil konsa, sa ki sa a ki pral kapab entèprete kòm
se 3 mwens pase 1 plis, 6, 2 fwa 1 plis, 6, 2 fwa 3.
>> Se konsa, pou rezon sa a ou prèske toujou vlope tout bagay nan parantèz.
Nenpòt varyab ou prèske toujou vlope nan parantèz.
Gen ka kote ou pa bezwen, tankou mwen konnen ke mwen pa bezwen fè sa isit la
paske mwens pase se bèl anpil toujou jis ale nan travay,
byenke ki pa ta ka menm dwe vre.
Si gen yon bagay ridikil tankou DOUBLE_MAX (1 == 2),
Lè sa a, ki nan pwal jwenn ranplase ak 3 mwens pase 1 egal egal 2,
e konsa Lè sa a, li la pral fè 3 mwens pase 1, ke 2 egal,
ki se pa sa nou vle.
Se konsa, yo nan lòd yo anpeche okenn operatè priyorite pwoblèm,
toujou vlope nan parantèz.
Oke. Epi sa a, l ', 5:30.
Si w gen nenpòt kesyon sou pset a, fè nou konnen.
Li ta dwe plezi, ak edisyon an aker tou se pi plis reyalis
pase edisyon an aker nan la ane pase a, pou nou espere ke yon anpil nan ou eseye li.
Ane pase a te trè akablan yo.
>> [CS50.TV]