[CHWARAE CERDDORIAETH] 

ATHRO: Pob hawl. Mae hyn yn CS50 ac mae hyn yn diwedd yr wythnos tri. Felly rydym ni yma heddiw, nid yn Sanders Theater, yn lle hynny yn Llyfrgell Weidner. Y tu mewn ohonynt yn stiwdio a elwir yn Hauser Studio, neu byddwn yn dweud Stiwdio H, neu bydd rydym say-- os ydych yn mwynhau y jôc, 'i' mewn gwirionedd o classmate, Mark, ar-lein, a awgrymodd gymaint drwy Twitter. Nawr beth cŵl am bod yma mewn stiwdio yw fy mod i'n amgylchynu gan y rhain gwyrdd waliau, sgrin gwyrdd neu chromakey, fel petai, sy'n golygu bod CS50 yn tîm cynhyrchu, unbeknownst i mi ar hyn o bryd, gallai fod yn rhoi mi y rhan fwyaf o unrhyw le yn y byd, er gwell neu er gwaeth. 

Nawr beth sydd o'n blaen, problem a osodwyd dau yn eich dwylo chi am yr wythnos hon, ond gyda phroblem a osodwyd tair wythnos hon sydd i ddod, byddwch yn cael eich herio gyda y gêm yn hyn a elwir o 15, hen blaid blaid sydd efallai y byddwch yn cofio derbyn fel plentyn sydd â criw cyfan o rifau sy'n gallu llithro i fyny, i lawr, chwith ac i'r dde, ac mae un bwlch o fewn y pos, i mewn yr ydych Gall gwirionedd sleid darnau pos hynny. Yn y pen draw byddwch yn derbyn hyn bendroni mewn rhyw drefn lled hap, a'r nod yw datrys y mater, top i'r gwaelod, o'r chwith i'r dde, o un yr holl ffordd i fyny drwy'r 15. 

Yn anffodus, mae'r gweithredu bydd gennych wrth law yn mynd i fod meddalwedd seiliedig ar waith, nid yn gorfforol. Rydych yn wir yn mynd i gael i ysgrifennu Cod â hwy can myfyrwyr neu ddefnyddiwr chwarae'r gêm o 15. Ac yn wir, yn y haciwr rhifyn o gêm o 15, byddwch yn her i weithredu, nid dim ond chwarae hen ysgol hon gêm, ond yn hytrach y datrys ohono, gweithredu dull duw, fel petai, sydd mewn gwirionedd datrys y pos ar gyfer y bobl, trwy roi iddynt awgrym, ar ôl awgrym, ar ôl awgrym. Felly mwy am hynny yr wythnos nesaf. Ond dyna beth o'n blaenau. 

Am y tro dwyn i gof bod yn gynharach yr wythnos hon cawsom Cliffhanger hwn, os gwnewch, lle y gorau oeddem yn ei wneud didoli doeth yn uchaf yn rhwymo o fawr o o n sgwâr. Mewn geiriau eraill, didoli swigen, didoli dewis, didoli mewnosod, pob un ohonynt, er bod gwahanol yn eu rhoi ar waith, ddatganoli i mewn i n sgwâr yn rhedeg amser yn yr achos gwaethaf iawn. Ac rydym yn gyffredinol yn cymryd yn ganiataol bod yr achos gwaethaf iawn ar gyfer didoli yn un sy'n eich mewnbynnau yn gwbl ôl. Ac yn wir, fe gymerodd dipyn o ychydig gamau i weithredu pob un o'r algorithmau hynny. 

Nawr ar ddiwedd y dosbarth galw i gof, rydym yn cymharu fath swigen yn erbyn didoli detholiad yn erbyn un arall ein bod yn elwir math uno ar y pryd, a chynigiaf ei fod yn cymryd mantais o wers o wythnos sero, rhaniad a gorchfygu. A rhywsut cyflawni rhyw fath o logarithmig rhedeg amser yn y pen draw, yn hytrach na rywbeth mae hynny'n cwadratig yn unig. Ac nid mae'n eithaf logarithmig, mae'n ychydig yn fwy na hynny. Ond os ydych yn cofio o'r dosbarth, yr oedd yn llawer, llawer cyflymach. Gadewch i ni edrych ar lle yr ydym yn gadael i ffwrdd. 

Didoli swigen yn erbyn dewis didoli yn erbyn uno fath. Erbyn hyn maen nhw i gyd yn rhedeg, yn theori, ar yr un pryd. Mae'r CPU yn rhedeg ar yr un cyflymder. Ond gallwch deimlo pa mor ddiflas hwn yn gyflym iawn yn mynd i ddod yn, ac yn union pa mor gyflym, pan fyddwn yn chwistrellu ychydig o algorithmau wythnos sero, yn gallwn gyflymu pethau. 

Felly fath marc yn edrych yn anhygoel. Sut y gallwn trosoledd hynny, er mwyn i ddidoli rhifau yn gyflymach. Wel gadewch i ni feddwl yn ôl i cynhwysyn ein bod yn Roedd yn ôl yn wythnos sero, sef chwilio am rywun mewn llyfr ffôn, a dwyn i gof bod y pseudocode a gynigiwyd i ni, drwy y gallwn ddod o hyd i rhywun fel Mike Smith, yn edrych rhywbeth bach fel hyn. 

Nawr cymerwch olwg yn arbennig yn llinell 7 ac 8, a 10 a 11, sy'n cymell y ddolen, lle yr ydym yn cadw mynd yn ôl i linell 3 eto, ac unwaith eto, ar ôl tro. Ond mae'n troi allan ein bod yn gallu gweld algorithm hwn, yma yn pseudocode, ychydig yn fwy cyfannol. Yn wir, yr hyn yr wyf i'n edrych yn fan ar y sgrin, yn algorithm ar gyfer chwilio am Mike Smith ymysg rhai set o dudalennau. Ac yn wir, gallem symleiddio hyn algorithm yn y llinellau hynny 7 ac 8, a 10 a 11 i ddim ond dweud hyn, yr wyf wedi cyflwyno yma mewn melyn. Mewn geiriau eraill, os yw Mike Smith yn gynharach yn y llyfr, Nid oes angen i ni nodi cam wrth gam yn awr sut i fynd o hyd iddo. Nid oes rhaid i ni bennu i fynd yn ôl i'r llinell 3, pam nad ydym yn unig yn lle hynny, dyweder, yn fwy cyffredinol, chwilio am Mike yn y chwith hanner y llyfr. 

I'r gwrthwyneb, os Mike yn mewn gwirionedd yn nes ymlaen yn y llyfr, pam nad ydym yn unig dyfynnu chwilio unquote i Mike yn hanner dde o'r llyfr. Mewn geiriau eraill, pam na wnewch rydym yn unig fath o punt i ni ein hunain gan ddweud, chwilio am Mike yn hyn is-set o'r llyfr, a'i adael i'n presennol algorithm i ddweud wrthym sut i chwilio am Mike yn fod hanner chwith y llyfr. Mewn geiriau eraill, mae ein algorithm yn gweithio boed yn llyfr ffôn o drwch hwn, o hyn trwch, neu unrhyw drwch o gwbl. Felly allwn recursively diffinio algorithm hwn. Mewn geiriau eraill, ar y sgrîn yma, yn algorithm ar gyfer chwilio am Mike Smith ymhlith y tudalennau llyfr ffôn. Felly, yn unol 7 a 10, gadewch i ni dim ond dweud yn union hynny. Ac yr wyf yn defnyddio'r term hwn eiliad yn ôl, ac yn wir, recursion yw'r buzzword am y tro, a 'i' y broses hon o wneud rhywbeth cylchol gan rhywsut gan ddefnyddio cod sy'n gennych eisoes, ac yn galw eto, ac unwaith eto, ac unwaith eto. Nawr mae'n mynd i fod yn bwysig ein bod rywsut gwaelod allan, ac nid ydynt yn gwneud hynny anfeidrol hir. Fel arall, rydym yn mynd i rhaid yn wir dolen ddiddiwedd. Ond gadewch i ni weld os allwn ni gael benthyg y syniad hwn o recursion, yn gwneud rhywbeth eto ac eto ac eto, i ddatrys y broblem didoli drwy uno didoli, yn fwy effeithlon. 

