[Seinm ceoil] DAVID MALAN: Gach ceart. Gach ceart, fáilte ar ais. Mar sin, is é seo Seachtain 4, an tús de, cheana féin. Agus beidh tú a thabhairt chun cuimhne go bhfuil an tseachtain seo caite, chuir muid códú ar leataobh le haghaidh ach beagán agus thosaigh muid ag caint beagán níos mó ard-leibhéal, faoi rudaí cosúil le cuardach agus sórtáil, a cé Tá smaointe beagán simplí, ionadaí d'aicme fadhbanna beidh tú tús a réiteach go háirithe mar a dtosaíonn tú ag smaoineamh faoi deiridh tionscadail agus réitigh suimiúil tú D'fhéadfadh a bheith ar fhadhbanna fíor-domhan. Anois, bhí saghas mboilgeog cheann de na simplí halgartaim den sórt sin, agus é a D'oibrigh ag a bhfuil na huimhreacha beaga i liosta nó i sraith de chineál mboilgeog a mbealach suas go dtí an barr, agus an bogadh líon mór ar a mbealach síos go dtí an deireadh an liosta sin. Agus cuimhne go raibh muid ábalta a shamhlú saghas mboilgeog beag rud éigin mar seo. Mar sin, lig dom dul ar aghaidh agus cliceáil Tosaigh. Tá mé preselected saghas mboilgeog. Agus má tá tú chun cuimhne go bhfuil an gorm níos airde Léiríonn línte líon mór, beag Léiríonn línte gorm uimhreacha beaga, mar théann muid tríd an arís agus arís eile agus arís, i gcomparáid dhá barraí aice le gach eile i dearg, táimid ag dul a mhalartú an is mó agus is lú má go bhfuil siad as ord. Mar sin, beidh sé seo dul ar aghaidh agus dul ar aghaidh agus dul ar, agus feicfidh tú go bhfuil an níos mó gnéithe ag déanamh a mbealach chuig an ceart, agus is iad na heilimintí níos lú ag déanamh a mbealach ar an taobh clé. Ach thosaigh muid a chainníochtú an éifeachtúlacht, an caighdeán an algartam. Agus dúirt muid gur i an ceann is measa chás, ghlac an algartam thart ar cé mhéad céimeanna? Mar sin, n cearnógach. Agus cad a bhí n? LUCHT ÉISTEACHTA: Líon na n-eilimintí. DAVID MALAN: Mar sin, n raibh an líon na n-eilimintí. Agus mar sin beidh orainn é seo a dhéanamh go minic. Aon uair is mian linn chun labhairt faoi an méid ar fhadhb nó ar mhéid an ionchur, nó an méid ama a thógann sé aschur a thabhairt ar aird, beidh muid díreach ghinearálaithe cibé Is é an t-ionchur mar n. Mar sin, ar ais i Seachtain 0, leathanaigh ar an líon sa leabhar teileafóin a bhí n. An líon na mac léinn sa seomra a bhí n. Mar sin anseo, freisin, tá muid tar éis go patrún. Anois, n cearnógach nach bhfuil go háirithe go tapa, mar sin rinneamar iarracht a dhéanamh níos fearr. Agus mar sin d'fhéachamar ar feadh cúpla algartaim eile, i measc a Bhí saghas roghnú. Mar sin, saghas roghnaithe a bhí beagán difriúil. Bhí sé beagnach simplí, dare liom a rá, trína thosaigh mé ag tús an liosta de na ár n-oibrithe deonacha agus mé díreach tar éis arís agus arís agus arís chuaigh trí an liosta, stoitheadh ​​amach is lú eilimint ag an am agus a chur air nó léi ag tús an liosta. Ach seo, freisin, nuair a thosaigh muid ag smaoineamh tríd an mata agus níos mó pictiúr, shíl faoi conas a mhéad uair Bhí mé ag dul ar ais agus amach agus ar ais 's anall, a dúirt muid i gcás is measa, saghas roghnú, freisin, a bhí cad é? n cearnógach. Anois, ar fud an domhain fíor, d'fhéadfadh sé a bheith i ndáiríre beagán níos tapúla. Toisc arís, ní raibh mé a choinneáil cúlú nuair a bhí curtha in eagar mé an heilimintí is lú. Ach má cheapann againn faoi n-mhór, agus má tá tú saghas a dhéanamh amach an mata mar Rinne mé ar an mbord, leis an cearnógach n rud éigin lúide, gach rud eile sa bhreis ar an n cearnógach, uair amháin n Faigheann ndáiríre mór nach bhfuil, ábhar i ndáiríre an oiread. Mar sin, mar eolaithe ríomhaireachta, linn a shórtáil de súil dall dul chuig an níos lú fachtóirí agus díriú ach ar an fachtóir i léiriú go bhfuil ag dul a dhéanamh an difríocht is mó. Bhuel, ar deireadh, d'fhéach muid ag sort isteach. Agus ba é seo den chineál céanna i spiorad, ach seachas dul trí iteratively agus roghnaigh an ceann is lú eilimint ag am, ghlac mé in áit an lámh go bhfuil mé Déileáladh, agus chinn mé, gach ceart, mbaineann tú anseo. Ansin bhog mé ar aghaidh go dtí an chéad bhall eile agus chinn go bhfuil sé nó bhain sí anseo. Agus ansin bhog mé ar aghaidh agus ar. Agus mé d'fhéadfadh a, feadh na slí, aistriú na guys d'fhonn seomra dóibh a dhéanamh. Mar sin, go raibh saghas an cúlú mheabhrach den saghas roghnaithe a chuirimid ar a dtugtar saghas chur isteach. Mar sin, na hábhair go dtarlóidh fud an domhain fíor. Díreach cúpla bliain ó shin, nuair a áirithe seanadóir bhí ag rith le haghaidh uachtarán, Eric Schmidt, ag an am an POF Google, bhí an deis iarbhír chun agallamh a chur air. Agus shíl muid gur mhaith linn seo a roinnt YouTube gearrthóg ar do shon anseo, más rud é go raibh muid ábalta dul suas an toirt. [Athsheinm físe] -Anois, Seanadóir, tá tú anseo ag Google, agus is maith liom chun smaoineamh ar an uachtaránacht mar agallaimh poist. [Gáire] -Anois, tá sé deacair a fháil post mar uachtarán. Agus tá tú ag dul trí an déine anois. Tá sé deacair freisin chun post a fháil ag Google. Tá ceisteanna againn agus iarraimid ár gceisteanna n-iarrthóirí. Agus is é an ceann seo ó Larry Schwimmer. [Gáire] -Tá tú guys smaoineamh Tá mé ag kidding? Tá sé ceart anseo. Cad é an bealach is éifeachtaí chun shórtáil milliún slánuimhreacha dhá-giotán? [Gáire] -Bhuel, uh - -I'm sorry. B'fhéidir ba chóir dúinn - -No, no, no, no, no. -Ní Sin - OK. -I mo thuairimse, ba mhaith an saghas mboilgeog a bheith ar an bealach mícheart chun dul. [Gáire] [Cheering agus bualadh bos] -Come on, a dúirt leis seo? OK. [Athsheinm físe END] DAVID MALAN: Mar sin, tá tú é. Mar sin, thosaigh muid a chainníochtú ar na rith amanna, mar a déarfá, le rud éigin ar a dtugtar nodaireacht asymptotic, a bhfuil ach a thagraíonn do ár saghas casadh súil dall ar na fachtóirí níos lú agus ach ag féachaint ar an am ag rith, fheidhmíocht na halgartaim, mar a fhaigheann n ndáiríre mór le himeacht ama. Agus mar sin thugamar isteach mór O. Agus mór O rud éigin ionadaíocht gur shíl muid de mar atá faoi cheangal uachtair. Agus i ndáiríre, Barry, is féidir linn níos ísle ná na mic le beagán? Shíl muid de é seo faoi cheangal uachtair. O chomh mór ar acmhainn n cearnógach go an cás is measa, rud éigin cosúil le Bheadh ​​saghas roghnú a ghlacadh n céimeanna cearnógach. Nó rud éigin cosúil le saghas leanas a chur isteach bheadh ​​n céimeanna cearnógach. Anois do rud éigin cosúil leanas a chur isteach saghas, cad a bhí an cás is measa? Mar gheall eagar, cad é an ceann is measa scéal is féidir go dtiocfadh leat a fháil bhíonn tú féin leis? Tá sé go hiomlán ar gcúl, ceart? Toisc má tá sé go hiomlán ar gcúl, bhfuil tú a dhéanamh a lán iomlán na hoibre. Toisc má tá tú go hiomlán ar gcúl, bhfuil tú ag dul chun teacht ar an eilimint is mó anseo, cé go Mbaineann sé síos ann. Mar sin, tá tú ag dul a rá, ceart go léir, ag an láthair in am, mbaineann tú anseo, mar sin a fhágann tú é féin. Ansin realize tú, ó, damnaigh, tá mé chun bogadh ngné seo beagán níos lú a an taobh clé de tú. Ansin, tá mé a dhéanamh arís agus arís agus arís eile. Agus má shiúil mé ar ais agus amach, tú Bheadh ​​saghas bhraitheann ar fheidhmíocht go algartam, mar tá i gcónaí mé shuffling gach duine eile síos sa sraith seomra a dhéanamh chun é. Mar sin tá go bhfuil an cás is measa. I gcodarsnacht leis sin - agus bhí sé seo cliffhanger uair dheireanach - dúirt muid gur saghas leanas a chur isteach Bhí óimige ar cad? Cad é an reáchtáil is fearr ar chás am saghas leanas a chur isteach? Mar sin, tá sé i ndáiríre n. Ba é sin an bán a d'fhág muid ar an mbord uair dheireanach. Agus tá sé óimige n mar gheall ar cén fáth? Bhuel, sa chás is fearr, an méid saghas chur isteach ag dul a bheith ar láimh? Bhuel, liosta go bhfuil curtha in eagar go hiomlán cheana féin, obair íosta a dhéanamh. Ach cad néata faoi saghas leanas a chur isteach is é sin mar a thosaíonn sé anseo agus chinneann, OH, tá tú ag an uimhir amháin, mbaineann tú anseo. Ó, cad a fhortún maith. Tá tú an uimhir a dó. Mbaineann tú anseo freisin. Uimhir a trí, níos fearr fós, mbaineann tú anseo. Chomh luath agus a fhaigheann sé go dtí deireadh na liosta, in aghaidh an saghas isteach ar pseudocode gur shiúil muid trí bhéal uair dheireanach, tá sé déanta. Ach saghas roghnú, ag gcodarsnacht leis sin, choimeád ag déanamh an méid? Choinnigh ag dul tríd an liosta arís agus arís agus arís eile. Mar gheall ar an léargas eochair ní raibh ach nuair atá tú d'fhéach sé go léir ar an mbealach chun an deireadh leis an liosta is féidir leat a bheith cinnte go raibh an eilimint a roghnaigh tú go deimhin, ar an eilimint láthair is lú. Mar sin, na éagsúla mheabhrach samhlacha deireadh suas bhunús dea roinnt fíor-domhan an- difríochtaí dúinn, chomh maith leis na difríochtaí asymptotic teoiriciúil. Mar sin, ach a recap, ansin, mór O de n cearnógach, atá feicthe againn le cúpla sórt sin halgartaim go dtí seo. Big O n? Cad é algartaim a d'fhéadfadh a a rá a bheith mór O n? Sa chás is measa, a thógann sé líon líneach céimeanna. OK, cuardaigh líneach. Agus i gcás is measa, áit a bhfuil an eilimint tá tú ag lorg nuair a bhfeidhm cuardaigh líneach? OK, i gcás is measa, nach bhfuil sé fiú ann. Nó sa dara cás is measa, tá sé léir ar an mbealach sa deireadh, a bhfuil móide-nó-lúide an difríocht amháin-chéim. Mar sin, ag deireadh an lae, is féidir linn a rá go bhfuil sé líneach. Bheadh ​​O Big de n a chuardach líneach, mar gheall ar an gcás is measa, an Tá eilimint ní fiú ann nó tá sé léir ar an mbealach ag an deireadh. Bhuel, mór O d'log de n. Ní raibh muid labhairt go mion mór faoi seo, ach atá feicthe againn seo roimhe seo. Cad ritheann i sin ar a dtugtar logartamach am, i gcás is measa? Yeah, cuardaigh ionas dénártha. Agus cuardaigh dénártha i gcás is measa D'fhéadfadh go mbeadh an eilimint áit éigin i an lár, nó áit éigin taobh istigh den eagar. Ach gheobhaidh tú ach aon uair amháin tú roinnt ar an liosta i leath, i leath, i leath, i leath. Agus ansin voila, tá sé ann. Nó arís, cás is measa, nach bhfuil sé fiú ann. Ach nach bhfuil a fhios agat nach bhfuil sé ann dtí go mbeidh tú saghas sin a bhaint amach deiridh bun-eilimintí an chuid is mó ag halving agus halving agus halving. Big O de 1. Mar sin, d'fhéadfadh muid mór O de 2, mór O de 3. Am ar bith is mian leat ach uimhir leanúnach, linn a shórtáil díreach de díreach shimpliú go chomh mór O de 1. Cé má tá go réalaíoch, a thógann sé 2 nó fiú 100 céim, má tá sé ina líon de shíor céimeanna, rá againn ach O mór de 1. Cad é an algartam go i mór O de 1? LUCHT ÉISTEACHTA: Lorg an fad na h-athróige. DAVID MALAN: Lorg an fad athróg? LUCHT ÉISTEACHTA: No, an fad má tá sé curtha in eagar cheana féin. DAVID MALAN: Maith. OK, mar sin a aimsiú an fad rud éigin a má tá an fad go bhfuil rud éigin, cosúil le eagar, a stóráiltear i roinnt athróg. Toisc gur féidir leat léamh ach an athróg, nó i gcló ar an athróg, nó ach rochtain a fháil go ginearálta go athraitheach. Agus voila, a thógann am tairiseach. I gcodarsnacht leis sin, smaoineamh ar ais go scratch. Smaoinigh ar ais go dtí an chéad seachtain de C, glaoch díreach printf agus priontáil Tá rud éigin ar an scáileán arguably am tairiseach, mar a thógann sé ach roinnt ar líon na timthriallta LAP a thaispeáint an téacs ar an scáileán. Nó fan - a dhéanann sé? Conas eile a d'fhéadfadh muid múnla an fheidhmíocht printf? Ar mhaith duine éigin cosúil go n-aontaíonn, go b'fhéidir nach bhfuil sé i ndáiríre am tairiseach? I cén chiall a d'fhéadfadh atá printf rith am, priontáil iarbhír ar shraith ar an scáileán, a bheith rud éigin seachas tairiseach. LUCHT ÉISTEACHTA: [inaudible]. DAVID MALAN: Yeah. Mar sin, braitheann sé ar ár thaobh. Má cheapann againn i ndáiríre ar an t-ionchur a printf mar an teaghrán, agus dá bhrí sin, a thomhas ar an méid sin ionchur ag a fhad - mar sin a ligean ar glaoch go fhad n chomh maith - fhéadfaí a rá, is é printf féin O mór de n mar atá sé ag dul a ghlacann tú n céimeanna a phriontáil amach gach ceann de na n carachtair, is dócha. Ar a laghad a mhéid glacaimid b'fhéidir go bhfuil sé ag baint úsáide as do lúb thíos an cochall. Ach ba mhaith linn chun breathnú ar an códú a thuiscint níos fearr. Agus go deimhin, nuair a thosaíonn tú guys anailís a dhéanamh ar do chuid féin halgartaim, beidh tú literally a dhéanamh go díreach. Sórtáil de eyeball do chód agus smaoineamh faoi ​​- ceart go léir, tá mé an lúb anseo nó mé a bheith lúb neadaithe anseo, go bhfuil ag dul a dhéanamh rudaí n n amanna, agus is féidir leat a shórtáil de bharr do bhealach a dhéanamh tríd an gcód, fiú má tá sé pseudocode agus ní ZIP iarbhír. Mar sin, cad mar gheall ar óimige de n cearnógach? Cad a bhí ar algartam go sa chuid is fearr cás, ghlac go fóill n céimeanna cearnógach? Yeah? LUCHT ÉISTEACHTA: [inaudible]. DAVID MALAN: sórtáil roghnú sin. Mar gheall go bhfuil fadhb laghdú i ndáiríre ar an bhfíric go arís, níl a fhios agam Fuair ​​mé an lú reatha go dtí go Mé sheiceáil go léir na heilimintí darn. Mar sin, óimige de, a rá, n, táimid ag ach tháinig suas le ceann amháin. Saghas Cuirtear isteach. Má tharlaíonn an liosta a shórtáil cheana féin, sa chás is fearr atá againn díreach a dhéanamh pas amháin tríd, ag an bpointe sin tá muid cinnte. Agus ansin d'fhéadfaí a rá a bheith líneach, do cinnte. Cad mar gheall ar óimige de 1? Cad iad, sa chás is fearr, a d'fhéadfadh a ghlacadh líon de shíor céimeanna? Search Mar sin, líneach, má tá tú a fháil ach t-ádh agus an eilimint bhfuil tú ag lorg Is ceart ag an tús an liosta, más rud é go nuair a bhíonn tú ag tosú do líneach traversal den liosta sin. Agus tá sé seo fíor a roinnt rudaí. Mar shampla, fiú dénártha search óimige de 1. Mar gheall ar cad má fhaigheann tú i ndáiríre darn ádh agus smack DAB-i lár an Is é do eagar an líon bhfuil tú ag lorg? Mar sin, is féidir leat a fháil t-ádh ann, chomh maith. Sé seo ar cheann, ar deireadh, óimige de n logáil n. Mar sin, n n logáil, ní raibh muid i ndáiríre labhairt faoi go fóill, ach - LUCHT ÉISTEACHTA: Cumaisc saghas? DAVID MALAN: Cumaisc saghas. Ba é sin an cliffhanger ar uair dheireanach, nuair a mhol muid, agus léirigh dúinn amhairc, go bhfuil halgartaim. Agus chumasadh saghas amháin den sórt sin algartam go bunúsach is tapúla ná cuid de na guys eile. Go deimhin, chumasadh gearr é ní hamháin sa chás is fearr n n logáil isteach, i an ceann is measa gcás n n logáil isteach. Agus nuair a tá tú an chomhtharlú de óimige agus mór O a bheith ar an rud céanna? Is féidir linn a cur síos a dhéanamh i ndáiríre go bhfuil mar cad atá ar a dtugtar téite, cé tá sé ina beagán níos lú coitianta. Ach ciallaíonn sin go díreach an dá bounds, sa chás seo, mar an gcéanna. Mar sin, merge sórtáil, cad a dhéanann seo i ndáiríre boil síos go dtí dúinn? Bhuel, chun cuimhne an spreagadh. Lig dom a tharraingt suas beochan eile go Ní raibh muid ag breathnú ar uair dheireanach. Seo ar cheann, smaoineamh céanna, ach tá sé ina beagán níos mó. Agus tá mé ag dul chun dul ar aghaidh agus pointe amach chéad - ní mór dúinn saghas chur isteach ar an barr ar clé, ansin saghas roghnú, saghas mboilgeog, cúpla cineál eile - bhlaosc agus tapa - nach mór dúinn Labhair faoi, agus carn agus chumasadh saghas. Mar sin, ar a laghad iarracht chun díriú ar do shúile ar na trí barr ar chlé agus ansin merge sórtáil nuair a chliceálann mé an arrow glas. Ach beidh mé in iúl iad ar fad a reáchtáil, ach a a thabhairt duit tuiscint ar an éagsúlacht halgartaim atá ann ar fud an domhain. Tá mé ag dul chun ligean seo á reáchtáil le haghaidh ach cúpla soicind. Agus má tá tú ag díriú ar do shúile - roghnaigh an algartam, ag díriú ar sé ar feadh ach soicind - beidh tú tús a fheiceáil ar an patrún go bhfuil feidhme. Tá Cumaisc saghas, fógra, a rinneadh. Saghas gcarn, saghas tapa, bhlaosc - mar sin is cosúil dúinn a tugadh isteach na trí halgartaim is measa an tseachtain seo caite. Ach tá go maith go bhfuil muid anseo inniu chun breathnú ar merge sórtáil, atá ar cheann de na Tá na cinn níos éasca chun breathnú ar, fiú cé go mbeidh sé Bend dócha d'intinn ach beagán. Anseo, is féidir linn a fheiceáil go díreach cé mhéad Sucks saghas roghnú. Ach ar an taobh smeach, tá sé i ndáiríre éasca a chur i bhfeidhm. Agus b'fhéidir le haghaidh Set P 3, go bhfuil ceann de na halgartaim a roghnaigh tú a chur i bhfeidhm don eagrán caighdeánach. Breá breá, ceart go foirfe. Ach arís, mar faigheann n mór, má tá tú roghnú a chur i bhfeidhm algartam níos tapúla Is maith merge sórtáil, tá odds i níos mó agus ionchuir níos mó é, do chód díreach ag dul a reáchtáil níos tapúla. Tá do láithreán gréasáin ag dul a bheith ag obair níos fearr. Do úsáideoirí ag dul a bheith níos sona. Agus mar sin tá na héifeachtaí de iarbhír a thabhairt dúinn roinnt shíl níos doimhne. Mar sin, a ligean ar ghlacadh le breathnú ar cad chumasadh Is saghas ndáiríre ar fad faoi. Is é an rud is iontaí a chumasadh Is saghas ach seo. Tá sé seo, arís, cad tá muid ar a dtugtar pseudocode, á pseudocode Error Béarla-mhaith. Agus is é an simplíocht saghas suimiúil. Mar sin, ar ionchur na n eilimintí - ionas go ach ciallaíonn, a anseo le sraith. Tá sé fuair rudaí n ann. Sin uile muid ag rá ann. Má tá níos lú ná 2 n, ar ais. Mar sin, tá go díreach an cás fánach. Má tá níos lú ná 2 n, ansin ar ndóigh tá sé 1 nó 0, agus sa chás sin an rud Tá sórtáilte cheana nó nonexistent, mar sin ar ais go díreach. Níl aon rud a dhéanamh. Mar sin, tá go cás simplí chun pluck amach. Eile, ní mór dúinn trí chéim. Shórtáil an leath clé den heilimintí, saghas an leath ceart na heilimintí, agus ansin chumasadh leis an leath curtha in eagar. Cad atá suimiúil anseo go Tá mé cineál punting, ceart? Níl chineál sainmhíniú ciorclach leis an algartam. I cén chiall is algartam seo ciorclán sainmhíniú? LUCHT ÉISTEACHTA: [inaudible]. DAVID MALAN: Yeah, mo algartam sórtáil, dhá cheann de na céimeanna is "saghas rud éigin. "Agus mar sin go begs an gceist, go maith, cad tá mé ag dul a úsáid a shórtáil an leath clé agus an leath ceart? Agus is é an áilleacht anseo, áfach, cé arís, is é seo an aigne-lúbthachta chuid d'fhéadfadh a bheith, is féidir leat úsáid a bhaint céanna algartam a shórtáil an leath clé. Ach fan nóiméad. Nuair a dúirt tú a shórtáil na leath chlé, cad iad an dá céimeanna ag dul a bheith seo chugainn? Beidh muid a shórtáil an leath clé den leath chlé agus an ceart leath de na leath chlé. Damn, conas is féidir liom a shórtáil dá leath, nó ceathrúna, anois? Ach tá sin ceart go leor. Tá algartam sórtáil anseo. Agus cé go dtiocfadh leat a bheith buartha ag chéad seo de chineál ar gan teorainn lúb, tá sé ina timthriall go riamh dul go dtí deireadh - tá sé ag dul chun deireadh uair amháin cad a tharlaíonn? Chomh luath agus is n níos lú ná 2. Cé acu is sa deireadh ag dul a tharlóidh, mar má tá tú a choinneáil halving agus halving i halving na leath, surely deireadh thiar tá tú ag dul go dtí deireadh suas le díreach 1 nó 0 eilimintí. Ag an bpointe sin, an algartam Deir tú ag déanamh. Mar sin, an draíocht fíor sa Dealraíonn algartam a bheith i go chéim deiridh, chumasc. Sin smaoineamh simplí ach chumasc dhá rudaí, go bhfuil an méid atá ar siúl ar deireadh thiar chun gur féidir linn a shórtáil le sraith de, ligean le rá, ocht eilimintí. Mar sin, tá mé ocht liathróidí strus níos mó suas anseo, ocht píosaí de pháipéar, agus ceann Google Gloine - a rachaidh mé a choinneáil. [Gáire] DAVID MALAN: Má d'fhéadfadh muid a chur ar ocht oibrithe deonacha, agus a ligean ar a fheiceáil más féidir linn imirt seo amach, mar sin. Wow, OK. Eolaíocht ríomhaireachta ag fáil spraoi. Gach ceart. Mar sin, conas mar gheall tú trí, lámh is mó suas ann. Ceithre cinn sa chúl. Agus conas mar gheall ar beidh muid a dhéanann tú trí sa tsraith? Agus ceithre i tosaigh. Mar sin, tú ocht, teacht ar suas. [Gáire] DAVID MALAN: Tá mé i ndáiríre nach bhfuil cinnte cad é atá ann. An bhfuil sé an liathróid strus? An lampaí deisce? An t-ábhar? An t-idirlíon? OK. Mar sin teacht ar suas. Cé a ba mhaith leat - a choinneáil ag teacht suas. A ligean ar a fheiceáil. Agus cuireann sé seo duit i suíomh - tá tú i suíomh amháin. Uh-OH, fan nóiméad. 1, 2, 3, 4, 5, 6, 7 - OH, maith. Gach ceart, tá muid go maith. Gach ceart, mar sin gach duine a bhfuil suíochán, ach ní ar an Gloine Google. Lig dom a scuaine suas na. Cad is ainm duit? MICHELLE: Michelle. DAVID MALAN: Michelle? Gach ceart, a fhaigheann tú chun breathnú cosúil le an geek, más rud é go OK. Bhuel, is féidir liom freisin, is dócha, le haghaidh nóiméad ach. Gach ceart, fuireachas. Tá muid ag iarraidh a theacht suas le úsáid an cás le haghaidh Google Gloine, agus táimid shíl go mbeadh sé spraoi a dhéanamh go díreach seo nuair a bhíonn daoine onstage. Beidh muid a thaifeadadh ar fud an domhain óna bpeirspictíocht féin. Gach ceart. Ní dócha cad Google beartaithe. Gach ceart, más rud é nach miste leat ag caitheamh seo le haghaidh na nóiméad seo chugainn awkward, bheadh ​​a bheith iontach. Gach ceart, ionas go mbeidh muid anseo le sraith de heilimintí, agus go eagar, mar atá in aghaidh an píosaí de pháipéar i na folks ' lámha, tá neamhshórtáilte faoi láthair. MICHELLE: Ó, go mar sin aisteach. DAVID MALAN: Tá sé go leor i bhfad randamach. Agus i nóiméad ach, táimid ag dul chun iarracht a a chur i bhfeidhm chumasadh saghas le chéile agus a fheiceáil nuair a bhfuil eochair léargas. Agus is é an cleas anseo le merge sórtáil rud nach mór dúinn glacadh leis go fóill. Ní mór dúinn i ndáiríre roinnt spás breise. Mar sin, tá cad a dul a bheith thar a bheith suimiúil faoi seo is go bhfuil na guys ag dul chun bogadh thart ar beag giotán, mar go bhfuil mé ag dul chun glacadh leis go níl le sraith breise de spás, rá, ar dheis taobh thiar dóibh. Mar sin, má tá siad taobh thiar a n-chathaoirleach, go bhfuil an sraith tánaisteach. Má tá siad ina suí anseo, tá go an sraith bunscoile. Ach tá sé seo le acmhainn atá againn Ní ghiaráil go dtí seo le mboilgeog saghas, leis an saghas roghnú, leis an saghas chur isteach. Athghairm tseachtain seo caite, ach gach duine de chineál ar shuffled i bhfeidhm. Ní raibh siad úsáid as aon chuimhne breise. Rinne muid seomra do dhaoine faoi daoine ag gluaiseacht timpeall. Mar sin, tá sé seo le léargas eochair, freisin. Níl an trádáil-uaire, go ginearálta i eolaíocht ríomhaireachta, na n-acmhainní. Más mian leat chun dlús a chur suas rud éigin cosúil le am, tá tú ag dul chun a íoc ar phraghas. Agus is é ceann de na praghsanna sin go minic spás, an méid de chuimhne nó crua spás diosca go bhfuil tú ag baint úsáide as. Nó, frankly, an méid den am Ríomhchláraitheoir. Cé mhéad ama a thógann sé tú, an duine, a chur i bhfeidhm iarbhír roinnt níos mó algartam casta. Ach le haghaidh lá atá inniu ann, an trádáil-uaire tá am agus spás. Mar sin, más féidir leat a shealbhú guys suas díreach do uimhreacha ionas gur féidir linn a fheiceáil go bhfuil tú go deimhin meaitseáil 4, 2, 6, 1, 3, 7, 8. Excellent. Mar sin, tá mé ag dul chun iarracht a orchestrate rudaí, is féidir má tá tú guys díreach leanúint mo luaidhe anseo. Mar sin, tá mé ag dul a chur i bhfeidhm, den chéad uair, an chéad chéim den pseudocode, a bhfuil ar ionchur na n heilimintí, más é n níos lú ná 2, ansin ar ais. Ar ndóigh, ní dhéanann sin i bhfeidhm, mar sin táimid ag bogadh ar aghaidh. Mar sin, a shórtáil an leath clé den heilimintí. Mar sin, ciallaíonn sé go bhfuil mé ag dul chun díriú ar mo aird haghaidh nóiméad ach ar na ceithre guys anseo. Gach ceart, cad a dhéanfaidh mé seo chugainn? LUCHT ÉISTEACHTA: Sórtáil an leath clé. DAVID MALAN: Mar sin, anois tá mé a shórtáil an leath clé de na guys. Toisc arís, glacadh leat féin an Is é sprioc a shórtáil an leath clé. Conas a dhéanann tú a dhéanamh? Just a lean na treoracha, fiú cé go bhfuil muid ag déanamh sé arís. Mar sin, a shórtáil an leath clé. Anois tá mé ag sórtáil na dhá guys. Cad a thagann chugainn? LUCHT ÉISTEACHTA: Sórtáil an leath clé. DAVID MALAN: Sórtáil an leath clé. Mar sin, anois ar na, an suíochán anseo, Tá liosta de mhéid 1. Agus cad is ainm duit arís? PRINCESS DAISY: Banphrionsa Daisy. DAVID MALAN: Banphrionsa Daisy anseo. Agus mar sin tá sí curtha in eagar cheana féin, mar gheall ar Tá an liosta de mhéid 1. Cad a dhéanfaidh mé seo chugainn? OK, ar ais, toisc go bhfuil an liosta de méid 1, a bhfuil níos lú ná 2. Ansin, cad é an chéad chéim eile? Agus anois tá tú chun cineál backtrack i d'intinn. Shórtáil an leath ceart, a bhfuil - cad is ainm duit? LINDA: Linda. DAVID MALAN: Linda. Agus mar sin cad a dhéanann muid anois go ní mór dúinn liosta de mhéid 1? LUCHT ÉISTEACHTA: Tuairisceán. DAVID MALAN: Cúramach. Ar ais muid an chéad, agus anois an tríú chéim - agus má tá mé cineál léiriú air ag ag glacadh leis an dhá shuíochán anois, anois mé a chumasadh leis na dhá ghné. Mar sin anois ar an drochuair, na heilimintí Is iad as ord. Ach sin an áit ar an bpróiseas chumasc Tosaíonn a fháil láidre. Mar sin, más féidir leat guys seasamh suas díreach nóiméad, tá mé ag dul go dtí gá duit, i nóiméad, chun dlús a chur taobh thiar do chathaoir. Agus má Linda, toisc go bhfuil 2 níos lú ná 4, cén fáth nach bhfuil a thagann tú ar fud an chéad? Fanacht ann. Mar sin, Linda, a thagann tú ar fud an chéad. Anois, i ndáiríre má tá sé ach le sraith d'fhéadfadh muid a bhogadh díreach aici i bhfíor-am as an chathaoir ar an bhfód. Mar sin a shamhlú gur thóg roinnt leanúnach líon na céimeanna 1. Agus anois - ach is gá dúinn tú a chur i an chéad suíomh anseo. Agus anois má d'fhéadfaí tú teacht timpeall, chomh maith, tá muid ag dul chun a bheith i suíomh beirt. Agus cé go mothaíonn seo mar tá sé ag cur ar feadh tamaill, an méid deas anois go bhfuil go bhfuil an leath clé den Tá leath chlé curtha in eagar anois. Mar sin, cad a bhí ar an chéad chéim eile, má táimid anois athchasadh eile sa scéal? LUCHT ÉISTEACHTA: leath Ceart. DAVID MALAN: Sórtáil an leath ceart. Mar sin, tá tú guys seo a dhéanamh, chomh maith. Mar sin, más féidir leat a seasamh suas le haghaidh nóiméad ach? Agus cad is ainm duit? JESS: Jess. DAVID MALAN: Jess. OK, mar sin tá Jess anois na láimhe clé leath an leath ceart. Agus mar sin tá sí ina liosta de mhéid 1. Sí curtha in eagar ndóigh. Agus d'ainm arís? MICHELLE: Michelle. DAVID MALAN: Michelle Is léir go liosta de mhéid 1. Sí sórtáilte cheana. Mar sin anois a tharlaíonn an draíocht, leis an bpróiseas chumasc. Mar sin, tá a dul chun teacht ar dtús? Is léir Michelle. Mar sin, más féidir leat teacht timpeall ar ais. An spás atá againn ar fáil di anois Is ceart taobh thiar de seo cathaoir anseo. Agus anois má d'fhéadfaí tú teacht ar ais chomh maith, ní mór dúinn anois, a bheith soiléir, dhá leath, gach ceann de na méid 2 - agus díreach ar mhaithe le léiriú ar, má tá tú d'fhéadfadh a dhéanamh le beagán de spás - D'fhág leath anseo, ceann amháin leath ceart anseo. Athchasadh eile sa scéal. Cén chéim eile? LUCHT ÉISTEACHTA: Cumaisc. DAVID MALAN: Mar sin, anois ní mór dúinn a chumasadh. Mar sin, OK, mar sin anois, buíochas le Dia, ní mór dúinn ach freed suas ceithre cathaoireacha. Mar sin, tá muid úsáid faoi dhó mar cuimhne i bhfad, ach Is féidir linn a thabhairt smeach-flopping idir an dá arrays. Mar sin, a bhfuil líon a thagann ar dtús? Mar sin, Michelle, ar ndóigh. Mar sin, teacht thart agus a ghlacadh do shuíochán anseo. Agus ansin tá uimhir 2 ar ndóigh seo chugainn, mar sin a thagann tú anseo. Uimhir 4, uimhir 6. Agus arís, cé go níl a beagán de ag siúl i gceist, i ndáiríre, d'fhéadfaí iad seo tarlú láithreach, ag bogadh amháin - OK, bhí go maith. [Gáire] DAVID MALAN: Agus anois tá muid i gcruth maith go leor. An leath clé den iomlán Tá ionchur sórtáilte curtha anois. Gach ceart, mar sin bhí na guys an leas a bhaint de mo - conas a rinne sé suas go deireadh na cailíní go léir ar an ar chlé agus na buachaillí ar dheis? OK, mar sin tá guys cas anois. Mar sin, ní bheidh mé shiúlann tú tríd an na céimeanna seo. Beidh orainn a fheiceáil más féidir linn iarratas a dhéanamh arís an pseudocode céanna. Más mian leat dul ar aghaidh agus seasamh suas, agus tú guys, lig dom a thabhairt duit na mic. Féach más rud é nach féidir leat a aithris a dhéanamh ar cad rinne muid díreach anseo ar an taobh eile den liosta. Cé a riachtanais a labhairt ar dtús, bunaithe ar an algartam? Mar sin, mínigh cad atá tú a dhéanamh roimh a dhéanann tú aon gluaiseachtaí shiúl na gcos. Cainteoir 1: Ceart go leor, mar sin ó Tá mé an leath clé den leath chlé, ar ais mé. Ceart? DAVID MALAN: Maith. Cainteoir 1: Agus ansin - DAVID MALAN: Cé a dhéanann na mic téigh go dtí anois? Cainteoir 1: Uimhir Aghaidh. Cainteoir 2: Mar sin, tá mé an leath ceart an leath clé den leath chlé, agus mé ar ais. DAVID MALAN: Maith. Fhilleann tú. Mar sin anois cad é an suas in aice le tú dhá? Cainteoir 2: Ba mhaith linn a fheiceáil atá ar níos lú. DAVID MALAN: Go díreach. Ba mhaith linn a chumasadh. An spás táimid ag dul a úsáid a chumasadh tú isteach, cé go bhfuil siad ar ndóigh sórtáilte cheana, táimid ag dul chun leanúint leis an algartam céanna. Mar sin, a théann i ais an chéad? Mar sin 3, agus ansin 7. Agus anois téann na mic leis na guys, ceart go leor? Cainteoir 3: Mar sin, tá mé an leath ceart an Tá leath chlé, agus mo n níos lú ná 1, mar sin tá mé ag dul díreach chun pas - DAVID MALAN: Maith. Cainteoir 4: Tá mé an leath ceart an leath ceart an leath ceart, agus tá mé chomh maith le duine amháin, mar sin tá mé ag dul a thabhairt ar ais. Mar sin, anois táimid ag chumasadh. Cainteoir 3: Mar sin, táimid ag dul ar ais. DAVID MALAN: Mar sin, a théann tú isteach sa chúl. Mar sin, téann 5 dtús, ansin 8. Agus lucht féachana anois, a bhfuil an chéim ní mór dúinn a athchasadh anois ar ais go dtí i ár n-intinn? LUCHT ÉISTEACHTA: Cumaisc. DAVID MALAN: Chumasc leath chlé agus ar dheis leath an leath clé bunaidh. Mar sin, anois - agus díreach a dhéanamh soiléir, a dhéanamh le beagán de spás idir tú dhá guys. Mar sin, anois go bhfuil an dá liosta, chlé agus ar dheis. Mar sin, conas is féidir linn chumasadh tú anois guys isteach an líne tosaigh na suíochán arís? 3 Téann ar dtús. Ansin 5, ar ndóigh. Ansin 7, agus anois 8. OK, agus anois tá muid? LUCHT ÉISTEACHTA: Nach bhfuil déanta. DAVID MALAN: Nach dhéanamh, toisc go ar ndóigh, níl céim amháin fágtha. Ach arís, an chúis Tá mé ag baint úsáide as an béarlagair cosúil le "athchasadh i d'intinn," tá sé toisc go bhfuil i ndáiríre cad atá ag tarlú. Táimid ag dul trí gach ceann de na céimeanna seo, ach tá muid saghas sos ar feadh nóiméad, níos doimhne tumadóireacht isteach an algartam, sos ar feadh nóiméad, tumadóireacht níos doimhne isteach an algartam, agus anois ní mór dúinn a shórtáil de athchasadh inár intinn agus gach ceann de na sraitheanna Cealaigh go atá againn saghas chur ar a shealbhú. Mar sin, anois táimid tar éis dhá liosta de mhéid 4. Má d'fhéadfaí tú guys seasamh suas uair dheireanach agus a dhéanamh le beagán de spás anseo chun dhéanamh soiléir gurb é seo an chlé leath de na bunaidh, an leath ceart an bunaidh. Cé hé an chéad uimhir a chuirimid gá a tharraingt isteach sa chúl? Michelle, ar ndóigh. Mar sin, chuir muid Michelle anseo. Agus tá a uimhir 2? Uimhir 2 thagann ar ais chomh maith. Uimhir 3? Excellent. Uimhir 4, uimhir 5, Uimhir 6, Uimhir 7, 8 agus uimhir. OK, mar sin bhraith sé cosúil le a lán na gcéimeanna, do cinnte. Ach anois a ligean ar a fheiceáil más rud é nach féidir linn a dhearbhú saghas intuitively go bhfuil an algartam go bunúsach, go háirithe mar n Faigheann ndáiríre mór, mar atá feicthe againn leis an beochan is, go bunúsach níos tapúla. Mar sin, éileamh mé an algartam, i an ceann is measa cás agus fiú sa chás is fearr, Is mór O de n uair logáil n. Is é sin, níl gné éigin de seo algartam a thógann n céimeanna, ach níl gné eile áit éigin i go atriall, go looping, go Bíonn céimeanna n logáil isteach. An féidir linn a chur ar ár mhéar ar an méid sin dhá uimhir ag tagairt do? Bhuel, sa chás - where'd na mic dul? Cainteoir 1: An mbeadh an logáil n a bheith briseadh dúinn suas i dhá - roinnt ar dhá, go bunúsach. DAVID MALAN: Go díreach. Aon uair a fheiceann muid in aon algartam dá bhrí sin dtí seo, tá tá an patrún seo de roinnt, a roinnt, a roinnt. Agus tá sé laghdaithe go hiondúil chun rud éigin go bhfuil logartamach, logáil bonn 2. Ach d'fhéadfadh sé a bheith i ndáiríre rud ar bith, ach logáil bonn 2. Anois, cad mar gheall ar an n? Is féidir liom a fheiceáil go bhfuil muid de chineál ar roinnte tú guys - roinnte tú, roinnte tú, roinnte tú, roinnte tú. Nuair a dhéanann an deireadh teacht ó? Mar sin, tá sé an chumasc. Toisc smaoineamh air. Nuair a chumasadh tú ocht daoine le chéile, sa chaoi is leath díobh sraith de cheithre agus an leath eile eile sraith de cheithre, conas a théann tú faoi ​​ag déanamh an chumasc? Bhuel, rinne tú guys sé cothrom intuitively. Ach má rinne mé ina ionad sin sé beagán níos mó methodically, d'fhéadfadh mé in iúl ag an duine leftmost chéad le mo chlé láimh, Luaigh ag an duine leftmost an leath le mo lámh dheas, agus ach shiúil ina dhiaidh sin tríd an liosta, ag cur in iúl ag an ghné is lú gach uair, bogadh mo mhéar thar agus níos mó ná mar is gá ar fud an liosta. Ach cad eochair faoi seo chumasc Is próiseas mé i gcomparáid leis na péirí na n-eilimintí. Ón an leath ceart agus ó thaobh na láimhe clé leath, ní mé ag cúlú uair amháin. Mar sin, tá an chumasadh féin ag cur níos mó ná n céimeanna. Agus cé mhéad uair a rinne mé a dhéanamh go chumasc? Bhuel, nach bhfuil níos mó ná n, agus muid díreach chonaic go bhfuil an chumasadh deiridh. Agus mar sin má dhéanann tú rud éigin a thógann logáil n céimeanna n amanna, nó vice versa, tá sé ag dul a thabhairt dúinn n amanna logáil n. Agus is é sin an fáth sé seo níos fearr? Bhuel, má tá a fhios againn cheana féin go bhfuil logáil isteach n Tá níos fearr ná n - ceart? Chonaic muid i cuardaigh dénártha, an leabhar teileafóin Mar shampla, bhí log n cinnte níos fearr ná líneach. Mar sin, a chiallaíonn go n amanna logáil n Tá sí níos fearr ná n uair eile n, aka n cearnógach. Agus sin an méid a bhraitheann muid ar deireadh thiar. Bhabhta chomh mór de bualadh bos, má gur féidir linn, le haghaidh na guys. [Bualadh bos] DAVID MALAN: Agus do bronntanais scaradh - is féidir leat a choinneáil ar na huimhreacha, más mian leat. Agus do bhronntanas parting, mar is gnách. Ó, agus beidh muid a sheolann tú an scannán, Michelle. Go raibh maith agat. Gach ceart. Cabhair duit féin le liathróid strus. Agus lig dom a tharraingt suas, idir an dá linn, ár gcara Rob Bowden a chur ar fáil dearcadh beagán difriúil ar seo, toisc gur féidir leat smaoineamh ar na céimeanna tarlú i beagán bhealach difriúil. Go deimhin, ar an leagan-suas do cad Rob faoi chun a thaispeáint dúinn ghlacann leis go atá againn Déantar an roinnt suas de na cheana liosta mór in ocht liostaí beag, gach ceann de na méid 1. Mar sin, tá muid ag athrú an pseudocode a beagán ach a shórtáil de a fháil ar an smaoineamh lárnach ar conas a oibríonn chumasc. Ach an t-am ag rith ar cad Tá sé ar tí sin a dhéanamh go fóill ag dul a bheith mar an gcéanna. Agus arís, is é an bun anseo go bhfuil sé tús curtha le hocht liostaí de mhéid 1. Mar sin, tá tú caillte an chuid ina bhfuil sé iarbhír a rinneadh an logáil n, logáil n, logáil n a roinnt ar an ionchur. [Athsheinm físe] -Sin é céim amháin. Chun céim dhá, arís agus arís eile chumasadh péirí de liostaí. DAVID MALAN: Hm. Tá Amháin fuaime ag teacht amach as mo ríomhaire. A ligean ar iarracht seo arís. -Just a phiocadh treallach a - anois ní mór dúinn ceithre liostaí. Foghlaim roimh. DAVID MALAN: Ní théann muid. Chumasc-108 agus 15, deireadh muid suas leis an liosta 15, 108. Chumasc 50 agus 4, táimid ag deireadh suas le 4, 50. Chumasc 8 agus 42, ní mór dúinn deireadh suas le 8, 42. Agus a chumasc 23 agus 16, ní mór dúinn deireadh suas le 16, 23. Anois go bhfuil ár gcuid liostaí uile de mhéid 2. Fógra go bhfuil gach ceann de na ceithre liostaí atá curtha in eagar. Mar sin, is féidir linn tús a chumasc péirí de liostaí arís. Chumasc 15 agus 108 agus 4 agus 50, ní mór dúinn chéad a chur ar an 4, ansin an 15, ansin an 50, ansin an 108. Chumasc 8, 42 agus 16, 23, ní mór dúinn a ghlacadh an chéad an 8, ansin an 16, ansin an 23, ansin an 42. Mar sin, anois ní mór dúinn ach dhá liosta de mhéid 4, gach ceann acu curtha in eagar. Mar sin, anois againn chumasadh leis an dá liostaí. Gcéad dul síos, a chur orainn an 4, ansin dúinn a chur ar an 8, ansin dúinn a chur ar an 15, ansin 16, ansin 23, ansin 42, ansin 50, ansin 108. [Athsheinm físe END] DAVID MALAN: Arís, fógra, sé riamh i dteagmháil léi cupán tugadh am níos mó ná ceann amháin tar éis a chur chun cinn níos faide ná sé. Mar sin, ní tá sé athrá. Mar sin, tá sé ag bogadh i gcónaí go dtí an taobh, agus sin nuair a fuair muid ár n. Cén fáth nach lig dom a tharraingt suas beochan amháin a chonaic muid níos luaithe, ach an uair seo ag díriú ach ar chumasadh saghas. Lig dom dul ar aghaidh agus súmáil isteach in ar an anseo. An Chéad lig dom a roghnú ionchur randamach, Formhéadaigh seo, agus is féidir leat a shórtáil de a fheiceáil cad a thóg muid do dheonú, níos luaithe, Tá merge sórtáil a dhéanamh i ndáiríre. Mar sin, faoi deara go bhfaigheann tú na leatha nó na ceathrúna nó na hochtú codanna de na fhadhb atá ann go léir a tobann tús a chur gcruth maith. Agus ansin ar deireadh, a fheiceann tú ag an deireadh an-go BAM, Tá gach rud a chomhcheangal le chéile. Mar sin, is iad seo ach trí éagsúla Bíonn ar an smaoineamh céanna. Ach an léargas eochair, díreach cosúil le deighilt agus conquer an-an chéad rang, Ba gur shocraigh muid a roinnt ar bhealach an fhadhb i rud éigin mór, i saghas rud éigin de comhionann i spiorad, ach níos lú agus níos lú agus níos lú agus níos lú. Anois ar bhealach eile spraoi a shórtáil de smaoineamh faoi ​​seo, cé nach bhfuil sé ag dul a thabhairt duit an iomasach céanna tuiscint go bhfuil, an beochan a leanas. Mar sin, tá sé seo le duine éigin físeán a chur le chéile méid sin a bhaineann éagsúla fuaimeanna leis na hoibríochtaí éagsúla saghas chur isteach, do merge sórtáil, agus ar feadh cúpla daoine eile. Mar sin, i láthair na huaire, tá mé ag dul a bhuail Súgartha. Tá sé thart ar nóiméad fada. Agus cé gur féidir leat a fheiceáil fós ar an patrúin tarlú, an uair seo is féidir leat chomh maith a fháil amach conas go bhfuil na halgartaim feidhmiú éagsúil agus le patrúin beagán difriúil. Is é seo an saghas chur isteach. [TONES seinm] DAVID MALAN: Tá sé arís ag iarraidh a chur isteach gach eilimint i gcás ina mbaineann sé leis. Is é seo an saghas mboilgeog. [TONES seinm] DAVID MALAN: Agus is féidir leat a shórtáil de bhraitheann cé chomh réasúnta obair beag tá sé ag déanamh ar gach céim. Is é seo cad fuaimeanna cosúil le tediousness. [TONES seinm] DAVID MALAN: Is é seo an saghas roghnú, nuair a roghnaigh muid an eilimint ba mhaith linn ag ag dul trí arís agus arís agus arís eile agus é a chur ag an tús. [TONES seinm] DAVID MALAN: Is é seo chumasadh saghas, a Is féidir leat tosú i ndáiríre a bhraitheann. [TONES seinm] [Gáire] DAVID MALAN: Rud ar a dtugtar gnome saghas, nach bhfuil muid d'fhéach sé ar. [TONES seinm] DAVID MALAN: Mar sin, lig dom a fheiceáil, anois, distracted mar a bhfuil tú ag súil go dtosnódh an ceol, más féidir liom duillín beag beagán de math i anseo. Mar sin, níl ar bhealach ceathrú gur féidir linn smaoineamh ar cad a chiallaíonn sé seo feidhmeanna a bheith níos tapúla ná na cinn go atá feicthe againn roimh. Agus má tá tú ag teacht ar an gcúrsa ó cúlra matamaitice, tú i ndáiríre tá a fhios b'fhéidir go bhfuil tú cheana féin Is féidir le slap téarma ar an teicníc - eadhon recursion, feidhm go bhfuil gá, ar bhealach féin. Agus arís, chun cuimhne gur saghas chumasadh pseudocode bhí Athchúrsach sa chiall go bhfuil ceann de na céimeanna chumasadh saghas ar Bhí a ghlaoch sort - is é sin, féin. Ach buíochas le Dia, mar gheall ar choinnigh muid glaoch saghas, nó a chumasadh saghas, go sonrach, ar lú agus níos lú agus liosta níos lú, ní mór dúinn deireadh thiar go raibh maith agat bottomed amach cad beidh muid ag glaoch cás bonn, an cás crua-códaithe go dúirt má tá an liosta beag, níos lú ná 2 sa chás sin, díreach ar ais láithreach. Más rud é nach raibh againn go cás speisialta, an Ní ba mhaith algartam bun amach, agus ba mhaith leat a fháil go deimhin isteach i lúb gan teorainn fíor go deo. Ach is dócha go bhíomar ag iarraidh a chur anois roinnt uimhreacha ar seo, arís, ag baint úsáide as n mar an méid ar an ionchur. Agus bhí mé a iarraidh ort, cad an t-am iomlán a bhfuil baint acu ag rith saghas chumasadh? Nó níos ginearálta, cad an costas a sé in am? Bhuel tá sé éasca go leor a thomhas go. Má tá níos lú ná 2 n, an t-am i gceist i sórtáil n heilimintí, inarb ionann n agus 2, 0. Toisc muid ar ais díreach. Níl aon obair atá le déanamh. Anois fhéadfaí a rá, b'fhéidir go bhfuil sé céim amháin nó dhá céimeanna chun an figiúr amach an méid ag obair, ach tá sé gar go leor chun 0 go Tá mé ag dul díreach tar éis a rá go bhfuil aon obair riachtanach má tá an liosta chomh beag a bheith uninteresting. Ach tá an gcás seo suimiúil. Ba é an cás recursive an brainse de an pseudocode a dúirt eile, saghas an leath clé, a shórtáil an ceart leath, chumasadh leis an dá leath. Anois, cén fáth a dhéanann an focal ionadaíocht a dhéanamh go chostas? Bhuel, T na n ciallaíonn ach an am a shórtáil eilimintí n. Agus ansin ar an thaobh na láimhe deise de na shíniú ionann ann, roinnte ar an T na n 2 Tá thagairt do chostas ar cad? Sórtáil an leath clé. Is é an T eile de n arna roinnt ar 2 dócha thagairt do chostas a shórtáil an leath ceart. Agus ansin an n móide? An bhfuil an chumasc. Toisc má tá tú dhá liosta, ar cheann de na Méid n os cionn 2 agus ceann eile ar mhéid n níos mó ná 2, caithfidh tú a dteagmháil go bunúsach gach ceann de na heilimintí sin, díreach cosúil le Rob i dteagmháil léi gach ceann de na cupáin, agus díreach mar a dúirt muid ag gach ceann de na oibrithe deonacha ar an stáitse. Mar sin, ionann n agus an costas chumasc. Anois ar an drochuair, foirmle seo Tá freisin féin recursive. Mar sin, má d'iarr an cheist, más rud é go n, a rá, 16, má tá 16 duine ar an stáitse nó 16 cupáin san fhíseán, cé mhéad iomlán céimeanna a thógann sé chun iad a shórtáil le merge sórtáil? Tá sé i ndáiríre ní freagra soiléir, mar anois go bhfuil tú a shórtáil de hathchúrsach cheist seo a fhoirmle. Ach tá sin ceart go leor, mar gheall ar lig dom a mholadh go bhfuil muid ar an méid seo a leanas. An t-am i gceist a shórtáil 16 duine nó 16 cupáin ag dul a bheith ionadaíocht go ginearálta mar T de 16. Ach is ionann sin, de réir ár foirmle roimhe, 2 uair an méid ama a thógann sé a shórtáil 8 cupáin móide 16. Agus arís, is móide 16 an t-am a chumasadh, agus is é an dhá uair T de 8 am a shórtáil leath chlé agus ar dheis leath. Ach arís, nach bhfuil sé seo go leor. Ní mór dúinn chun tumadóireacht a dheanamh i níos doimhne. Ciallaíonn sé seo ní mór dúinn a fhreagairt ar an cheist, cad é T an 8? Bhuel tá T de 8 díreach 2 amanna T de 4 móide 8. Bhuel, cad T de 4? T de 4 é ach 2 uair T de 2 móide 4. Bhuel, cad T de 2? T de 2 Is é ach 2 uair T de 1 móide 2. Agus arís, tá muid de chineál ar dul bhfostú sa timthriall. Ach tá sé ar tí é a bhuail go mar a thugtar cás bonn. Mar gheall ar cad T de 1, raibh muid a éileamh? 0. Mar sin, anois ar deireadh, is féidir linn a bheith ag obair ar gcúl. Más rud é T an 1 0, is féidir liom dul ar ais anois suas amháin líne leis an Guy anseo, agus is féidir liom breiseán i do T 0 de 1. Mar sin, go ciallaíonn sé cothrom le 2 uair náid, mhalairt ar a dtugtar 0, móide 2. Agus mar sin go bhfuil an abairt sin ar fad 2. Anois, má ghlacaim an T de 2, a bhfuil a freagra Tá 2, breiseán sé isteach ar an líne lár, T de 4, tugann sin dom 2 uair 2 móide 4, mar sin 8. Má breiseán mé ansin i 8 leis an roimhe sin líne, tugann go dom 2 uair 8, 16. Agus má leanaimid ar aghaidh ansin go bhfuil an 24, ag cur i 16, ní mór dúinn a fháil ar deireadh luach de 64. Anois go labhraíonn i agus de féin saghas aon rud ar an nodaireacht n, an mór O, an óimige go atá againn ag caint faoi. Ach casadh sé amach go bhfuil 64 go deimhin 16, an méid de na ionchur, logáil bonn 2 de 16. Agus má tá sé seo le beagán neamhchoitianta, ach smaoineamh ar ais, agus beidh sé teacht ar ais a thabhairt duit sa deireadh. Má tá an bonn logáil 2, tá sé cosúil le 2 a ardaíodh leis an cad a thugann tú 16? Ó, go 4, mar sin tá sé 16 uair 4. Agus arís, nach bhfuil sé le déileáil go mór má tá seo Is saghas chuimhne soineanta anois. Ach do anois, a chur ar chreideamh go bhfuil 16 log 16 64. Agus mar sin go deimhin, leis an sanity simplí sheiceáil, tá muid deimhnithe - ach ní go gcruthófar go foirmiúil - go bhfuil an t-am ag rith de chumasadh Is saghas deimhin n logáil n. Mar sin, ní dona. Tá sé cinnte níos fearr ná an halgartaim againn le feiceáil go dtí seo, agus tá sé mar tá muid giaráilte, ceann amháin, teicníocht a dtugtar recursion. Ach níos suimiúla ná sin, go coincheap a roinnt agus conquering. Arís, go fírinneach seachtain 0 stuif go fiú anois arís agus arís eile i ar bhealach níos láidre. Anois, a fheidhmiú beag spraoi, má tá tú riamh a rinneadh seo - agus tú is dócha Ní bheadh, mar gheall saghas gnáth Ní dhéanann daoine a cheapann é seo a dhéanamh. Ach má théim chuig google.com agus má Ba mhaith liom rud éigin ar tí é a fhoghlaim recursion, Iontráil. [Gáire] [Gáire NÍOS] DAVID MALAN: joke Droch leathadh go mall. [Gáire] DAVID MALAN: Díreach i gcás, tá sé ann. Ní raibh mé é a litriú mícheart, agus níl an joke. Gach ceart. É a mhíniú do na daoine eile a thabhairt duit má nach bhfuil sé chliceáil go leor ach go fóill. Ach recursion, níos ginearálta Tagraíonn, leis an bpróiseas feidhm ag glaoch féin, nó níos mó go ginearálta, tríd a fadhb i rud is féidir a bheith réiteach réir a chéile ag réiteach comhionann fadhbanna ionadaíocha. Bhuel, a ligean ar giaranna athrú le haghaidh nóiméad ach. Is maith linn chun deireadh a chur ar cliffhangers áirithe, mar sin a ligean ar tús a chur ar bun an stáitse, le haghaidh roinnt nóiméad, ar smaoineamh an-simplí - go swapping dhá ghné, ceart? Gach ceann de na halgartaim atá déanta againn ag caint faoi an lánúin anuas i gceist léachtaí áirithe saghas swapping. Sa lá atá inniu go raibh sé visualized ag dul dóibh suas as a gcuid cathaoireacha agus ag siúl timpeall, ach sa chód, ba mhaith linn a ghlacadh ach eilimint ó eagar agus Plop sé isteach i gceann eile. Mar sin, conas is féidir linn dul faoi seo a dhéanamh? Bhuel, lig dom dul ar aghaidh agus scríobh clár tapaidh anseo. Tá mé ag dul chun dul ar aghaidh agus a dhéanamh seo mar seo a leanas. A ligean ar glaoch seo - cad a dhéanann muid ag iarraidh a ghlaoch an gceann seo? I ndáiríre, uimh. Lig dom athchasadh. Níl mé ag iarraidh a dhéanamh go cliffhanger fóill. Beidh sé spoil an spraoi. A ligean ar é seo a dhéanamh ina ionad. Má ghlactar leis go Ba mhaith liom a scríobh ar beag clár agus a chuimsíonn anois seo smaoineamh athchúrsáil. Mé cineál fuair chun tosaigh ar mé féin ann. Tá mé ag dul a dhéanamh ar an méid seo a leanas. Gcéad dul síos, a tapa tá an caighdeán io.h, chomh maith le Áirítear ar cs50.h. Agus ansin tá mé ag dul chun dul ar aghaidh agus a dhearbhú príomh neamhní slánuimhir ar an mbealach is gnách. Thuig mé mé misnamed an comhad, mar sin lig dom a chur díreach a. síneadh c anseo mar sin gur féidir linn a thiomsú i gceart. Tosaigh an fheidhm seo amach. Agus an fheidhm mhaith liom a scríobh, go leor ach tá sé ar cheann a iarrann an úsáideora do roinnt agus ansin cuireann suas na huimhreacha idir líon agus, a rá, 0. Mar sin, an chéad tá mé ag dul chun dul ar aghaidh agus a dhearbhú n slánuimhir. Ansin, a chóipeáil mé roinnt cód gur táimid Bainim úsáid as ar feadh tamaill. Cé go bhfuil rud éigin fíor. Beidh mé ag teacht ar ais go dtí go bhfuil i láthair na huaire. Cad ba mhaith liom a dhéanamh? Ba mhaith liom a rá printf dearfach slánuimhir do thoil. Agus ansin tá mé ag dul go dtí Deir n Faigheann slánuimhir a fháil. Mar sin, arís, roinnt cód Boilerplate go atá againn a úsáid roimh. Agus mé ag dul chun é seo a cé go bhfuil níos lú ná n 1. Mar sin, beidh sé seo a chinntiú go mbeidh an t-úsáideoir Tugann dom slánuimhir dheimhneach. Agus anois tá mé ag dul a dhéanamh ar an méid seo a leanas. Ba mhaith liom a chur suas gach ceann de na huimhreacha idir 1 agus agus n, nó 0 agus n, equivalently, a fháil ar an tsuim iomlán. Mar sin, an tsiombail sigme mór go mb'fhéidir go mbeadh tú a thabhairt chun cuimhne. Mar sin, tá mé ag dul chun é seo a dhéanamh trí chéad ghlaoch feidhm a dtugtar sigme, rith sé i n, agus ansin mé ag dul a rá printf, is é an freagra ceart ann. Mar sin, i mbeagán focal, a rachaidh mé agus slánuimhir ón úsáideoir. Liom a chinntiú go bhfuil sé dearfach. Dearbhaím freagra ar a dtugtar athraitheach cineál slánuimhir agus a stóráil i sé an tuairisceán luach sigme, ag dul i n mar ionchur. Agus ansin mé a phriontáil amach sin a fhreagairt. Ar an drochuair, cé go fuaimeanna sigme cosúil le rud éigin a d'fhéadfadh a bheith i an comhad math.h, a dhearbhú, tá sé i ndáiríre ní. Mar sin tá sin ceart go leor. Is féidir liom a chur i bhfeidhm seo mé féin. Tá mé ag dul a chur i bhfeidhm le feidhm a dtugtar sigme, agus tá sé ag dul a ghlacadh paraiméadar - a ligean ar ghlaoch air go díreach m, ach mar sin tá sé difriúil. Agus ansin suas anseo, tá mé ag dul a rá, go maith, más rud é go m níos lú ná 1 - tá sé seo le an-uninteresting clár. Mar sin, tá mé ag dul chun dul ar aghaidh agus ar ais láithreach 0. Sé nach bhfuil ach ciall a bhaint as a chur suas go léir na huimhreacha idir 1 agus m má m Is é féin 0 nó diúltach. Agus ansin tá mé ag dul chun dul ar aghaidh agus é seo a dhéanamh go han-iteratively. Tá mé ag dul a dhéanamh saghas sean-scoil, agus tá mé ag dul chun dul ar aghaidh agus a rá go bhfuil mé ag dul go dtí a dhearbhú go bhfuil suim a bheith 0. Ansin, tá mé ag dul a bheith acu a d'lúb de int - agus lig dom é a dhéanamh chun freastal ar ár cód dáilte, ionas go mbeidh tú cóip sa bhaile. o Faigheann i 1 ar suas le Tá mé níos lú ná nó cothrom le m. i móide móide. Agus ansin taobh istigh de seo le haghaidh lúb - tá muid beagnach ann - Faigheann suim suim móide 1. Agus ansin tá mé ag dul a thabhairt ar ais an tsuim. Mar sin, rinne mé seo go tapa, go leor admittedly. Ach arís, tá an fheidhm is mó go leor simplí, bunaithe ar cód atá déanta againn scríofa go dtí seo. Úsáidí an lúb dé a fháil dearfach slánuimhir ón úsáideoir. Mé pas a fháil ansin go slánuimhir le feidhm nua ar a dtugtar sigme, ag iarraidh é, arís, n. Agus a stóráil mé an luach ar ais, an freagra as an bosca dubh faoi láthair ar a dtugtar sigme, i athróg ar a dtugtar freagra. Ansin mé a phriontáil. Má táimid ag leanúint ar aghaidh anois leis an scéal, gcaoi a bhfuil sigme i bhfeidhm? Molfaidh mé a chur i bhfeidhm mar seo a leanas. Gcéad dul síos, le beagán de earráid-seiceáil a dhéanamh cinnte go bhfuil an t-úsáideoir nach messing le liom agus ag dul i roinnt luach diúltach nó 0. Ansin mé a dhearbhú athróg ar a dtugtar suim agus é a shocrú chun 0. Agus anois tús a chur mé chun bogadh ó cothrom i 1 léir ar an mbealach suas go dtí agus lena n-áirítear m, mar ba mhaith liom a chur san áireamh go léir an san áireamh líon na ndaoine ó cheann trí m,. Agus taobh istigh de seo le haghaidh lúb, a dhéanamh mé díreach tar éis Faigheann suim is cuma cad é anois, móide an luach i. Plus an luach na i. Mar leataobh, más rud é nach bhfaca tú é seo roimh, tá roinnt shiúcra syntactic don líne seo. Is féidir liom a athscríobh seo mar is ionann móide i, ach a shábháil mé féin le cúpla keystrokes agus chun breathnú with giotán. Ach tá go léir. Tá sé feidhmiúil an rud céanna. Ar an drochuair, cód seo nach bhfuil ag dul a thiomsú go fóill. Má ritheann liom a dhéanamh sigme 0, conas rn Mé ag dul a fháil yelled ag? Cad atá sé ag dul a Ní maith liom? LUCHT ÉISTEACHTA: [inaudible]. DAVID MALAN: Yeah, ní raibh mé a dhearbhú an fheidhm suas barr, ceart? Is é C de chineál ar dúr, sa mhéid is go sé ach a dhéanann cad a insint duit é sin a dhéanamh, agus tú é a dhéanamh san ord sin. Agus mar sin má bhuail mé Cuir isteach anseo, tá mé ag dul chun a fháil rabhadh faoi sigme intuigthe dearbhú. Ní Oh, ina fhadhb. Is féidir liom dul suas go dtí an barr, agus is féidir liom rá, ceart go léir, fan nóiméad. Is Sigma feidhm go bhfilleann ina slánuimhir agus tá sé ag súil le slánuimhir mar ionchur, Leathstad. Nó d'fhéadfadh mé a chur ar an fheidhm iomlán thuas is mó, ach go ginearálta, ba mhaith liom mholadh i gcoinne, mar tá sé deas a bheith acu is mó i gcónaí ag an mbarr sin Is féidir leat Léim ceart i agus tá a fhios cad a tá clár déanamh ag léamh phríomh dtús. Mar sin, anois lig dom soiléir ar an scáileán. Remake sigme 0. Gach is cosúil a sheiceáil amach. Lig dom a reáchtáil sigme 0. Inter dearfach. Feicfidh mé a thabhairt dó an uimhir 3 a choinneáil simplí. Mar sin, ba chóir a thabhairt dom 3 móide 2 móide 1, mar sin 6. Cuir isteach, agus go deimhin a rachaidh mé 6. Is féidir liom a dhéanamh rud éigin níos mó - 50, 12, 75. Díreach mar tadhlaí, tá mé ag dul a dhéanamh rud éigin a ridiculous cosúil le mór i ndáiríre líon, Ó, a d'oibrigh i ndáiríre amach - eh, ní dóigh liom go bhfuil an ceart. A ligean ar a fheiceáil. A ligean ar praiseach i ndáiríre leis. Sin fadhb. Cad atá ar siúl? Tá an cód go dona. Tá sé fós líneach. Is feadaíl i bhfeidhm go maith, cé. Cad atá ar siúl? Níl mé cinnte má chuala mé é. Mar sin, casadh sé amach - agus tá sé seo mar leataobh. Ní hé seo an croílár an smaoineamh athchúrsáil. Casadh sé amach, mar go bhfuil mé ag iarraidh a ionadaíocht a dhéanamh ar líon mór, an chuid is mó dócha go bhfuil sé á misinterpreted le C mar uimhir ní dearfach, ach uimhir dhiúltach. Ní mór dúinn Labhair faoi seo, ach tá sé casadh amach go bhfuil uimhreacha diúltacha ar fud an domhain chomh maith chun uimhreacha deimhneacha. Agus an tslí ar féidir leat a ionadaíocht a dhéanamh ar uimhir dhiúltach go bunúsach é, a úsáideann tú amháin giotán speisialta a chur in iúl dearfach thar diúltach. Tá sé beagán níos casta ná sin, ach sin ar an smaoineamh bunúsach. Mar sin, ar an drochuair, má tá C mearbhall amháin de na píosaí is brí i ndáiríre, OH, tá sé seo le uimhir dhiúltach, mo lúb anseo, mar shampla go bhfuil, i ndáiríre riamh ag dul a fhoirceannadh. Mar sin, má bhí mé i ndáiríre rud éigin priontáil arís agus arís eile, ba mhaith linn féach ar a lán iomlán. Ach arís, tá sé seo sa bhreis ar an bpointe. Tá sé seo i ndáiríre ach saghas fiosracht intleachtúil go beidh muid ag teacht ar ais go dtí ar deireadh thiar. Ach do anois, tá sé seo ceart chur i bhfeidhm má glacadh againn go bhfuil an Beidh úsáideoirí a chur ar fáil ints go cuí laistigh ints. Ach Éilím go gcód seo, frankly, d'fhéadfaí a dhéanamh sin i bhfad níos simplí. Má tá an sprioc ar láimh go dtógfaidh sé roinnt cosúil le m agus cuir suas gach ceann de na uimhreacha idir é agus 1, nó a mhalairt idir 1 agus, Éilím gur féidir liom a fháil ar iasacht an smaoineamh seo go chumasadh saghas bhí, a bhí ag cur le fadhb an méid agus tríd sé i rud éigin níos lú. B'fhéidir nach bhfuil leath, ach níos lú, ach representatively mar an gcéanna. Smaoineamh céanna, ach is fadhb níos lú. Mar sin, tá mé i ndáiríre - lig dom comhad seo a shábháil le roinnt leagan éagsúla. Beidh muid ag glaoch ar an leagan seo 1 in ionad 0. Agus Éilím gur féidir liom i ndáiríre reimplement seo i saghas seo de aigne-lúbthachta bhealach. Tá mé ag dul a fhágáil cuid de ina n-aonar. Tá mé ag dul a rá más rud é go m níos lú mó ná nó cothrom le fiú 0 - Tá mé ag dul díreach tar éis a bheith beagán níos anal am seo le mo seiceáil earráid - Tá mé ag dul chun dul ar aghaidh agus ar ais 0. Tá sé seo treallach. Tá mé díreach tar cinneadh ach má tá an t-úsáideoir Tugann dom uimhir dhiúltach, tá mé filleadh 0, agus ba chóir iad a bheith léite an doiciméadú níos dlúithe. Eile - faoi ​​deara cad tá mé ag dul a dhéanamh. Eile Tá mé ag dul a thabhairt ar ais m móide - cad é sigme de m? Bhuel, sigme de m móide m lúide 1, móide m lúide 2, móide m lúide 3. Níl mé ag iarraidh a scríobh gach ceann de sin amach. Cén fáth nach féidir liom ach punta? Hathchúrsach glaoch mé féin le beagán fadhb níos lú, Leathstad, agus glao sé lá? Ceart? Anois anseo, freisin, d'fhéadfadh mbraitheann tú nó imní go bhfuil sé seo le lúb gan teorainn go bhfuil mé inducing, trína Táim ag cur sigma trí ghlaoch sigme. Ach go breá OK, mar gheall mé shíl amach romhainn le breise a línte? LUCHT ÉISTEACHTA: [inaudible]. DAVID MALAN: 23 go 26, a Is é mo má riocht. Mar gheall ar cad atá deas mar gheall ar an dealú anseo, mar gheall ar mé a choinneáil fuair tú fadhbanna níos lú sigme, níos lú fadhbanna, níos lú - nach bhfuil sé leath an méid. Tá sé ach ina chéim leanbh níos lú, ach sin ceart go leor. Mar gheall ar deireadh thiar, beidh muid ag obair ár mbealach síos go dtí 1 nó 0. Agus nuair a bhuail muid 0, ní sigme ag dul chun glaoch féin níos mó. Tá sé ag dul a thabhairt ar ais láithreach 0. Mar sin, an éifeacht, má saghas tú na gaoithe seo suas i d'intinn, a chur m móide m lúide 1, móide m lúide 2, móide m lúide 3, móide ponc, ponc, ponc, m lúide m, ar deireadh thiar a thabhairt duit 0, agus an Is é éifeacht sa deireadh thiar a chur leis ar fad na rudaí seo le chéile. Mar sin, ní mór dúinn, le recursion, réiteach ar an bhfadhb go bhfuil muid Ní fhéadfaí a réiteach roimh. Go deimhin, leagan 0 seo, agus gach fhadhb go dtí seo, bhí solvable le díreach ag baint úsáide as do lúba nó cé lúba nó constructs den chineál céanna. Ach recursion, mé daresay, tugann dúinn ar bhealach difriúil ag smaoineamh faoi fadhbanna, trína más féidir linn a ghlacadh le fhadhb, déan é a roinnt ó rud éigin beagán mór i rud éigin beagán níos lú, éileamh mé gur féidir linn a réiteach é b'fhéidir beagán níos elegantly i dtéarmaí an dearadh, le cód níos lú, agus b'fhéidir fiú fadhbanna a bheadh ​​a réiteach a bheith níos deacra, mar beidh muid ag deireadh a fheiceáil, a réiteach amháin iteratively. Ach an cliffhanger go ndearna mé ag iarraidh a fhágáil linn ar go raibh sé seo. Lig dom dul ar aghaidh agus a oscailt suas comhad ó - i ndáiríre, lig dom dul agus é seo a dhéanamh go tapa fíor. Lig dom dul ar aghaidh agus a mholadh an méid seo a leanas. I measc cód an lae inniu é an comhad seo anseo. Sé seo ar cheann anseo, noswap. Mar sin, tá sé seo le clár beag dúr go Bhuailtí mé suas go n-éileamh a dhéanamh an méid seo a leanas. I is mó, fógraíonn sé ar dtús ar slánuimhir x dtugtar agus sannann sé an luach 1. Ansin Dearbhaíonn sé y slánuimhir agus Sannann sé an luach 2. Ansin, priontaí sé amach cad é x agus y. Ansin deir sé, swapping, ponc ponc ponc. Ansin, éilimh sé a bheith ag glaoch feidhm ar a dtugtar babhtála, ag dul in x agus y, an smaoineamh a bhfuil an súil go dtosnódh Beidh x agus y teacht ar ais éagsúla, an os coinne. Ansin éileamh é a bhabhtáil! le pointe exclamation. Ansin, priontaí sé amach x agus y. Ach casadh sé amach go bhfuil sé seo an- taispeántais shimplí síos anseo i ndáiríre Buggy. Cé go bhfuil mé á dhearbhú sealadach athraitheach agus a chur go sealadach i sé, ansin tá mé ag athshannadh a luach b - a bhraitheann réasúnta, mar tá mé shábháil cóip de i teocht. Ansin mé suas chun dáta go cothrom b cuma cad a bhí i teocht. An saghas cluiche bhlaosc de bogadh ar i b agus b isteach ag baint úsáide as an lár-fear ar a dtugtar mothaíonn teocht breá réasúnta. Ach Éilím go nuair a ritheann liom é seo Cód, mar beidh mé a dhéanamh anois - lig dom dul ar aghaidh agus é a ghreamú i anseo. Feicfidh mé glaoch seo noswap.c. Agus mar a léiríonn an t-ainm, nach bhfuil sé seo dul chun bheith ina clár ceart. Déan noswap. / Gan babhtála. Is é x 1, y 2, swapping, swapped. Is é x 1, y 2. Tá sé seo go bunúsach mícheart, fiú cé is cosúil seo breá réasúnta dom. Agus tá cúis ann, ach nach bhfuil muid ag dul a nochtann an chúis ach go fóill. Chun anois an dara cliffhanger bhí mé a fhágann tú leis é seo, fógra de shaghas ar cóid cúpón. Ár nuálaíocht le laethanta go déanach i mbliana tá provoked roinnt neamh-fánach ceisteanna, a bhí Ní ár n-intinn. An aidhm do na cóid cúpón, trína má dhéanann tú cuid den fhadhb leagtha go luath, rud a fháil lá breise, a bhí i ndáiríre chun cabhrú leat guys cabhrú tús a chur ort féin go luath, saghas de réir incentivizing agat. Cabhraíonn sé linn ualach a dháileadh ar fud na uaireanta oifige níos fearr ionas go tá sé saghas bua-bua. Ar an drochuair, I mo thuairimse, mo treoracha Ní raibh, go dtí seo, an-soiléir, mar sin Chuaigh mé ar ais an deireadh seachtaine seo agus cothrom le dáta an spec i níos mó, téacs níos dána le urchair mar seo a mhíniú. Agus ach a rá sé níos poiblí, ag réamhshocraithe, leagann fhadhb atá dlite Déardaoin ag meán lae, in aghaidh an siollabas. Má thosaíonn tú go luath, ag críochnú mar chuid de an fhadhb atá leagtha síos ag Dé Céadaoin ag 12:00 AM, an chuid a bhaineann le cúpón Cód, is é an smaoineamh gur féidir leat a leathnú do spriocdháta don P atá leagtha go dtí an Aoine. Is é sin, beagán de thalamh cuid bheag bhídeach den P atá leagtha i gcoibhneas leis an méid a bhfuil de ghnáth an fadhb níos mó, agus a cheannaíonn tú tú féin lá breise. Arís, faigheann sé tú ag smaoineamh faoi an fhadhb a leagtar, faigheann tú uaireanta oifige túisce. Ach tá an fhadhb cód cúpón fós teastáil, fiú mura bhfuil tú isteach é. Ach tá níos mó compellingly seo. (CÉIM cogar) Agus na folks ag fágáil luath iad ag dul a aiféala é. Toisc go bhfuil na folks ar an mbalcóin. Mé leithscéal a ghabháil roimh ré leis an folks ar an mbalcóin ar chúiseanna a bheidh soiléir i díreach nóiméad. Mar sin, tá muid t-ádh a bheith ar cheann de na Iar comhaltaí teagaisc ceann CS50 ag cuideachta ar a dtugtar dropbox.com. Tá siad bhronn go fial le Cód cúpón anseo le haghaidh an spás i bhfad, a bhfuil suas as an is gnách ghigibheart 2. Mar sin, cad a cheap mé go mbeadh linn a dhéanamh ar an Tá nóta deiridh a dhéanamh le beagán de giveaway, trína i díreach nóiméad, beidh muid ag nochtann Tá an buaiteoir agus a cúpón Cód gur féidir leat dul ansin chuig a gcuid láithreán gréasáin, cineál sé isteach, agus voila, a fháil lán iomlán níos mó Dropbox spás le haghaidh do fearas agus do do chuid comhad pearsanta. Agus an chéad, ar mhaith leo a bheith páirteach sa líníocht? OK, anois a dhéanann sé níos spraoi fiú. An duine a fhaigheann an 25-gigabyte Cód cúpón - atá i bhfad níos láidre ná an déanach lá anois, b'fhéidir - Is é an duine atá ina shuí ar bharr mhaolú suíochán faoi bhun a bhfuil go bhfuil cód cúpón. Is féidir leat breathnú anois thíos do mhaolú suíochán. [Athsheinm físe] -Aon, dó, trí. [Screaming] -Tá tú a fháil gluaisteán! A gheobhaidh tú carr! DAVID MALAN: Beidh muid a fheiceáil tú ar an gCéadaoin. -Tá tú a fháil gluaisteán! A gheobhaidh tú carr! A gheobhaidh tú carr! A gheobhaidh tú carr! A gheobhaidh tú carr! DAVID MALAN: folks BALCÓIN, teacht síos anseo chun an tosaigh, áit a bhfuil muid extras. Faigheann gach duine-carr! Faigheann gach duine carr! [Athsheinm físe END] Scéalaí: Ag CS50 seo chugainn - Cainteoir 5: Oh my gosh gosh gosh gosh gosh gosh gosh gosh gosh gosh - [Drámaí UKELELE]