>> [MUSIC nagpe-play]
>> ANDI PENG: Maligayang pagdating sa week 3 ng section.
Salamat, guys, para sa lahat ng mga darating na ito nang mas maaga ang oras ng simula sa araw na ito.
Mayroon kaming isang magaling, maliit matalik na ngayon.
Kaya sana kami ay kumuha sa matapos, marahil, maaga,
Medyo maaga ngayon.
Kaya mabilis, ilan lang anunsyo para sa agenda ngayong araw.
Bago namin simulan, hindi namin pagpunta sa pumunta lamang sa paglipas ng
ilang maikling logistical isyu, pset katanungan, debrief, mga bagay na tulad ng.
At pagkatapos ay makikita namin sumisid karapatan sa.
Gagamitin namin ang isang debugger tinatawag GDB sa simulan debunking ang aming code, na si David
ipinaliwanag sa lecture ng ibang mga araw.
Kami ay pumunta sa ibabaw ng apat na mga uri ng mga uri.
Kami ay pumunta sa paglipas ng mga ito medyo mabilis dahil ang mga ito pretty intensive.
Ngunit alam na ang lahat ng mga slide at source code ay palaging online.
Kaya huwag mag-atubiling, sa iyong pagbasa, upang bumalik at tingnan kung iyon.
>> Kami ay pumunta sa pamamagitan ng asymptotic pagtatanda, na
ay lamang ng isang magarbong paraan na sabihing "runtimes,"
kung saan mayroon kaming ang malaking O, kung saan David ipinaliwanag sa panayam.
At mayroon din kaming Omega, na ay ang mas mababang nakatali runtime.
At kami na makipag-usap ng kaunti pang sa malalim tungkol sa kung paano ang mga trabaho.
At sa wakas, kami ay pumunta sa paglipas ng binary paghahanap, dahil ang isang pulutong ng sa iyo na nag
glanced sa iyong psets marahil alam na iyon ay isang katanungan na sa iyong pset.
Kaya ikaw ay masaya ang lahat na sumasaklaw namin ito ngayon.
>> At sa wakas, sa bawat iyong mga feedback section, ako talaga
kaliwa tungkol sa 15 minuto sa sa dulo upang pumunta lamang sa ibabaw
Logistics ng pset3, anumang mga katanungan, marahil isang piraso ng guidance, kung ikaw ay,
bago namin simulan ang programming.
Kaya sabihin subukan upang makakuha ng sa pamamagitan ipaalam ang materyal medyo mabilis.
At pagkatapos ay maaari naming gumastos ng ilang oras pagkuha ng higit pang mga tanong para sa pset.
SIGE.
>> Mabilis, kaya lamang ng ilang announcements bago namin simulan ang araw na ito.
Una, maligayang pagdating sa paggawa ng ito sa pamamagitan ng dalawang ng iyong psets.
Kinuha ko ang isang pagtingin sa your-- oo, sabihin makakuha ng isang ikot ng papuri para sa isa.
Sa totoo lang, ako ay talagang, talagang impressed.
Gradong ko ang unang pset para sa iyo guys noong nakaraang linggo at ang iyong guys ay hindi kapani-paniwala.
>> Style ay sa puntong bukod sa ilang mga komento.
Tiyakin na ikaw ay palaging pagkomento sa iyong code.
Ngunit ang iyong psets ay sa punto.
At panatilihin ito up.
At ito ay mabuti para sa mga baytang na makita na ikaw guys ay paglagay
sa mas maraming pagsisikap sa iyong estilo at ang iyong mga disenyo sa iyong code
na nais namin para sa iyo na makita.
Kaya ako pagpasa kasama ang aking pasasalamat para sa ang magpahinga ng ang TAS.
>> Subalit may mga ilang mga katanungan debrief
Gusto ko lang pumunta sa paglipas na gagawing parehong aking buhay
at ng maraming iba pang mga TAS 'buhay ng kaunti mas madali.
Una, napansin ko na ito nakaraang week-- kung ilan sa inyo
ay tumatakbo check50 sa ang iyong code bago mo isumite?
SIGE.
Kaya lahat ng tao ay dapat na ginagawa check50, because-- isang secret-- namin talagang
tumakbo check50 bilang bahagi ng aming kawastuhan script para sa pagsubok ang iyong mga code.
Kaya kung ang iyong code ay hindi pagtupad check50, sa lahat ng posibilidad,
marahil ito ay pagpunta sa mabibigo ang aming check rin.
Minsan mo guys May karapatan mga sagot.
Tulad ng, sa sakim, ang ilan sa ikaw ay may karapatan na numero,
i-print out mo lamang ng ilang dagdag na mga bagay-bagay.
At na ang dagdag na mga bagay-bagay talagang nabigo ang check,
dahil ang computer ay hindi talaga alam kung ano ito ay naghahanap para sa.
At kaya ito ay tatakbo lamang sa pamamagitan ng, makita na ang iyong output ay hindi
tumutugma sa kung ano ang inaasahan namin ang sagot upang maging, at markahan ito ay mali.
>> At alam ko na nangyari sa ang ilan sa inyong mga kaso sa linggong ito.
Kaya nagpunta ako sa likod at manu-mano nang muli code ng lahat.
Sa hinaharap bagaman, mangyaring, mangyaring tiyakin
na ikaw ay nagpapatakbo ng check 50 sa iyong code.
Dahil ito ay uri ng isang sakit para sa TA na kailangang bumalik at mano-manong regrade
bawat solong pset para sa bawat single, maliit na hindi nakuha ng pagkakataon.
Kaya ako ay hindi mag-alis ng anumang mga puntos.
Sa tingin ko kinuha ko off siguro isa o dalawang para sa disenyo.
Sa hinaharap bagaman, kung ikaw ay nanghihina check50,
puntos dadalhin off para sa kawastuhan.
>> Higit pa rito, psets ay dahil Biyernes sa tanghali.
Sa tingin ko ay may isang pitong minutong late panahon ng palugit na bigyan ka namin.
Per Harvard oras, sila ay pinapayagan na pitong minuto huli na ang lahat.
Kaya dito sa Yale, bibigyan namin ng sumunod pati na rin sa mga iyon.
Ngunit medyo marami, sa 12:07, kung ang iyong pset ay hindi sa,
ito ay pagpunta sa ay minarkahan bilang late.
At kaya habang ito ay minarkahan bilang huli, ang TA-- Ako
pagpunta pa rin na pagmamarka iyong psets.
Kaya makikita mo pa rin ang lumitaw ang isang grado.
Gayunpaman, alam na sa sa katapusan ng semestre,
lahat ng late psets ay lamang ay awtomatikong zeroed sa pamamagitan ng mga computer.
>> Ginagawa namin ito para sa dalawang kadahilanan.
One, minsan na nakukuha namin paumanhin, tulad ng paliwanag dean,
sa susunod na hindi ko alam tungkol sa pa.
Kaya gusto naming makasiguro na kami ay pagmamarka ang lahat ng bagay kung sakali, tulad ng, ako
nawawala excuse isang dean.
At pangalawa, panatilihin sa isip, maaari mo pa ring
drop isa pset na ay may ganap na puntos saklaw.
At kaya gusto namin na grade ang lahat ng iyong psets lamang
tiyakin na ang iyong saklaw ng doon at sinusubukan ang mga ito.
Kaya kahit na ito ay huli, makikita mo pa rin makakuha ng credit para sa saklaw ng mga puntos, sa tingin ko.
>> Kaya moral ng kuwento ay, gumawa Siguraduhin na ang iyong psets ay sa on-time.
At kung sila ay hindi sa on-time, alam na ito ay hindi mahusay.
Oo, bago ko ilipat sa, ay hindi magkaroon ng kahit sino anumang mga katanungan tungkol pset feedback?
Oo.
>> Madla: sabihin mo ba kami maaaring i-drop ang isa sa mga psets?
>> ANDI PENG: Oo.
Kaya may siyam psets pangkalahatang sa kabuuan ng semestre.
At kung mayroon kang scope points-- kaya scope ay makatarungan,
medyo marami, ikaw ay sinusubukan ang Ang problema, ikaw ay paglalagay sa oras,
ikaw ay nagpapakita na na sa iyo nagpakita nabasa mo na ang spec.
Iyan ay medyo magkano ang saklaw.
At kung ikaw ay tuparin saklaw ng mga puntos, kami ay
maaaring i-drop ang pinakamababang isa sa labas ng buong saklaw.
Kaya na sa iyong kalamangan sa kumpletuhin at subukan ang bawat pset.
>> Kahit upload-- kung wala sa mga ito sa trabaho, i-upload ang mga ito lahat.
At pagkatapos ay gagamitin namin inaasahan namin na maaaring magbibigay sa iyo ang ilan sa mga puntos pabalik.
Cool.
Anumang iba pang mga katanungan?
Great.
>> Pangalawa, opisina hours-- ng ilang mabilis na mga tala tungkol sa mga oras ng opisina.
Kaya una, dumating ng maaga sa linggo.
Walang isa ay kailanman sa oras ng opisina tuwing Lunes.
Christabel ang dumating sa oras ng opisina kagabi.
Oo, Christabel.
At ano ang mayroon kami sa opisina oras kagabi, Christabel?
>> Madla: Nagkaroon kami ng ice cream.
>> ANDI PENG: So na tama, kami ay nagkaroon ng ice cream sa oras ng opisina kagabi.
Habang hindi ko pangako mo na kakailanganin naming ice cream sa oras ng opisina
bawat linggo, kung ano ang maaari kong pangako sa iyo ay na magkakaroon ng makabuluhang isang
mas mahusay na mag-aaral sa TA ratio.
Tulad ng legit, ito ay tulad ng tatlong sa isa.
Sapagkat, kaibahan na may Huwebes, nakuha mo na ang tungkol sa 150
talagang pagkabalisa sa mga bata at walang ice cream.
At ito lang ang hindi produktibong para sa sinuman.
Kaya moral ng kuwento ay, dumating nang maaga sa mga oras ng opisina at magandang bagay
mangyayari.
>> Gayundin, dumating handa upang magtanong.
Alam mo?
Hindi alintana ng kung ano ang TAS, ako mag-isip, ay sinasabi,
ay nakakakuha kami ng ilang mga mag-aaral na papasok sa Huwebes sa, tulad ng, 10:50
hindi pagkakaroon ng basahin ang spec pagiging tulad tulungan mo ako, tulungan mo ako.
Sa kasamaang palad sa puntong iyon, may hindi marami ang maaari naming gawin upang makatulong sa iyo.
Kaya mangyaring bumalik sa unang bahagi ng linggo.
Halika maaga sa oras ng opisina.
Halika na handa na magtanong.
Tiyakin na ikaw, tulad ng isang mag-aaral, ay kung saan
kailangan mo upang maging sa gayon na ang Maaaring gabay sa iyo TAS kasama,
na kung saan ay kung ano ang mga oras ng opisina dapat na inilaan para sa.
>> Pangalawa, kaya alam ko na propesor nais na sorpresa sa amin sa mga pagsubok.
Nagkaroon na ako ng isang propesor sa mga tulad ng, yo, sa daan,
tandaan na midterm mayroon ka sa susunod na Lunes.
Oo, hindi ko alam kung tungkol na midterm.
Kaya ako pagpunta upang ma-na TA na nagpapaalala sa inyo ang lahat ng pagsusulit na
0-- dahil, alam mo, hindi namin CS.
Ngayon na kami tapos array, makakakuha ka ng kung bakit ito ay pagsusulit 0, hindi magtatanong 1, eh?
SIGE.
Oh, Nakatanggap ako ng ilang chuckles na ang isa.
SIGE.
>> Kaya pagsusulit 0 ay Oktubre 14 kung ikaw ay nasa section Lunes-Miyerkules
at Oktubre 15 kung ikaw ay nasa ang seksyon Martes-Huwebes.
Ito ay hindi akma para sa sa mga mo sa Harvard
who-- tingin ko makikita mo ang lahat maging pagkuha ng iyong mga pagsusulit sa ika-14.
>> Kaya oo, sa susunod na linggo, kung David, sa panayam, pag-uusapan,
oo, kaya tungkol na pagsusulit sa susunod na linggo, ikaw ang lahat
hindi nagulat dahil ikaw ay dumating sa section
at alam mo na ang iyong quiz 0 ay sa loob ng dalawang linggo.
At kami ay may review session at lahat ng bagay.
Kaya huwag mag-alala tungkol sa pagiging natakot para doon.
Ang anumang mga katanungan before-- anumang mga katanungan sa lahat ng tungkol logistical mga isyu,
pagmamarka, mga oras ng opisina, mga seksyon?
Oo.
>> Madla: Kaya ang pagsusulit ay magiging panahon ng panayam?
>> ANDI PENG: Oo.
Kaya ang pagsusulit, tingin ko, ay 60 minuto na inilaan sa na puwang ng oras
na ikaw lang ang dadalhin sa lecture hall.
Kaya hindi mo na kailangang dumating sa on, tulad ng, ang isang random na 07:00.
Lahat ng ito ay mabuti.
Oo.
Cool.
>> Lahat tama.
Kaya kami ay pagpunta sa ipakilala ang isang konsepto sa iyo
this week na si David ay mayroon na uri ng baliw sa lecture ito nakaraang linggo.
Ito ay tinatawag na GDB.
At kung paano marami sa inyo, habang sa ang mga kurso ng pagsulat ng iyong psets,
napansin ang isang malaking button na nagsasabing "Debug" sa tuktok ng iyong IDE?
SIGE.
Kaya ngayon makikita namin talagang makakuha upang makatuklas ang misteryo ng kung ano na button talagang
ay.
At ginagarantiya ko sa inyo, ito ay isang maganda, magandang bagay.
>> Kaya hanggang ngayon, sa tingin ko mayroong nangyaring dalawang bagay
mga mag-aaral ay karaniwang ginagawa kapag debugging psets.
One, alinman sa mga ito idagdag sa printf () - kaya ang bawat ilang mga linya,
idagdag sila sa isang printf () - oh, kung ano ang mga variable na ito?
Oh, kung ano ang mga variable na ito now-- at ang uri ng iyong nakikita sa paglala
ng iyong mga code na ito ay tumatakbo.
O kids gawin ang ikalawang paraan ay na isulat ang mga ito lamang ang buong bagay
at pagkatapos ay pumunta tulad nito sa dulo.
Sana ito gumagana.
Ginagarantiya ko sa iyo, GDB ay mas mahusay sa pareho ng mga pamamaraan.
Oo.
Kaya ito ay ang iyong bagong pinakamatalik na kaibigan.
Dahil ito ay isang magandang bagay na biswal na nagpapakita sa parehong
kung ano ang iyong code ay ginagawa sa isang tiyak na punto
pati na rin ang kung ano ang lahat ng iyong variable ay dala,
tulad ng kung ano ang kanilang mga halaga ay, sa mga tiyak na punto.
At sa ganitong paraan, maaari mong tunay itakda breakpoints sa iyong code.
Maaari kang magpatakbo ng sa pamamagitan ng linya sa pamamagitan ng linya.
At GDB ay na lang ay para sa mo, ipinapakita para sa iyo,
kung ano ang lahat ng iyong mga variable ay, kung ano ang ginagawa nila,
kung ano ang nangyayari sa code.
At sa paraan, ito ay kaya mas madali upang makita ang
kung ano ang nangyayari sa halip ng printf-ing o pagsusulat ang iyong mga pahayag.
>> Kaya gagawin namin ang isang halimbawa ng ito sa ibang pagkakataon.
Kaya ito ay tila medyo abstract.
Huwag mag-alala, ipapakita namin ang mga halimbawa.
At kaya mahalagang, tatlong pinakamalaking, pinaka-ginagamit na mga pagpapaandar na kailangan mo sa GDB
ay ang Susunod, Tumawid, at Hakbang sa mga pindutan.
Pupunta ako sa tumuloy doon, talaga, ngayon.
>> Kaya maaari makita ka guys lahat na o ang dapat kong mag-zoom in ng kaunti?
Sa likod, maaari mong makita na?
Dapat ko bang mag-zoom in?
Kahit kaunti lang?
OK, cool.
Mayroon kaming pumunta.
SIGE.
>> Kaya ko, dito, ang aking pagpapatupad para sa matakaw.
At habang ang isang pulutong ng mga ka guys sinulat matakaw sa habang loop form-- na
ay isang ganap na katanggap-tanggap na paraan upang gawin it-- isa pang paraan upang gawin ito ay upang i
hatiin sa modulo.
Dahil pagkatapos ay maaari kang magkaroon ng iyong halaga at pagkatapos ay ang iyong mga naiwan.
At pagkatapos ay maaari mo lamang idagdag ang lahat ng ito nang magkasama.
Sinusuportahan ba ng logic ng kung ano ang ako paggawa dito magkaroon ng kahulugan sa lahat ng tao,
bago tayo magsimula?
Medyo?
Cool.
Great.
Ito ay isang medyo sexy piraso ng code, nais kong sabihin.
Tulad ng sinabi ko, David, sa magbigay ng panayam, matapos ang ilang panahon,
Makikita mo ang lahat ay magsisimulang makakita ng code bilang isang bagay na maganda.
At kung minsan kapag nakita mo ang maganda code, ito ay tulad ng isang kahanga-hangang pakiramdam.
>> Kaya gayunpaman, habang ang code na ito ay tunay maganda, ito ay hindi gumagana ng maayos.
Tumakbo ni check50 sa mga ito upang ipaalam sa.
Suriin 50 20-- oop.
2?
Ay na pset2?
Oo.
Oh, pset1.
SIGE.
Kaya tumakbo kami check50.
>> At bilang ay maaaring makita dito sa iyo guys, ito ay bagsak ng ilang mga kaso.
At para sa ilan sa inyo, sa kurso ng paggawa ng iyong hanay ng problema,
ikaw ay tulad ng, ah, bakit hindi ito gumagana.
Bakit ay gumagana ito para sa ilang halaga ngunit hindi para sa iba?
Well, GDB ay pagpunta upang makatulong sa iyo na figure kung bakit ang mga input ay hindi gumagana.
>> SIGE.
Kaya tingnan natin, isa sa mga checks ko ay nanghihina sa check50
ay ang halaga ng 0.41 input.
Kaya na ang mga tamang sagot dapat ay sa pagkuha ay isang 4.
Ngunit sa halip na kung ano ang ako pag-print out ay ang 3-n, na kung saan ay hindi tama.
Patakbuhin lamang ni ito ng mano-mano upang ipaalam sa, lang tiyakin na check50 ay gumagana.
Ni gawin ./greedy Hayaan.
Oops, kailangan kong gumawa ng matakaw.
Mayroon kaming pumunta.
./greedy Now.
>> Magkano ang utang?
Ni gawin 0.41 Hayaan.
And yep, nakikita natin dito na ito ay outputting 3
kapag ang tamang sagot, sa katunayan, ay dapat na 4.
Kaya sabihin ipasok GDB at makita kung paano namin maaaring pumunta tungkol sa pag-aayos ng problemang ito.
>> Kaya ang unang hakbang sa palaging pag-debug ang iyong code
ay upang itakda ang isang breakpoint, o ng isang punto kung saan mo
gusto ang computer o ang debugger upang simulan ang naghahanap sa.
Kaya kung hindi mo talaga malaman kung ano ang iyong problema ay,
kadalasan, ang pangkaraniwang bagay na gusto naming gawin ay itakda ang aming mga breakpoint sa pangunahing.
Kaya kung maaari makita ang mga ito sa iyo guys red button doon,
yep, noon ay ako pagtatakda ng isang breakpoint para sa mga pangunahing pag-andar.
I-click ko na.
>> At pagkatapos ay ako maaaring pumunta ng hanggang sa button aking Debug.
Pindutin ko ang pindutan na iyon.
Hayaan akong mag-zoom back out kung ako.
Mayroon kaming pumunta.
Kaya kami, dito, ang isang panel sa kanan.
Sorry, guys sa likod, ikaw ay hindi talaga makita talagang mahusay.
Ngunit mahalagang, ang lahat ng karapatang ito panel ay ginagawa
ay iingat subaybayan ng parehong mga naka-highlight line, kung saan ay ang linya ng code
na ang computer ay kasalukuyang tumatakbo, pati na rin ang lahat ng iyong mga variable
dito sa baba.
>> Kaya nakuha mo cents, mga barya, n, lahat ng ipinahayag sa iba't-ibang mga bagay-bagay
sa puntong ito.
Huwag mag-alala, dahil kami ay hindi tunay initialize ang mga ito sa anumang mga variable pa.
Kaya sa iyong computer, ang iyong lang ang nakakakita ng computer,
oh, 32,767 ang huling ginamit na mga function ng na puwang ng memory sa aking computer.
At kaya na kung saan cents sa kasalukuyan ay.
Ngunit walang isang beses na tumakbo ang code, dapat itong maging initialize.
>> Kaya sabihin pumunta sa pamamagitan ng, linya sa pamamagitan ng line, kung ano ang nangyayari sa dito.
SIGE.
Kaya dito ay ang tatlong buttons na ako lang naipaliwanag.
Kayo ay may Play, o ang Run function, button, ikaw ay may mga hakbang na button sa loob,
at magkakaroon ka rin ng Hakbang sa button.
At mahalagang, ang lahat ng tatlong mga ang mga ito pumunta lamang sa pamamagitan ng iyong code
at gawin ang iba't-ibang mga bagay-bagay.
>> Kaya kadalasan, kapag kayo ay ang pag-debug, Hindi natin nais na pindutin lang Play,
dahil Play ay lamang tumakbo ang iyong code sa dulo ng mga ito.
At pagkatapos ay sa iyo ay hindi talaga malaman kung ano ang iyong problema
ay maliban kung magtatakda ka ng maramihang breakpoints.
Kung itinakda mo ang maramihang breakpoints, ito ay awtomatikong lamang
tumakbo mula sa isang breakpoint, sa susunod na, sa susunod.
Ngunit sa kasong ito na namin isa lamang na, dahil tayo
nais na trabaho ang aming paraan mula sa tuktok pababa sa ilalim.
Kaya kami ay pagpunta upang huwag pansinin ang pindutan na ngayon para sa mga layunin ng programang ito.
>> Kaya ang Step paglipas ng function lamang mga hakbang sa paglipas ng bawat isang linya
at nagsasabi sa iyo kung ano ang ang computer ay ginagawa.
Ang Hakbang sa function na napupunta sa aktwal na pag-andar
na sa iyong linya ng code.
Kaya halimbawa, tulad ng printf (), iyon ay isang function, right?
Kung Nais kong pisikal na hakbang sa function printf (),
Gusto ko talagang pumunta sa mga piraso ng code na kung saan printf () ay isinulat at makita
kung ano ang nangyayari doon.
>> Ngunit karaniwan, ipinapalagay namin na ang code na bigyan ka namin gumagana.
Ipinapalagay namin ang printf () ay gumagana.
Ipinapalagay namin na GetInt () ay gumagana.
Kaya walang kailangan upang hakbang sa mga pag-andar.
Ngunit kung may mga pag-andar na sinulat mo sa iyong sarili
na nais mong suriin kung ano ang nangyayari,
Gusto mo nais na hakbang sa na function.
>> Kaya ngayon lang kami sa hakbang sa paglipas ng ito piraso ng code.
Kaya sabihin makita.
Oh, i-print, "Oh hai, kung paano maraming pagbabago ang utang? "
Hindi namin pakialam.
Alam namin na ang gumagana, kaya kami na hakbang sa ibabaw nito.
>> Kaya n, na kung saan ay ang aming float na na namin initialized-- o declared--
up sa tuktok, hindi namin ngayon pinapantayan na sa GetFloat ().
Kaya ng hakbang sa ibabaw na ipaalam.
At nakita namin sa ibaba dito, ang programa
ay pagdikta sa akin upang input isang halaga.
Kaya ng input hayaan ang mga halaga na gusto namin upang subukan dito, na kung saan ay 0.41.
Great.
>> Kaya ngayon n-- gagawin mo guys makita dito, sa bottom-- ito ay
stored-- dahil tayo hindi pa bilugan, ito ay
naka-imbak sa mga ito tulad ng mga higanteng float na .4099999996,
na kung saan ay malapit na sapat upang aming mga layunin, sa ngayon, sa 0.41.
At pagkatapos ay makikita namin makita sa susunod, bilang namin patuloy tuntong sa programa,
matapos dito, n ay naging bilugan at cents ay naging 41.
Great.
Upang malaman namin na nagtatrabaho sa aming mga rounding ni.
Alam namin na kami ay may mga tamang bilang ng mga cents,
upang malaman namin na iyon ang hindi talaga ang problema.
>> Kaya patuloy kaming tuntong on sa programang ito.
Pumunta kami dito.
At kaya pagkatapos ito linya ng code, kami ay dapat malaman kung gaano karaming mga quarters namin.
Hakbang namin ang higit sa.
At nakita mo kami, sa katunayan, ay may isa quarter dahil na-awas namin 25
mula sa aming unang halaga ng 41.
At kami ay may 16 kaliwa para sa aming cents.
>> Ba ang lahat maunawaan kung paano ang programa ay tuntong sa pamamagitan ng
at bakit cents naging 16 na ngayon at kung bakit, ngayon, barya ay naging 1?
Lahat ng tao sumusunod na Ay na logic?
Cool.
Kaya bilang ng mga puntong ito, ang working program, di ba?
Alam namin na ito ay ginagawa nang eksakto kung ano ang aming nais ito sa.
At kami ay hindi talaga kailangang i-print out, o, anong
ay cents sa puntong ito, kung ano ang mga barya sa puntong ito.
>> Kami ay patuloy na pagpunta sa pamamagitan ng programa.
Tumawid.
Cool.
Pumunta kami sa paglipas ng dimes.
Great.
Nakita namin na ito ay kinuha off $ 0.10 para sa isang magagamit ng lahat.
At ngayon kami ay may dalawang mga barya.
Tama iyan.
>> Pumunta kami ng mahigit sa pennies at makikita natin na nakuha na iniwan namin sa paglipas ng cents.
Hmm, iyan ay kakaiba.
Up dito sa programa, ako ay dapat sa may bawas aking pennies.
Marahil ko lang ay hindi paggawa na linya sa kanan.
At ay, maaari mong makita ang dito, dahil alam namin
na tayo ay tuntong pamamagitan ng mga linya 32 at 33,
na kung saan ang aming programa hindi wasto nagkaroon variable tumakbo.
Kaya maaari naming tumingin at makita, oh, Ako pagbabawas cents dito,
ngunit hindi ako talaga pagdagdag sa aking barya halaga.
Magdaragdag ako sa cents.
At hindi ko nais upang idagdag sa cents, gusto kong idagdag sa mga barya.
Kaya kung babaguhin namin na sa barya, Nakakuha kami ng isang gumaganang program.
Maaari ko bang patakbuhin check50.
Maaari mo lamang lumabas sa labas ng GDB karapatan dito at pagkatapos ay patakbuhin muli check50.
Hindi ko na lang gawin ito.
Kailangan ko bang gumawa ng matakaw.
0.41.
At dito, ito ay pag-print ang mga tamang sagot.
>> Kaya bilang maaari mong makita ang isang lalaki, GDB ay isang talagang malakas na tool
para kapag kami ay may kaya magkano ang code nangyayari at kaya maraming mga variable
na ito ay mahirap para sa atin, tulad ng isang tao, upang subaybayan.
Ang computer, sa GDB debugger, ay may kakayahan
upang subaybayan ang lahat ng bagay.
Alam ko, sa Visionaire, guys marahil ay maaaring magkaroon ng ilang mga hit segmentation faults
dahil kayo ay tumatakbo sa labas ng hangganan ng iyong array.
Sa halimbawa ng Caesar, na ang kung ano mismo ang naipatupad ko dito.
>> Kaya Nakalimutan ko upang suriin para sa ano ang mangyayari kung ako ay
ay hindi magkakaroon ng dalawang argumento command line.
Katatapos ko lamang ay hindi ilalagay sa check iyon.
At kaya kung nagpatakbo ako Debug-- ako magse-set aking breakpoint mag-right doon.
Tumakbo ako Debug.
>> SIGE.
Oo.
Kaya talaga, GDB ay dapat na may nagsabi sa akin doon
ay isang segmentation fault doon.
Hindi ko alam kung ano ang nangyayari may karapatan, ngunit kapag nagpatakbo ako ng ito,
ito ay gumagana.
Kapag nagpatakbo ka ng mga linya ng code sa pamamagitan ng at GDB baka biglang lang umalis sa iyo,
pumunta up at tingnan kung ano ang pulang error ay.
Makikita ito ang magsasabi sa iyo, hey, ikaw nagkaroon ng segmentation fault,
na nangangahulugan na sinubukan mong i-access space sa isang array na ay hindi umiiral.
Oo.
>> Kaya sa susunod na problema itakda sa linggong ito, ikaw guys
ay malamang na magkaroon ng maraming variable lumulutang sa paligid.
Hindi ka pagpunta sa maging sigurado kung ano ang ibig sabihin ng mga ito sa isang tuldok.
Kaya GDB ay talagang makakatulong sa iyo sa pag-uunawa kung ano ang mga ito ay katumbas ng lahat ng
at ng kakayahang mag-biswal.
Kahit sino nalilito Ay sa kung paano anumang na ay nagtatrabaho?
Cool.
Lahat tama.
Kaya matapos na, kami ay pagpunta sa sumisid karapatan
sa apat na iba't ibang mga uri ng mga uri para sa linggong ito.
Ilan sa inyo, first sa lahat, bago tayo magsimula,
nabasa ko ang buong spec para pset3?
SIGE.
Ako ay maipagmamalaki ng sa iyo guys.
Iyan ay tulad ng kalahati ng mga klase, na ay makabuluhang higit sa huling pagkakataon.
>> Kaya iyan, dahil kapag makipag-usap namin tungkol sa mga nilalaman
sa lecture-- o sorry, sa section-- gusto ko
na may kaugnayan sa isang pulutong ng mga na bumalik sa kung ano ang pset ay
at kung paano mo nais na ipatupad na sa iyong pset.
Kaya't kung ikaw ay dumating sa pagkakaroon basahin ang spec, makikita ito
maging isang pulutong mas madali para sa iyo upang maunawaan kung ano ang sinasabi ko kapag sinasabi ko,
oh hey, ito ay maaaring maging isang tunay na ito magandang lugar upang ipatupad ang uri na ito.
Kaya mga mo na nabasa ko ang pagsasapalaran alam na, bilang bahagi ng iyong pset,
ikaw ay pagpunta sa may sa magsulat ng isang uri ng pag-uuri.
Kaya ito ay maaaring maging kapaki-pakinabang para sa isang pulutong ng sa iyo ngayon.
>> Kaya makikita namin magsimula sa, mahalagang, ang pinaka-simpleng uri
ng mga uri, ang uri ng pagpili.
Ang tipikal na algorithm para sa kung paano gusto namin pumunta tungkol sa mga ito
is-- nagpatuloy si David sa pamamagitan ng mga lahat sa lecture, kaya ko makikita mabilis ilipat kasama
here-- ay mahalagang, ikaw magkaroon ng isang hanay ng mga halaga.
At pagkatapos mo ang Pinakamaliit unsorted halaga
at magpalit ka na ng halaga sa ang unang unsorted halaga.
At pagkatapos mo lamang panatilihin ang paulit-ulit na sa ibang bahagi ng iyong listahan.
>> At narito ang isang visual na paliwanag ng kung paano na gumagana.
Kaya halimbawa, kung kami ay upang simulan may isang hanay ng limang mga sangkap, index
0 hanggang 4, na may 3, 5, 2, 6, at 4 na mga halaga inilagay sa array-- kaya sa ngayon,
lang kami ng pagpunta sa ipalagay na ang mga ito ang lahat ng unsorted
dahil hindi pa namin nasubukan kung hindi man.
>> Kaya kung paano gagawin ang isang uri seleksyon trabaho ay na gagawin muna ito
tumakbo sa pamamagitan ng kabuuan ng unsorted array.
Mas piliin ang pinakamaliit na halaga.
Sa kasong ito, 3, right ngayon, ay ang pinakamaliit.
Ito ay makakakuha ng hanggang 5.
Nope, 5 ay hindi mas malaki than-- o paumanhin, ay hindi mas than-- 3.
Kaya ang minimum na halaga ay pa rin 3.
At pagkatapos mong makakuha ng hanggang 2.
Ang computer na nakikita, oh, 2 ay mas mababa sa 3.
2 ay dapat na ngayon ay ang minimum na halaga.
At kaya 2 swaps sa na unang halaga.
>> Kaya pagkatapos ng isa pass, namin katunayan makita na ang 2 at ang 3 ay swapped.
At lamang kami ay pagpunta sa patuloy na paggawa ito muli gamit ang natitirang bahagi ng array.
Kaya kami ay pagpunta upang tumakbo lamang sa pamamagitan ng ang huling apat na ini-index ng array.
Susubukan naming makita na ang 3 ay mga susunod na minimum na halaga.
Kaya kami ay pagpunta sa swap na may 4 na.
At pagkatapos lamang kami ay pagpunta sa panatilihin tumatakbo sa pamamagitan ng hanggang sa, sa huli, ikaw
makapunta sa isang inayos array na 2, 3, 4, 5, at 6 ay pinagsunod-sunod sa lahat.
Ba ang lahat maunawaan ang lohika ng kung paano gumagana ang isang uri ng pagpili?
>> Ikaw lamang ang ilang mga uri ng isang minimum na halaga.
Ikaw ay nag-iingat subaybayan ng kung ano na.
At kapag nalaman mo ito, swap mo ito sa unang halaga sa array--
o, hindi ito ang unang value-- ang susunod na halaga sa array.
Cool.
>> Kaya bilang mo guys uri ng Nakita mula sa isang maikling sulyap,
kami ay pagpunta sa Pseudocode this out.
Kaya't kung ikaw guys sa likod nais na bumuo ng isang grupo, lahat ng tao sa isang table
maaaring bumuo ng isang maliit na partner, pupuntahan ko upang bigyan ka ng mga guys tulad ng tatlong minuto
upang makipag-usap lamang sa pamamagitan ng ang logic, sa wikang Ingles,
ng kung paano namin maaaring magagawang ipatupad pseudocode na magsulat ng isang uri selection.
At may kendi.
Mangyari lamang na dumating up at makakuha ng kendi.
Kung ikaw ay nasa likod at gusto mong kendi, maaari kong magtapon ng kendi sa inyo.
Sa totoo lang, gawin you-- cool.
Pasensya na.
SIGE.
>> Kaya kung nais namin na, tulad ng isang klase, write pseudocode
para sa kung paano ang isa ay maaaring lapitan ang problemang ito, lamang mag-atubili.
Kukunin ko pumunta lamang sa paligid at, sa pagkakasunud-sunod, tanungin grupo
para sa susunod na linya ng kung ano ang dapat naming gawin.
Kaya kung nais mong guys na simulan off, ano ang unang bagay
na gawin kapag sinusubukan mong ipatupad ang isang paraan upang malutas ang program na ito
upang pili uriin isang listahan?
Sabihin lamang ipagpalagay natin magkaroon ng isang array, ang lahat ng karapatan?
>> Madla: Gusto mong gumawa ng ilang mga uri ng [hindi marinig] na ikaw ay
tumatakbo sa pamamagitan ng iyong buong array.
>> ANDI PENG: Kanan.
Kaya ikaw ay pagpunta sa gusto mong umulit sa pamamagitan ng bawat space, di ba?
So, malaki.
Kung ikaw guys na nais na magbigay sa akin ang susunod line-- oo, sa likod.
>> Madla: Suriin ang mga ito lahat para sa pinakamaliit na.
>> ANDI PENG: Mayroon kaming pumunta.
Kaya gusto namin upang pumunta sa pamamagitan at suriin upang makita kung ano ang minimum na halaga ay, di ba?
Pupunta ako sa paikliin na sa "min."
Ano ang gusto mong guys na gawin pagkatapos nakakita ka ng minimum na halaga?
>> Madla: [hindi marinig]
ANDI PENG: Kaya ikaw ay pagpunta sa nais na lumipat ito sa unang ng na array,
right?
Iyon ang simula, ako pagpunta sa sabihin.
Lahat tama.
Kaya ngayon na ikaw ay swapped ang unang isa, ano ang gusto mong gawin pagkatapos na?
Kaya ngayon ay alam natin na ang isang ito dito ay dapat na ang pinakamaliit na halaga, di ba?
Pagkatapos ay mayroon kang isang karagdagang pahinga ng array na unsorted.
Kaya kung ano ang gusto mong gawin dito, kung ikaw guys nais na magbigay sa akin ang mga susunod na linya?
Madla: Kaya nga ang gusto mong umulit sa pamamagitan ng mga naiwan ng array.
ANDI PENG: Oo.
At kaya kung ano ang ibig iterating sa pamamagitan ng uri ng magpahiwatig kami ay marahil na kailangan?
Anong uri of--
>> Madla: Oh, ang isang karagdagang variable?
ANDI PENG: Malamang isa pa para sa loop, di ba?
Kaya marahil kami ay pagpunta sa gusto upang umulit through-- malaki.
At pagkatapos ikaw ay pagpunta sa bumalik at marahil suriin muli ang minimum,
right?
At ikaw ay pagpunta upang panatilihin ang paulit-ulit na ito, dahil ang mga loop lamang ang pagpunta
upang panatilihing tumatakbo, di ba?
>> Kaya bilang ka guys ay maaaring makita, kami ay Mayroon lamang ng isang pangkalahatang pseudocode
ng kung paano namin gusto ang program na ito upang tumingin.
Umulit na ito dito, kung ano ang ginagawa namin karaniwang kailangan upang isulat sa aming code
kung gusto naming upang umulit sa pamamagitan ng isang array, kung anong uri ng istraktura?
Sa tingin ko Christabel na sinabi ito bago.
>> Madla: A para sa loop.
>> ANDI PENG: A para sa loop?
Mismong.
Kaya ito ay marahil pagpunta sa isang para sa loop.
Ano ang isang check dito pagpunta upang magpahiwatig?
Kadalasan, kung nais mong suriin kung ang isang bagay ay isang bagay else--
>> Madla: Kung.
>> ANDI PENG: Isang kung, di ba?
At pagkatapos ay ang swap dito, ipapakita namin pumunta sa ibang pagkakataon, dahil David
dumaan na sa lecture rin.
At pagkatapos ay ang ikalawang umulit implies--
>> Madla: Ang isa pang para sa loop.
>> ANDI PENG: --another para sa loop, eksakto.
Kaya kung kami ay naghahanap sa tama ito, kami
maaaring makita na hindi namin marahil pagpunta sa kailangan ng isang nested para sa loop
sa isang kondisyon na pahayag sa doon at pagkatapos ng isang aktwal na piraso ng code na
pagpunta sa swap ang mga halaga.
Kaya ko na sa pangkalahatan ay lamang na nakasulat isang pseudocode code dito.
At pagkatapos ay aktwal na kami ay pagpunta sa pisikal na, tulad ng isang klase,
subukan upang ipatupad ito ngayon.
Bumalik tayo sa ganitong IDE.
>> Naku.
Bakit na not-- may ito ay.
SIGE.
Paumanhin, hayaan mo akong subukan na mag-zoom in pa ng kaunti.
Mayroon kaming pumunta.
Lahat ako paggawa dito ay na aking nilikha isang programa na tinatawag na "pagpili / sort.c."
Lumikha ako ng isang array ng siyam halaga, 4, 8, 2, 1, 6, 9, 7, 5, 3.
Sa kasalukuyan, tulad ng maaari mong makita, ang mga ito ay unordered.
n ay magiging ang numero na ay nagsasabi sa iyo ang halaga ng mga halaga
mayroon ka sa iyong array.
Sa kasong ito, kami ay may siyam na mga halaga.
At lamang ako got isang para sa loop dito na mga print out ang unsorted array.
>> At sa dulo, nakuha rin ako ng isang para sa loop na ang mga kopya lamang ito muli.
Kaya theoretically, kung ang program na ito ay gumagana nang tama, sa dulo,
dapat mong makita ang isang naka-print para sa loop na kung saan ang 1, 2, 3, 4, 5, 6, 7, 8,
9 ay ang lahat ng tama sa order.
>> Kaya namin nakuha ang aming pseudocode dito.
Gusto ba to-- lang ako pagpunta sa pumunta humingi ng volunteers--
sabihin sa akin kung ano mismo ang mag-type kung gusto naming, una, umulit lang
sa pamamagitan ng simula ng array?
Ano ang mga linya ng code Ako marahil pagpunta sa kailangan dito?
>> Madla: [hindi marinig]
>> ANDI PENG: Oo, sa palagay libreng to-- Paumanhin, ikaw ay
Hindi mo na kailangang tumayo up-- pakiramdam free na itaas ang iyong boses ng kaunti.
>> Madla: Para sa int i katumbas 0--
>> ANDI PENG: Oo, mabuti.
>> Madla: i ay mas mababa sa haba ng array.
>> ANDI PENG: Kaya panatilihin sa bale dito, dahil kami ay
hindi magkaroon ng isang function na Sinasabi sa amin ang haba ng isang array,
kami ay mayroon ng isang halaga na ang mga tindahan na iyon.
Right?
Isa pang bagay na panatilihin sa mind-- sa isang array
ng siyam na mga halaga, ano ang mga ini-index?
Sabihin lang sabihin ang array na ito ay 0 hanggang 3.
Ang makikita mo na ang huling index ay aktwal na 3.
Ito ay hindi 4, kahit na may apat na mga halaga sa array.
>> Kaya sa dito, mayroon kaming upang maging maingat ng kung ano ang aming mga kondisyon para sa ang haba
ay magiging.
>> Madla: Hindi ba ito ay n minus 1?
ANDI PENG: Ito ay pagpunta n minus 1, eksakto.
Ba na magkaroon ng kahulugan, bakit ito ay n minus 1, lahat ng tao?
Ito ay dahil ang array ay zero-index.
Sila magsimula sa 0 at tumakbo hanggang sa n minus 1.
Oo, ito ay isang bit mapanlinlang.
SIGE.
At then--
Madla: Isnt'1 na nakuha na pag-aalaga ng kahit na,
sa pamamagitan ng hindi lamang sinasabi "mas mababa sa o katumbas ng "at lamang na nagsasabing" mas mababa kaysa? "
>> ANDI PENG: Iyan ay isang talagang mahusay na tanong.
So, yes.
Ngunit din, ang mga paraan na hindi namin pagpapatupad ng pagsuri ng mga karapatan,
kailangan mong ihambing ang dalawang mga halaga.
Kaya talagang gusto ninyong iwan ang "sa" walang laman.
Dahil kung ikaw ay ihambing ang isang ito, hindi ka pagpunta
magkaroon ng anumang bagay matapos na ito upang ihambing sa, right?
Oo.
Kaya i ++.
Magdagdag ng aming mga bracket sa Hayaan.
Oops.
Great.
Kaya kami ay may simula ng aming mga panlabas na loop.
Kaya ngayon marahil gusto naming lumikha ng isang variable para sa pagsunod
subaybayan ng pinakamaliit na halaga, di ba?
Nais ba ng sinuman upang bigyan ako ang linya ng code na gawin iyon?
Ano ang kailangan namin kung kami ay pagpunta sa nais na mag-imbak ng isang bagay?
>> Right.
Siguro isang mas mahusay na pangalan para sa na Gusto be-- "temp" lubos works--
marahil ng isang mas aptly pinangalanan ay magiging, kung nais namin na ang pinakamaliit value--
>> Madla: Min.
ANDI PENG: min, doon pumunta kami.
min ay magiging mabuti.
At kaya dito, kung ano ang ginagawa namin Gusto upang magpasimula ito sa?
Ito ay isang bit mapanlinlang.
Dahil sa ngayon sa simula ng array na ito,
hindi mo pa tumingin sa anumang bagay, di ba?
Kaya kung ano, nang awtomatiko, kung hindi namin lamang sa i katumbas ng 0,
kung ano ang gusto namin upang magpasimula ang aming unang minimum na halaga sa?
Madla: i.
ANDI PENG: i, eksakto.
Christabel, bakit gusto namin upang magpasimula ito upang i?
>> Madla: Dahil, well, kami ay nagsisimula sa 0.
Kaya dahil mayroon kaming walang upang ihambing ito sa, ang minimum ay humantong sa pagiging 0.
>> ANDI PENG: Eksakto.
Kaya siya ay akmang-akma.
Dahil kami ay hindi tunay tumingin sa kahit ano pa,
hindi namin alam kung ano ang aming mga minimum na halaga ay.
Gusto naming upang magpasimula lamang ito sa i, na kung saan, sa kasalukuyan, ay dito mismo.
At habang patuloy naming ilipat pababa ang array na ito,
kami ay makikita na, sa bawat karagdagang pass, dinadagdagan i.
At kaya sa puntong iyon, i ay marahil pagpunta
na gusto mong maging ang minimum, dahil ito ay pagpunta sa maging kahit anong
ay ang simula ng unsorted array.
Cool.
>> Kaya ngayon gusto naming idagdag isang para sa loop dito na
pagpunta sa ulitin sa pamamagitan ng unsorted, o sa ibang bahagi ng array na ito.
Nais ba ng sinuman upang bigyan ako ng isang linya ng code na gawin iyon?
Hint-- ano ang kailangan pababa namin dito?
Ano kaya ang nangyari upang pumunta sa para sa loop?
Oo.
Madla: Kaya gusto namin nais na magkaroon ng isang iba't ibang mga integer,
dahil kami ay tumatakbo sa pamamagitan ng pahinga ng array sa halip na ang i, kaya siguro
j.
>> ANDI PENG: Oo, j tunog mabuti sa akin.
Katumbas?
>> Madla: Kaya ay i plus 1, dahil ikaw ay simula sa susunod na halaga.
At pagkatapos ay sa end-- kaya muli, j ay mas mababa sa n minus 1, at pagkatapos j ++.
ANDI PENG: Great.
>> At pagkatapos in dito, kami ay pagpunta sa nais upang suriin upang makita kung ang aming mga kondisyon ay natutugunan,
right?
Dahil ang nais mong baguhin ang minimum na halaga
kung ito ay aktwal na mas maliit kaysa sa kung ano ikaw ay paghahambing nito sa, right?
Kaya kung ano ang kami ay pagpunta sa gusto dito?
Suriin upang makita.
Anong uri ng mga pahayag kami ay marahil pagpunta
gusto ti gamitin kung tayo nais na suriin ang isang bagay?
>> Madla: Isang pahayag kung.
>> ANDI PENG: Ang isang kung pahayag.
Kaya if-- at kung ano ang magiging kondisyon na gusto natin sa loob
ng aming mga pahayag kung?
>> Madla: Kung ang halaga ng j ay mas mababa kaysa sa halaga ng i--
>> ANDI PENG: Eksakto.
Kaya if-- kaya ito array ay tinatawag na "array."
Great.
Kaya kung array-- kung ano ang na?
Sabihin na muli.
>> Madla: Kung array-j ay mas mababa sa array-i, at pagkatapos namin ay magbabago sa min.
Kaya ang min ay j.
>> ANDI PENG: Ba na magkaroon ng kahulugan?
SIGE.
At ngayon down dito, kami ay tunay na nais na ipatupad ang swap, di ba?
Kaya isipin, sa panayam, na si David, nang siya ay sinusubukan upang magpalitan the-- kung ano ang
it-- orange juice at milk--
>> Madla: Iyon ay gross.
>> ANDI PENG: Oo, na ay uri ng gross.
Ngunit ito ay isang medyo magandang konsepto ng oras na nagpapakita.
Kaya sa tingin ng iyong mga halaga dito.
Nakuha mo na ang isang array ng min, isang array ng i,
o ano pa man namin na sinusubukan mong magpalit dito.
At marahil ay hindi maaaring ibuhos ang mga ito sa bawat isa at sa parehong oras, tama?
Kaya kung ano ang kami ay pagpunta na kailangan upang lumikha dito
upang magpalitan ng tama ang mga halaga?
>> Madla: Ang isang pansamantalang variable.
>> ANDI PENG: Ang isang pansamantalang variable.
Kaya sabihin gawin int temp.
Tingnan, ito ay isang mas mahusay time to-- aba, ano ang na?
SIGE.
Kaya ito ay naging isang mas mahusay na oras sa pangalan ng variable na "temp."
Kaya sabihin gawin int temp.
Ano ang mga namin pagpunta sa set temp pantay na dito?
Madla: Min?
ANDI PENG: Ito ay isang bit mapanlinlang.
Ito ang tunay ay hindi mahalaga sa dulo.
Hindi mahalaga kung ano ang sunod kang pumili upang magpalit in
hangga't ginagawa mo ba na ikaw ay pagpapanatili ng track ng kung ano ang iyong pagpapalit.
>> Madla: Ito ay maaaring maging array-i.
>> ANDI PENG: Oo, gawin ang array-i ipaalam.
At pagkatapos ay kung ano ang susunod na linya ng code gusto naming magkaroon dito?
Madla: array-i katumbas ng array-j.
ANDI PENG: At sa wakas?
Madla: array-j katumbas array-i.
Madla: O array-j equals array-temp-- o, temp.
>> ANDI PENG: OK.
Kaya sabihin patakbuhin ito at makita kung ito ay pagpunta sa trabaho.
Saan na nangyayari?
Oh, na ang isang problema.
Tingnan, sa 40 na linya, hindi namin sinusubukan mong gamitin ang array-j?
Ngunit kung saan ang j umiiral lamang sa?
>> Madla: Sa para sa loop.
ANDI PENG: Kanan.
Kaya kung ano ang kami ay pagpunta sa kailangan mong gawin?
>> Madla: Tukuyin ang mga ito sa labas the--
Madla: Oo, ako hulaan ikaw ay gumamit ng isa pang kung statement, di ba?
Kaya tulad ng, kung ang minimum-- lahat ng karapatan, hayaan mo akong mag-isip.
>> ANDI PENG: Guys, subukan upang tingnan Natin
makita, kung ano ang isang bagay na maaari naming gawin dito?
>> Madla: OK.
Kaya kung ang minimum ay hindi katumbas ng j-- kaya kung ang minimum pa rin ang i--
pagkatapos ay hindi namin ay may upang magpalitan.
>> ANDI PENG: ba na pantay-pantay na i?
Ano ang gusto mong sabihin dito?
>> Madla: O oo, kung ang minimum ay hindi katumbas i, oo.
ANDI PENG: OK.
Well na malulutas nito, uri ng, ang aming mga problema.
Ngunit iyon ay hindi pa rin malutas ang problema ng kung ano ang mangyayari kung j-- dahil j
ay hindi na umiiral sa labas ng mga ito, kung ano ang mo gusto naming gawin dito?
Ipinahahayag ito sa labas?
Subukan tumatakbo natin ito.
Naku.
Ang aming mga uri ang hindi gumagana.
>> Tulad ng iyong nakikita, ang aming paunang array nagkaroon ng mga halaga.
At pagkatapos ito ay dapat magkaroon ay sa 1, 2, 3, 4, 5, 6, 7, 8, 9.
Hindi gumagana.
Ahh.
Ano ang gagawin namin?
Madla: Debug.
ANDI PENG: Lahat ng mga karapatan, maaari naming subukan na.
Maaari naming i-debug.
Mag-zoom out ng kaunti.
Itakda ang aming mga breakpoint Hayaan.
Sabihin pumunta like-- OK.
>> So dahil na alam namin na mga linyang ito, 15 hanggang 22,
ay working-- dahil ang lahat ng ginagawa ko lamang iterating sa pamamagitan at printing--
Maaari kong magpatuloy at laktawan iyon.
Magsimula tayo sa 25 linya Hayaan.
Oop, hayaan mo akong magtanggal ng mga iyon.
>> Madla: Kaya ang breakpoint ni kung saan ang pag-debug ay nagsisimula?
ANDI PENG: O hinto.
Madla: O hinto.
ANDI PENG: Oo.
Maaari kang magtakda ng maramihang breakpoints at Maaari lamang ito tumalon mula sa isa sa iba pang.
Ngunit sa kasong ito hindi namin alam kung saan ang mga error ay nangyayari.
Kaya nais lang namin sa simulan mula sa itaas pababa.
Yep.
SIGE.
>> Kaya ito linya dito, maaari naming hakbang sa.
Maaari mong makita sa ibaba rito, Nakakuha kami ng isang array.
Ang mga ay ang mga halaga na sa array.
Nakikita mo ba na, kung paano index 0, ito tumutugon sa value-- oh,
Pupunta ako sa subukan upang mag-zoom in.
Paumanhin, ito ay talagang mahirap upang see-- sa array index 0,
kami ay may isang halaga ng 4 at pagkatapos ay iba pa at iba pa.
Mayroon kaming aming mga lokal na variable.
Sa ngayon ay i katumbas ng 0, na kung saan gusto naming ito upang maging.
>> At ni panatilihin tuntong sa pamamagitan ng kaya hayaan.
Ang aming minimum ay katumbas ng 0, kung saan gusto rin naming ito upang maging.
At pagkatapos ay ipasok namin ang aming ikalawang para sa loop, kung array-j ay mas mababa sa array-i,
na kung saan ito ay hindi.
Kaya nakita mo kung paano na nilaktawan sa paglipas na?
>> Madla: Kaya dapat ang kung minimum, ang lahat ng hindi na- dapat na
maging sa loob ng unang para sa loop?
ANDI PENG: Hindi, dahil gusto mo pa ring subukan.
Gusto mong gawin ang isang paghahambing ng bawat oras, kahit na matapos na patakbuhin mo sa pamamagitan nito.
Ayaw mo lamang na gawin ito sa unang pass-through.
Gusto mong gawin ito na may bawat karagdagang muli pass.
Kaya nais mong suriin para sa ang iyong kalagayan sa loob.
Kaya kami ay lamang ng pagpunta sa patuloy na tumatakbo sa pamamagitan dito.
Bibigyan kita ng isang lalaki na isang hint.
Ito ay may sa gawin sa ang katunayan na kapag naka-check ang iyong mga kondisyon,
hindi naka-check para sa tamang index.
Kaya ngayon naka-check para sa array index ng j ay mas mababa sa array
index ng i.
Ngunit ano ang ginagawa mo up sa simula ng para sa loop?
Hindi ka ba pagtatakda j katumbas i?
>> Oo, kaya maaari namin talagang lumabas ang debugger dito.
Kaya sabihin kumuha ng isang pagtingin sa aming pseudocode.
For-- kami ng pagpunta sa magsimula sa katumbas i 0.
Kami ay pagpunta sa pumunta hanggang sa n minus 1.
Ating tingnan Hayaan, ay mayroon kaming ang mga karapatan?
Oo, na karapatan.
>> Kaya nga ang loob dito, hindi namin pagpunta upang lumikha ng isang minimum na halaga ng
at itakda na katumbas ng i.
Ibig namin gawin iyon?
Oo, ginawa na.
Ngayon sa aming panloob na para sa loop, hindi namin pagpunta sa gawin j i katumbas sa n 1 minus.
Ibig namin gawin iyon?
Sa katunayan, ginawa namin na.
>> Kaya gayunpaman, kung ano ang namin ang paghahambing dito?
>> Madla: j plus 1.
ANDI PENG: Eksakto.
At pagkatapos ikaw ay pagpunta sa nais na itakda ang iyong minimum na katumbas j plus 1 rin.
Kaya nagpunta ako sa pamamagitan na talagang mabilis.
Naiintindihan ba ninyo guys kung bakit ito ay j plus 1?
SIGE.
>> Kaya sa inyong array, in iyong unang pass sa pamamagitan ng,
iyong para sa loop, para sa int i katumbas ng 0, sabihin lamang
ipalagay na ito ay hindi pa nabago.
Mayroon kaming isang array ng, ganap, apat na lang unsorted elemento, tama?
Kaya gusto namin upang magpasimula pantay i sa 0.
At i ay pagpunta sa makatarungan tumakbo ito sa pamamagitan ng loop.
At kaya sa unang pass, kami ay pagpunta upang magpasimula ng isang variable na tinatawag na "min"
na rin i katumbas, dahil hindi namin ay may isang minimum na halaga.
Kaya na sa kasalukuyan ay katumbas ng 0 rin.
At pagkatapos kami ay pagpunta upang pumunta sa pamamagitan ng.
At gusto namin na umulit muli.
Ngayon na nalaman namin kung ano ang aming minimum ay, gusto naming upang umulit sa pamamagitan
muli upang makita kung ito ay ang paghahambing, di ba?
Kaya j, dito, ay pagpunta sa pantay na i, na kung saan ay 0.
At pagkatapos ay kung array j plus i, na ay ang isa na ang susunod sa ibabaw, tulad ng mas mababa
kaysa sa kung ano ang iyong kasalukuyang minimum halaga ay, gusto mong magpalit.
>> Kaya sabihin lamang sabihin na namin got, i, 2, 5, 1, 8.
Sa ngayon, i ay katumbas ng 0 at j ay katumbas sa 0.
At iyon ang aming minimum na halaga.
Kung array-j plus i-- kaya kung ang isa na pagkatapos ng isa kaming naghahanap sa
ay mas malaki kaysa sa isa bago ito, ito ay pagpunta sa maging ang minimum.
>> Kaya dito makikita natin na 5 ay hindi mas mababa kaysa sa na.
Kaya ito ay pagpunta sa hindi 5.
Nakita namin na 1 ay mas mababa sa 2, di ba?
Kaya ngayon ay alam namin na ang aming minimum ay magiging halaga ng index sa 0, 1, 2.
Oo?
At pagkatapos ay kapag ikaw ay makakuha ng down dito, maaari mong ipagpalit ang tamang halaga.
>> Kaya kapag ikaw guys ay lamang ang pagkakaroon ng j bago, hindi na kayo ay naghahanap sa isa
pagkatapos na ito.
Ikaw ay naghahanap sa sa parehong halaga, na kung saan
ang dahilan kung bakit ito lamang ay hindi gumagawa ng anumang bagay.
Ba na magkaroon ng kahulugan sa lahat ng tao, bakit kailangan natin na plus 1 doon?
SIGE.
Ngayon tatakbo lang sa pamamagitan nito na gumawa ng ipaalam Siguraduhin na ang natitirang bahagi ng code ay tama.
Bakit na nangyayari?
Ah, ito ay ang min dito mismo.
Kami ay paghahambing ng maling halaga.
Oh hindi.
>> Oh oo, pababa dito tayo ay pagpapalit ang maling halaga pati na rin.
Dahil kami ay naghahanap sa i at j.
Iyon ang mga bago namin checking.
Kami ay talagang nais na magpalit ng mga minimum, ang kasalukuyang minimum,
sa ano man ang isa sa labas ay.
At bilang ay maaaring makita ka guys down dito, mayroon kaming isang pinagsunod-sunod array.
Lamang nagkaroon ito upang gawin sa ang katotohanan na kapag
checking namin ay ang halaga namin ay paghahambing,
hindi namin ay naghahanap sa tamang halaga.
Kami ay naghahanap sa parehong isa dito, hindi aktwal na pagpapalit ito.
Ikaw ay may na tingnan ang isa sa tabi na ito at pagkatapos ay maaari mong ipagpalit.
Kaya na kung ano ang uri ng bugging aming code bago.
At kung ano ang ginawa ko dito ay ang lahat ng bagay ang debugger ay may ginagawa para sa iyo
Ginawa ko lang ito sa board, dahil sa ito ay mas madali
upang makita ang sa halip na sinusubukan upang mag-zoom in sa debugger.
Ba na magkaroon ng kahulugan sa lahat ng tao?
Cool.
>> Lahat tama.
Maaari naming ilipat sa sa pakikipag-usap tungkol asymptotic pagtatanda, na
ay lamang ng isang magarbong paraan ng sinasabi ng runtimes ng lahat ng mga uri.
Kaya alam ko David, sa panayam, hinawakan sa runtimes.
At siya nagpunta sa pamamagitan ng buong formula ng kung paano kinakalkula ang runtimes.
Huwag mag-alala tungkol sa na.
Kung ikaw ay talagang kakaiba sa kung paano na gumagana,
mag-atubili na makipag-usap sa akin pagkatapos ng section.
Maaari naming sa pamamagitan ng paglalakad ang mga formula na magkasama.
Ngunit ang lahat ng ka guys kung talagang alam na n nakalapat sa higit sa 2
ay ang mga parehong bagay tulad n nakalapat.
Dahil ang pinakamalaking bilang, ang exponent, lumalaki ang pinaka.
At kaya para sa aming mga layunin, lahat ng pag-aalaga namin ang tungkol sa
ay na giant numero na lumalaki.
>> Kaya kung ano ang pinakamahusay na kaso runtime ng pagpili ng uri?
Kung ikaw ay pagpunta sa may upang umulit sa pamamagitan ng isang listahan
at pagkatapos ay ulitin sa pamamagitan ng ang natitirang bahagi ng listahan na iyon,
kung gaano karaming beses ang marahil ka ng pagpunta sa,
sa pinakamalala case-- sa pinakamahusay na kaso, sorry-- tumakbo sa pamamagitan ng?
Siguro ang mas magandang tanong ay na magtanong, kung ano ay ang pinakamasama kaso
runtime ng pagpili ng uri.
Madla: n nakalapat.
ANDI PENG: Ito ay n nakalapat, right.
Kaya isang madaling paraan upang isipin ng mga ito ay tulad ng, anumang oras na mayroon kang dalawang nested para sa mga loop,
ito ay pagpunta sa maging n nakalapat.
Dahil hindi lamang ikaw ay tumatakbo muli sa pamamagitan ng,
kailangan mong pumunta sa likod paligid at tumakbo sa pamamagitan nito
sa sandaling muli sa loob para sa bawat halaga.
Kaya sa kasong iyon, ikaw ay nagpapatakbo ng n beses n nakalapat, na is-- Paumanhin,
n beses n, na kung saan ay katumbas n nakalapat.
>> At ang uri ay din ng isang bit natatangi sa kamalayan
na ito ay hindi mahalaga kung ang mga mga halaga ay nasa order.
Ito ay pagpunta pa rin upang tumakbo sa pamamagitan pa rin.
Sabihin lang sabihin na ito ay 1, 2, 3, 4.
Kahit na o hindi ito ay sa order, pa rin ito ay may bumangga sa pamamagitan ng
at pa rin naka-check ang minimum na halaga.
Itong ginawa ang parehong bilang ng mga tseke
ng lahat ng oras, kahit na ito ay hindi aktwal na hawakan ng kahit ano.
>> Kaya sa ganoong kaso, ang mga pinakamahusay at pinakamasamang runtimes ay talagang katumbas.
Kaya ang inaasahan runtime ng pagpili ng uri,
na maitalaga kami sa pamamagitan ng mga simbolo ng theta, theta, sa kasong ito,
ay n din nakalapat.
Lahat ng tatlong ng mga ito ay magiging n nakalapat.
Ay malinaw sa lahat ng tao sa kung bakit ang runtime ay n nakalapat?
>> Lahat tama.
Kaya lang ako pagpunta sa mabilis na tumakbo sa pamamagitan ng ang natitirang bahagi ng mga masama.
Ang algorithm para sa bubble sort-- tandaan,
ito ay ang unang isa Tumawid David sa panayam.
Totoo, ikaw hakbang sa pamamagitan ng buong listahan
at swap-- ka ikaw lamang paghambingin ang dalawang sa isang pagkakataon.
At kung ang isa ay mas malaki, kaysa mo lamang palitan ang mga ito.
Kaya kung ang mga ito ay mas malaki, gusto mo magpalit.
Mayroon akong opisyal na karapatan dito.
>> Kaya sabihin lamang sabihin na kayo ay nagkaroon ng 8, 6, 4, 2.
Gusto mong ihambing ang 8 at 6.
Gusto mo kailangan upang magpalitan ng mga ito.
Gusto mong ihambing ang 8 at isang 4.
Gusto mo kailangan upang magpalitan ng mga ito.
Kung ikaw ay may upang magpalit ng 8 at ang 2, magbabago rin ang mga ito.
Kaya sa ganoong kahulugan, maaari mong makita, play out sa loob ng mahabang panahon,
kung paano ang mga halaga ng uri ng bubble sa ang mga dulo, na kung saan ay kung bakit ang tawag namin ito
sort bubble.
>> Nais tumakbo lang namin sa pamamagitan sa muli ang aming pangalawang pass, at ang aming ikatlong pass,
at ang aming ika-apat na pass.
Mahalaga, bubble ay tumatakbo lamang uri hanggang hindi mo na gumawa ng anumang higit swaps.
Kaya sa na kahulugan, ito ay lamang ang pangkalahatang pseudocode para dito.
Huwag mag-alala, ang mga ito ay ang lahat ay online.
Wala kaming upang aktwal na pumunta sa paglipas ng ito.
>> Magpasimula lang namin ng counter variable na nagsisimula sa 0.
At umulit kami sa pamamagitan ng buong array.
At kung ang isa halaga is-- kung ito halaga ay mas mataas kaysa sa halaga na iyon,
ikaw ay pagpunta sa swap sa kanila.
At pagkatapos ay ikaw lamang pagpunta sa panatilihin ang pagpunta.
At ikaw ay pagpunta sa count.
At lamang ikaw ay pagpunta sa patuloy na paggawa ito habang ang counter ay mas malaki
kaysa sa 0, na nangangahulugan na ang sa bawat oras na ikaw ay may upang magpalitan,
alam mo na gusto mong puntahan bumalik at suriin muli.
Gusto mong panatilihin ang checking hanggang malaman mo na hindi mo na kailangang magpalit anymore.
>> Kaya kung ano ang pinakamahusay at pinakamasamang kaso runtimes para bubble sort?
At hint-- ito ay tunay na naiiba mula sa mga uri sa kamalayan seleksyon
na ang mga dalawang mga sagot ay hindi pareho.
Mag-isip tungkol sa kung ano ang mangyayari sa isang kaso kung ito ay mayroon na pinagsunod-sunod.
At sa tingin tungkol sa kung ano ang mangyayari kung ito ay
sa kaso na kung saan hindi ito ay pinagsunod-sunod.
At maaari mong uri ng tumakbo sa pamamagitan ng kung bakit na ang nangyayari.
Bibigyan kita ng isang lalaki, tulad ng, 30 segundo upang isipin ang tungkol na.
>> SIGE.
Kahit sino ay may isang hula sa kung ano ang pinakamasama kaso runtime ng bubble sort ay?
Oo.
>> Madla: Gusto ito ay, tulad ng, n ulit n minus 1 o isang bagay tulad na?
Tulad ng, sa bawat panahon na ito ay tumatakbo, ito lang, gusto, isa swap mas mababa
na anuman ito.
>> ANDI PENG: Oo, kaya hindi lubos na karapatan sa iyo.
At ito ay isang kaso kung saan ang iyong mga Ang sagot ay talagang mas kumplikadong
kaysa sa isa kailangan namin na magbigay sa.
Kaya ito ay pagpunta sa run-- Ako Buburahin ang lahat ng ito dito.
Mabuti ba ang lahat?
Maaari ko bang burahin ito?
SIGE.
Ikaw ay pagpunta upang tumakbo sa pamamagitan n beses sa unang pagkakataon, i-right?
At sila ay pagpunta upang tumakbo sa pamamagitan n minus 1 sa pangalawang pagkakataon, di ba?
At pagkatapos ikaw ay pagpunta sa panatilihin tuloy, n mine 2, at iba pa.
Ginawa ito ni David sa isang panayam, kung saan, kung iyong idinagdag up sa lahat ng mga halaga,
makakakuha ka ng isang bagay na like-- yeah-- higit sa 2, na mahalagang lamang binabawasan
pababa sa n nakalapat.
Ikaw ay pagpunta upang makakuha ng isang kakaiba maliit na bahagi sa doon.
At kaya lamang malaman na ang n nakalapat laging
tumatagal ng higit na kahalagahan sa mga maliit na bahagi.
At kaya sa kasong ito, ang pinakamasama runtime ay n nakalapat.
Kung ito ay sa pababang order, mag-isip, ikaw ay
kailangang gumawa ng isang magpalitan ng bawat solong oras.
>> Ano ang gusto ay, potensyal na, ang pinakamahusay na runtime kaso?
Sabihin lang sabihin, kung ang listahan ay mayroon na sa pagkakasunud-sunod, ano ang magiging runtime?
>> Madla: n.
ANDI PENG: Ito ay n, eksakto.
At kung bakit ito ay n?
Madla: Dahil ikaw lamang kung suriin sa bawat beses.
ANDI PENG: Eksakto.
Kaya sa posibleng pinakamahusay na runtime, kung ang listahan na ito ay mayroon na
sorted-- sabihin natin 1, 2, 3, 4-- mo ay pumunta lamang sa pamamagitan ng, na iyong nais na tingnan,
Gusto mo makita, oh, ang lahat ng mga ito ay mag-pan out.
Hindi ko na kailangang magpalit.
Tapos na ako.
Kaya sa kasong iyon, ito ay n lang o ang bilang ng mga hakbang mo lamang
nagkaroon upang suriin sa unang listahan.
>> At pagkatapos, kami ay pindutin ngayon uuri, kung saan
ang algorithm ay mahalagang upang hatiin ito sa isang inayos at unsorted bahagi.
At pagkatapos ay isa-isa, unsorted mga halaga ay
nakapasok sa kanilang mga naaangkop na mga posisyon sa simula ng listahan.
>> Kaya halimbawa, kami ay may isang listahan ng 3, 5, 2, 6, 4 muli.
Alam namin na ito ay kasalukuyang unsorted dahil hindi namin lamang
nagsimula ang pagtingin sa mga ito.
Tinitingnan namin at alam namin na sa unang halaga ay inayos, right?
Kung lamang ikaw ay naghahanap sa isang hanay ng mga laki ng isa, alam mo na ito ay pinagsunod-sunod.
>> Kaya nga nalalaman natin na ang iba pang apat ay unsorted.
Pumunta kami sa pamamagitan ng at nakita namin ang halaga.
Bumalik tayo.
Tingnan na halaga ng 5?
Kumuha kami ng isang pagtingin sa mga ito.
Inihambing namin ito sa 3.
Alam namin na ito ay mas malaki kaysa sa 3, upang malaman namin na na pinagsunod-sunod.
Kaya alam namin ngayon na ang unang dalawang ay pinagsunod-sunod at ang huling tatlong ay hindi.
>> Kumuha kami ng isang pagtingin sa 2.
Una naming suriin ito sa 5.
Ito ba ay mas mababa sa 5?
Hindi iyon.
Kaya kami ay may upang panatilihin ang naghahanap down.
Pagkatapos mong suriin ang 2 off 3.
Ito ba ay mas mababa kaysa sa?
Hindi.
Kaya alam mo ng 2 ay may na nakapasok sa harap at 3 at 5
parehong may upang maging hunhon out.
Gawin ito muli sa 6 at 4.
At kami lamang panatilihin ang mahalagang suri, kung saan namin lamang suriin, suriin, suriin.
At hanggang sa ito ay nasa tamang posisyon, namin uri ng lamang
ipasok ito sa tamang posisyon, na kung saan ay kung saan ang pangalan ng ito nanggaling.
>> Kaya ito lamang ang algorithm, pseudocode per se, uri ng,
sa kung paano namin ipatupad isang uri pagpapasok.
Pseudocode ay dito.
Lahat ng ito ay online.
Huwag mag-alala kung ikaw guys ay sinusubukan mong kopyahin ito pababa.
Kaya muli, parehong question-- ano ay ang pinakamahusay at pinakamasamang runtimes
para sa uri pagpapasok?
Ito ay halos kapareho sa huling tanong.
Bibigyan kita ng isang lalaki, tulad ng, 30 segundo upang isipin ang tungkol sa mga ito pati na rin.
>> OK sinumang gusto ba sa bigyan ako ang pinakamasama runtime?
Oo.
>> Madla: n nakalapat.
>> ANDI PENG: Ito ay n nakalapat.
At bakit ito n nakalapat?
>> Madla: Dahil sa reverse order, mayroon kang
upang pumunta sa pamamagitan n beses n, na is--
ANDI PENG: Oo, eksakto.
Kaya parehong bagay tulad ng sa bubble sort.
Kung ang listahan na ito ay nasa pababang pagkakasunud-sunod, ikaw ay
pagpunta sa may upang suriin ang unang beses.
At pagkatapos ay sa bawat karagdagang halaga, ikaw ay
pagpunta sa may upang suriin ito kumpara bawat solong halaga, di ba?
At kaya sa kabuuan, ikaw ay pagpunta sa gumawa isang n pass ulit ng isa pang n pumasa, na
ay n nakalapat.
Ano ang tungkol sa mga pinakamahusay na kaso?
Oo.
>> Madla: n minus 1, dahil ang unang isa ay naka nakalapat.
>> ANDI PENG: So, malapit na.
Ang sagot ay talagang n.
Dahil habang ang una ay ayun, maaaring hindi ito actually-- ito
lucked lang namin sa labas, sa Halimbawa na, na ang 2
nangyari na ang pinakamaliit na bilang.
Ngunit iyon ay hindi palaging ang kaso.
Kung 2 na pinagsunod-sunod sa simula ngunit tumingin ka at mayroong isang 1 dito,
ang 1 ay pagpunta sa paga ito.
At ito ay pagpunta sa dulo up pagiging bumped anyways.
>> Kaya sa mga pinakamahusay na kaso sitwasyon, ito ay talagang lamang magiging n.
Kung ikaw ay may 1, 2, 3, 4, 5, 6, 7, 8, ikaw ay
pagpunta upang tumakbo sa pamamagitan na ang buong listahan ng isang beses
upang suriin upang makita kung fine ang lahat.
Ay malinaw na lahat ng tao sa pagtakbo mga oras ng pagpipilian pati na rin?
Alam ko ako pagpunta sa pamamagitan ng mabilis talaga ang mga ito.
Ngunit lamang malaman na kung alam mo ang pangkalahatang konsepto, dapat ay handa na.
SIGE.
Kaya kukunin ko na lang magbibigay sa iyo ng isang lalaki siguro, tulad ng, isang minuto upang makipag-usap sa iyong mga kapitbahay
sa kung ano lang ang ilan sa mga pangunahing pagkakaiba
pagitan ng mga uri ng mga uri.
Susubukan naming pumunta sa paglipas na sa lalong madaling panahon.
Madla: Oh, OK.
ANDI PENG: Oo.
SIGE.
Cool, ni reconvene bilang isang klase ipaalam.
SIGE.
Kaya ito ay uri ng isang open-ended na tanong sa kamalayan
na mayroong maraming mga kasagutan sa mga ito.
At kami ay pumunta sa paglipas ng ilan sa mga ito sa madaling sabi.
Nais ko lamang na makakuha ka ng isang lalaki nag-iisip tungkol sa kung ano differentiated
lahat ng tatlong mga uri ng mga uri.
At narinig ko, din, ang isang malaking question-- ano ang sumanib uri gawin?
Mahusay na katanungan, dahil na kung ano ang pinag sumasaklaw namin sa susunod.
>> Kaya sumanib-uuri ay ang isang uri na pag-andar
tunay naiiba mula sa iba pang mga uri.
Tulad see-- ka guys ang ginawa ni David na demo
kung saan siya ay nagkaroon ng lahat ng mga cool mga ingay ng mga nakakakita kung paano pagsamahin
sort tumakbo, tulad ng, walang katapusan mas mabilis kaysa sa iba pang mga dalawang uri?
SIGE.
Kaya na dahil merge sort nagpapatupad na hatiin
at mapaglabanan konsepto na kami usapan tungkol sa isang pulutong sa lecture.
Sa kahulugan na tulad namin sa trabaho mas matalinong, hindi mahirap, kapag hatiin mo
at mapaglabanan ang mga problema, at masira ang mga ito down, at pagkatapos ay ilagay ang mga ito nang sama-sama,
magandang bagay na laging mangyayari.
>> Kaya ang paraan na sumanib sort mahalagang gumagana
ay na ito naghihiwalay ang isang unsorted array sa kalahati.
At pagkatapos ito ay nakuha ng dalawang kalahati ng array.
At kusa itong isinasaayos lamang ang mga dalawang halves.
Ito ay para mapigil lang naghahati sa kalahati, sa kalahati, sa kalahati hanggang ang lahat ay inayos
at pagkatapos ay recursively inilalagay ang lahat ng ito nang magkasama.
>> Kaya na talagang abstract.
Kaya ito ay lamang ng isang piraso ng pseudocode.
Ba na magkaroon ng kahulugan sa ang paraan na ito ay tumatakbo?
Kaya sabihin lamang sabihin mayroon kang isang ang dami ng n elemento, tama?
Kung ang n ay mas mababa sa 2, maaari kang bumalik.
Dahil alam mo na kung may lamang ng isang bagay, ito ay dapat na pinagsunod-sunod.
Iba Pa, mong ayusin ang kaliwang kalahati, at pagkatapos mong ayusin ang kanang kalahati,
at pagkatapos mong pagsamahin.
>> Kaya habang mukhang talagang madali na, sa katotohanan, ang pag-iisip tungkol sa mga ito ay
uri ng mahirap. Dahil ikaw ay tulad ng, well, na uri ng mga tumatakbo sa sarili nito.
Right?
Ito ay tumatakbo sa sarili nito.
Kaya sa na kahulugan, hinawakan David sa recursion sa klase.
At iyon ay isang konsepto kami makipag-usap tungkol sa higit pa.
Ito ay na ito, ang mga ito ng dalawang linya dito, talagang ay lamang ang programa
nagsasabi ito upang magpatakbo ng sarili nito may iba't ibang mga input.
Kaya sa halip na tumakbo ang sarili sa ang kabuuan ng n elemento,
maaari mong break na ito down sa mga kaliwang kalahati at ang kanang kalahati
at pagkatapos ay patakbuhin itong muli.
>> At pagkatapos ay titingnan namin ito biswal, dahil ako ay isang visual learner.
Ito ay gumagana mas mahusay para sa akin.
Kaya kami ay tumingin sa isang visual na halimbawa dito.
>> Ipagpalagay natin na mayroon kami ng isang array, anim elemento, 3, 5, 2, 6, 4, 1, hindi nakaayos.
Lahat ng karapatan, mayroong isang pulutong sa pahinang ito.
Kaya kung maaari pagtingin mo guys sa unang hakbang dito, 3, 5, 2, 6, 4, 1,
maaari mong hatiin ito sa kalahati.
Ikaw ay may 3, 5, 2, 6, 4, 1.
Alam mo na ang mga aren't-- mo hindi alam kung sila ay inayos o hindi,
kaya patuloy mong paglabag sa kanila down, sa kalahati, sa kalahati, sa kalahati, hanggang sa huli,
mayroon ka lamang isang element.
At ang isang elemento ay palaging nakaayos, di ba?
>> Upang malaman namin na 3, 5, 2, 4, 6, 1, sa pamamagitan ng kanilang sarili, ay nakaayos.
At ngayon, maaari naming ilagay ang mga ito pabalik sama-sama.
Upang malaman namin ang 3, 5.
Inilalagay namin ang mga magkasama.
Alam namin na ang pinagsunod-sunod na.
Ang 2 pa rin doon.
Maaari naming ilagay ang 4 at ang 6 na magkasama.
Alam namin na na pinagsunod-sunod, kaya ilagay natin na magkasama.
At ang 1 ay may.
>> At pagkatapos ay tumingin ka lamang sa ang dalawang halves karapatan dito.
Ikaw ay may 3, 5, 2, 2, 3, 5.
Maaari mo lamang ihambing ang simula ng lahat ng bagay.
Dahil alam mo na ito ay inayos at alam mo na na pinagsunod-sunod.
Kaya nga hindi mo kahit na may sa ihambing ang 5, ihambing mo ang mga 3.
At ang 2 ay mas mababa sa 3, kaya kung 2 ay dapat pumunta sa dulo.
>> Parehong bagay sa banda roon.
Ang 1 ay dapat pumunta dito.
At pagkatapos ay kapag pumunta sa iyo upang ilagay dalawang mga halaga sa mga sama-sama,
alam sa iyo na ito ay inayos at alam mo na na pinagsunod-sunod.
Kaya pagkatapos ay ang 1 at ang 2, ang 1 ay mas mababa sa 2.
Iyon ay nagsasabi sa iyo na ang 1 dapat pumunta sa dulo ng ito
walang kahit na naghahanap sa 3 o 5.
At pagkatapos ay ang 4, maaari mo lamang suriin, ito ay pumunta sa dito mismo.
Hindi mo na kailangang hanapin ang 5.
Parehong bagay na may 6.
Alam mo na ang 6-- ito lamang ay hindi kailangang tumingin.
>> At kaya sa paraang iyon, ikaw ay lamang sa pag-save ang iyong sarili
isang pulutong ng mga hakbang na ito kapag ikaw ay paghahambing.
Wala kang upang ihambing ang bawat elemento laban sa iba pang mga elemento.
Lamang ihambing mo laban sa mga na kailangan mo upang ihambing ito laban.
Kaya na uri ng isang abstract na konsepto.
Huwag mag-alala kung ito ay hindi lubos na pagpindot sa iyo karapatan pa.
Ngunit sa pangkalahatan, ito ay kung paano gumagana ang isang uri merge.
Tanong, mabilis na katanungan, bago ako lumipat sa?
Oo.
>> Madla: Kaya sinabi mo na ikaw ay kumuha ng ang 1, at pagkatapos ay ang 4, at ang 6
at ilagay ang mga ito sa.
Kaya hindi those-- ay hindi Naghahanap ka ba sa kanila
bilang hiwalay na mga elemento, hindi gaya ng buo?
ANDI PENG: Oo.
Kaya kung ano ang nangyayari ay na ikaw talaga
ay ang paglikha ng isang bagong tatak ng array.
Kaya alam mo na, dito, mayroon akong dalawang array ng laki 3, di ba?
Kaya alam mo na ang aking pinagsunod-sunod array pangangailangan na magkaroon ng anim na mga sangkap.
Kaya gumawa ka na lamang ng isang bagong halaga ng memorya.
Kaya ikaw ay uri ng tulad ng pagiging mapag-aksaya ng memory,
ngunit iyon ay hindi mahalaga dahil ito ay kaya maliit.
Kaya tingnan mo ang 1 at titingnan mo ang 2.
At alam mo na ang 1 ay mas mababa sa 2.
Kaya alam mo na ang 1 ay dapat pumunta sa ang simula ng lahat ng mga iyon.
>> Hindi mo na kailangan na tingnan ang 3 at ang 5.
Kaya alam mo 1 napupunta doon.
Pagkatapos talaga ikaw tumaga off ang 1.
Ito ay, tulad ng, mga patay na sa amin.
Pagkatapos kami na lang 2, 3, 5, at pagkatapos ay 4 at 6.
At pagkatapos mong malaman na, ikaw ihambing ang 4 at ang 2,
oh, ang 2 ay dapat pumunta sa doon.
Kaya gumawa ng mapa sa iyo ang 2 down, tumaga off mo ito.
Kaya pagkatapos mo na lang ang 3 at ang 5 sa 4 at ang 6.
At mo lamang panatilihin ang pagpuputol ito off hanggang sa inilagay mo ang mga ito sa array.
>> Madla: Kaya ikaw ay laging lamang paghahambing ng [hindi marinig]?
>> ANDI PENG: Eksakto.
Kaya sa kamalayan, ikaw ay lamang sa paghahambing, mahalagang,
isang numero laban sa iba pang numero.
At dahil alam mo na ito ay inayos, mo
Hindi mo na kailangang hanapin sa pamamagitan ng lahat ng mga numero.
Ikaw lamang ang may upang tumingin sa ang unang isa.
At pagkatapos ay maaari mo lamang gumawa ng mapa down ang mga ito, dahil alam mo
pag-aari nila kung saan kailangan nilang nabibilang.
Oo.
Magandang tanong.
>> At pagkatapos ay kung anuman sa iyo ay isang bit mapaglunggati,
huwag mag-atubiling tingnan ang code na ito.
Ito ay talagang ang pisikal na pagpapatupad
ng kung paano namin magsulat pagsasama-uuri.
At maaari mong makita, ito ay masyadong maikli.
Ngunit ang mga ideya sa likod mga ito pretty complex.
Kaya kung sa tingin mo ay tulad ng pagguhit this out sa iyong mga araling-bahay sa gabing ito, huwag mag-atubiling.
>> SIGE.
Kaya din nagpunta si David sa mga ito sa panayam.
Ano ang mga pinakamahusay na kaso runtimes, pinakamasama runtimes kaso,
at ang inaasahang runtimes ng pagsasama-uuri?
Ang isang pares segundo mag-isip.
Ito ay medyo mahirap, ngunit ang uri ng intuitive kung sa tingin mo ang tungkol dito.
Lahat tama.
>> Madla: ang pinakamasama kaso n log n Ay?
ANDI PENG: Eksakto.
At bakit ito n log n.
>> Madla: Ay hindi ito sapagkat ito nagiging exponentially mas mabilis,
kaya ito ay tulad ng isang function ng na sa halip na lamang simpleng pagiging n
nakalapat o isang bagay?
ANDI PENG: Eksakto.
Kaya ang dahilan kung bakit ang mga runtime sa mga ito ay n log
n ay because-- kung ano ang iyong paggawa sa lahat ng mga hakbang na ito?
Lamang ka pagpuputol ito sa kalahati, di ba?
At kaya kapag kami ay gumagawa ng mga mag-log, ang lahat na ito ay ginagawa
ay naghahati ng isang problema sa kalahati, sa kalahati, sa kalahati, sa mas maraming mga halves.
At sa na kahulugan, maaari mong uri ng maalis ang mga linear na modelo
na hindi namin ginagamit.
Dahil kapag tumaga mga bagay-bagay sa kalahati, ito ay isang mag-log.
Iyan na lamang ang mathematical paraan ng kumakatawan sa mga ito.
>> At pagkatapos ay sa wakas, sa dulo, ikaw ay paggawa ng lamang ng isang huling pass sa pamamagitan ng
upang ilagay ang lahat ng mga ito sa pagkakasunud-sunod, i-right?
At kaya kung mayroon lamang sa iyo upang suriin ang isang bagay, na ang n.
At kaya ikaw ay uri ng multiply ang dalawang magkasama.
Kaya ito ay tulad nakuha mo na ang final suriin para n down dito sa isang log ng n
dito sa taas.
At kung ikaw ay paramihin kanila, na n log n.
>> At upang ang mga pinakamahusay na kaso at pinakamasama kaso at inaasahan ay ang lahat n log n.
Ito ay tulad ng iba pang mga uri din.
Ito ay tulad ng pagpili ng uri sa kahulugan na ito
hindi mahalaga kung ano ang iyong listahan ay, ito lamang ay pagpunta
upang gawin ang parehong bagay sa bawat isang oras.
SIGE.
Kaya bilang maaari mong makita ang isang lalaki, kahit na ang uri na kami ay wala through-- n
nakalapat, ito ay hindi masyadong mahusay.
At kahit na ito n log n ay hindi ang pinaka mahusay.
Kung ikaw guys ay kakaiba, mayroong mga mekanismo uri
na kaya mahusay na ang mga ito halos mahalagang flat sa runtime.
>> Mayroon kang ilang mga mag-log n ni.
Mayroon kang ilang mga mag-log-log n ni.
Hindi namin hawakan sa kanila sa ganitong klase ngayon.
Ngunit kung ikaw guys ay kakaiba, huwag mag-atubili sa google, kung ano ang
ang pinaka mahusay na pag-uuri mekanismo.
Hindi ko alam, may mga ang ilang mga talagang nakakatawa iyan,
like-- mayroong ilang mga talagang funny mga na gumawa ng mga tao.
At iniisip mo kung paano sila kailanman naisip na iyon.
Kaya google, kung mayroon kang ilang mga bakanteng panahon, sa, ano ang ilang mga nakakatawang paraan
na people-- pati na rin mabisa ways-- tao
ay maaaring ipatupad ng masama.
SIGE.
At dito ay lamang ng isang madaling-magamit na maliit na chart.
Alam ko ang lahat ng sa iyo, bago na pagsusulit 0, ay magiging sa iyong room marahil sinusubukan
kabisaduhin iyon.
Kaya na magaling sa doon para sa iyo guys.
Lang huwag kalimutan ang logic na made-- kung bakit ang mga numero ay nagaganap.
Kung palaging ikaw ay nawala, kailangan lang gumawa Siguraduhin na alam mo kung ano ang mga uri ay.
At maaari mong patakbuhin sa pamamagitan ng ang mga ito sa iyong isip
upang malaman kung bakit ang mga mga sagot ay ang mga sagot.
>> Lahat tama.
Kaya kami ay pagpunta upang ilipat on, sa wakas, upang maghanap.
Dahil bilang mga mo na basahin ang pset,
searching ay bahagi rin ng Nagtatakda ang problemang ito linggong ito.
Hihilingin sa iyo na ipatupad dalawang uri ng mga paghahanap.
Ang isa ay isang linear paghahanap at ang isa ay isang binary paghahanap.
>> Kaya ang haba ng paghahanap ay medyo madali.
Ikaw lamang ang nais na elemento sa paghahanap ng isang listahan upang makita kung nakuha mo ito.
Ikaw lamang ang may upang umulit sa pamamagitan ng.
At kung ito ay katumbas ng isang bagay, maaari kang bumalik lang ito, di ba?
Ngunit ang isa na hindi namin pinaka interesado sa pakikipag-usap tungkol
ay binary paghahanap, kanan, kung saan ay ang hatiin at mapaglabanan mekanismo kung saan
David ay nagpapakita sa panayam.
>> Tandaan ang mga halimbawa ng telepono ng libro na siya mapigil ang nagdadala up,
ang isa na siya ang uri ng nahirapan ng kaunti sa ito nakaraang taon,
kung saan mo hatiin ang problema sa kalahati, sa kalahati, sa kalahati, muli at muli,
hanggang sa mahanap mo kung ano ang iyong hinahanap?
At nakuha mo na ang runtime ng na pati na rin.
At maaari mong makita, ito ay makabuluhang mas mahusay
kaysa sa anumang iba pang uri ng paghahanap.
>> Kaya ang paraan na gusto namin pumunta tungkol sa pagpapatupad ng isang binary search
ay, kung kami ay may isang array, index 0 hanggang 6, pitong elemento,
maaari naming tumingin sa gitna, right-- Paumanhin, kung ang aming mga tanong first--
kung gusto naming tanungin ang tanong ng, ay ang array na naglalaman ng mga elemento ng 7,
malinaw naman, ang pagiging tao, at pagkakaroon tulad ng isang maliit na hanay, ito ay madali para sa amin
sabihin ninyo ang oo.
Ngunit ang mga paraan upang ipatupad ang isang binary search ay upang tumingin sa gitna.
>> Alam namin na ang index 3 ay gitna, dahil tayo
kung may mga pitong elemento.
Ano 7 hinati sa 2?
Maaari mong tumaga off na ang dagdag na 1.
Nakuha mo na ang 3 sa gitna.
Kaya ay ang dami ng mga 3 katumbas ng 7?
Ito ay hindi, tama?
Ngunit maaari naming gawin ang isang pares ng mga tseke.
Ay array of 3 mas mababa sa 7 o ay ang dami ng mga 3 mas malaki kaysa sa 7?
>> At nalalaman natin na ito ay mas mababa kaysa sa 7.
Upang malaman namin na, oh, ito ay dapat na hindi sa kaliwang kalahati.
Alam namin na ito ay dapat na sa kanang kalahati, di ba?
Kaya maaari lang namin tumaga off ang kalahati ng array.
Hindi namin kahit na may sa tingnan ang mga ito anymore.
Dahil alam namin na kalahati ng aming problem--
Alam namin na ang mga sagot ay nasa ang kanang kalahati ng aming mga problema.
Kaya tingnan lang namin sa na ngayon.
>> Kaya ngayon tinitingnan namin ang mga gitna ng kung ano ang natitira.
Iyon index 5.
Ginagawa namin ang parehong muli check at nakita namin na ito ay mas maliit.
Kaya tingnan natin sa kaliwa ng na.
At pagkatapos ay namin makita ang check na iyon.
Ay ang halaga ng array sa index 4 na katumbas ng 7?
Ito ay.
Kaya maaari naming nagbabalik ng tunay, dahil natagpuan namin ang mga halaga sa aming listahan.
Sinusuportahan ba ng paraan nagpunta ako sa pamamagitan na magkaroon ng kahulugan sa lahat ng tao?
SIGE.
Bibigyan kita ng isang lalaki na siguro, tulad ng, tatlo, apat na minuto upang malaman kung
kung paano mag-Pseudocode ito in.
>> Kaya akala tinanong ko sa iyo na magsulat ng isang function na tinatawag na search () na ibabalik
isang halaga, isang Boolean halaga, iyon ay totoo o false-- gusto,
tunay na kung nahanap mo ang halaga, huwad na kung ikaw ay hindi.
At pagkatapos ay kayo ay lumipas sa ang halaga sa iyo
hinahanap sa mga halaga, na ay ang array-- oh, talagang ilagay ko
na sa maling lugar.
SIGE.
Anyways, na dapat magkaroon ng naging sa kanan ng halaga.
At pagkatapos int n ay ang bilang ng mga elemento sa array na.
Paano mo pumunta tungkol sa pagsubok sa pseudocode na problema sa?
Bibigyan kita ng isang lalaki tulad ng tatlong minuto upang gawin iyon.
Hindi, tingin ko ay may only-- oo, mayroong isang karapatan up dito.
Madla: Maaari ko bang?
ANDI PENG: Oo, nakuha ko sa iyo.
Ay na working?
OK, cool.
>> SIGE.
Lahat ng mga karapatan guys, hindi namin pagpunta upang bigyang-laya ang mga ito sa.
SIGE.
Kaya akala namin nakuha ang kaibig-ibig maliit na array na may n mga halaga sa loob nito.
Hindi ko gumuhit ng mga linya.
Ngunit kung paano namin pumunta tungkol sa sinusubukang isulat ito?
Sinumang gusto ba sa bigyan ako ang unang linya?
Kung nais mong ibigay sa akin ang unang linya ng pseudocode.
>> Madla: [hindi marinig]
Madla: Gusto mo gusto upang umulit through--
Madla: lamang ng isa pang para sa loop?
Madla: --for.
>> ANDI PENG: Kaya ang isang ito ay isang bit mapanlinlang.
Isipin about-- gusto mong upang panatilihing tumatakbo ito loop
paulit-ulit-ulit hanggang kailan?
>> Madla: Hanggang sa [hindi marinig] halaga ay katumbas ng halaga.
ANDI PENG: Eksakto.
Kaya maaari mong talagang lamang write-- maaari naming kahit na gawing simple ito ng mas maraming.
Maaari lang namin gawin ang isang habang loop, di ba?
Kaya maaari mo na lang ay loop-- alam namin na ito ay isang habang.
Ngunit para sa ngayon, ako pagpunta sabihin ang "loop" - sa pamamagitan ng kung ano?
Umikot until-- kung ano ang ang aming pagtatapos na kalagayan?
Sa tingin ko narinig ko ito.
Narinig ko ang isang tao sabihin ito.
>> Madla: Values ​​katumbas gitna.
ANDI PENG: Sabihin mo ulit ito.
Madla: O, hanggang sa halaga ang iyong hinahanap
para sa ay pantay-pantay sa gitna halaga.
>> ANDI PENG: Paano kung ito ay hindi doon?
Paano kung ang halaga ng iyong hinahanap para sa ay hindi tunay na sa array na ito?
Madla: Bumalik ka 1.
>> ANDI PENG: Ngunit kung ano ang gusto namin na loop hanggang kung kami ay may isang kondisyon?
Oo.
>> Madla: Hanggang mayroong isa lamang na halaga?
ANDI PENG: Maaari kang loop until-- upang malaman mo na ikaw ay
pagpunta sa magkaroon ng isang max na halaga, i-right?
At alam mo na ikaw ay pagpunta na magkaroon ng isang halaga min, di ba?
Dahil din, na isang bagay Nakalimutan ko na sabihin sa bago,
na ang isang bagay na kritikal na tungkol sa binary paghahanap
ay na ang iyong array na pinagsunod-sunod.
Dahil walang paraan ng paggawa ng na ito kung ang mga ito ay lamang ng random na mga halaga.
Hindi mo alam kung ang isa ay mas malaki kaysa sa isa, i-right?
>> Kaya alam mo na ang iyong mga max at iyong mins ang narito, di ba?
Kung ikaw ay pupunta sa pag-aayos iyong max sa iyong mins at ang mid--
akala ni lamang ipaalam sa iyong mid halaga ay tama here--
ikaw ay pagpunta sa isa lamang loop hanggang ang iyong minimum ay
tungkol sa parehong bilang iyong max, kanan, o kung ang iyong max ay hindi ang parehong bilang iyong min.
Right?
Dahil kapag nangyari iyon, alam mo na huli mo na pindutin ang parehong halaga.
Kaya nais mong loop hanggang ang iyong min ay mas mababa sa o katumbas ng to-- Oops,
hindi mas mababa sa o katumbas ng, ang iba pang paraan around-- max ay.
>> Ang ibig na magkaroon ng kahulugan?
Kinuha ko ng ilang pagsubok upang makakuha ng karapatan.
Ngunit loop hanggang ang iyong max na halaga ay mahalagang halos mas mababa
kaysa sa o katumbas ng iyong minimum, di ba?
Na kapag alam mo na iyong converged.
Madla: Kapag ang sa iyong maximum halaga na mas mababa kaysa sa minimum na?
ANDI PENG: Kung patuloy mong pag-aayos ng mga ito, na
ay kung ano ang kami ay pagpunta na ginagawa sa mga ito.
Ba na magkaroon ng kahulugan?
Minimum at max ay lamang integer na tayo ay marahil
pagpunta sa nais na lumikha upang panatilihin subaybayan ng kung saan kami ay naghahanap.
Dahil umiiral ang array hindi alintana ng kung anong ginagawa namin.
Tulad ng, hindi namin hindi aktwal na pisikal na pagpuputol off ang array, di ba?
Lang kami ng pag-aayos na kung saan kami ay naghahanap.
Ba na magkaroon ng kahulugan?
>> Madla: Oo.
>> ANDI PENG: OK.
Kaya kung iyon ang kondisyon para sa aming loop, kung ano ang gusto namin sa loob ng loop na ito?
Ano kami ay pagpunta sa ma-kulang na gawin?
Kaya ngayon, mayroon ka namin isang max at isang min, kanan,
Malamang na nilikha up dito lugar.
Kami ay pagpunta sa marahil nais upang mahanap ang isang gitnang, di ba?
Paano kami magiging maaaring upang mahanap ang gitna?
Ano ang mathematical--
Madla: Max plus min hinati sa 2.
ANDI PENG: Eksakto.
Ba na magkaroon ng kahulugan?
At gawin mo guys makita kung bakit namin Hindi lang use-- kung bakit namin ginawa ito
sa halip ng paggawa ng lamang n hinati sa 2?
Ito ay dahil n ay isang halaga na pupuntahan manatiling pareho.
Right?
Ngunit bilang ayusin namin ang aming minimum at maximum na mga halaga, sila ay pagpunta upang baguhin.
At bilang isang resulta, ang aming gitnang ay pagpunta sa baguhin masyadong.
Kaya na ang dahilan kung bakit gusto naming upang gawin ito karapatan dito.
SIGE.
>> At pagkatapos ay, ngayon na nalaman namin our-- oo.
>> Madla: lamang ng isang mabilis question-- kapag sinabi mong min at max,
tayo sa pagpapalagay na na ito ay inayos?
>> ANDI PENG: Oo, na talagang isang precondition para sa isang binary paghahanap,
na kailangan mong malaman kung ito ay pinagsunod-sunod.
Aling ang dahilan kung bakit ang uri, isulat mo sa iyong itakda ang problema bago ang iyong binary paghahanap.
SIGE.
Kaya ngayon na alam namin kung saan ang aming midpoint ay, kung ano ang gusto mong gawin dito?
>> Madla: Gusto naming ihambing na sa iba pang isa.
ANDI PENG: Eksakto.
Kaya ikaw ay pagpunta upang ihambing kalagitnaan sa halaga, i-right?
At ano ang na sabihin sa amin kapag kami ihambing?
Ano ang gusto naming gawin pagkatapos?
>> Madla: Kung ang halaga ay mas malaki kaysa sa mid, gusto naming i-cut-off ito.
ANDI PENG: Eksakto.
Kaya kung ang halaga ay mas malaki kaysa sa mid, hindi namin
pagpunta sa nais na baguhin ang mga minimum at maxes, di ba?
Ano ang gusto namin upang baguhin?
Kaya kung alam namin ang halaga ay isang lugar sa dito, kung ano ang ginagawa namin sa inyo na baguhin?
Gusto naming baguhin ang aming mga minimum na mid, di ba?
At pagkatapos ng iba pa, kung ito ay sa ito kalahati, ano ang gusto namin upang baguhin?
>> Madla: Ang iyong maximum.
ANDI PENG: Oo.
At pagkatapos lamang ikaw ay pagpunta upang panatilihin ang looping, di ba?
Dahil ngayon, pagkatapos ng isang pag-ulit sa pamamagitan ng, mayroon ka ng isang max dito.
At pagkatapos ay maaari mong muling kalkulahin ang isang kalagitnaan.
At pagkatapos ay maaari mong ihambing.
At ikaw ay pagpunta upang panatilihin ang pagpunta hanggang sa min at ang maxes
may mahalagang converged.
At na kapag alam mo na ikaw ay pindutin ang dulo nito.
At alinman na iyong natagpuan ito o hindi mo pa sa puntong iyon.
>> Ba ito gumawa ng kahulugan sa lahat ng tao?
SIGE.
Ito ay medyo mahalaga, dahil magkakaroon ka ng
na isulat ito sa iyong code na ngayong gabi.
Ngunit mayroon kang guys isang magandang magandang kahulugan ng kung ano ang dapat mong ginagawa,
na kung saan ay mabuti.
SIGE.
Kaya mayroon kami tungkol sa pitong section minuto ang natitira.
Kaya kami ay pagpunta sa makipag-usap tungkol sa pset na ito na makikita ginagawa namin.
Kaya ang pset ay nahahati sa dalawang halves.
Ang unang kalahati ay nagsasangkot pagpapatupad ng isang mahanap
kung saan ka magsulat ng isang linear paghahanap, ang isang binary paghahanap, at isang pag-uuri algorithm.
>> Kaya ito ay ang unang oras sa isang pset kung saan
kami ay magiging pagbibigay sa iyo ng isang lalaki kung ano ang tinatawag code ng pamamahagi, na kung saan ay code
na tayo ay may pre-nakasulat, ngunit iniwan lamang ng ilang mga piraso off
para sa iyo upang tapusin ang pagsusulat.
Kaya ikaw lalaki, kapag tiningnan mo ang mga ito code, maaari kang makakuha ng talagang natakot.
Kung ikaw ay tulad lamang, ahh, ako hindi alam kung ano na ang ginagawa,
Hindi ko alam, tulad ng, na tila kaya kumplikado, ahh, magpahinga.
Ito ay OK.
Basahin ang spec.
Spec ay magpapaliwanag nang eksakto sa iyo kung ano ang lahat ng mga programang ito ay ginagawa.
>> Halimbawa, generate.c ay isang programa na darating sa iyong pset.
Hindi mo talagang may sa hawakan ito, ngunit dapat mong maunawaan kung ano ang ginagawa nito.
At generate.c, ang lahat ng ito ay ginagawa ay alinman sa pagbuo ng mga random na numero
o maaari mong bigyan ito ng isang binhi, tulad ng isang nakasaayos number na ito ay tumatagal,
at ito ay bumubuo ng mas maraming numero.
Kaya mayroong isang tiyak na paraan upang ipatupad generate.c kung saan
maaari ka lamang magkaroon ng isang bungkos ng mga numero para sa iyo na subukan ang iyong mga iba pang mga pamamaraan sa.
>> Kaya kung nais mong, para sa Halimbawa, subukan ang iyong mahanap,
Gusto mo nais na tumakbo generate.c, makabuo ng grupo ng mga numero,
at pagkatapos ay patakbuhin ang iyong mga function katulong.
Ang iyong function Katulong ay kung saan ikaw ay aktwal na pisikal na pagsusulat ng code.
At sa tingin ng mga Katulong bilang isang file library sumusulat ka na find ang tumatawag.
At kaya sa loob helpers.c, makikita mo gawin ang paghahanap at pag-uuri.
>> At pagkatapos ang iyong pagpunta sa mahalagang lamang ilagay ang mga ito sa lahat ng sama-sama.
Spec ay magsasabi sa iyo kung paano ilagay na sa linya ng command.
At makikita mo na ang pagsubok kung o hindi ang iyong uri-uriin at paghahanap ay gumagana.
Cool.
Nagsimula na ang sinuman at Nakatagpo ng mga problema o mga katanungan
Mayroon ngayon sila sa mga ito?
SIGE.
>> Madla: Maghintay.
May tanong ako.
>> ANDI PENG: Oo.
>> Madla: Kaya sinimulan ko ang paggawa ang haba ng paghahanap sa helpers.c
at ito ay hindi talaga gumagana.
Ngunit pagkatapos ay sa ibang pagkakataon, natagpuan ko ang lang namin kung tanggalin ang mga ito at gawin binary paghahanap.
Kaya ang bagay na ito kung ito ay hindi gumagana?
>> ANDI PENG: Maikling sagot ay hindi.
Ngunit dahil hindi namin not--
Madla: Subalit walang sinuman ang talagang suri.
ANDI PENG: Kami ay hindi kailanman pagpunta upang makita na.
Ngunit malamang na gusto mong magkaroon ng siguraduhin na ang iyong paghahanap ay gumagana.
Dahil kung ang iyong linear search ay hindi gumagana,
pagkatapos pagkakataon ay ang iyong binary paghahanap ay hindi pumapasok sa trabaho pati na rin.
Dahil ikaw ay may katulad na logic sa pareho ng mga ito.
At hindi, ito ay hindi talagang mahalaga.
Kaya ang tanging mga makikita mo naman sa mga uri at binary paghahanap.
Oo.
>> At din, ang isang pulutong ng mga bata ay sinusubukan upang makatipon helpers.c.
Hindi ka talagang pinapayagan upang gawin iyon, dahil helpers.c
hindi magkaroon ng isang pangunahing pag-andar.
At kaya dapat mo lamang maging tunay na pag-ipon
bumuo at hanapin, dahil mahanap tawag helpers.c at ang mga function sa loob nito.
Kaya na gumagawa ng pag-debug isang sakit sa puwit.
Ngunit iyon lamang ang kung ano ang mayroon kaming gawin.
Madla: Gagawin mo lamang ang lahat, di ba?
ANDI PENG: Maaari mo lamang gumawa ng lahat pati na rin, oo.
SIGE.
Kaya na ito sa mga tuntunin ng kung ano ang ang pset ay humihingi sa inyo ang lahat ng dapat gawin.
Kung mayroon kang anumang mga katanungan, huwag mag atubiling magtanong sa akin pagkatapos ng seksyon.
Kukunin ko dito para sa, tulad ng, mga 20 minuto.
>> At oo, ang pset ni talagang hindi na masama.
Ikaw guys ay dapat na OK.
Ang mga ito, sundin lamang ang mga alituntunin.
Uri ng magkaroon ng isang pakiramdam ng pagkakaroon ng, lohikal, kung ano dapat mangyari at ikaw ay multa.
Huwag masyadong natakot.
May isang pulutong ng code na nakasulat doon.
Huwag masyadong natakot kung wala ka maunawaan kung ano ang ibig sabihin ng lahat ng iyon.
Kung ito ay isang pulutong, ito ay ganap fine.
At dumating sa oras ng opisina.
Tutulungan ka namin tingnan.
>> Madla: Gamit ang dagdag na pag-andar, ang pagtingin namin sa mga up?
>> ANDI PENG: Oo, ang mga ito ay sa code.
Sa laro ng 15, kalahati ng na ito ay isinulat para sa iyo.
Kaya ang mga function ay mayroon na sa code.
Yep.
Lahat tama.
Well, best of luck.
Ito ay isang kasuklam-suklam na araw.
Kaya sana ka guys ay hindi pakiramdam masyadong masamang tungkol sa manatili sa loob at sa coding.