Felly, yr wyf yn rhoi i chi yn uno fath. Gadewch i ni edrych. Felly dyma pseudocode, gyda y gallem gweithredu didoli, gan ddefnyddio algorithm hwn a elwir yn didoli uno. Ac mae'n eithaf syml hyn. Ar fewnbwn o elfennau n, mewn geiriau eraill, os ydych yn Rhoddir n elfennau a rhifau a llythyrau neu beth bynnag yw'r mewnbwn yn, os ydych yn rhoi elfennau n, os n yn llai na 2, dim ond yn dychwelyd. Iawn? Oherwydd os n yn llai na 2, bod yn golygu bod fy rhestr o elfennau naill ai o faint 0 neu 1, a yn y ddau achos dibwys hynny, mae'r rhestr eisoes yn cael ei datrys. Os nad oes rhestr, mae'n datrys. Ac os oes 'na restr o hyd 1, mae'n amlwg eu didoli. Felly, dim ond mae angen i'r algorithm 'n sylweddol yn gwneud rhywbeth diddorol, os bydd gennym ddau neu fwy elfennau a roddwyd i ni. Felly gadewch i ni edrych ar y hud bryd hynny. Arall ddatrys y hanner chwith y elfennau, Yna ddatrys yr hanner cywir o elfennau, Yna uno haneri didoli. A beth sy'n fath o feddwl plygu yma, yw nad wyf yn ei wneud mewn gwirionedd ymddangos i wedi dweud wrthych unrhyw beth eto, dde? Y cyfan yr wyf wedi dweud yn, rhoddir rhestr o n elfennau, didoli yr hanner chwith, Yna yr hanner dde, ac yna cyfuno'r haneri didoli, ond ble mae'r saws gyfrinach gwirioneddol? Ble mae'r algorithm? Wel mae'n troi allan bod y rhai ddwy linell yn gyntaf, didoli chwith hanner o elfennau, a math priodol hanner yr elfennau, galwadau recursive, fel petai. 

Wedi'r cyfan, ar hyn o bwynt mewn amser, mae gen i algorithm â hwy didoli criw cyfan o elfennau? Ydw. Mae'n iawn yma. Mae'n iawn yma ar y sgrin, ac fel y gallaf ddefnyddio'r un set o risiau i roi trefn ar yr hanner chwith, ag y gallaf yr hanner cywir. Ac yn wir, unwaith eto, ac unwaith eto. Felly rywsut neu'i gilydd, ac rydym annhymerus 'yn fuan gweld hyn, hud a lledrith math uno wedi'i wreiddio yn y rownd derfynol iawn llinell, gyfuno'r haneri didoli. Ac mae hynny'n ymddangos yn weddol 'n athrylithgar. Byddwch yn cymryd dau hanner, a chi, rywsut, uno nhw at ei gilydd, a byddwn yn gweld hyn diriaethol mewn munud. 

Ond mae hyn yn algorithm cyflawn. A gadewch i ni weld yn union pam. Wel mae'n debyg ein bod yn rhoi y rhain un fath wyth elfen yma ar y sgrin, un drwy wyth, ond maen nhw'n er mwyn i bob golwg ar hap. A'r nod dan sylw yw i ddidoli elfennau hyn. Wel sut gallaf fynd ati i ei wneud gan ddefnyddio, unwaith eto, uno yn didoli, yn unol pseudocode hwn? Ac eto, drwytho hyn mewn eich meddwl, am ddim ond eiliad. Yr achos cyntaf yn eithaf ddibwys, os yw'n llai na 2, dim ond yn dychwelyd, does dim gwaith i'w wneud o hyd. Felly mewn gwirionedd does dim ond tri camau i gadw 'n sylweddol mewn golwg. Unwaith eto, ac unwaith eto, rwy'n mynd i eisiau i gael i roi trefn ar yr hanner chwith, didoli'r hanner cywir, ac yna unwaith y bydd eu dau hanner yn cael eu datrys, Rwyf am i uno gyda'i gilydd i mewn i un rhestr didoli. Felly cadwch hynny mewn cof. 

Felly dyma y rhestr wreiddiol. Gadewch i drin hyn fel array, wrth i ni ddechrau mewn wythnos dau, sydd yn bloc cyffiniol o gof. Yn yr achos hwn, sy'n cynnwys wyth rhifau, cefn wrth gefn wrth gefn. A gadewch i ni yn awr yn berthnasol fath uno. Felly, yn gyntaf yr wyf am roi trefn hanner chwith y rhestr hon, a gadewch i ni, felly, canolbwyntio ar 4, 8, 6, a 2. 

Nawr, sut ydw i'n mynd ati didoli rhestr o faint 4? Wel rhaid i mi ystyried yn awr didoli ar ochr chwith y hanner chwith. Unwaith eto, gadewch i ailddirwyn am ddim ond ennyd. Os bydd y pseudocode yn hyn, ac rwy'n rhoi wyth elfen, 8 yn amlwg yn fwy na neu'n hafal i 2. Felly, gyda nad yw'r achos cyntaf yn berthnasol. Felly, i ddidoli wyth elfen, yr wyf yn gyntaf ddatrys y hanner chwith o elfennau, yna yr wyf didoli'r hanner dde, ac yna yr wyf yn uno y ddau hanner ddidoli, pob un o faint 4. IAWN. 

Ond os ydych chi newydd ddweud wrthyf, didoli'r chwith hanner, sydd bellach o faint 4, sut ydw i'n ddatrys yr hanner ar ôl? Wel os oes gennyf mewnbwn pedair elfen, Rwyf yn gyntaf ddatrys y chwith dau, yna bydd y ddau yn iawn, ac yna rwyf yn uno nhw at ei gilydd. Felly unwaith eto, mae'n dod yn dipyn o feddwl plygu gêm yma, oherwydd eich bod, math o, rhaid i cofio ble rydych chi yn y stori, ond ar ddiwedd y dydd, o ystyried unrhyw nifer o elfennau, eich bod am y tro cyntaf i ddidoli'r chwith hanner, yna bydd y hanner cywir, Yna uno nhw at ei gilydd. Gadewch i ni ddechrau i wneud yn union hynny. Heres '' r mewnbwn o wyth elfen. Nawr rydym yn edrych ar yr hanner chwith fan hyn. Sut ydw i'n trefnu pedair elfen? Wel cyntaf i mi ddatrys yr hanner chwith. Nawr, sut ydw i'n ddatrys yr hanner ar ôl? Wel rydw i wedi ei roi dwy elfen. Felly gadewch i ni ddatrys y ddwy elfen. 2 yn fwy na neu'n gyfartal i 2, wrth gwrs. Fel nad yw achos cyntaf yn berthnasol. 

Felly, rhaid i mi roi trefn ar y chwith bellach hanner y rhain ddwy elfen. Mae'r hanner chwith, wrth gwrs, yn unig 4. Felly, sut ydw i'n trefnu rhestr o un elfen? Wel nawr, bod achos sylfaenol arbennig i fyny top, fel petai, yn berthnasol. 1 yn llai na 2, ac mae fy rhestr hon yn wir o faint 1. Felly, Fi jyst yn dychwelyd. Dydw i ddim yn gwneud unrhyw beth. Ac yn wir, yn edrych ar yr hyn yr wyf i wedi wneud, 4 eisoes yn didoli. Fel dwi'n barod rhannol lwyddiannus yma. 

Nawr bod yn ymddangos fath o dwp i hawlio, ond mae'n wir. 4 yn rhestr o faint 1. Mae eisoes wedi eu didoli. Dyna yr hanner chwith. Nawr rwy'n ddatrys yr hanner cywir. Mae fy mewnbwn yn un elfen, 8 yn yr un modd, eisoes yn didoli. Stupid, hefyd, ond unwaith eto, yr egwyddor sylfaenol hon yn mynd i ganiatáu i ni i adeiladu nawr ar ben hyn yn llwyddiannus. 4 didoli, 8 yn cael ei datrys, yn awr beth oedd y cam olaf? Felly y trydydd a'r olaf cam, unrhyw amser yr ydych yn didoli rhestr, galw i gof, oedd uno'r ddau hanner, y chwith a'r dde. Felly, gadewch i ni wneud yn union hynny. Fy hanner chwith, wrth gwrs, 4. Fy hanner cywir yw 8. 

Felly, gadewch i ni wneud hyn. Yn gyntaf i ddim yn mynd i ddyrannu rhywfaint cof ychwanegol, y byddaf yn cynrychioli yma, fel dim ond amrywiaeth eilaidd, mae hynny'n ddigon mawr i ffitio hyn. Ond gallwch ddychmygu ymestyn y petryal hyd cyfan, os bydd angen mwy yn nes ymlaen. Sut ydw i'n cymryd 4 ac 8, ac yn uno y rhai ddwy restr o faint 1 at ei gilydd? Yma, hefyd, eithaf syml. 4 yn dod yn gyntaf, yna daw 8. Oherwydd os wyf am i ddatrys y chwith hanner, yna bydd y hanner cywir, ac yna uno dau hanner y rhai gyda'i gilydd, er mwyn ddidoli, 4 yn dod yn gyntaf, yna daw 8. 

Felly, rydym yn ymddangos i fod yn gwneud cynnydd, hyd yn oed er nad wyf wedi gwneud unrhyw waith gwirioneddol. Ond cofiwch lle'r ydym ni yn y stori. Rydym yn wreiddiol yn cymryd wyth elfen. Rydym yn datrys yr hanner chwith, sydd 4. Yna rydym yn datrys yr hanner chwith yr hanner chwith, a oedd yn 2. A dyma ni yn mynd. Rydym yn ei wneud gyda y cam hwnnw. 

Felly, os ydym wedi datrys y Gadawodd hanner 2, yn awr rydym rhaid i ddatrys yr hanner dde 2. Felly yr hanner dde 2 yw y ddau gwerthoedd yma, 6 a 2. Felly, gadewch i ni yn awr yn cymryd mewnbwn o faint 2, a didoli'r hanner chwith, ac yna yr hanner i'r dde, ac yna uno nhw at ei gilydd. Wel sut ydw i'n trefnu rhestr o faint 1, yn cynnwys dim ond y rhif 6? Im 'yn gwneud yn barod. Bod rhestr o faint 1 yn cael ei datrys. 

Sut ydw i'n ddatrys rhestr arall o maint 1, yr hanner cywir fel y'u gelwir. Wel mae'n, hefyd, yn cael ei eisoes didoli. Mae'r rhif 2 yn unig. Felly nawr mae gen i ddau hanner, i'r chwith ac iawn, mae angen i mi uno gyda'i gilydd. Gadewch i mi roi rhywfaint o le ychwanegol fy hun. A rhowch 2 mewn 'na, Yna 6 mewn 'na, a thrwy hynny didoli y rhestr honno, i'r chwith ac i'r dde, a chyfuno ei gilydd, yn y pen draw. Felly rwy'n mewn siâp ychydig yn well. Dydw i ddim yn ei wneud, oherwydd yn amlwg 4, 8, 2, 6 Nid yw'r archebu olaf yr wyf am. Ond yr wyf yn awr wedi dwy restr o faint 2, bod ill dau, yn y drefn honno, wedi'u didoli. Felly nawr os ydych yn ail-ddirwyn yn eich meddwl yn llygad, lle oedd hynny'n ein gadael? Dechreuais gydag wyth elfen, yna rwyf yn dreulio o dipyn i lawr i hanner chwith 4, yna bydd y hanner chwith 2, a yna bydd y hanner cywir o 2, Gorffennais, felly, didoli y chwith hanner 2, ac mae'r hanner cywir o 2, felly beth yw'r trydydd a'r olaf cam yma? Mae'n rhaid i mi uno gyda'n gilydd dwy restr o faint 2. Felly gadewch i ni fynd yn ei flaen. Ac ar y sgrin yma, yn rhoi m rhyw cof ychwanegol, er yn dechnegol, yn sylwi fy mod i wedi got criw cyfan o le i fyny top wag yno. Os ydw i eisiau i fod yn arbennig gofod effeithlon ddoeth, Gallai Fi jyst yn dechrau symud yr elfennau yn ôl ac ymlaen, top a gwaelod. Ond dim ond am eglurder gweledol, Rydw i'n mynd i roi i lawr isod, i gadw pethau neis ac yn lân. 

Felly, yr wyf wedi cael dwy restr o faint 2. Mae'r rhestr gyntaf Mae 4 ac 8. Mae'r ail restr Mae 2 a 6. Gadewch i uno rhai at ei gilydd er mwyn didoli. 2, wrth gwrs, yn dod yn gyntaf, Yna, 4, ac yna 6, yna 8. Ac yn awr rydym yn ymddangos i fod yn ei gael rhywle diddorol. Hanner Nawr rydw i wedi datrys y rhestru, ac gyd-ddigwyddiad, 'i' yr holl rifau hyd yn oed, ond bod yw, yn wir, dim ond cyd-ddigwyddiad. Ac yr wyf yn awr wedi datrys y chwith hanner, fel ei fod yn 2, 4, 6, ac 8. Nid oes unrhyw beth sydd allan o drefn. Mae hynny'n teimlo fel gynnydd. 

Nawr mae'n teimlo fel fy mod i wedi bod yn siarad am byth yn awr, felly beth rhaid aros i weld os yw hyn algorithm yw, yn wir, yn fwy effeithlon. Ond rydym yn mynd trwy mae'n super drefnus. Mae cyfrifiadur, wrth gwrs, Byddai gwneud hynny fel 'na. Felly, lle rydym ni? Rydym yn dechrau gyda wyth elfen. Yr wyf yn datrys yr hanner chwith 4. Yr wyf yn ymddangos i gael ei wneud â hynny. Felly, yn awr y cam nesaf yw i didoli hanner dde 4. Ac mae rhan hon y gallwn fynd drwy ychydig mwy gyflym, er eich bod chi'n croeso i ailddirwyn neu oedi, dim ond feddwl drwyddo ar eich cyflymder eich hun, ond beth gennym yn awr gyfle i wneud yr un peth algorithm union ar bedwar niferoedd gwahanol. 

Felly gadewch i ni fynd yn ei flaen, ac yn canolbwyntio ar yr hanner cywir, yr ydym yma. Mae hanner chwith y hanner i'r dde, ac yn awr y chwith hanner y chwith hanner y bod hanner cywir, a sut ydw i'n trefnu rhestr o faint 1 yn cynnwys dim ond y rhif 1? Mae'n ei wneud yn barod. Sut ydw i'n gwneud yr un peth am restr o faint 1 sy'n cynnwys dim ond 7? Mae'n ei wneud yn barod. Cam tri am hanner hwn, yna yw cyfuno'r ddwy elfen i mewn i restr newydd o faint 2, 1 a 7. Peidiwch ymddangos i wedi gwneud popeth bod llawer o waith diddorol. Gadewch i ni weld beth fydd yn digwydd nesaf. Fi jyst didoli hanner chwith y hanner dde fy mewnbwn gwreiddiol. Nawr, gadewch i ddatrys yr hawl hanner, sy'n cynnwys 5 a 3. Gadewch i ni edrych eto ar y chwith hanner, didoli, hanner cywir, didoli, ac uno y ddau gyda'i gilydd, i mewn i rai lle ychwanegol, 3 yn dod yn gyntaf, yna daw 5. Ac felly yn awr, yr ydym wedi datrys y chwith hanner yr hanner cywir y broblem wreiddiol, ac hanner dde o'r hanner cywir y broblem wreiddiol. Beth yw'r trydydd a'r olaf Step? Wel i uno dau hanner y rheini at ei gilydd. Felly, gadewch i mi gael fy hun rai gofod ychwanegol, ond, unwaith eto, yr wyf yn Gallai fod yn defnyddio'r lle i fyny top sbâr. Ond rydym yn mynd i gadw bethau'n syml ar eu golwg. Gadewch i mi uno yn awr 1, a Yna, 3, ac yna 5, ac yna 7. Gan adael i mi yn awr gyda'r hanner dde o'r broblem wreiddiol sy'n datrys berffaith. 

Felly beth yn parhau i fod? Rwy'n teimlo fy mod yn dal i ddweud y un pethau eto, ac unwaith eto, ond mae hynny'n adlewyrchu ffaith ein bod yn defnyddio recursion. Mae'r broses o ddefnyddio algorithm eto, ac unwaith eto, ar is-setiau llai o broblem wreiddiol. Felly yr wyf bellach wedi i'r chwith didoli hanner y broblem wreiddiol. Mae gen i hanner ddidoli hawl y broblem wreiddiol. Beth yw'r trydydd cam a'r olaf? O, mae'n cyfuno. Felly, gadewch i ni wneud hynny. Gadewch i ni ddyrannu rhai ychwanegol cof, ond mae fy duw, rydym yn gallai roi unrhyw le yn awr. Mae gennym gymaint o le sydd ar gael i ni, ond byddwn yn cadw pethau'n syml. Yn hytrach na mynd yn ôl ac allan gyda'n cof gwreiddiol, gadewch i jyst yn ei wneud yn weledol lawr yma isod, i orffen i fyny uno'r chwith hanner a hanner cywir. 

Felly trwy gyfuno, beth sydd angen i mi ei wneud? Rwyf am gymryd yr elfennau yn eu trefn. Felly edrych ar yr hanner chwith, Rwy'n gweld y rhif cyntaf yw 2. Yr wyf yn edrych ar yr hanner cywir, Rwy'n gweld y rhif cyntaf yw 1, felly mae'n amlwg pa Rhif ydw i am tyn allan, a rhoi yn gyntaf yn fy rhestr derfynol? Wrth gwrs, 1. Nawr rwyf am ofyn bod un cwestiwn. Ar yr hanner chwith, rwyf wedi yn dal i gael y rhif 2. Ar yr hanner cywir, Rwyf wedi cael y rhif 3. Pa un ydw i am ei ddewis? Wrth gwrs, rhif 2 A bellach yn sylwi ar yr ymgeiswyr Mae 4 ar y chwith, 3 ar y dde. Gadewch i ni, wrth gwrs, dewiswch 3. Nawr bod yr ymgeiswyr yn cael eu 4 ar y chwith, 5 ar y dde. Yr ydym, wrth gwrs, dewiswch 4. 6 ar y chwith, 5 ar y dde. Yr ydym, wrth gwrs, dewiswch 5. 6 ar y chwith, 7 ar y dde. Rydym yn dewis 6, ac yna rydym yn dewiswch 7, ac yna rydym yn dewis 8. Voila. 

Felly mae nifer fawr o eiriau yn ddiweddarach, rydym yn wedi datrys y rhestr hon o wyth elfen i mewn i restr o un drwy wyth, sy'n cynyddu gyda phob cam, ond gwnaeth faint o amser ei gymryd i ni wneud hynny. Wel dwi wedi fwriadol pethau a osodwyd allan ar ffurf lluniau yma, fel y gallwn fath o gweld neu'n gwerthfawrogi'r is-adran yn trechu sydd wedi bod yn digwydd. 

Yn wir, os ydych yn edrych yn ôl ar y sgil, Rwyf wedi gadael pob un o'r llinellau toredig hyn mewn dalwyr lle, gallwch, math o, gweler, er mwyn cefn, os ydych yn fath o edrych yn ôl mewn hanes yn awr, fy rhestr wreiddiol yw, wrth gwrs, o faint 8. Ac yna o'r blaen, roeddwn yn delio â dwy restr o faint 4, ac yna pedair rhestr o faint 2, ac yna wyth rhestrau o faint 1. 

Felly beth yn gwneud hyn, math o, yn eich atgoffa? Wel, yn wir, unrhyw un algorithmau rydym wedi edrych ar hyd yn hyn lle rydym rhaniad, a rhannu, a rhannu, parhau i gael pethau eto, a unwaith eto, yn arwain at syniad cyffredinol hwn. Ac felly mae yna rywbeth mynd yn logarithmig yma. Ac nid yw log eithaf o n, ond mae 'na elfen logarithmig i'r hyn yr ydym wedi ei wneud yn unig. 

Nawr, gadewch i ni ystyried sut mae hynny'n mewn gwirionedd. Felly, log o n, unwaith eto roedd amser rhedeg mawr, pan wnaethom rhywbeth fel chwilio deuaidd, fel yr ydym yn awr yn ei alw, y strategaeth rhaniad a gorchfygu trwy yr ydym yn dod o hyd i Mike Smith. Nawr yn dechnegol. Dyna sylfaen log 2 o n, hyd yn oed er yn y rhan fwyaf o ddosbarthiadau mathemateg, 10 Fel arfer, yn y sylfaen eich bod yn cymryd yn ganiataol. Ond mae gwyddonwyr cyfrifiadurol bron bob amser feddwl a siarad yn nhermau sylfaen 2, felly rydym yn gyffredinol dim ond dweud log n, yn hytrach na sylfaen log 2 o n, ond maent yn union yr un a'r un fath yn y byd o gyfrifiadur gwyddoniaeth, ac wrth fynd heibio, mae 'na ffactor cyson gwahaniaeth rhwng y ddau, felly mae'n Moot beth bynnag, am resymau mwy ffurfiol. 

Ond am nawr, yr hyn yr ydym yn gofalu ei gylch yw yr enghraifft hon. Felly gadewch i ni brofi trwy esiampl, ond ar lleiaf yn defnyddio enghraifft o'r rhifau wrth law fel gwiriad pwyll, os mynnwch. Felly, yn flaenorol y fformiwla yn sylfaen log 2 o n, ond beth yw n yn yr achos hwn. Roedd gen rhifau n wreiddiol, neu 8 o rif gwreiddiol benodol. Nawr mae wedi bod ychydig yn tra, ond rwy'n eithaf yn siwr bod sylfaen log 2 o werth 8 yn 3, ac yn wir, beth sy'n neis am hynny yw bod 3 yn union y nifer o weithiau eich bod yn gallu rhannu rhestr o hyd 8 eto, ac unwaith eto, ac eto, hyd nes eich bod yn gadael gyda rhestrau o faint dim ond 1. Iawn? 8 yn mynd i 4, yn mynd i 2, mynd i 1, a dyna adlewyrchu yn union hynny llun oedd gennym ychydig funudau'n ôl. Felly ychydig o bwyll wirio ynghylch lle logarithm yn cymryd rhan mewn gwirionedd. 

Felly nawr, beth arall sy'n cymryd rhan yma? n. Felly sylwi bod pob tro y byddaf yn rhannu y rhestr, er bod hynny am yn ôl mewn hanes yma, yr oeddwn yn dal i wneud pethau n. Mae hynny'n gam uno ofynnol bod Yr wyf yn cyffwrdd pob un o'r rhifau, er mwyn i lithro i mewn ei leoliad priodol. Felly, er bod y uchder o hyn diagram o faint log n o n neu 3, yn benodol, mewn geiriau eraill, Fe wnes tair adran yma. Faint o waith wnes i yn llorweddol ar hyd y siart hwn bob tro? 

Wel, mi wnes n camau o yn gweithio, oherwydd os wyf i wedi got pedair elfen a pedair elfen, ac mae angen i mi uno gyda'i gilydd. Angen i mi fynd drwy y pedair a phedwar hyn, yn y pen draw i uno nhw yn ôl i wyth elfen. Os y llaw gen i wyth bysedd dros yma, ac nid wyf yn ei wneud, ac wyth fingers-- sorry-- Os byddaf i wedi got pedwar bysedd dros yma, yr wyf yn ei wneud, pedwar bysedd dros yma, yr wyf yn ei wneud, yna mae hynny'n yr un fath enghraifft fel o'r blaen, os wyf yn gwneud wyth bysedd er yn cyfanswm, a gallaf, math o, yn ei wneud. Gallaf union wneud yma, Yna, gallaf yn sicr uno pob un o'r rhestrau hyn o faint 1 gyda'i gilydd. Ond yn sicr yn rhaid i mi edrych ar bob elfen yn union unwaith. Felly, mae'r uchder y broses hon yw n log, lled y broses hon, fel petai, yn n, felly yr hyn yr ydym yn ymddangos i gael, yn y pen draw, yw amser yn rhedeg o faint n amserau log n. 

Mewn geiriau eraill, yr ydym yn ei rannu y rhestr, log n amserau, ond bob tro baem yn gwneud hynny, yr ydym wedi cael i gyffwrdd pob un o'r elfennau er mwyn uno nhw i gyd gyda'i gilydd, a oedd yn Roedd n gam, felly mae gennym n amserau log n, neu fel y byddai gwyddonydd cyfrifiadurol yn dweud, asymptotically, a oedd yn fyddai'r gair mawr i ddisgrifio'r uchaf rhwymo ar amser rhedeg, rydym yn rhedeg mewn o fawr o log n amser, fel petai. 

Yn awr mae hyn yn arwyddocaol, oherwydd galw i gof yr hyn yr amseroedd yn rhedeg yn gyda'r math swigod, a dethol didoli, a didoli mewnosod, a hyd yn oed ychydig o bobl eraill sy'n bodoli, n sgwâr oedd lle yr oeddem yn. A gallwch, math o, yn gweld hyn yma. Os yw n sgwâr yn amlwg n amserau n, ond yma rydym wedi n amserau log n, ac yr ydym eisoes yn gwybod o wythnos sero, hynny log n, y logarithmig, yn well na rhywbeth llinol. Wedi'r cyfan, yn dwyn i gof y llun gyda'r coch a melyn ac mae'r llinellau gwyrdd oedd yn tynnu ni, y llinell logarithmig gwyrdd yn llawer is. Ac am hynny, yn llawer gwell ac yn gyflymach na'r llinellau melyn a choch yn syth, n amseroedd log n yw, yn wir, yn well na amserau n n, neu n sgwario. 

Felly, rydym yn ymddangos i gael nodwyd yn uno algorithm didoli sy'n rhedeg yn llawer amser yn gyflymach, ac yn wir, dyna pam, yn gynharach yr wythnos hon, pan fydd gwelsom fod cystadleuaeth rhwng swigen didoli, trefnu dethol, ac yn uno didoli, yn uno fath mewn gwirionedd, enillodd mewn gwirionedd. Ac yn wir, doedden ni ddim hyd yn oed yn aros ar gyfer y math swigen a didoli dethol i orffen. 

Nawr, gadewch i ni gymryd un tocyn arall ar hyn, o ychydig yn fwy persbectif ffurfiol, dim ond mewn achos, mae hyn yn atseinio yn well na'r drafodaeth ar lefel uwch. Felly dyma y algorithm eto. Gadewch i ni ofyn i ni'n hunain, yr hyn y mae'r amser yn rhedeg yw o hyn algorithmau gwahanol gamau? Gadewch i ni rannu yn y cyntaf achos a'r ail achos. Mae'r IF a'r ARALL Yn achos OS, OS n yn llai na 2, dim ond yn dychwelyd. Teimlo fel amser yn gyson. Mae'n, math o, fel dau gam, OS n yn llai na 2, ac yna dychwelyd. Ond fel y dywedasom ar ddydd Llun, amser cyson, neu fawr o o 1, gall fod dau gam, tri grisiau, hyd yn oed 1,000 o gamau. Yr hyn sy'n bwysig yw ei fod yn nifer cyson o gamau. Felly amlygodd y melyn pseudocode yma yn rhedeg i mewn, byddwn yn ei alw, amser yn gyson. Felly fwy ffurfiol, a rydym yn mynd i'r canlynol-- hwn fydd y graddau yr ydym ffurfioli hyn hawl now-- T n, yr amser yn rhedeg o broblem sy'n cymryd somethings n fel mewnbwn, yn hafal i fawr o un, OS n yn llai na 2. Felly mae'n amodol ar hynny. Felly, er mwyn bod yn glir, OS n yn llai na 2, mae gennym restr fer iawn, yna yr amser yn rhedeg, T n, lle mae n yn 1 neu 0, yn yr achos penodol iawn, dim ond ei fod yn mynd i fod yn amser yn gyson. Mae'n mynd i gymryd un cam, dau gam, beth bynnag. Mae'n nifer penodol o gamau. 

Felly mae'n rhaid i'r rhan juicy yn sicr yn yr achos arall yn y pseudocode. Mae'r achos ARALL. Trefnu yn hanner chwith o elfennau, math cywir hanner o elfennau, uno haneri didoli. Pa mor hir y pob un o'r camau hynny eu cymryd? Wel, os y gwaith o redeg amser i ddatrys elfennau n yw, gadewch i ni alw yn iawn yn gyffredinol, T n, Yna, didoli y chwith hanner yr elfennau yw, math o, fel dweud, T o n rannu â 2, ac yn yr un modd didoli yr hanner cywir o elfennau yw, math o, fel dweud, T n wedi'i rannu 2, ac yna cyfuno'r haneri didoli. Wel, os wyf wedi cael rhai nifer o elfennau yma, fel pedwar, ac mae rhai rhif o elfennau yma, fel bedwar, ac mae'n rhaid i mi uno pob un o'r pedwar hyn i mewn, ac mae pob un o'r rhain pedwar mewn, un ar ôl y llall, fel bod yn y pen draw Mae gen i wyth elfen. Mae'n teimlo fel mae hynny'n fawr o o gamau n? Os gen n bysedd a phob un o'r ohonynt gael eu cyfuno i mewn lle, dyna fel grisiau arall n. 

Felly yn wir formulaically, gallwn fynegi hyn, er yn ychydig o brawychus ar y dechrau yr olwg, ond mae'n rhywbeth sy'n dal yn union y rhesymeg. Mae'r amser rhedeg, T n, OS n yn fwy na neu'n hafal i 2. Yn yr achos hwn, mae'r achos ARALL, mae T n wedi'i rannu â 2, yn ogystal â T n rannu â 2, fantais fawr o o n, mae rhai Nifer llinol o gamau, efallai yn union n, efallai 2 waith n, ond mae'n fras, trefn n. Fel bod, hefyd, yw sut y gallwn yn mynegi hyn formulaically. Nawr fyddech chi ddim yn gwybod hyn oni bai rydych wedi ei gofnodi yn eich meddwl, neu yn edrych i fyny yn y cefn gwerslyfr, bod gallai fod ychydig yn twyllo daflen ar y diwedd, ond mae hyn yn, yn wir, yn mynd i rhoi i ni yn fawr o o n log n, oherwydd bod y digwydd eto y ydych yn gweld yma ar y sgrin, os ydych mewn gwirionedd yn gwneud hynny allan, gyda nifer anfeidrol o enghreifftiau, neu y gwnaethoch hynny formulaically, byddech gweld bod hyn, oherwydd fformiwla hon ei hun yn recursive, gyda t o n dros rywbeth ar y dde, a t o n drosodd ar y chwith, gall hyn cael eu mynegi mewn gwirionedd, yn y pen draw, Rhowch gynnig mor fawr o n log n. Os na argyhoeddedig, dyna dirwy am y tro, yn unig cymryd ar ffydd, mai dyna, yn wir, yr hyn sy'n digwydd eto yn arwain at, ond mae hyn yn unig yw ychydig yn fwy o dull mathemategol i chwilio ar y pryd yn rhedeg o'r math uno yn seiliedig ar ei pseudocode yn unig. 

Nawr gadewch i ni gymryd dipyn o anadlu o hynny i gyd, ac edrych ar cyn-seneddwr penodol, sy'n Gallai edrych ychydig yn gyfarwydd, oedd yn eistedd i lawr gyda Google Eric Schmidt, beth amser yn ôl, ar gyfer cyfweliad ar y llwyfan, o flaen criw cyfan o bobl, yn siarad yn y pen draw am pwnc, mae hynny'n eithaf cyfarwydd erbyn hyn. Gadewch i ni edrych. 

ERIC SCHMIDT: Nawr Seneddwr, byddwch yma yn Google, ac yr wyf yn hoffi meddwl y llywyddiaeth fel cyfweliad am swydd. Nawr mae'n anodd cael swydd fel llywydd. Arlywydd Obama: Iawn. ERIC SCHMIDT: A ydych yn mynd i wneud [Anghlywadwy] yn awr. Mae hefyd yn anodd cael swydd yn Google. Arlywydd Obama: Iawn. 

ERIC SCHMIDT: Mae gennym gwestiynau, ac rydym yn gofyn ein cwestiynau i ymgeiswyr, ac mae hyn yn un yn dod o Larry Schwimmer. 

Arlywydd Obama: OK. 

ERIC SCHMIDT: Beth? Rydych guys yn meddwl fy mod yn kidding? Mae'n iawn yma. Beth yw'r ffordd fwyaf effeithlon o didoli miliwn 32 bit gyfanrifau? 

Arlywydd Obama: Well-- ERIC SCHMIDT: Weithiau, efallai ddrwg gen i, maybe-- Arlywydd Obama: Na, na, na, na, na, yr wyf yn think-- ERIC SCHMIDT: Dyw hynny ddim yn iddo-- Arlywydd Obama: I yn meddwl, yr wyf yn meddwl y swigen Byddai fath yn y ffordd anghywir i fynd. ERIC SCHMIDT: Dewch ar. A ddywedodd wrtho hwn? IAWN. Doeddwn i ddim y wyddoniaeth gyfrifiadurol on-- 

Arlywydd Obama: Rydym wedi got ein ysbiwyr i mewn 'na. ATHRO: Pob hawl. Gadewch i ni adael y tu ôl i ni yn awr y byd damcaniaethol o algorithmau yn y dadansoddiad asymptotic o hynny, a dychwelyd at rai pynciau o wythnos sero ac un, a dechrau i gael gwared ar rai olwynion hyfforddiant, os mynnwch. Fel eich bod yn wir yn deall yn y pen draw o'r gwaelod i fyny, beth sydd mynd ymlaen o dan y cwfl, pan fyddwch yn ysgrifennu, crynhoi, a gweithredu rhaglenni. Dwyn i gof yn arbennig, bod hyn yn y rhaglen C gyntaf buom yn edrych ar, rhaglen canonaidd, yn syml o ryw fath, yn gymharol siarad, wherein, mae'n printiau, Hello World. Ac cofio imi ddweud, y broses y cod ffynhonnell yn mynd drwy yn union hyn. Byddwch yn cymryd eich cod ffynhonnell, pasio drwy casglwr, fel chlang, ac allan yn dod cod gwrthrych, bod Gallai edrych fel hyn, zeros a rhai bod CPU y cyfrifiadur, canolog uned brosesu neu'r ymennydd, yn y pen draw yn deall. 

Mae'n ymddangos bod hynny'n dipyn o gorsymleiddio, ein bod bellach mewn sefyllfa i pryfocio ar wahân i ddeall yr hyn wedi bod mewn gwirionedd mynd ymlaen o dan y cwfl bob tro y byddwch yn rhedeg Chlang, neu'n fwy cyffredinol, bob tro y byddwch yn gwneud rhaglen, gan ddefnyddio Gwneud a CF 50 IDE. Yn benodol, pethau fel mae hyn yn cael ei gynhyrchu yn gyntaf, pan fyddwch yn llunio eich rhaglen gyntaf. Mewn geiriau eraill, pan fyddwch yn cymryd eich cod ffynhonnell ac yn llunio ei, beth sydd yn gyntaf sy'n cael ei outputted gan chlang yn rhywbeth a elwir yn cod cynulliad. Ac yn wir, mae'n edrych yn union fel hyn. 

Rwy'n rhedeg gorchymyn yn y llinell gorchymyn yn gynharach. Cyfalaf dash chlang s hello.c, ac roedd hyn yn creu ffeil i mi o'r enw hello.s, tu mewn a oedd yn union cynnwys hyn, ac ychydig mwy uchod ac ychydig yn fwy isod, ond rwyf wedi rhoi'r juiciest o wybodaeth yma ar y sgrin. Ac os ydych yn edrych yn ofalus, byddwch yn gweld o leiaf ychydig eiriau allweddol cyfarwydd. Mae gennym brif ar y top. Rydym wedi printf i lawr yn y canol. Ac mae gennym hefyd helo byd slaes n mewn dyfynodau i lawr isod. 

A phopeth arall yn y fan hyn yw cyfarwyddiadau lefel isel iawn bod CPU y cyfrifiadur yn deall. Cyfarwyddiadau CPU sy'n symud cof o gwmpas, y llinynnau llwyth o'r cof, ac yn y pen draw, print pethau ar y sgrin. Nawr beth sy'n digwydd er ar ôl y cod cynulliad yn cael ei gynhyrchu? Yn y pen draw, byddwch yn gwneud, yn wir, dal yn cynhyrchu cod gwrthrych. Ond mae'r camau sydd wedi 'n sylweddol bod yn mynd ymlaen o dan y cwfl edrych ychydig mwy fel hyn. Cod ffynhonnell yn dod yn cod cynulliad, sydd wedyn yn dod cod gwrthrych, ac mae'r geiriau gweithredol yma yw bod, pan fyddwch yn llunio eich cod ffynhonnell, allan yn dod cod cynulliad, ac yna pan fyddwch yn ymgynnull eich cod cynulliad, allan yn dod cod gwrthrych. 

Nawr chlang yn super soffistigedig, fel llawer o crynoadyddion, ac mae'n gwneud pob un o'r camau hyn gyda'i gilydd, ac mae'n ei wneud yw o reidrwydd allbwn unrhyw canolradd ffeiliau a gallwch hyd yn oed weld. 'I jyst yn llunio pethau, sef y term cyffredinol bod disgrifio'r broses gyfan hon. Ond os ydych wir eisiau i fod yn benodol, mae llawer yn digwydd mwy ar yno yn ogystal. 

Ond gadewch i ni hefyd yn ystyried bod hyd yn oed yn awr y rhaglen honno super syml, hello.c, Gelwir swyddogaeth. Fe'i gelwir printf. Ond doeddwn i ddim yn ysgrifennu printf, yn wir, sy'n dod gyda c, fel petai. Mae'n dwyn i gof swyddogaeth sy'n ddatgan yn io.h safonol, sydd yn ffeil header, a oedd yn yn bwnc yr ydym fe mewn gwirionedd plymio i mewn mwy o ddyfnder cyn bo hir. Ond ffeil pennawd yn cyd-fynd fel arfer gan ffeil cod, ffynhonnell ffeil cod, felly yn debyg iawn yno io.h. safonol yn bodoli 

Rhywbryd yn ôl, rhywun, neu someones, hefyd yn ysgrifennu ffeil o'r enw io.c safonol, yn y mae'r diffiniadau go iawn, neu gweithrediadau o printf, a sypiau o swyddogaethau eraill, yn cael eu hysgrifennu mewn gwirionedd. Felly o gofio bod, os ydym yn ystyried cael yma ar y chwith, hello.c, pan llunio, yn rhoi i ni hello.s, hyd yn oed os Nid yw chlang yn trafferthu cynilo mewn lle gallwn ei weld, a bod y cod cynulliad yn cael ei ymgynnull i mewn i hello.o, a oedd yn yw, yn wir, yr enw diofyn Rhoddir pryd bynnag y byddwch yn llunio ffynhonnell cod i mewn cod gwrthrych, ond nid ydynt yn yn barod i weithredu eto, gan fod cam arall rhaid i hyn ddigwydd, ac mae ganddo bod yn digwydd am yr ychydig diwethaf wythnosau, efallai unbeknownst i chi. 

Yn benodol rhywle yn CS50 IDE, ac mae hyn, hefyd, yn dipyn o gorsymleiddio am eiliad, mae, neu yr oedd ar un adeg, ffeil o'r enw io.c safonol, bod rhywun grynhoi mewn io.s safonol neu gyfwerth, bod rhywun wedyn yn ymgynnull i mewn i io.o safonol, neu ei fod yn troi allan i fod yn ychydig yn wahanol ffeil fformat all gael gwahanol ffeil estyniad yn gyfan gwbl, ond yn ddamcaniaethol ac yn gysyniadol, yn union Roedd y camau hynny i ddigwydd ar ryw ffurf. Pa un yw dweud, bod bellach pan dwi'n ysgrifennu rhaglen, hello.c, mai dim ond yn dweud, helo byd, ac rwy'n ei ddefnyddio cod rhywun arall fel printf, a fu unwaith ar un amser, mewn ffeil o'r enw io.c safonol, Yna, rhywsut rhaid i mi gymryd fy cod gwrthrych, fy zeros a rhai, a gwrthrych y person hwnnw cod, neu sero a rhai, a rhywsut eu cysylltu â'i gilydd i mewn i un ffeil terfynol, a elwir helo, bod Mae gan bob un o'r sero a rhai o fy mhrif swyddogaeth, a phob un o'r sero a rhai ar gyfer printf. 

Ac yn wir, y broses olaf yn Gelwir, gan gysylltu eich cod gwrthrych. Mae'r allbwn o'r rhain hon ar ffurf ffeil weithredadwy. Felly er tegwch, yn y ddiwedd y dydd, dim byd wedi newid ers wythnos un, pan fyddwn yn ddechreuais llunio rhaglenni. Yn wir, mae hyn oll wedi bod yn yn digwydd o dan y cwfl, ond yn awr rydym yn mewn sefyllfa lle y gallwn mewn gwirionedd canfod ar wahân amrywiol hyn gamau. Ac yn wir, ar y diwedd y dydd, rydym yn dal i gadael gyda zeros a rhai, a oedd yn mewn gwirionedd yn segue mawr yn awr i allu arall o C, bod nid ydym wedi gorfod trosoledd mwyaf tebygol hyd yn hyn, a elwir yn weithredwyr bitwise. Mewn geiriau eraill, hyd yn hyn, unrhyw bryd rydym wedi ymdrin â data yn C neu newidynnau yn C, rydym wedi cael pethau fel chars a fflotiau a ins ac ysu a dyblau ac yn y blaen, ond pob un o'r rheini o leiaf wyth did. Nid ydym erioed wedi bod yn gallu eto trin darnau unigol, er bod un darn unigol, rydym yn gwybod, gall gynrychioli 0 a 1. Nawr mae'n ymddangos fod yn C, yr ydych yn gallu cael gafael ar ddarnau unigol, os ydych yn gwybod y gystrawen, i fynd arnynt â hwy. 

Felly, gadewch i ni edrych at weithredwyr bitwise. Felly y llun dyma rai symbolau sy'n rydym wedi, math o, math o, weld o'r blaen. Rwy'n gweld ampersand, a fertigol bar, a rhai eraill yn ogystal, ac yn dwyn i gof bod ampersand ampersand yn rhywbeth yr ydym wedi ei weld o'r blaen. Mae'r gweithredwr rhesymegol A, lle mae gennych dau ohonynt gyda'i gilydd, neu yr rhesymegol NEU gweithredydd, lle rydych yn gael dau far fertigol. Gweithredwyr bitwise, yr ydym chi helpu gweld gweithredu ar ddarnau unigol, dim ond yn defnyddio ampersand sengl, sengl bar fertigol, y symbol lleolnod dod nesaf, yr ychydig tilde, ac yna i'r chwith bachyn chwith braced, neu bachyn dde bachyn dde. Mae pob un o'r rhain wahanol ystyron. 

Yn wir, gadewch i ni edrych. Gadewch i ni fynd hen ysgol heddiw, a defnydd sgrîn gyffwrdd rhag fu, a elwir fel bwrdd gwyn. Ac mae hyn yn bwrdd gwyn yn mynd i ganiatáu i ni i fynegi rhai symbolau gweddol syml, neu yn hytrach rhai fformiwlâu gweddol syml, y gallwn wedyn yn y pen draw trosoledd, er mwyn i gael mynediad at unigolyn darnau o fewn rhaglen C. Mewn geiriau eraill, gadewch i ni wneud hyn. Gadewch i ni siarad gyntaf am foment am ampersand, sef y bitwise A gweithredwr. Mewn geiriau eraill, mae hyn yn gweithredydd sy'n caniatáu mi gael newidyn chwith yn nodweddiadol, ac newidyn dde, neu gwerth unigol, os ydym AC nhw at ei gilydd, yn rhoi canlyniad terfynol i mi. Felly, beth ddylwn i ei olygu? Os mewn rhaglen, mae gennych newidyn bod storfeydd un o'r gwerthoedd hyn, neu gadewch i ni gadw'n syml, a dim ond ysgrifennu seroau a rhai yn unigol, dyma sut mae'r gweithredwr ampersand yn gweithio. 0 ampersand 0 yn mynd i fod yn gyfartal 0. Nawr, pam hynny? 

Mae'n debyg iawn i Ymadroddion boolean, ein bod wedi trafod hyd yn hyn. Os ydych yn credu wedi'r cyfan, mae'r 0 yw ffug, 0 yn ffug, ffug a ffug yw, fel yr ydym wedi ei drafod rhesymegol, hefyd yn ffug. Felly rydym yn cael 0 yma hefyd. Os ydych yn cymryd 0 ampersand 1, yn dda bod, hefyd, yn mynd i fod yn 0, oherwydd ar gyfer hyn mynegiant chwith i fod yn wir neu 1, byddai angen iddo fod yn wir ac yn wir. Ond yma mae gennym ffug ac yn wir, neu 0 ac 1. Yn awr eto, os oes gennym 1 ampersand 0, hynny, hefyd, yn mynd i fod 0, ac os oes gennym 1 ampersand 1, o'r diwedd oes gennym dipyn 1. Felly, mewn geiriau eraill, nid ydym yn ei wneud unrhyw beth diddorol gyda gweithredwr hon eto, gweithredwr ampersand hwn. Mae'n y bitwise A gweithredwr. Ond mae'r rhain yn y cynhwysion drwy y gallwn ei wneud bethau diddorol, fel y byddwn yn fuan yn gweld. 

Nawr, gadewch i ni edrych ar yr union sengl bar fertigol dros yma ar y dde. Os oes gennyf 0 bit ac yr wyf yn NEU 'i ag, mae'r bitwise NEU gweithredwr, 0 bit arall, mae hynny'n mynd i roi i mi 0. Os byddaf yn cymryd ychydig ac mae'n OR 0 gyda ychydig 1, yna dwi'n mynd i gael 1. Ac yn wir, dim ond ar gyfer eglurder, gad i mi fynd yn ôl, fel bod fy bariau fertigol Nid oes camgymryd am 1 yn. Gadewch i mi ailysgrifennu'r holl fy 1 ychydig yn fwy yn glir, fel ein bod yn nesaf yn gweld, os wyf yn wedi i 1 NEU 0, mae hynny'n mynd i fod yn 1, ac os oes gennyf 1 NEU 1 sydd, hefyd, yn mynd i fod yn 1. Fel y gallwch weld yn rhesymegol bod y OR gweithredwr ymddwyn yn wahanol iawn. Mae hyn yn rhoi i mi 0 NEU 0 rhoi i mi 0, ond pob cyfuniad arall yn rhoi i mi 1. Cyn belled â gen i un 1 yn y fformiwla, y canlyniad yn mynd i fod 1. 

Mewn cyferbyniad â'r AND gweithredydd, mae'r ampersand, Dim ond os oes gen i ddau 1 yn y hafaliad, peidiwch Fi 'n weithredol yn cael allan 1. Nawr mae rhai eraill gweithredwyr hefyd. Mae un ohonynt yn ychydig mwy o ran. Felly gadewch i mi fynd yn ei flaen ac yn dileu hwn i ryddhau rhywfaint o le. A gadewch i ni edrych ar yr symbol caret, am ddim ond eiliad. Mae hyn yn nodweddiadol yn cymeriad gallwch deipio ar eich Shift daliad bysellfwrdd a Yna, un o'r rhifau ar ben eich Unol Daleithiau bysellfwrdd. 

Felly dyma'r unig NEU gweithredwr, unigryw OR. Felly rydym yn unig yn gweld y gweithredwr OR. Mae hyn yn y unigryw OR gweithredwr. Beth sydd mewn gwirionedd yw'r gwahaniaeth? Wel gadewch i ni dim ond yn edrych ar y fformiwla, a defnyddio hyn fel cynhwysion yn y pen draw. 0 XOR 0. Rydw i'n mynd i ddweud yw 0 bob amser. Dyna y diffiniad o XOR. 0 XOR 1 yn mynd i fod 1. 1 XOR 0 yn mynd i fod yn 1, ac 1 XOR 1 yn mynd i fod? Anghywir? Neu iawn? Nid wyf yn gwybod. 0. Nawr yr hyn sy'n digwydd yma? Wel meddwl am y enw gweithredwr hwn. Unigryw OR, felly wrth i'r enw, math o, yn awgrymu, yr ateb yn unig yn mynd i fod o 1 os yw'r mewnbynnau yn unigryw, yn wahanol yn unig. Felly dyma mewnbynnau yw'r un fath, felly mae'r allbwn yn 0. Yma mae'r mewnbynnau yw'r un fath, felly mae'r allbwn yn 0. Dyma'r allbynnau yn wahanol, maent yn yn unigryw, ac felly mae'r allbwn yn 1. Felly mae'n debyg iawn i A, mae'n debyg iawn, neu yn hytrach ei fod yn debyg iawn i NEU, ond dim ond mewn ffordd unigryw. Mwyach Mae hyn yn un yn 1, gan fod gennym ddau 1 yn, ac nid yn gyfan gwbl, dim ond un ohonynt. Iawn. Beth am y lleill? Wel y tilde, yn y cyfamser, mae mewn gwirionedd yn neis ac yn syml, diolch byth. Ac mae hwn yn unary gweithredydd, sy'n golygu mae'n berthnasol i dim ond un mewnbwn, un operand, fel petai. Nid i chwith a dde. Mewn geiriau eraill, os ydych yn cymryd tilde o 0, bydd yr ateb yn y gwrthwyneb. Ac os ydych yn cymryd tilde o 1, mae'r Bydd ateb fydd y gwrthwyneb. Felly mae'r gweithredydd tilde yn ffordd o negyddu'r ychydig, neu flipping ychydig o 0-1, neu 1-0. 

Ac mae hynny'n ein gadael yn olaf gyda dim ond dau gweithredwyr terfynol, yr hyn a elwir sifft chwith, a'r hyn a elwir gweithredwr shifft gywir. Gadewch i ni edrych ar sut y mae'r rhai y gwaith. Mae'r gweithredwr sifft chwith, a ysgrifennwyd gyda dau cromfachau ongl fel 'na, yn gweithredu fel a ganlyn. Os bydd fy mewnbwn, neu fy operand, i'r chwith gweithredwr sifft yn eithaf syml 1. Ac yr wyf wedyn yn dweud wrth y cyfrifiadur i Gadawodd sifft bod 1, dywedwch saith o leoedd, y canlyniad yw fel pe bawn cymryd bod 1, a'i symud saith o leoedd draw i'r chwith, ac at ball, rydym yn mynd i gymryd yn ganiataol y y gofod ar y dde yn mynd i gael ei padded gyda sero. Mewn geiriau eraill, 1 gadawodd sifft 7 yn mynd i roi i mi bod 1, wedi'i ddilyn gan 1, 2, 3, 4, 5, 6, 7 sero. Felly, mewn ffordd, mae'n eich galluogi i gymryd nifer bach fel 1, ac yn gwneud yn glir ei fod yn llawer llawer, llawer mwy yn y ffordd hon, ond rydym yn wir yn mynd i weld dulliau mwy glyfar ar ei gyfer yn lle hynny, yn ogystal, 

Iawn. Dyna ni am wythnos tri. Byddwn yn gweld y tro nesaf i chi. Roedd hyn yn CS50. 

[CHWARAE CERDDORIAETH] 

SIARADWR 1: Yr oedd ar y byrbryd bar bwyta Syndi cyffug poeth. Roedd ganddo ei fod i gyd dros ei wyneb. Mae'n gwisgo y siocled fel barf SIARADWR 2: Beth ydych chi'n ei wneud? SIARADWR 3: Hmmm? Beth? 

SIARADWR 2: Oeddech chi'n jyst dip dwbl? Rydych dwbl trochi y sglodion. SIARADWR 3: Esgusodwch fi. SIARADWR 2: Rydych gostwng y sglodion, yr ydych Cymerodd brathiad, ac rydych yn gostwng eto. SIARADWR 3: SIARADWR 2: Felly dyna fel rhoi eich hawl ceg cyfan yn y pant. Y tro nesaf byddwch yn cymryd sglodion, jyst dipio unwaith, ac yn y pen iddo. 

SIARADWR 3: Rydych yn gwybod beth, Dan? Rydych dip y ffordd yr ydych am ei dipio. 'N annhymerus' trochi y ffordd yr wyf am ei dipio.