1 00:00:00,000 --> 00:00:11,904 >> [CHWARAE CERDDORIAETH] 2 00:00:11,904 --> 00:00:12,910 >> ATHRO: Pob hawl. 3 00:00:12,910 --> 00:00:16,730 Mae hyn yn CS50 ac mae hyn yn diwedd yr wythnos tri. 4 00:00:16,730 --> 00:00:20,230 Felly rydym ni yma heddiw, nid yn Sanders Theater, yn lle hynny yn Llyfrgell Weidner. 5 00:00:20,230 --> 00:00:23,170 Y tu mewn ohonynt yn stiwdio a elwir yn Hauser Studio, 6 00:00:23,170 --> 00:00:28,310 neu byddwn yn dweud Stiwdio H, neu bydd rydym say-- os ydych yn mwynhau y jôc, 7 00:00:28,310 --> 00:00:30,540 'i' mewn gwirionedd o classmate, Mark, ar-lein, 8 00:00:30,540 --> 00:00:32,420 a awgrymodd gymaint drwy Twitter. 9 00:00:32,420 --> 00:00:34,270 Nawr beth cŵl am bod yma mewn stiwdio 10 00:00:34,270 --> 00:00:38,410 yw fy mod i'n amgylchynu gan y rhain gwyrdd waliau, sgrin gwyrdd neu chromakey, 11 00:00:38,410 --> 00:00:43,290 fel petai, sy'n golygu bod CS50 yn tîm cynhyrchu, unbeknownst i mi 12 00:00:43,290 --> 00:00:47,380 ar hyn o bryd, gallai fod yn rhoi mi y rhan fwyaf o unrhyw le yn y byd, 13 00:00:47,380 --> 00:00:48,660 er gwell neu er gwaeth. 14 00:00:48,660 --> 00:00:51,800 >> Nawr beth sydd o'n blaen, problem a osodwyd dau yn eich dwylo chi am yr wythnos hon, 15 00:00:51,800 --> 00:00:53,830 ond gyda phroblem a osodwyd tair wythnos hon sydd i ddod, 16 00:00:53,830 --> 00:00:56,600 byddwch yn cael eich herio gyda y gêm yn hyn a elwir o 15, 17 00:00:56,600 --> 00:00:58,960 hen blaid blaid sydd efallai y byddwch yn cofio derbyn 18 00:00:58,960 --> 00:01:02,030 fel plentyn sydd â criw cyfan o rifau sy'n gallu llithro i fyny, i lawr, 19 00:01:02,030 --> 00:01:05,790 chwith ac i'r dde, ac mae un bwlch o fewn y pos, i mewn yr ydych 20 00:01:05,790 --> 00:01:07,840 Gall gwirionedd sleid darnau pos hynny. 21 00:01:07,840 --> 00:01:11,150 Yn y pen draw byddwch yn derbyn hyn bendroni mewn rhyw drefn lled hap, 22 00:01:11,150 --> 00:01:12,940 a'r nod yw datrys y mater, top i'r gwaelod, 23 00:01:12,940 --> 00:01:16,310 o'r chwith i'r dde, o un yr holl ffordd i fyny drwy'r 15. 24 00:01:16,310 --> 00:01:19,360 >> Yn anffodus, mae'r gweithredu bydd gennych wrth law 25 00:01:19,360 --> 00:01:21,590 yn mynd i fod meddalwedd seiliedig ar waith, nid yn gorfforol. 26 00:01:21,590 --> 00:01:25,280 Rydych yn wir yn mynd i gael i ysgrifennu Cod â hwy can myfyrwyr neu ddefnyddiwr 27 00:01:25,280 --> 00:01:26,760 chwarae'r gêm o 15. 28 00:01:26,760 --> 00:01:29,030 Ac yn wir, yn y haciwr rhifyn o gêm o 15, 29 00:01:29,030 --> 00:01:32,155 byddwch yn her i weithredu, nid dim ond chwarae hen ysgol hon 30 00:01:32,155 --> 00:01:35,010 gêm, ond yn hytrach y datrys ohono, gweithredu dull duw, 31 00:01:35,010 --> 00:01:38,280 fel petai, sydd mewn gwirionedd datrys y pos ar gyfer y bobl, 32 00:01:38,280 --> 00:01:41,080 trwy roi iddynt awgrym, ar ôl awgrym, ar ôl awgrym. 33 00:01:41,080 --> 00:01:42,280 Felly mwy am hynny yr wythnos nesaf. 34 00:01:42,280 --> 00:01:43,720 Ond dyna beth o'n blaenau. 35 00:01:43,720 --> 00:01:47,610 >> Am y tro dwyn i gof bod yn gynharach yr wythnos hon cawsom Cliffhanger hwn, os gwnewch, 36 00:01:47,610 --> 00:01:52,560 lle y gorau oeddem yn ei wneud didoli doeth yn uchaf yn rhwymo o fawr o o n 37 00:01:52,560 --> 00:01:53,210 sgwâr. 38 00:01:53,210 --> 00:01:56,520 Mewn geiriau eraill, didoli swigen, didoli dewis, didoli mewnosod, 39 00:01:56,520 --> 00:01:59,120 pob un ohonynt, er bod gwahanol yn eu rhoi ar waith, 40 00:01:59,120 --> 00:02:03,480 ddatganoli i mewn i n sgwâr yn rhedeg amser yn yr achos gwaethaf iawn. 41 00:02:03,480 --> 00:02:06,010 Ac rydym yn gyffredinol yn cymryd yn ganiataol bod yr achos gwaethaf iawn ar gyfer didoli 42 00:02:06,010 --> 00:02:08,814 yn un sy'n eich mewnbynnau yn gwbl ôl. 43 00:02:08,814 --> 00:02:11,980 Ac yn wir, fe gymerodd dipyn o ychydig gamau i weithredu pob un o'r algorithmau hynny. 44 00:02:11,980 --> 00:02:15,110 >> Nawr ar ddiwedd y dosbarth galw i gof, rydym yn cymharu fath swigen 45 00:02:15,110 --> 00:02:19,390 yn erbyn didoli detholiad yn erbyn un arall ein bod yn elwir math uno ar y pryd, 46 00:02:19,390 --> 00:02:22,120 a chynigiaf ei fod yn cymryd mantais o wers o wythnos 47 00:02:22,120 --> 00:02:24,060 sero, rhaniad a gorchfygu. 48 00:02:24,060 --> 00:02:28,810 A rhywsut cyflawni rhyw fath o logarithmig rhedeg amser yn y pen draw, 49 00:02:28,810 --> 00:02:31,024 yn hytrach na rywbeth mae hynny'n cwadratig yn unig. 50 00:02:31,024 --> 00:02:33,440 Ac nid mae'n eithaf logarithmig, mae'n ychydig yn fwy na hynny. 51 00:02:33,440 --> 00:02:36,520 Ond os ydych yn cofio o'r dosbarth, yr oedd yn llawer, llawer cyflymach. 52 00:02:36,520 --> 00:02:38,210 Gadewch i ni edrych ar lle yr ydym yn gadael i ffwrdd. 53 00:02:38,210 --> 00:02:41,880 54 00:02:41,880 --> 00:02:45,370 >> Didoli swigen yn erbyn dewis didoli yn erbyn uno fath. 55 00:02:45,370 --> 00:02:47,700 Erbyn hyn maen nhw i gyd yn rhedeg, yn theori, ar yr un pryd. 56 00:02:47,700 --> 00:02:50,510 Mae'r CPU yn rhedeg ar yr un cyflymder. 57 00:02:50,510 --> 00:02:54,990 Ond gallwch deimlo pa mor ddiflas hwn yn gyflym iawn yn mynd i ddod yn, 58 00:02:54,990 --> 00:02:58,790 ac yn union pa mor gyflym, pan fyddwn yn chwistrellu ychydig o algorithmau wythnos sero, yn 59 00:02:58,790 --> 00:03:00,080 gallwn gyflymu pethau. 60 00:03:00,080 --> 00:03:01,630 >> Felly fath marc yn edrych yn anhygoel. 61 00:03:01,630 --> 00:03:05,220 Sut y gallwn trosoledd hynny, er mwyn i ddidoli rhifau yn gyflymach. 62 00:03:05,220 --> 00:03:07,140 Wel gadewch i ni feddwl yn ôl i cynhwysyn ein bod yn 63 00:03:07,140 --> 00:03:10,380 Roedd yn ôl yn wythnos sero, sef chwilio am rywun mewn llyfr ffôn, 64 00:03:10,380 --> 00:03:12,380 a dwyn i gof bod y pseudocode a gynigiwyd i ni, 65 00:03:12,380 --> 00:03:14,560 drwy y gallwn ddod o hyd i rhywun fel Mike Smith, 66 00:03:14,560 --> 00:03:16,310 yn edrych rhywbeth bach fel hyn. 67 00:03:16,310 --> 00:03:20,820 >> Nawr cymerwch olwg yn arbennig yn llinell 7 ac 8, a 10 a 11, 68 00:03:20,820 --> 00:03:25,240 sy'n cymell y ddolen, lle yr ydym yn cadw mynd yn ôl i linell 3 eto, ac unwaith eto, 69 00:03:25,240 --> 00:03:26,520 ar ôl tro. 70 00:03:26,520 --> 00:03:31,790 Ond mae'n troi allan ein bod yn gallu gweld algorithm hwn, yma yn pseudocode, 71 00:03:31,790 --> 00:03:33,620 ychydig yn fwy cyfannol. 72 00:03:33,620 --> 00:03:35,960 Yn wir, yr hyn yr wyf i'n edrych yn fan ar y sgrin, 73 00:03:35,960 --> 00:03:41,180 yn algorithm ar gyfer chwilio am Mike Smith ymysg rhai set o dudalennau. 74 00:03:41,180 --> 00:03:45,520 Ac yn wir, gallem symleiddio hyn algorithm yn y llinellau hynny 7 ac 8, 75 00:03:45,520 --> 00:03:49,860 a 10 a 11 i ddim ond dweud hyn, yr wyf wedi cyflwyno yma mewn melyn. 76 00:03:49,860 --> 00:03:52,210 Mewn geiriau eraill, os yw Mike Smith yn gynharach yn y llyfr, 77 00:03:52,210 --> 00:03:55,004 Nid oes angen i ni nodi cam wrth gam yn awr sut i fynd o hyd iddo. 78 00:03:55,004 --> 00:03:56,920 Nid oes rhaid i ni bennu i fynd yn ôl i'r llinell 3, 79 00:03:56,920 --> 00:03:58,960 pam nad ydym yn unig yn lle hynny, dyweder, yn fwy cyffredinol, 80 00:03:58,960 --> 00:04:01,500 chwilio am Mike yn y chwith hanner y llyfr. 81 00:04:01,500 --> 00:04:03,960 >> I'r gwrthwyneb, os Mike yn mewn gwirionedd yn nes ymlaen yn y llyfr, 82 00:04:03,960 --> 00:04:07,540 pam nad ydym yn unig dyfynnu chwilio unquote i Mike yn hanner dde o'r llyfr. 83 00:04:07,540 --> 00:04:11,030 Mewn geiriau eraill, pam na wnewch rydym yn unig fath o punt i ni ein hunain gan ddweud, 84 00:04:11,030 --> 00:04:13,130 chwilio am Mike yn hyn is-set o'r llyfr, 85 00:04:13,130 --> 00:04:16,279 a'i adael i'n presennol algorithm i ddweud wrthym 86 00:04:16,279 --> 00:04:18,750 sut i chwilio am Mike yn fod hanner chwith y llyfr. 87 00:04:18,750 --> 00:04:20,750 Mewn geiriau eraill, mae ein algorithm yn gweithio boed yn 88 00:04:20,750 --> 00:04:24,670 llyfr ffôn o drwch hwn, o hyn trwch, neu unrhyw drwch o gwbl. 89 00:04:24,670 --> 00:04:27,826 Felly allwn recursively diffinio algorithm hwn. 90 00:04:27,826 --> 00:04:29,950 Mewn geiriau eraill, ar y sgrîn yma, yn algorithm 91 00:04:29,950 --> 00:04:33,130 ar gyfer chwilio am Mike Smith ymhlith y tudalennau llyfr ffôn. 92 00:04:33,130 --> 00:04:37,410 Felly, yn unol 7 a 10, gadewch i ni dim ond dweud yn union hynny. 93 00:04:37,410 --> 00:04:40,250 Ac yr wyf yn defnyddio'r term hwn eiliad yn ôl, ac yn wir, recursion 94 00:04:40,250 --> 00:04:42,450 yw'r buzzword am y tro, a 'i' y broses hon 95 00:04:42,450 --> 00:04:47,210 o wneud rhywbeth cylchol gan rhywsut gan ddefnyddio cod sy'n gennych eisoes, 96 00:04:47,210 --> 00:04:49,722 ac yn galw eto, ac unwaith eto, ac unwaith eto. 97 00:04:49,722 --> 00:04:51,930 Nawr mae'n mynd i fod yn bwysig ein bod rywsut gwaelod 98 00:04:51,930 --> 00:04:53,821 allan, ac nid ydynt yn gwneud hynny anfeidrol hir. 99 00:04:53,821 --> 00:04:56,070 Fel arall, rydym yn mynd i rhaid yn wir dolen ddiddiwedd. 100 00:04:56,070 --> 00:04:59,810 Ond gadewch i ni weld os allwn ni gael benthyg y syniad hwn o recursion, yn gwneud rhywbeth eto 101 00:04:59,810 --> 00:05:03,600 ac eto ac eto, i ddatrys y broblem didoli drwy uno 102 00:05:03,600 --> 00:05:05,900 didoli, yn fwy effeithlon. 103 00:05:05,900 --> 00:05:06,970 >> Felly, yr wyf yn rhoi i chi yn uno fath. 104 00:05:06,970 --> 00:05:07,920 Gadewch i ni edrych. 105 00:05:07,920 --> 00:05:10,850 Felly dyma pseudocode, gyda y gallem gweithredu didoli, 106 00:05:10,850 --> 00:05:12,640 gan ddefnyddio algorithm hwn a elwir yn didoli uno. 107 00:05:12,640 --> 00:05:13,880 Ac mae'n eithaf syml hyn. 108 00:05:13,880 --> 00:05:15,940 Ar fewnbwn o elfennau n, mewn geiriau eraill, os ydych yn 109 00:05:15,940 --> 00:05:18,830 Rhoddir n elfennau a rhifau a llythyrau neu beth bynnag yw'r mewnbwn yn, 110 00:05:18,830 --> 00:05:22,430 os ydych yn rhoi elfennau n, os n yn llai na 2, dim ond yn dychwelyd. 111 00:05:22,430 --> 00:05:22,930 Iawn? 112 00:05:22,930 --> 00:05:26,430 Oherwydd os n yn llai na 2, bod yn golygu bod fy rhestr o elfennau 113 00:05:26,430 --> 00:05:30,446 naill ai o faint 0 neu 1, a yn y ddau achos dibwys hynny, 114 00:05:30,446 --> 00:05:31,570 mae'r rhestr eisoes yn cael ei datrys. 115 00:05:31,570 --> 00:05:32,810 Os nad oes rhestr, mae'n datrys. 116 00:05:32,810 --> 00:05:35,185 Ac os oes 'na restr o hyd 1, mae'n amlwg eu didoli. 117 00:05:35,185 --> 00:05:38,280 Felly, dim ond mae angen i'r algorithm 'n sylweddol yn gwneud rhywbeth diddorol, 118 00:05:38,280 --> 00:05:40,870 os bydd gennym ddau neu fwy elfennau a roddwyd i ni. 119 00:05:40,870 --> 00:05:42,440 Felly gadewch i ni edrych ar y hud bryd hynny. 120 00:05:42,440 --> 00:05:47,500 Arall ddatrys y hanner chwith y elfennau, Yna ddatrys yr hanner cywir o elfennau, 121 00:05:47,500 --> 00:05:49,640 Yna uno haneri didoli. 122 00:05:49,640 --> 00:05:52,440 A beth sy'n fath o feddwl plygu yma, yw nad wyf yn ei wneud mewn gwirionedd 123 00:05:52,440 --> 00:05:56,190 ymddangos i wedi dweud wrthych unrhyw beth eto, dde? 124 00:05:56,190 --> 00:05:59,560 Y cyfan yr wyf wedi dweud yn, rhoddir rhestr o n elfennau, didoli yr hanner chwith, 125 00:05:59,560 --> 00:06:01,800 Yna yr hanner dde, ac yna cyfuno'r haneri didoli, 126 00:06:01,800 --> 00:06:03,840 ond ble mae'r saws gyfrinach gwirioneddol? 127 00:06:03,840 --> 00:06:05,260 Ble mae'r algorithm? 128 00:06:05,260 --> 00:06:09,150 Wel mae'n troi allan bod y rhai ddwy linell yn gyntaf, didoli chwith hanner o elfennau, 129 00:06:09,150 --> 00:06:13,970 a math priodol hanner yr elfennau, galwadau recursive, fel petai. 130 00:06:13,970 --> 00:06:16,120 >> Wedi'r cyfan, ar hyn o bwynt mewn amser, mae gen i 131 00:06:16,120 --> 00:06:18,950 algorithm â hwy didoli criw cyfan o elfennau? 132 00:06:18,950 --> 00:06:19,450 Ydw. 133 00:06:19,450 --> 00:06:20,620 Mae'n iawn yma. 134 00:06:20,620 --> 00:06:25,180 Mae'n iawn yma ar y sgrin, ac fel y gallaf ddefnyddio'r un set o risiau 135 00:06:25,180 --> 00:06:28,500 i roi trefn ar yr hanner chwith, ag y gallaf yr hanner cywir. 136 00:06:28,500 --> 00:06:30,420 Ac yn wir, unwaith eto, ac unwaith eto. 137 00:06:30,420 --> 00:06:34,210 Felly rywsut neu'i gilydd, ac rydym annhymerus 'yn fuan gweld hyn, hud a lledrith math uno 138 00:06:34,210 --> 00:06:37,967 wedi'i wreiddio yn y rownd derfynol iawn llinell, gyfuno'r haneri didoli. 139 00:06:37,967 --> 00:06:39,300 Ac mae hynny'n ymddangos yn weddol 'n athrylithgar. 140 00:06:39,300 --> 00:06:41,050 Byddwch yn cymryd dau hanner, a chi, rywsut, uno nhw at ei gilydd, 141 00:06:41,050 --> 00:06:43,260 a byddwn yn gweld hyn diriaethol mewn munud. 142 00:06:43,260 --> 00:06:45,080 >> Ond mae hyn yn algorithm cyflawn. 143 00:06:45,080 --> 00:06:46,640 A gadewch i ni weld yn union pam. 144 00:06:46,640 --> 00:06:50,912 Wel mae'n debyg ein bod yn rhoi y rhain un fath wyth elfen yma ar y sgrin, un 145 00:06:50,912 --> 00:06:53,120 drwy wyth, ond maen nhw'n er mwyn i bob golwg ar hap. 146 00:06:53,120 --> 00:06:55,320 A'r nod dan sylw yw i ddidoli elfennau hyn. 147 00:06:55,320 --> 00:06:58,280 Wel sut gallaf fynd ati i ei wneud gan ddefnyddio, unwaith eto, 148 00:06:58,280 --> 00:07:00,407 uno yn didoli, yn unol pseudocode hwn? 149 00:07:00,407 --> 00:07:02,740 Ac eto, drwytho hyn mewn eich meddwl, am ddim ond eiliad. 150 00:07:02,740 --> 00:07:05,270 Yr achos cyntaf yn eithaf ddibwys, os yw'n llai na 2, 151 00:07:05,270 --> 00:07:07,060 dim ond yn dychwelyd, does dim gwaith i'w wneud o hyd. 152 00:07:07,060 --> 00:07:09,290 Felly mewn gwirionedd does dim ond tri camau i gadw 'n sylweddol mewn golwg. 153 00:07:09,290 --> 00:07:11,081 Unwaith eto, ac unwaith eto, rwy'n mynd i eisiau i gael 154 00:07:11,081 --> 00:07:13,980 i roi trefn ar yr hanner chwith, didoli'r hanner cywir, 155 00:07:13,980 --> 00:07:15,890 ac yna unwaith y bydd eu dau hanner yn cael eu datrys, 156 00:07:15,890 --> 00:07:18,710 Rwyf am i uno gyda'i gilydd i mewn i un rhestr didoli. 157 00:07:18,710 --> 00:07:19,940 Felly cadwch hynny mewn cof. 158 00:07:19,940 --> 00:07:21,310 >> Felly dyma y rhestr wreiddiol. 159 00:07:21,310 --> 00:07:23,510 Gadewch i drin hyn fel array, wrth i ni ddechrau 160 00:07:23,510 --> 00:07:25,800 mewn wythnos dau, sydd yn bloc cyffiniol o gof. 161 00:07:25,800 --> 00:07:28,480 Yn yr achos hwn, sy'n cynnwys wyth rhifau, cefn wrth gefn wrth gefn. 162 00:07:28,480 --> 00:07:30,700 A gadewch i ni yn awr yn berthnasol fath uno. 163 00:07:30,700 --> 00:07:33,300 Felly, yn gyntaf yr wyf am roi trefn hanner chwith y rhestr hon, 164 00:07:33,300 --> 00:07:37,370 a gadewch i ni, felly, canolbwyntio ar 4, 8, 6, a 2. 165 00:07:37,370 --> 00:07:41,000 >> Nawr, sut ydw i'n mynd ati didoli rhestr o faint 4? 166 00:07:41,000 --> 00:07:45,990 Wel rhaid i mi ystyried yn awr didoli ar ochr chwith y hanner chwith. 167 00:07:45,990 --> 00:07:47,720 Unwaith eto, gadewch i ailddirwyn am ddim ond ennyd. 168 00:07:47,720 --> 00:07:51,010 Os bydd y pseudocode yn hyn, ac rwy'n rhoi wyth elfen, 169 00:07:51,010 --> 00:07:53,230 8 yn amlwg yn fwy na neu'n hafal i 2. 170 00:07:53,230 --> 00:07:54,980 Felly, gyda nad yw'r achos cyntaf yn berthnasol. 171 00:07:54,980 --> 00:07:58,120 Felly, i ddidoli wyth elfen, yr wyf yn gyntaf ddatrys y hanner chwith o elfennau, 172 00:07:58,120 --> 00:08:01,930 yna yr wyf didoli'r hanner dde, ac yna yr wyf yn uno y ddau hanner ddidoli, pob un o faint 4. 173 00:08:01,930 --> 00:08:02,470 IAWN. 174 00:08:02,470 --> 00:08:07,480 >> Ond os ydych chi newydd ddweud wrthyf, didoli'r chwith hanner, sydd bellach o faint 4, 175 00:08:07,480 --> 00:08:09,350 sut ydw i'n ddatrys yr hanner ar ôl? 176 00:08:09,350 --> 00:08:11,430 Wel os oes gennyf mewnbwn pedair elfen, 177 00:08:11,430 --> 00:08:14,590 Rwyf yn gyntaf ddatrys y chwith dau, yna bydd y ddau yn iawn, 178 00:08:14,590 --> 00:08:16,210 ac yna rwyf yn uno nhw at ei gilydd. 179 00:08:16,210 --> 00:08:18,700 Felly unwaith eto, mae'n dod yn dipyn o feddwl plygu gêm yma, 180 00:08:18,700 --> 00:08:21,450 oherwydd eich bod, math o, rhaid i cofio ble rydych chi yn y stori, 181 00:08:21,450 --> 00:08:23,620 ond ar ddiwedd y dydd, o ystyried unrhyw nifer o elfennau, 182 00:08:23,620 --> 00:08:25,620 eich bod am y tro cyntaf i ddidoli'r chwith hanner, yna bydd y hanner cywir, 183 00:08:25,620 --> 00:08:26,661 Yna uno nhw at ei gilydd. 184 00:08:26,661 --> 00:08:28,630 Gadewch i ni ddechrau i wneud yn union hynny. 185 00:08:28,630 --> 00:08:30,170 Heres '' r mewnbwn o wyth elfen. 186 00:08:30,170 --> 00:08:31,910 Nawr rydym yn edrych ar yr hanner chwith fan hyn. 187 00:08:31,910 --> 00:08:33,720 Sut ydw i'n trefnu pedair elfen? 188 00:08:33,720 --> 00:08:35,610 Wel cyntaf i mi ddatrys yr hanner chwith. 189 00:08:35,610 --> 00:08:37,720 Nawr, sut ydw i'n ddatrys yr hanner ar ôl? 190 00:08:37,720 --> 00:08:39,419 Wel rydw i wedi ei roi dwy elfen. 191 00:08:39,419 --> 00:08:41,240 Felly gadewch i ni ddatrys y ddwy elfen. 192 00:08:41,240 --> 00:08:44,540 2 yn fwy na neu'n gyfartal i 2, wrth gwrs. 193 00:08:44,540 --> 00:08:46,170 Fel nad yw achos cyntaf yn berthnasol. 194 00:08:46,170 --> 00:08:49,010 >> Felly, rhaid i mi roi trefn ar y chwith bellach hanner y rhain ddwy elfen. 195 00:08:49,010 --> 00:08:50,870 Mae'r hanner chwith, wrth gwrs, yn unig 4. 196 00:08:50,870 --> 00:08:54,020 Felly, sut ydw i'n trefnu rhestr o un elfen? 197 00:08:54,020 --> 00:08:57,960 Wel nawr, bod achos sylfaenol arbennig i fyny top, fel petai, yn berthnasol. 198 00:08:57,960 --> 00:09:01,470 1 yn llai na 2, ac mae fy rhestr hon yn wir o faint 1. 199 00:09:01,470 --> 00:09:02,747 Felly, Fi jyst yn dychwelyd. 200 00:09:02,747 --> 00:09:03,580 Dydw i ddim yn gwneud unrhyw beth. 201 00:09:03,580 --> 00:09:06,770 Ac yn wir, yn edrych ar yr hyn yr wyf i wedi wneud, 4 eisoes yn didoli. 202 00:09:06,770 --> 00:09:09,220 Fel dwi'n barod rhannol lwyddiannus yma. 203 00:09:09,220 --> 00:09:11,750 >> Nawr bod yn ymddangos fath o dwp i hawlio, ond mae'n wir. 204 00:09:11,750 --> 00:09:13,700 4 yn rhestr o faint 1. 205 00:09:13,700 --> 00:09:15,090 Mae eisoes wedi eu didoli. 206 00:09:15,090 --> 00:09:16,270 Dyna yr hanner chwith. 207 00:09:16,270 --> 00:09:18,010 Nawr rwy'n ddatrys yr hanner cywir. 208 00:09:18,010 --> 00:09:22,310 Mae fy mewnbwn yn un elfen, 8 yn yr un modd, eisoes yn didoli. 209 00:09:22,310 --> 00:09:25,170 Stupid, hefyd, ond unwaith eto, yr egwyddor sylfaenol hon 210 00:09:25,170 --> 00:09:28,310 yn mynd i ganiatáu i ni i adeiladu nawr ar ben hyn yn llwyddiannus. 211 00:09:28,310 --> 00:09:32,260 4 didoli, 8 yn cael ei datrys, yn awr beth oedd y cam olaf? 212 00:09:32,260 --> 00:09:35,330 Felly y trydydd a'r olaf cam, unrhyw amser yr ydych yn didoli rhestr, galw i gof, 213 00:09:35,330 --> 00:09:38,310 oedd uno'r ddau hanner, y chwith a'r dde. 214 00:09:38,310 --> 00:09:39,900 Felly, gadewch i ni wneud yn union hynny. 215 00:09:39,900 --> 00:09:41,940 Fy hanner chwith, wrth gwrs, 4. 216 00:09:41,940 --> 00:09:43,310 Fy hanner cywir yw 8. 217 00:09:43,310 --> 00:09:44,100 >> Felly, gadewch i ni wneud hyn. 218 00:09:44,100 --> 00:09:46,410 Yn gyntaf i ddim yn mynd i ddyrannu rhywfaint cof ychwanegol, 219 00:09:46,410 --> 00:09:48,680 y byddaf yn cynrychioli yma, fel dim ond amrywiaeth eilaidd, 220 00:09:48,680 --> 00:09:49,660 mae hynny'n ddigon mawr i ffitio hyn. 221 00:09:49,660 --> 00:09:52,243 Ond gallwch ddychmygu ymestyn y petryal hyd cyfan, 222 00:09:52,243 --> 00:09:53,290 os bydd angen mwy yn nes ymlaen. 223 00:09:53,290 --> 00:09:58,440 Sut ydw i'n cymryd 4 ac 8, ac yn uno y rhai ddwy restr o faint 1 at ei gilydd? 224 00:09:58,440 --> 00:10:00,270 Yma, hefyd, eithaf syml. 225 00:10:00,270 --> 00:10:03,300 4 yn dod yn gyntaf, yna daw 8. 226 00:10:03,300 --> 00:10:07,130 Oherwydd os wyf am i ddatrys y chwith hanner, yna bydd y hanner cywir, 227 00:10:07,130 --> 00:10:09,900 ac yna uno dau hanner y rhai gyda'i gilydd, er mwyn ddidoli, 228 00:10:09,900 --> 00:10:11,940 4 yn dod yn gyntaf, yna daw 8. 229 00:10:11,940 --> 00:10:15,810 >> Felly, rydym yn ymddangos i fod yn gwneud cynnydd, hyd yn oed er nad wyf wedi gwneud unrhyw waith gwirioneddol. 230 00:10:15,810 --> 00:10:17,800 Ond cofiwch lle'r ydym ni yn y stori. 231 00:10:17,800 --> 00:10:19,360 Rydym yn wreiddiol yn cymryd wyth elfen. 232 00:10:19,360 --> 00:10:21,480 Rydym yn datrys yr hanner chwith, sydd 4. 233 00:10:21,480 --> 00:10:24,450 Yna rydym yn datrys yr hanner chwith yr hanner chwith, a oedd yn 2. 234 00:10:24,450 --> 00:10:25,270 A dyma ni yn mynd. 235 00:10:25,270 --> 00:10:26,920 Rydym yn ei wneud gyda y cam hwnnw. 236 00:10:26,920 --> 00:10:29,930 >> Felly, os ydym wedi datrys y Gadawodd hanner 2, yn awr rydym 237 00:10:29,930 --> 00:10:32,130 rhaid i ddatrys yr hanner dde 2. 238 00:10:32,130 --> 00:10:35,710 Felly yr hanner dde 2 yw y ddau gwerthoedd yma, 6 a 2. 239 00:10:35,710 --> 00:10:40,620 Felly, gadewch i ni yn awr yn cymryd mewnbwn o faint 2, a didoli'r hanner chwith, ac yna 240 00:10:40,620 --> 00:10:42,610 yr hanner i'r dde, ac yna uno nhw at ei gilydd. 241 00:10:42,610 --> 00:10:45,722 Wel sut ydw i'n trefnu rhestr o faint 1, yn cynnwys dim ond y rhif 6? 242 00:10:45,722 --> 00:10:46,430 Im 'yn gwneud yn barod. 243 00:10:46,430 --> 00:10:48,680 Bod rhestr o faint 1 yn cael ei datrys. 244 00:10:48,680 --> 00:10:52,140 >> Sut ydw i'n ddatrys rhestr arall o maint 1, yr hanner cywir fel y'u gelwir. 245 00:10:52,140 --> 00:10:54,690 Wel mae'n, hefyd, yn cael ei eisoes didoli. 246 00:10:54,690 --> 00:10:56,190 Mae'r rhif 2 yn unig. 247 00:10:56,190 --> 00:11:00,160 Felly nawr mae gen i ddau hanner, i'r chwith ac iawn, mae angen i mi uno gyda'i gilydd. 248 00:11:00,160 --> 00:11:01,800 Gadewch i mi roi rhywfaint o le ychwanegol fy hun. 249 00:11:01,800 --> 00:11:05,580 A rhowch 2 mewn 'na, Yna 6 mewn 'na, a thrwy hynny 250 00:11:05,580 --> 00:11:10,740 didoli y rhestr honno, i'r chwith ac i'r dde, a chyfuno ei gilydd, yn y pen draw. 251 00:11:10,740 --> 00:11:12,160 Felly rwy'n mewn siâp ychydig yn well. 252 00:11:12,160 --> 00:11:16,250 Dydw i ddim yn ei wneud, oherwydd yn amlwg 4, 8, 2, 6 Nid yw'r archebu olaf yr wyf am. 253 00:11:16,250 --> 00:11:20,640 Ond yr wyf yn awr wedi dwy restr o faint 2, bod ill dau, yn y drefn honno, wedi'u didoli. 254 00:11:20,640 --> 00:11:24,580 Felly nawr os ydych yn ail-ddirwyn yn eich meddwl yn llygad, lle oedd hynny'n ein gadael? 255 00:11:24,580 --> 00:11:28,520 Dechreuais gydag wyth elfen, yna rwyf yn dreulio o dipyn i lawr i hanner chwith 4, 256 00:11:28,520 --> 00:11:31,386 yna bydd y hanner chwith 2, a yna bydd y hanner cywir o 2, 257 00:11:31,386 --> 00:11:34,510 Gorffennais, felly, didoli y chwith hanner 2, ac mae'r hanner cywir o 2, 258 00:11:34,510 --> 00:11:37,800 felly beth yw'r trydydd a'r olaf cam yma? 259 00:11:37,800 --> 00:11:41,290 Mae'n rhaid i mi uno gyda'n gilydd dwy restr o faint 2. 260 00:11:41,290 --> 00:11:42,040 Felly gadewch i ni fynd yn ei flaen. 261 00:11:42,040 --> 00:11:43,940 Ac ar y sgrin yma, yn rhoi m rhyw cof ychwanegol, 262 00:11:43,940 --> 00:11:47,170 er yn dechnegol, yn sylwi fy mod i wedi got criw cyfan o le i fyny top wag 263 00:11:47,170 --> 00:11:47,670 yno. 264 00:11:47,670 --> 00:11:50,044 Os ydw i eisiau i fod yn arbennig gofod effeithlon ddoeth, 265 00:11:50,044 --> 00:11:52,960 Gallai Fi jyst yn dechrau symud yr elfennau yn ôl ac ymlaen, top a gwaelod. 266 00:11:52,960 --> 00:11:55,460 Ond dim ond am eglurder gweledol, Rydw i'n mynd i roi i lawr isod, 267 00:11:55,460 --> 00:11:56,800 i gadw pethau neis ac yn lân. 268 00:11:56,800 --> 00:11:58,150 >> Felly, yr wyf wedi cael dwy restr o faint 2. 269 00:11:58,150 --> 00:11:59,770 Mae'r rhestr gyntaf Mae 4 ac 8. 270 00:11:59,770 --> 00:12:01,500 Mae'r ail restr Mae 2 a 6. 271 00:12:01,500 --> 00:12:03,950 Gadewch i uno rhai at ei gilydd er mwyn didoli. 272 00:12:03,950 --> 00:12:09,910 2, wrth gwrs, yn dod yn gyntaf, Yna, 4, ac yna 6, yna 8. 273 00:12:09,910 --> 00:12:12,560 Ac yn awr rydym yn ymddangos i fod yn ei gael rhywle diddorol. 274 00:12:12,560 --> 00:12:15,720 Hanner Nawr rydw i wedi datrys y rhestru, ac gyd-ddigwyddiad, 'i' 275 00:12:15,720 --> 00:12:18,650 yr holl rifau hyd yn oed, ond bod yw, yn wir, dim ond cyd-ddigwyddiad. 276 00:12:18,650 --> 00:12:22,220 Ac yr wyf yn awr wedi datrys y chwith hanner, fel ei fod yn 2, 4, 6, ac 8. 277 00:12:22,220 --> 00:12:23,430 Nid oes unrhyw beth sydd allan o drefn. 278 00:12:23,430 --> 00:12:24,620 Mae hynny'n teimlo fel gynnydd. 279 00:12:24,620 --> 00:12:26,650 >> Nawr mae'n teimlo fel fy mod i wedi bod yn siarad am byth yn awr, 280 00:12:26,650 --> 00:12:29,850 felly beth rhaid aros i weld os yw hyn algorithm yw, yn wir, yn fwy effeithlon. 281 00:12:29,850 --> 00:12:31,766 Ond rydym yn mynd trwy mae'n super drefnus. 282 00:12:31,766 --> 00:12:34,060 Mae cyfrifiadur, wrth gwrs, Byddai gwneud hynny fel 'na. 283 00:12:34,060 --> 00:12:34,840 Felly, lle rydym ni? 284 00:12:34,840 --> 00:12:36,180 Rydym yn dechrau gyda wyth elfen. 285 00:12:36,180 --> 00:12:37,840 Yr wyf yn datrys yr hanner chwith 4. 286 00:12:37,840 --> 00:12:39,290 Yr wyf yn ymddangos i gael ei wneud â hynny. 287 00:12:39,290 --> 00:12:42,535 Felly, yn awr y cam nesaf yw i didoli hanner dde 4. 288 00:12:42,535 --> 00:12:44,410 Ac mae rhan hon y gallwn fynd drwy ychydig mwy 289 00:12:44,410 --> 00:12:47,140 gyflym, er eich bod chi'n croeso i ailddirwyn neu oedi, dim ond 290 00:12:47,140 --> 00:12:49,910 feddwl drwyddo ar eich cyflymder eich hun, ond beth 291 00:12:49,910 --> 00:12:53,290 gennym yn awr gyfle i wneud yr un peth algorithm union ar bedwar 292 00:12:53,290 --> 00:12:54,380 niferoedd gwahanol. 293 00:12:54,380 --> 00:12:57,740 >> Felly gadewch i ni fynd yn ei flaen, ac yn canolbwyntio ar yr hanner cywir, yr ydym yma. 294 00:12:57,740 --> 00:13:01,260 Mae hanner chwith y hanner i'r dde, ac yn awr y 295 00:13:01,260 --> 00:13:04,560 chwith hanner y chwith hanner y bod hanner cywir, 296 00:13:04,560 --> 00:13:08,030 a sut ydw i'n trefnu rhestr o faint 1 yn cynnwys dim ond y rhif 1? 297 00:13:08,030 --> 00:13:09,030 Mae'n ei wneud yn barod. 298 00:13:09,030 --> 00:13:11,830 Sut ydw i'n gwneud yr un peth am restr o faint 1 sy'n cynnwys dim ond 7? 299 00:13:11,830 --> 00:13:12,840 Mae'n ei wneud yn barod. 300 00:13:12,840 --> 00:13:16,790 Cam tri am hanner hwn, yna yw cyfuno'r ddwy elfen 301 00:13:16,790 --> 00:13:20,889 i mewn i restr newydd o faint 2, 1 a 7. 302 00:13:20,889 --> 00:13:23,180 Peidiwch ymddangos i wedi gwneud popeth bod llawer o waith diddorol. 303 00:13:23,180 --> 00:13:24,346 Gadewch i ni weld beth fydd yn digwydd nesaf. 304 00:13:24,346 --> 00:13:29,210 Fi jyst didoli hanner chwith y hanner dde fy mewnbwn gwreiddiol. 305 00:13:29,210 --> 00:13:32,360 Nawr, gadewch i ddatrys yr hawl hanner, sy'n cynnwys 5 a 3. 306 00:13:32,360 --> 00:13:35,740 Gadewch i ni edrych eto ar y chwith hanner, didoli, hanner cywir, didoli, 307 00:13:35,740 --> 00:13:39,120 ac uno y ddau gyda'i gilydd, i mewn i rai lle ychwanegol, 308 00:13:39,120 --> 00:13:41,670 3 yn dod yn gyntaf, yna daw 5. 309 00:13:41,670 --> 00:13:46,190 Ac felly yn awr, yr ydym wedi datrys y chwith hanner yr hanner cywir 310 00:13:46,190 --> 00:13:49,420 y broblem wreiddiol, ac hanner dde o'r hanner cywir 311 00:13:49,420 --> 00:13:50,800 y broblem wreiddiol. 312 00:13:50,800 --> 00:13:52,480 Beth yw'r trydydd a'r olaf Step? 313 00:13:52,480 --> 00:13:54,854 Wel i uno dau hanner y rheini at ei gilydd. 314 00:13:54,854 --> 00:13:57,020 Felly, gadewch i mi gael fy hun rai gofod ychwanegol, ond, unwaith eto, yr wyf yn 315 00:13:57,020 --> 00:13:58,699 Gallai fod yn defnyddio'r lle i fyny top sbâr. 316 00:13:58,699 --> 00:14:00,490 Ond rydym yn mynd i gadw bethau'n syml ar eu golwg. 317 00:14:00,490 --> 00:14:07,070 Gadewch i mi uno yn awr 1, a Yna, 3, ac yna 5, ac yna 7. 318 00:14:07,070 --> 00:14:10,740 Gan adael i mi yn awr gyda'r hanner dde o'r broblem wreiddiol 319 00:14:10,740 --> 00:14:12,840 sy'n datrys berffaith. 320 00:14:12,840 --> 00:14:13,662 >> Felly beth yn parhau i fod? 321 00:14:13,662 --> 00:14:16,120 Rwy'n teimlo fy mod yn dal i ddweud y un pethau eto, ac unwaith eto, 322 00:14:16,120 --> 00:14:18,700 ond mae hynny'n adlewyrchu ffaith ein bod yn defnyddio recursion. 323 00:14:18,700 --> 00:14:21,050 Mae'r broses o ddefnyddio algorithm eto, ac unwaith eto, 324 00:14:21,050 --> 00:14:23,940 ar is-setiau llai o broblem wreiddiol. 325 00:14:23,940 --> 00:14:27,580 Felly yr wyf bellach wedi i'r chwith didoli hanner y broblem wreiddiol. 326 00:14:27,580 --> 00:14:30,847 Mae gen i hanner ddidoli hawl y broblem wreiddiol. 327 00:14:30,847 --> 00:14:32,180 Beth yw'r trydydd cam a'r olaf? 328 00:14:32,180 --> 00:14:33,590 O, mae'n cyfuno. 329 00:14:33,590 --> 00:14:34,480 Felly, gadewch i ni wneud hynny. 330 00:14:34,480 --> 00:14:36,420 Gadewch i ni ddyrannu rhai ychwanegol cof, ond mae fy duw, rydym yn 331 00:14:36,420 --> 00:14:37,503 gallai roi unrhyw le yn awr. 332 00:14:37,503 --> 00:14:40,356 Mae gennym gymaint o le sydd ar gael i ni, ond byddwn yn cadw pethau'n syml. 333 00:14:40,356 --> 00:14:42,730 Yn hytrach na mynd yn ôl ac allan gyda'n cof gwreiddiol, 334 00:14:42,730 --> 00:14:44,480 gadewch i jyst yn ei wneud yn weledol lawr yma isod, 335 00:14:44,480 --> 00:14:47,240 i orffen i fyny uno'r chwith hanner a hanner cywir. 336 00:14:47,240 --> 00:14:49,279 >> Felly trwy gyfuno, beth sydd angen i mi ei wneud? 337 00:14:49,279 --> 00:14:50,820 Rwyf am gymryd yr elfennau yn eu trefn. 338 00:14:50,820 --> 00:14:53,230 Felly edrych ar yr hanner chwith, Rwy'n gweld y rhif cyntaf yw 2. 339 00:14:53,230 --> 00:14:55,230 Yr wyf yn edrych ar yr hanner cywir, Rwy'n gweld y rhif cyntaf 340 00:14:55,230 --> 00:14:58,290 yw 1, felly mae'n amlwg pa Rhif ydw i am tyn allan, 341 00:14:58,290 --> 00:15:00,430 a rhoi yn gyntaf yn fy rhestr derfynol? 342 00:15:00,430 --> 00:15:01,449 Wrth gwrs, 1. 343 00:15:01,449 --> 00:15:02,990 Nawr rwyf am ofyn bod un cwestiwn. 344 00:15:02,990 --> 00:15:05,040 Ar yr hanner chwith, rwyf wedi yn dal i gael y rhif 2. 345 00:15:05,040 --> 00:15:07,490 Ar yr hanner cywir, Rwyf wedi cael y rhif 3. 346 00:15:07,490 --> 00:15:08,930 Pa un ydw i am ei ddewis? 347 00:15:08,930 --> 00:15:11,760 Wrth gwrs, rhif 2 A bellach yn sylwi ar yr ymgeiswyr 348 00:15:11,760 --> 00:15:13,620 Mae 4 ar y chwith, 3 ar y dde. 349 00:15:13,620 --> 00:15:15,020 Gadewch i ni, wrth gwrs, dewiswch 3. 350 00:15:15,020 --> 00:15:18,020 Nawr bod yr ymgeiswyr yn cael eu 4 ar y chwith, 5 ar y dde. 351 00:15:18,020 --> 00:15:19,460 Yr ydym, wrth gwrs, dewiswch 4. 352 00:15:19,460 --> 00:15:21,240 6 ar y chwith, 5 ar y dde. 353 00:15:21,240 --> 00:15:22,730 Yr ydym, wrth gwrs, dewiswch 5. 354 00:15:22,730 --> 00:15:25,020 6 ar y chwith, 7 ar y dde. 355 00:15:25,020 --> 00:15:29,320 Rydym yn dewis 6, ac yna rydym yn dewiswch 7, ac yna rydym yn dewis 8. 356 00:15:29,320 --> 00:15:30,100 Voila. 357 00:15:30,100 --> 00:15:34,370 >> Felly mae nifer fawr o eiriau yn ddiweddarach, rydym yn wedi datrys y rhestr hon o wyth elfen 358 00:15:34,370 --> 00:15:38,450 i mewn i restr o un drwy wyth, sy'n cynyddu gyda phob cam, 359 00:15:38,450 --> 00:15:40,850 ond gwnaeth faint o amser ei gymryd i ni wneud hynny. 360 00:15:40,850 --> 00:15:43,190 Wel dwi wedi fwriadol pethau a osodwyd allan ar ffurf lluniau 361 00:15:43,190 --> 00:15:46,330 yma, fel y gallwn fath o gweld neu'n gwerthfawrogi'r is-adran 362 00:15:46,330 --> 00:15:49,060 yn trechu sydd wedi bod yn digwydd. 363 00:15:49,060 --> 00:15:52,830 >> Yn wir, os ydych yn edrych yn ôl ar y sgil, Rwyf wedi gadael pob un o'r llinellau toredig hyn 364 00:15:52,830 --> 00:15:55,660 mewn dalwyr lle, gallwch, math o, gweler, er mwyn cefn, 365 00:15:55,660 --> 00:15:58,800 os ydych yn fath o edrych yn ôl mewn hanes yn awr, fy rhestr wreiddiol 366 00:15:58,800 --> 00:16:00,250 yw, wrth gwrs, o faint 8. 367 00:16:00,250 --> 00:16:03,480 Ac yna o'r blaen, roeddwn yn delio â dwy restr o faint 4, 368 00:16:03,480 --> 00:16:08,400 ac yna pedair rhestr o faint 2, ac yna wyth rhestrau o faint 1. 369 00:16:08,400 --> 00:16:10,151 >> Felly beth yn gwneud hyn, math o, yn eich atgoffa? 370 00:16:10,151 --> 00:16:11,858 Wel, yn wir, unrhyw un algorithmau rydym wedi 371 00:16:11,858 --> 00:16:14,430 edrych ar hyd yn hyn lle rydym rhaniad, a rhannu, a rhannu, 372 00:16:14,430 --> 00:16:19,500 parhau i gael pethau eto, a unwaith eto, yn arwain at syniad cyffredinol hwn. 373 00:16:19,500 --> 00:16:23,100 Ac felly mae yna rywbeth mynd yn logarithmig yma. 374 00:16:23,100 --> 00:16:26,790 Ac nid yw log eithaf o n, ond mae 'na elfen logarithmig 375 00:16:26,790 --> 00:16:28,280 i'r hyn yr ydym wedi ei wneud yn unig. 376 00:16:28,280 --> 00:16:31,570 >> Nawr, gadewch i ni ystyried sut mae hynny'n mewn gwirionedd. 377 00:16:31,570 --> 00:16:34,481 Felly, log o n, unwaith eto roedd amser rhedeg mawr, 378 00:16:34,481 --> 00:16:36,980 pan wnaethom rhywbeth fel chwilio deuaidd, fel yr ydym yn awr yn ei alw, 379 00:16:36,980 --> 00:16:40,090 y strategaeth rhaniad a gorchfygu trwy yr ydym yn dod o hyd i Mike Smith. 380 00:16:40,090 --> 00:16:41,020 Nawr yn dechnegol. 381 00:16:41,020 --> 00:16:43,640 Dyna sylfaen log 2 o n, hyd yn oed er yn y rhan fwyaf o ddosbarthiadau mathemateg, 382 00:16:43,640 --> 00:16:45,770 10 Fel arfer, yn y sylfaen eich bod yn cymryd yn ganiataol. 383 00:16:45,770 --> 00:16:48,940 Ond mae gwyddonwyr cyfrifiadurol bron bob amser feddwl a siarad yn nhermau sylfaen 2, 384 00:16:48,940 --> 00:16:52,569 felly rydym yn gyffredinol dim ond dweud log n, yn hytrach na sylfaen log 2 o n, 385 00:16:52,569 --> 00:16:55,110 ond maent yn union yr un a'r un fath yn y byd o gyfrifiadur 386 00:16:55,110 --> 00:16:57,234 gwyddoniaeth, ac wrth fynd heibio, mae 'na ffactor cyson 387 00:16:57,234 --> 00:17:01,070 gwahaniaeth rhwng y ddau, felly mae'n Moot beth bynnag, am resymau mwy ffurfiol. 388 00:17:01,070 --> 00:17:04,520 >> Ond am nawr, yr hyn yr ydym yn gofalu ei gylch yw yr enghraifft hon. 389 00:17:04,520 --> 00:17:08,520 Felly gadewch i ni brofi trwy esiampl, ond ar lleiaf yn defnyddio enghraifft o'r rhifau 390 00:17:08,520 --> 00:17:10,730 wrth law fel gwiriad pwyll, os mynnwch. 391 00:17:10,730 --> 00:17:14,510 Felly, yn flaenorol y fformiwla yn sylfaen log 2 o n, ond beth yw n yn yr achos hwn. 392 00:17:14,510 --> 00:17:18,526 Roedd gen rhifau n wreiddiol, neu 8 o rif gwreiddiol benodol. 393 00:17:18,526 --> 00:17:20,359 Nawr mae wedi bod ychydig yn tra, ond rwy'n eithaf 394 00:17:20,359 --> 00:17:25,300 yn siwr bod sylfaen log 2 o werth 8 yn 3, 395 00:17:25,300 --> 00:17:29,630 ac yn wir, beth sy'n neis am hynny yw bod 3 yn union y nifer o weithiau 396 00:17:29,630 --> 00:17:33,320 eich bod yn gallu rhannu rhestr o hyd 8 eto, ac unwaith eto, 397 00:17:33,320 --> 00:17:36,160 ac eto, hyd nes eich bod yn gadael gyda rhestrau o faint dim ond 1. 398 00:17:36,160 --> 00:17:36,660 Iawn? 399 00:17:36,660 --> 00:17:40,790 8 yn mynd i 4, yn mynd i 2, mynd i 1, a dyna 400 00:17:40,790 --> 00:17:43,470 adlewyrchu yn union hynny llun oedd gennym ychydig funudau'n ôl. 401 00:17:43,470 --> 00:17:47,160 Felly ychydig o bwyll wirio ynghylch lle logarithm yn cymryd rhan mewn gwirionedd. 402 00:17:47,160 --> 00:17:50,180 >> Felly nawr, beth arall sy'n cymryd rhan yma? n. 403 00:17:50,180 --> 00:17:53,440 Felly sylwi bod pob tro y byddaf yn rhannu y rhestr, 404 00:17:53,440 --> 00:17:58,260 er bod hynny am yn ôl mewn hanes yma, yr oeddwn yn dal i wneud pethau n. 405 00:17:58,260 --> 00:18:02,320 Mae hynny'n gam uno ofynnol bod Yr wyf yn cyffwrdd pob un o'r rhifau, 406 00:18:02,320 --> 00:18:05,060 er mwyn i lithro i mewn ei leoliad priodol. 407 00:18:05,060 --> 00:18:10,760 Felly, er bod y uchder o hyn diagram o faint log n o n neu 3, 408 00:18:10,760 --> 00:18:13,860 yn benodol, mewn geiriau eraill, Fe wnes tair adran yma. 409 00:18:13,860 --> 00:18:18,800 Faint o waith wnes i yn llorweddol ar hyd y siart hwn bob tro? 410 00:18:18,800 --> 00:18:21,110 >> Wel, mi wnes n camau o yn gweithio, oherwydd os wyf i wedi 411 00:18:21,110 --> 00:18:24,080 got pedair elfen a pedair elfen, ac mae angen i mi uno gyda'i gilydd. 412 00:18:24,080 --> 00:18:26,040 Angen i mi fynd drwy y pedair a phedwar hyn, 413 00:18:26,040 --> 00:18:28,123 yn y pen draw i uno nhw yn ôl i wyth elfen. 414 00:18:28,123 --> 00:18:32,182 Os y llaw gen i wyth bysedd dros yma, ac nid wyf yn ei wneud, ac wyth 415 00:18:32,182 --> 00:18:34,390 fingers-- sorry-- Os byddaf i wedi got pedwar bysedd dros yma, 416 00:18:34,390 --> 00:18:37,380 yr wyf yn ei wneud, pedwar bysedd dros yma, yr wyf yn ei wneud, 417 00:18:37,380 --> 00:18:40,590 yna mae hynny'n yr un fath enghraifft fel o'r blaen, os wyf yn gwneud 418 00:18:40,590 --> 00:18:44,010 wyth bysedd er yn cyfanswm, a gallaf, math o, yn ei wneud. 419 00:18:44,010 --> 00:18:47,950 Gallaf union wneud yma, Yna, gallaf yn sicr 420 00:18:47,950 --> 00:18:50,370 uno pob un o'r rhestrau hyn o faint 1 gyda'i gilydd. 421 00:18:50,370 --> 00:18:54,050 Ond yn sicr yn rhaid i mi edrych ar bob elfen yn union unwaith. 422 00:18:54,050 --> 00:18:59,640 Felly, mae'r uchder y broses hon yw n log, lled y broses hon, fel petai, 423 00:18:59,640 --> 00:19:02,490 yn n, felly yr hyn yr ydym yn ymddangos i gael, yn y pen draw, yw 424 00:19:02,490 --> 00:19:06,470 amser yn rhedeg o faint n amserau log n. 425 00:19:06,470 --> 00:19:08,977 >> Mewn geiriau eraill, yr ydym yn ei rannu y rhestr, log n amserau, 426 00:19:08,977 --> 00:19:11,810 ond bob tro baem yn gwneud hynny, yr ydym wedi cael i gyffwrdd pob un o'r elfennau 427 00:19:11,810 --> 00:19:13,560 er mwyn uno nhw i gyd gyda'i gilydd, a oedd yn 428 00:19:13,560 --> 00:19:18,120 Roedd n gam, felly mae gennym n amserau log n, neu fel y byddai gwyddonydd cyfrifiadurol yn dweud, 429 00:19:18,120 --> 00:19:20,380 asymptotically, a oedd yn fyddai'r gair mawr 430 00:19:20,380 --> 00:19:22,810 i ddisgrifio'r uchaf rhwymo ar amser rhedeg, 431 00:19:22,810 --> 00:19:28,010 rydym yn rhedeg mewn o fawr o log n amser, fel petai. 432 00:19:28,010 --> 00:19:31,510 >> Yn awr mae hyn yn arwyddocaol, oherwydd galw i gof yr hyn yr amseroedd yn rhedeg yn 433 00:19:31,510 --> 00:19:34,120 gyda'r math swigod, a dethol didoli, a didoli mewnosod, 434 00:19:34,120 --> 00:19:38,200 a hyd yn oed ychydig o bobl eraill sy'n bodoli, n sgwâr oedd lle yr oeddem yn. 435 00:19:38,200 --> 00:19:39,990 A gallwch, math o, yn gweld hyn yma. 436 00:19:39,990 --> 00:19:45,720 Os yw n sgwâr yn amlwg n amserau n, ond yma rydym wedi n amserau log n, 437 00:19:45,720 --> 00:19:48,770 ac yr ydym eisoes yn gwybod o wythnos sero, hynny log n, y logarithmig, 438 00:19:48,770 --> 00:19:50,550 yn well na rhywbeth llinol. 439 00:19:50,550 --> 00:19:52,930 Wedi'r cyfan, yn dwyn i gof y llun gyda'r coch a melyn 440 00:19:52,930 --> 00:19:56,500 ac mae'r llinellau gwyrdd oedd yn tynnu ni, y llinell logarithmig gwyrdd yn llawer is. 441 00:19:56,500 --> 00:20:00,920 Ac am hynny, yn llawer gwell ac yn gyflymach na'r llinellau melyn a choch yn syth, 442 00:20:00,920 --> 00:20:05,900 n amseroedd log n yw, yn wir, yn well na amserau n n, neu n sgwario. 443 00:20:05,900 --> 00:20:09,110 >> Felly, rydym yn ymddangos i gael nodwyd yn uno algorithm 444 00:20:09,110 --> 00:20:11,870 didoli sy'n rhedeg yn llawer amser yn gyflymach, ac yn wir, 445 00:20:11,870 --> 00:20:16,560 dyna pam, yn gynharach yr wythnos hon, pan fydd gwelsom fod cystadleuaeth rhwng swigen 446 00:20:16,560 --> 00:20:20,750 didoli, trefnu dethol, ac yn uno didoli, yn uno fath mewn gwirionedd, enillodd mewn gwirionedd. 447 00:20:20,750 --> 00:20:23,660 Ac yn wir, doedden ni ddim hyd yn oed yn aros ar gyfer y math swigen a didoli dethol 448 00:20:23,660 --> 00:20:24,790 i orffen. 449 00:20:24,790 --> 00:20:27,410 >> Nawr, gadewch i ni gymryd un tocyn arall ar hyn, o ychydig yn fwy 450 00:20:27,410 --> 00:20:31,030 persbectif ffurfiol, dim ond mewn achos, mae hyn yn atseinio yn well 451 00:20:31,030 --> 00:20:33,380 na'r drafodaeth ar lefel uwch. 452 00:20:33,380 --> 00:20:34,880 Felly dyma y algorithm eto. 453 00:20:34,880 --> 00:20:36,770 Gadewch i ni ofyn i ni'n hunain, yr hyn y mae'r amser yn rhedeg 454 00:20:36,770 --> 00:20:39,287 yw o hyn algorithmau gwahanol gamau? 455 00:20:39,287 --> 00:20:41,620 Gadewch i ni rannu yn y cyntaf achos a'r ail achos. 456 00:20:41,620 --> 00:20:46,280 Mae'r IF a'r ARALL Yn achos OS, OS n yn llai na 2, dim ond yn dychwelyd. 457 00:20:46,280 --> 00:20:47,580 Teimlo fel amser yn gyson. 458 00:20:47,580 --> 00:20:50,970 Mae'n, math o, fel dau gam, OS n yn llai na 2, ac yna dychwelyd. 459 00:20:50,970 --> 00:20:54,580 Ond fel y dywedasom ar ddydd Llun, amser cyson, neu fawr o o 1, 460 00:20:54,580 --> 00:20:57,130 gall fod dau gam, tri grisiau, hyd yn oed 1,000 o gamau. 461 00:20:57,130 --> 00:20:59,870 Yr hyn sy'n bwysig yw ei fod yn nifer cyson o gamau. 462 00:20:59,870 --> 00:21:03,240 Felly amlygodd y melyn pseudocode yma yn rhedeg i mewn, byddwn yn ei alw, 463 00:21:03,240 --> 00:21:04,490 amser yn gyson. 464 00:21:04,490 --> 00:21:06,780 Felly fwy ffurfiol, a rydym yn mynd i'r canlynol-- hwn 465 00:21:06,780 --> 00:21:09,910 fydd y graddau yr ydym ffurfioli hyn hawl now-- T n, 466 00:21:09,910 --> 00:21:15,030 yr amser yn rhedeg o broblem sy'n cymryd somethings n fel mewnbwn, 467 00:21:15,030 --> 00:21:19,150 yn hafal i fawr o un, OS n yn llai na 2. 468 00:21:19,150 --> 00:21:20,640 Felly mae'n amodol ar hynny. 469 00:21:20,640 --> 00:21:24,150 Felly, er mwyn bod yn glir, OS n yn llai na 2, mae gennym restr fer iawn, yna 470 00:21:24,150 --> 00:21:29,151 yr amser yn rhedeg, T n, lle mae n yn 1 neu 0, yn yr achos penodol iawn, 471 00:21:29,151 --> 00:21:30,650 dim ond ei fod yn mynd i fod yn amser yn gyson. 472 00:21:30,650 --> 00:21:32,691 Mae'n mynd i gymryd un cam, dau gam, beth bynnag. 473 00:21:32,691 --> 00:21:33,950 Mae'n nifer penodol o gamau. 474 00:21:33,950 --> 00:21:38,840 >> Felly mae'n rhaid i'r rhan juicy yn sicr yn yr achos arall yn y pseudocode. 475 00:21:38,840 --> 00:21:40,220 Mae'r achos ARALL. 476 00:21:40,220 --> 00:21:44,870 Trefnu yn hanner chwith o elfennau, math cywir hanner o elfennau, uno haneri didoli. 477 00:21:44,870 --> 00:21:46,800 Pa mor hir y pob un o'r camau hynny eu cymryd? 478 00:21:46,800 --> 00:21:49,780 Wel, os y gwaith o redeg amser i ddatrys elfennau n 479 00:21:49,780 --> 00:21:53,010 yw, gadewch i ni alw yn iawn yn gyffredinol, T n, 480 00:21:53,010 --> 00:21:55,500 Yna, didoli y chwith hanner yr elfennau 481 00:21:55,500 --> 00:21:59,720 yw, math o, fel dweud, T o n rannu â 2, 482 00:21:59,720 --> 00:22:03,000 ac yn yr un modd didoli yr hanner cywir o elfennau yw, math o, fel dweud, 483 00:22:03,000 --> 00:22:06,974 T n wedi'i rannu 2, ac yna cyfuno'r haneri didoli. 484 00:22:06,974 --> 00:22:08,890 Wel, os wyf wedi cael rhai nifer o elfennau yma, 485 00:22:08,890 --> 00:22:11,230 fel pedwar, ac mae rhai rhif o elfennau yma, fel bedwar, 486 00:22:11,230 --> 00:22:14,650 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 487 00:22:14,650 --> 00:22:17,160 ar ôl y llall, fel bod yn y pen draw Mae gen i wyth elfen. 488 00:22:17,160 --> 00:22:20,230 Mae'n teimlo fel mae hynny'n fawr o o gamau n? 489 00:22:20,230 --> 00:22:23,500 Os gen n bysedd a phob un o'r ohonynt gael eu cyfuno i mewn lle, 490 00:22:23,500 --> 00:22:25,270 dyna fel grisiau arall n. 491 00:22:25,270 --> 00:22:27,360 >> Felly yn wir formulaically, gallwn fynegi hyn, 492 00:22:27,360 --> 00:22:29,960 er yn ychydig o brawychus ar y dechrau yr olwg, ond mae'n rhywbeth 493 00:22:29,960 --> 00:22:31,600 sy'n dal yn union y rhesymeg. 494 00:22:31,600 --> 00:22:35,710 Mae'r amser rhedeg, T n, OS n yn fwy na neu'n hafal i 2. 495 00:22:35,710 --> 00:22:42,500 Yn yr achos hwn, mae'r achos ARALL, mae T n wedi'i rannu â 2, yn ogystal â T n rannu â 2, 496 00:22:42,500 --> 00:22:45,320 fantais fawr o o n, mae rhai Nifer llinol o gamau, 497 00:22:45,320 --> 00:22:51,630 efallai yn union n, efallai 2 waith n, ond mae'n fras, trefn n. 498 00:22:51,630 --> 00:22:54,060 Fel bod, hefyd, yw sut y gallwn yn mynegi hyn formulaically. 499 00:22:54,060 --> 00:22:56,809 Nawr fyddech chi ddim yn gwybod hyn oni bai rydych wedi ei gofnodi yn eich meddwl, 500 00:22:56,809 --> 00:22:58,710 neu yn edrych i fyny yn y cefn gwerslyfr, bod 501 00:22:58,710 --> 00:23:00,501 gallai fod ychydig yn twyllo daflen ar y diwedd, 502 00:23:00,501 --> 00:23:03,940 ond mae hyn yn, yn wir, yn mynd i rhoi i ni yn fawr o o n log n, 503 00:23:03,940 --> 00:23:06,620 oherwydd bod y digwydd eto y ydych yn gweld yma ar y sgrin, 504 00:23:06,620 --> 00:23:09,550 os ydych mewn gwirionedd yn gwneud hynny allan, gyda nifer anfeidrol o enghreifftiau, 505 00:23:09,550 --> 00:23:13,000 neu y gwnaethoch hynny formulaically, byddech gweld bod hyn, oherwydd fformiwla hon 506 00:23:13,000 --> 00:23:17,100 ei hun yn recursive, gyda t o n dros rywbeth ar y dde, 507 00:23:17,100 --> 00:23:21,680 a t o n drosodd ar y chwith, gall hyn cael eu mynegi mewn gwirionedd, yn y pen draw, 508 00:23:21,680 --> 00:23:24,339 Rhowch gynnig mor fawr o n log n. 509 00:23:24,339 --> 00:23:26,130 Os na argyhoeddedig, dyna dirwy am y tro, yn unig 510 00:23:26,130 --> 00:23:28,960 cymryd ar ffydd, mai dyna, yn wir, yr hyn sy'n digwydd eto yn arwain at, 511 00:23:28,960 --> 00:23:31,780 ond mae hyn yn unig yw ychydig yn fwy o dull mathemategol i chwilio 512 00:23:31,780 --> 00:23:36,520 ar y pryd yn rhedeg o'r math uno yn seiliedig ar ei pseudocode yn unig. 513 00:23:36,520 --> 00:23:39,030 >> Nawr gadewch i ni gymryd dipyn o anadlu o hynny i gyd, 514 00:23:39,030 --> 00:23:41,710 ac edrych ar cyn-seneddwr penodol, sy'n 515 00:23:41,710 --> 00:23:44,260 Gallai edrych ychydig yn gyfarwydd, oedd yn eistedd i lawr gyda Google Eric 516 00:23:44,260 --> 00:23:48,410 Schmidt, beth amser yn ôl, ar gyfer cyfweliad ar y llwyfan, o flaen criw cyfan 517 00:23:48,410 --> 00:23:53,710 o bobl, yn siarad yn y pen draw am pwnc, mae hynny'n eithaf cyfarwydd erbyn hyn. 518 00:23:53,710 --> 00:23:54,575 Gadewch i ni edrych. 519 00:23:54,575 --> 00:24:01,020 520 00:24:01,020 --> 00:24:03,890 >> ERIC SCHMIDT: Nawr Seneddwr, byddwch yma yn Google, 521 00:24:03,890 --> 00:24:09,490 ac yr wyf yn hoffi meddwl y llywyddiaeth fel cyfweliad am swydd. 522 00:24:09,490 --> 00:24:11,712 Nawr mae'n anodd cael swydd fel llywydd. 523 00:24:11,712 --> 00:24:12,670 Arlywydd Obama: Iawn. 524 00:24:12,670 --> 00:24:13,940 ERIC SCHMIDT: A ydych yn mynd i wneud [Anghlywadwy] yn awr. 525 00:24:13,940 --> 00:24:15,523 Mae hefyd yn anodd cael swydd yn Google. 526 00:24:15,523 --> 00:24:17,700 Arlywydd Obama: Iawn. 527 00:24:17,700 --> 00:24:21,330 >> ERIC SCHMIDT: Mae gennym gwestiynau, ac rydym yn gofyn ein cwestiynau i ymgeiswyr, 528 00:24:21,330 --> 00:24:24,310 ac mae hyn yn un yn dod o Larry Schwimmer. 529 00:24:24,310 --> 00:24:25,890 >> Arlywydd Obama: OK. 530 00:24:25,890 --> 00:24:27,005 >> ERIC SCHMIDT: Beth? 531 00:24:27,005 --> 00:24:28,130 Rydych guys yn meddwl fy mod yn kidding? 532 00:24:28,130 --> 00:24:30,590 Mae'n iawn yma. 533 00:24:30,590 --> 00:24:33,490 Beth yw'r ffordd fwyaf effeithlon o didoli miliwn 32 bit gyfanrifau? 534 00:24:33,490 --> 00:24:37,560 535 00:24:37,560 --> 00:24:38,979 >> Arlywydd Obama: Well-- 536 00:24:38,979 --> 00:24:41,020 ERIC SCHMIDT: Weithiau, efallai ddrwg gen i, maybe-- 537 00:24:41,020 --> 00:24:42,750 Arlywydd Obama: Na, na, na, na, na, yr wyf yn think-- 538 00:24:42,750 --> 00:24:43,240 ERIC SCHMIDT: Dyw hynny ddim yn iddo-- 539 00:24:43,240 --> 00:24:45,430 Arlywydd Obama: I yn meddwl, yr wyf yn meddwl y swigen 540 00:24:45,430 --> 00:24:46,875 Byddai fath yn y ffordd anghywir i fynd. 541 00:24:46,875 --> 00:24:49,619 542 00:24:49,619 --> 00:24:50,535 ERIC SCHMIDT: Dewch ar. 543 00:24:50,535 --> 00:24:52,200 A ddywedodd wrtho hwn? 544 00:24:52,200 --> 00:24:54,020 IAWN. 545 00:24:54,020 --> 00:24:55,590 Doeddwn i ddim y wyddoniaeth gyfrifiadurol on-- 546 00:24:55,590 --> 00:24:58,986 >> Arlywydd Obama: Rydym wedi got ein ysbiwyr i mewn 'na. 547 00:24:58,986 --> 00:24:59,860 ATHRO: Pob hawl. 548 00:24:59,860 --> 00:25:03,370 Gadewch i ni adael y tu ôl i ni yn awr y byd damcaniaethol o algorithmau 549 00:25:03,370 --> 00:25:06,520 yn y dadansoddiad asymptotic o hynny, a dychwelyd at rai pynciau 550 00:25:06,520 --> 00:25:09,940 o wythnos sero ac un, a dechrau i gael gwared ar rai olwynion hyfforddiant, 551 00:25:09,940 --> 00:25:10,450 os mynnwch. 552 00:25:10,450 --> 00:25:13,241 Fel eich bod yn wir yn deall yn y pen draw o'r gwaelod i fyny, beth sydd 553 00:25:13,241 --> 00:25:16,805 mynd ymlaen o dan y cwfl, pan fyddwch yn ysgrifennu, crynhoi, a gweithredu rhaglenni. 554 00:25:16,805 --> 00:25:19,680 Dwyn i gof yn arbennig, bod hyn yn y rhaglen C gyntaf buom yn edrych ar, 555 00:25:19,680 --> 00:25:22,840 rhaglen canonaidd, yn syml o ryw fath, yn gymharol siarad, 556 00:25:22,840 --> 00:25:24,620 wherein, mae'n printiau, Hello World. 557 00:25:24,620 --> 00:25:27,610 Ac cofio imi ddweud, y broses y cod ffynhonnell yn mynd drwy 558 00:25:27,610 --> 00:25:28,430 yn union hyn. 559 00:25:28,430 --> 00:25:31,180 Byddwch yn cymryd eich cod ffynhonnell, pasio drwy casglwr, fel chlang, 560 00:25:31,180 --> 00:25:34,650 ac allan yn dod cod gwrthrych, bod Gallai edrych fel hyn, zeros a rhai 561 00:25:34,650 --> 00:25:37,880 bod CPU y cyfrifiadur, canolog uned brosesu neu'r ymennydd, 562 00:25:37,880 --> 00:25:39,760 yn y pen draw yn deall. 563 00:25:39,760 --> 00:25:42,460 >> Mae'n ymddangos bod hynny'n dipyn o gorsymleiddio, 564 00:25:42,460 --> 00:25:44,480 ein bod bellach mewn sefyllfa i pryfocio ar wahân 565 00:25:44,480 --> 00:25:46,720 i ddeall yr hyn wedi bod mewn gwirionedd mynd ymlaen o dan y cwfl 566 00:25:46,720 --> 00:25:48,600 bob tro y byddwch yn rhedeg Chlang, neu'n fwy cyffredinol, 567 00:25:48,600 --> 00:25:53,040 bob tro y byddwch yn gwneud rhaglen, gan ddefnyddio Gwneud a CF 50 IDE. 568 00:25:53,040 --> 00:25:56,760 Yn benodol, pethau fel mae hyn yn cael ei gynhyrchu yn gyntaf, 569 00:25:56,760 --> 00:25:58,684 pan fyddwch yn llunio eich rhaglen gyntaf. 570 00:25:58,684 --> 00:26:00,600 Mewn geiriau eraill, pan fyddwch yn cymryd eich cod ffynhonnell 571 00:26:00,600 --> 00:26:04,390 ac yn llunio ei, beth sydd yn gyntaf sy'n cael ei outputted gan chlang 572 00:26:04,390 --> 00:26:06,370 yn rhywbeth a elwir yn cod cynulliad. 573 00:26:06,370 --> 00:26:08,990 Ac yn wir, mae'n edrych yn union fel hyn. 574 00:26:08,990 --> 00:26:11,170 >> Rwy'n rhedeg gorchymyn yn y llinell gorchymyn yn gynharach. 575 00:26:11,170 --> 00:26:16,260 Cyfalaf dash chlang s hello.c, ac roedd hyn yn creu ffeil 576 00:26:16,260 --> 00:26:19,490 i mi o'r enw hello.s, tu mewn a oedd yn union 577 00:26:19,490 --> 00:26:22,290 cynnwys hyn, ac ychydig mwy uchod ac ychydig yn fwy isod, 578 00:26:22,290 --> 00:26:25,080 ond rwyf wedi rhoi'r juiciest o wybodaeth yma ar y sgrin. 579 00:26:25,080 --> 00:26:29,190 Ac os ydych yn edrych yn ofalus, byddwch yn gweld o leiaf ychydig eiriau allweddol cyfarwydd. 580 00:26:29,190 --> 00:26:31,330 Mae gennym brif ar y top. 581 00:26:31,330 --> 00:26:35,140 Rydym wedi printf i lawr yn y canol. 582 00:26:35,140 --> 00:26:38,670 Ac mae gennym hefyd helo byd slaes n mewn dyfynodau i lawr isod. 583 00:26:38,670 --> 00:26:42,450 >> A phopeth arall yn y fan hyn yw cyfarwyddiadau lefel isel iawn 584 00:26:42,450 --> 00:26:45,500 bod CPU y cyfrifiadur yn deall. 585 00:26:45,500 --> 00:26:50,090 Cyfarwyddiadau CPU sy'n symud cof o gwmpas, y llinynnau llwyth o'r cof, 586 00:26:50,090 --> 00:26:52,750 ac yn y pen draw, print pethau ar y sgrin. 587 00:26:52,750 --> 00:26:56,780 Nawr beth sy'n digwydd er ar ôl y cod cynulliad yn cael ei gynhyrchu? 588 00:26:56,780 --> 00:26:59,964 Yn y pen draw, byddwch yn gwneud, yn wir, dal yn cynhyrchu cod gwrthrych. 589 00:26:59,964 --> 00:27:02,630 Ond mae'r camau sydd wedi 'n sylweddol bod yn mynd ymlaen o dan y cwfl 590 00:27:02,630 --> 00:27:04,180 edrych ychydig mwy fel hyn. 591 00:27:04,180 --> 00:27:08,390 Cod ffynhonnell yn dod yn cod cynulliad, sydd wedyn yn dod cod gwrthrych, 592 00:27:08,390 --> 00:27:11,930 ac mae'r geiriau gweithredol yma yw bod, pan fyddwch yn llunio eich cod ffynhonnell, 593 00:27:11,930 --> 00:27:16,300 allan yn dod cod cynulliad, ac yna pan fyddwch yn ymgynnull eich cod cynulliad, 594 00:27:16,300 --> 00:27:17,800 allan yn dod cod gwrthrych. 595 00:27:17,800 --> 00:27:20,360 >> Nawr chlang yn super soffistigedig, fel llawer o crynoadyddion, 596 00:27:20,360 --> 00:27:23,151 ac mae'n gwneud pob un o'r camau hyn gyda'i gilydd, ac mae'n ei wneud yw o reidrwydd 597 00:27:23,151 --> 00:27:25,360 allbwn unrhyw canolradd ffeiliau a gallwch hyd yn oed weld. 598 00:27:25,360 --> 00:27:28,400 'I jyst yn llunio pethau, sef y term cyffredinol bod 599 00:27:28,400 --> 00:27:30,000 disgrifio'r broses gyfan hon. 600 00:27:30,000 --> 00:27:32,000 Ond os ydych wir eisiau i fod yn benodol, mae 601 00:27:32,000 --> 00:27:34,330 llawer yn digwydd mwy ar yno yn ogystal. 602 00:27:34,330 --> 00:27:38,860 >> Ond gadewch i ni hefyd yn ystyried bod hyd yn oed yn awr y rhaglen honno super syml, hello.c, 603 00:27:38,860 --> 00:27:40,540 Gelwir swyddogaeth. 604 00:27:40,540 --> 00:27:41,870 Fe'i gelwir printf. 605 00:27:41,870 --> 00:27:46,900 Ond doeddwn i ddim yn ysgrifennu printf, yn wir, sy'n dod gyda c, fel petai. 606 00:27:46,900 --> 00:27:51,139 Mae'n dwyn i gof swyddogaeth sy'n ddatgan yn io.h safonol, sydd 607 00:27:51,139 --> 00:27:53,180 yn ffeil header, a oedd yn yn bwnc yr ydym fe mewn gwirionedd 608 00:27:53,180 --> 00:27:55,780 plymio i mewn mwy o ddyfnder cyn bo hir. 609 00:27:55,780 --> 00:27:58,000 Ond ffeil pennawd yn cyd-fynd fel arfer 610 00:27:58,000 --> 00:28:02,920 gan ffeil cod, ffynhonnell ffeil cod, felly yn debyg iawn yno io.h. safonol yn bodoli 611 00:28:02,920 --> 00:28:05,930 >> Rhywbryd yn ôl, rhywun, neu someones, hefyd yn ysgrifennu 612 00:28:05,930 --> 00:28:11,040 ffeil o'r enw io.c safonol, yn y mae'r diffiniadau go iawn, 613 00:28:11,040 --> 00:28:15,220 neu gweithrediadau o printf, a sypiau o swyddogaethau eraill, 614 00:28:15,220 --> 00:28:16,870 yn cael eu hysgrifennu mewn gwirionedd. 615 00:28:16,870 --> 00:28:22,140 Felly o gofio bod, os ydym yn ystyried cael yma ar y chwith, hello.c, pan 616 00:28:22,140 --> 00:28:26,250 llunio, yn rhoi i ni hello.s, hyd yn oed os Nid yw chlang yn trafferthu cynilo mewn lle 617 00:28:26,250 --> 00:28:31,360 gallwn ei weld, a bod y cod cynulliad yn cael ei ymgynnull i mewn i hello.o, a oedd yn 618 00:28:31,360 --> 00:28:34,630 yw, yn wir, yr enw diofyn Rhoddir pryd bynnag y byddwch yn llunio ffynhonnell 619 00:28:34,630 --> 00:28:39,350 cod i mewn cod gwrthrych, ond nid ydynt yn yn barod i weithredu eto, 620 00:28:39,350 --> 00:28:41,460 gan fod cam arall rhaid i hyn ddigwydd, ac mae ganddo 621 00:28:41,460 --> 00:28:44,440 bod yn digwydd am yr ychydig diwethaf wythnosau, efallai unbeknownst i chi. 622 00:28:44,440 --> 00:28:47,290 >> Yn benodol rhywle yn CS50 IDE, ac mae hyn, 623 00:28:47,290 --> 00:28:49,870 hefyd, yn dipyn o gorsymleiddio am eiliad, 624 00:28:49,870 --> 00:28:54,670 mae, neu yr oedd ar un adeg, ffeil o'r enw io.c safonol, 625 00:28:54,670 --> 00:28:58,440 bod rhywun grynhoi mewn io.s safonol neu gyfwerth, 626 00:28:58,440 --> 00:29:02,010 bod rhywun wedyn yn ymgynnull i mewn i io.o safonol, 627 00:29:02,010 --> 00:29:04,600 neu ei fod yn troi allan i fod yn ychydig yn wahanol ffeil 628 00:29:04,600 --> 00:29:07,220 fformat all gael gwahanol ffeil estyniad yn gyfan gwbl, 629 00:29:07,220 --> 00:29:11,720 ond yn ddamcaniaethol ac yn gysyniadol, yn union Roedd y camau hynny i ddigwydd ar ryw ffurf. 630 00:29:11,720 --> 00:29:14,060 Pa un yw dweud, bod bellach pan dwi'n ysgrifennu rhaglen, 631 00:29:14,060 --> 00:29:17,870 hello.c, mai dim ond yn dweud, helo byd, ac rwy'n ei ddefnyddio cod rhywun arall 632 00:29:17,870 --> 00:29:22,480 fel printf, a fu unwaith ar un amser, mewn ffeil o'r enw io.c safonol, 633 00:29:22,480 --> 00:29:26,390 Yna, rhywsut rhaid i mi gymryd fy cod gwrthrych, fy zeros a rhai, 634 00:29:26,390 --> 00:29:29,260 a gwrthrych y person hwnnw cod, neu sero a rhai, 635 00:29:29,260 --> 00:29:34,970 a rhywsut eu cysylltu â'i gilydd i mewn i un ffeil terfynol, a elwir helo, bod 636 00:29:34,970 --> 00:29:38,070 Mae gan bob un o'r sero a rhai o fy mhrif swyddogaeth, 637 00:29:38,070 --> 00:29:40,830 a phob un o'r sero a rhai ar gyfer printf. 638 00:29:40,830 --> 00:29:44,900 >> Ac yn wir, y broses olaf yn Gelwir, gan gysylltu eich cod gwrthrych. 639 00:29:44,900 --> 00:29:47,490 Mae'r allbwn o'r rhain hon ar ffurf ffeil weithredadwy. 640 00:29:47,490 --> 00:29:49,780 Felly er tegwch, yn y ddiwedd y dydd, dim byd 641 00:29:49,780 --> 00:29:52,660 wedi newid ers wythnos un, pan fyddwn yn ddechreuais llunio rhaglenni. 642 00:29:52,660 --> 00:29:55,200 Yn wir, mae hyn oll wedi bod yn yn digwydd o dan y cwfl, 643 00:29:55,200 --> 00:29:57,241 ond yn awr rydym yn mewn sefyllfa lle y gallwn mewn gwirionedd 644 00:29:57,241 --> 00:29:58,794 canfod ar wahân amrywiol hyn gamau. 645 00:29:58,794 --> 00:30:00,710 Ac yn wir, ar y diwedd y dydd, rydym yn dal i 646 00:30:00,710 --> 00:30:04,480 gadael gyda zeros a rhai, a oedd yn mewn gwirionedd yn segue mawr yn awr 647 00:30:04,480 --> 00:30:08,620 i allu arall o C, bod nid ydym wedi gorfod trosoledd mwyaf tebygol 648 00:30:08,620 --> 00:30:11,250 hyd yn hyn, a elwir yn weithredwyr bitwise. 649 00:30:11,250 --> 00:30:15,220 Mewn geiriau eraill, hyd yn hyn, unrhyw bryd rydym wedi ymdrin â data yn C neu newidynnau yn C, 650 00:30:15,220 --> 00:30:17,660 rydym wedi cael pethau fel chars a fflotiau a ins 651 00:30:17,660 --> 00:30:21,990 ac ysu a dyblau ac yn y blaen, ond pob un o'r rheini o leiaf wyth did. 652 00:30:21,990 --> 00:30:25,550 Nid ydym erioed wedi bod yn gallu eto trin darnau unigol, 653 00:30:25,550 --> 00:30:28,970 er bod un darn unigol, rydym yn gwybod, gall gynrychioli 0 a 1. 654 00:30:28,970 --> 00:30:32,640 Nawr mae'n ymddangos fod yn C, yr ydych yn gallu cael gafael ar ddarnau unigol, 655 00:30:32,640 --> 00:30:35,530 os ydych yn gwybod y gystrawen, i fynd arnynt â hwy. 656 00:30:35,530 --> 00:30:38,010 >> Felly, gadewch i ni edrych at weithredwyr bitwise. 657 00:30:38,010 --> 00:30:41,700 Felly y llun dyma rai symbolau sy'n rydym wedi, math o, math o, weld o'r blaen. 658 00:30:41,700 --> 00:30:45,580 Rwy'n gweld ampersand, a fertigol bar, a rhai eraill yn ogystal, 659 00:30:45,580 --> 00:30:49,430 ac yn dwyn i gof bod ampersand ampersand yn rhywbeth yr ydym wedi ei weld o'r blaen. 660 00:30:49,430 --> 00:30:54,060 Mae'r gweithredwr rhesymegol A, lle mae gennych dau ohonynt gyda'i gilydd, neu yr rhesymegol NEU 661 00:30:54,060 --> 00:30:56,300 gweithredydd, lle rydych yn gael dau far fertigol. 662 00:30:56,300 --> 00:31:00,550 Gweithredwyr bitwise, yr ydym chi helpu gweld gweithredu ar ddarnau unigol, 663 00:31:00,550 --> 00:31:03,810 dim ond yn defnyddio ampersand sengl, sengl bar fertigol, y symbol lleolnod 664 00:31:03,810 --> 00:31:06,620 dod nesaf, yr ychydig tilde, ac yna i'r chwith 665 00:31:06,620 --> 00:31:08,990 bachyn chwith braced, neu bachyn dde bachyn dde. 666 00:31:08,990 --> 00:31:10,770 Mae pob un o'r rhain wahanol ystyron. 667 00:31:10,770 --> 00:31:11,950 >> Yn wir, gadewch i ni edrych. 668 00:31:11,950 --> 00:31:16,560 Gadewch i ni fynd hen ysgol heddiw, a defnydd sgrîn gyffwrdd rhag fu, 669 00:31:16,560 --> 00:31:18,002 a elwir fel bwrdd gwyn. 670 00:31:18,002 --> 00:31:19,710 Ac mae hyn yn bwrdd gwyn yn mynd i ganiatáu i ni 671 00:31:19,710 --> 00:31:27,360 i fynegi rhai symbolau gweddol syml, neu yn hytrach rhai fformiwlâu gweddol syml, 672 00:31:27,360 --> 00:31:29,560 y gallwn wedyn yn y pen draw trosoledd, er mwyn 673 00:31:29,560 --> 00:31:33,230 i gael mynediad at unigolyn darnau o fewn rhaglen C. 674 00:31:33,230 --> 00:31:34,480 Mewn geiriau eraill, gadewch i ni wneud hyn. 675 00:31:34,480 --> 00:31:37,080 Gadewch i ni siarad gyntaf am foment am ampersand, 676 00:31:37,080 --> 00:31:39,560 sef y bitwise A gweithredwr. 677 00:31:39,560 --> 00:31:42,130 Mewn geiriau eraill, mae hyn yn gweithredydd sy'n caniatáu 678 00:31:42,130 --> 00:31:45,930 mi gael newidyn chwith yn nodweddiadol, ac newidyn dde, 679 00:31:45,930 --> 00:31:50,640 neu gwerth unigol, os ydym AC nhw at ei gilydd, yn rhoi canlyniad terfynol i mi. 680 00:31:50,640 --> 00:31:51,560 Felly, beth ddylwn i ei olygu? 681 00:31:51,560 --> 00:31:54,840 Os mewn rhaglen, mae gennych newidyn bod storfeydd un o'r gwerthoedd hyn, 682 00:31:54,840 --> 00:31:58,000 neu gadewch i ni gadw'n syml, a dim ond ysgrifennu seroau a rhai yn unigol, 683 00:31:58,000 --> 00:32:00,940 dyma sut mae'r gweithredwr ampersand yn gweithio. 684 00:32:00,940 --> 00:32:06,400 0 ampersand 0 yn mynd i fod yn gyfartal 0. 685 00:32:06,400 --> 00:32:07,210 Nawr, pam hynny? 686 00:32:07,210 --> 00:32:09,291 >> Mae'n debyg iawn i Ymadroddion boolean, 687 00:32:09,291 --> 00:32:10,540 ein bod wedi trafod hyd yn hyn. 688 00:32:10,540 --> 00:32:15,800 Os ydych yn credu wedi'r cyfan, mae'r 0 yw ffug, 0 yn ffug, ffug a ffug 689 00:32:15,800 --> 00:32:18,720 yw, fel yr ydym wedi ei drafod rhesymegol, hefyd yn ffug. 690 00:32:18,720 --> 00:32:20,270 Felly rydym yn cael 0 yma hefyd. 691 00:32:20,270 --> 00:32:24,390 Os ydych yn cymryd 0 ampersand 1, yn dda bod, hefyd, 692 00:32:24,390 --> 00:32:29,890 yn mynd i fod yn 0, oherwydd ar gyfer hyn mynegiant chwith i fod yn wir neu 1, 693 00:32:29,890 --> 00:32:32,360 byddai angen iddo fod yn wir ac yn wir. 694 00:32:32,360 --> 00:32:36,320 Ond yma mae gennym ffug ac yn wir, neu 0 ac 1. 695 00:32:36,320 --> 00:32:42,000 Yn awr eto, os oes gennym 1 ampersand 0, hynny, hefyd, yn mynd i fod 0, 696 00:32:42,000 --> 00:32:47,240 ac os oes gennym 1 ampersand 1, o'r diwedd oes gennym dipyn 1. 697 00:32:47,240 --> 00:32:50,340 Felly, mewn geiriau eraill, nid ydym yn ei wneud unrhyw beth diddorol gyda gweithredwr hon 698 00:32:50,340 --> 00:32:51,850 eto, gweithredwr ampersand hwn. 699 00:32:51,850 --> 00:32:53,780 Mae'n y bitwise A gweithredwr. 700 00:32:53,780 --> 00:32:57,290 Ond mae'r rhain yn y cynhwysion drwy y gallwn ei wneud 701 00:32:57,290 --> 00:32:59,240 bethau diddorol, fel y byddwn yn fuan yn gweld. 702 00:32:59,240 --> 00:33:02,790 >> Nawr, gadewch i ni edrych ar yr union sengl bar fertigol dros yma ar y dde. 703 00:33:02,790 --> 00:33:06,710 Os oes gennyf 0 bit ac yr wyf yn NEU 'i ag, mae'r bitwise 704 00:33:06,710 --> 00:33:11,030 NEU gweithredwr, 0 bit arall, mae hynny'n mynd i roi i mi 0. 705 00:33:11,030 --> 00:33:17,540 Os byddaf yn cymryd ychydig ac mae'n OR 0 gyda ychydig 1, yna dwi'n mynd i gael 1. 706 00:33:17,540 --> 00:33:19,830 Ac yn wir, dim ond ar gyfer eglurder, gad i mi fynd yn ôl, 707 00:33:19,830 --> 00:33:23,380 fel bod fy bariau fertigol Nid oes camgymryd am 1 yn. 708 00:33:23,380 --> 00:33:26,560 Gadewch i mi ailysgrifennu'r holl fy 1 ychydig yn fwy 709 00:33:26,560 --> 00:33:32,700 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, 710 00:33:32,700 --> 00:33:39,060 ac os oes gennyf 1 NEU 1 sydd, hefyd, yn mynd i fod yn 1. 711 00:33:39,060 --> 00:33:42,900 Fel y gallwch weld yn rhesymegol bod y OR gweithredwr ymddwyn yn wahanol iawn. 712 00:33:42,900 --> 00:33:48,070 Mae hyn yn rhoi i mi 0 NEU 0 rhoi i mi 0, ond pob cyfuniad arall yn rhoi i mi 1. 713 00:33:48,070 --> 00:33:52,480 Cyn belled â gen i un 1 yn y fformiwla, y canlyniad yn mynd i fod 1. 714 00:33:52,480 --> 00:33:55,580 >> Mewn cyferbyniad â'r AND gweithredydd, mae'r ampersand, 715 00:33:55,580 --> 00:34:00,940 Dim ond os oes gen i ddau 1 yn y hafaliad, peidiwch Fi 'n weithredol yn cael allan 1. 716 00:34:00,940 --> 00:34:02,850 Nawr mae rhai eraill gweithredwyr hefyd. 717 00:34:02,850 --> 00:34:04,810 Mae un ohonynt yn ychydig mwy o ran. 718 00:34:04,810 --> 00:34:07,980 Felly gadewch i mi fynd yn ei flaen ac yn dileu hwn i ryddhau rhywfaint o le. 719 00:34:07,980 --> 00:34:13,020 720 00:34:13,020 --> 00:34:16,460 A gadewch i ni edrych ar yr symbol caret, am ddim ond eiliad. 721 00:34:16,460 --> 00:34:18,210 Mae hyn yn nodweddiadol yn cymeriad gallwch deipio 722 00:34:18,210 --> 00:34:21,420 ar eich Shift daliad bysellfwrdd a Yna, un o'r rhifau ar ben eich Unol Daleithiau 723 00:34:21,420 --> 00:34:22,250 bysellfwrdd. 724 00:34:22,250 --> 00:34:26,190 >> Felly dyma'r unig NEU gweithredwr, unigryw OR. 725 00:34:26,190 --> 00:34:27,790 Felly rydym yn unig yn gweld y gweithredwr OR. 726 00:34:27,790 --> 00:34:29,348 Mae hyn yn y unigryw OR gweithredwr. 727 00:34:29,348 --> 00:34:30,639 Beth sydd mewn gwirionedd yw'r gwahaniaeth? 728 00:34:30,639 --> 00:34:34,570 Wel gadewch i ni dim ond yn edrych ar y fformiwla, a defnyddio hyn fel cynhwysion yn y pen draw. 729 00:34:34,570 --> 00:34:37,690 0 XOR 0. 730 00:34:37,690 --> 00:34:39,650 Rydw i'n mynd i ddweud yw 0 bob amser. 731 00:34:39,650 --> 00:34:41,400 Dyna y diffiniad o XOR. 732 00:34:41,400 --> 00:34:47,104 0 XOR 1 yn mynd i fod 1. 733 00:34:47,104 --> 00:34:58,810 1 XOR 0 yn mynd i fod yn 1, ac 1 XOR 1 yn mynd i fod? 734 00:34:58,810 --> 00:34:59,890 Anghywir? 735 00:34:59,890 --> 00:35:00,520 Neu iawn? 736 00:35:00,520 --> 00:35:01,860 Nid wyf yn gwybod. 737 00:35:01,860 --> 00:35:02,810 0. 738 00:35:02,810 --> 00:35:04,700 Nawr yr hyn sy'n digwydd yma? 739 00:35:04,700 --> 00:35:06,630 Wel meddwl am y enw gweithredwr hwn. 740 00:35:06,630 --> 00:35:09,980 Unigryw OR, felly wrth i'r enw, math o, yn awgrymu, 741 00:35:09,980 --> 00:35:13,940 yr ateb yn unig yn mynd i fod o 1 os yw'r mewnbynnau yn unigryw, 742 00:35:13,940 --> 00:35:15,560 yn wahanol yn unig. 743 00:35:15,560 --> 00:35:18,170 Felly dyma mewnbynnau yw'r un fath, felly mae'r allbwn yn 0. 744 00:35:18,170 --> 00:35:20,700 Yma mae'r mewnbynnau yw'r un fath, felly mae'r allbwn yn 0. 745 00:35:20,700 --> 00:35:25,640 Dyma'r allbynnau yn wahanol, maent yn yn unigryw, ac felly mae'r allbwn yn 1. 746 00:35:25,640 --> 00:35:28,190 Felly mae'n debyg iawn i A, mae'n debyg iawn, 747 00:35:28,190 --> 00:35:32,760 neu yn hytrach ei fod yn debyg iawn i NEU, ond dim ond mewn ffordd unigryw. 748 00:35:32,760 --> 00:35:36,210 Mwyach Mae hyn yn un yn 1, gan fod gennym ddau 1 yn, 749 00:35:36,210 --> 00:35:38,621 ac nid yn gyfan gwbl, dim ond un ohonynt. 750 00:35:38,621 --> 00:35:39,120 Iawn. 751 00:35:39,120 --> 00:35:40,080 Beth am y lleill? 752 00:35:40,080 --> 00:35:44,220 Wel y tilde, yn y cyfamser, mae mewn gwirionedd yn neis ac yn syml, diolch byth. 753 00:35:44,220 --> 00:35:46,410 Ac mae hwn yn unary gweithredydd, sy'n golygu 754 00:35:46,410 --> 00:35:50,400 mae'n berthnasol i dim ond un mewnbwn, un operand, fel petai. 755 00:35:50,400 --> 00:35:51,800 Nid i chwith a dde. 756 00:35:51,800 --> 00:35:56,050 Mewn geiriau eraill, os ydych yn cymryd tilde o 0, bydd yr ateb yn y gwrthwyneb. 757 00:35:56,050 --> 00:35:59,710 Ac os ydych yn cymryd tilde o 1, mae'r Bydd ateb fydd y gwrthwyneb. 758 00:35:59,710 --> 00:36:02,570 Felly mae'r gweithredydd tilde yn ffordd o negyddu'r ychydig, 759 00:36:02,570 --> 00:36:06,000 neu flipping ychydig o 0-1, neu 1-0. 760 00:36:06,000 --> 00:36:09,820 >> Ac mae hynny'n ein gadael yn olaf gyda dim ond dau gweithredwyr terfynol, 761 00:36:09,820 --> 00:36:13,840 yr hyn a elwir sifft chwith, a'r hyn a elwir gweithredwr shifft gywir. 762 00:36:13,840 --> 00:36:16,620 Gadewch i ni edrych ar sut y mae'r rhai y gwaith. 763 00:36:16,620 --> 00:36:20,780 Mae'r gweithredwr sifft chwith, a ysgrifennwyd gyda dau cromfachau ongl fel 'na, 764 00:36:20,780 --> 00:36:22,110 yn gweithredu fel a ganlyn. 765 00:36:22,110 --> 00:36:27,390 Os bydd fy mewnbwn, neu fy operand, i'r chwith gweithredwr sifft yn eithaf syml 1. 766 00:36:27,390 --> 00:36:33,750 Ac yr wyf wedyn yn dweud wrth y cyfrifiadur i Gadawodd sifft bod 1, dywedwch saith o leoedd, 767 00:36:33,750 --> 00:36:37,150 y canlyniad yw fel pe bawn cymryd bod 1, a'i symud 768 00:36:37,150 --> 00:36:40,160 saith o leoedd draw i'r chwith, ac at ball, 769 00:36:40,160 --> 00:36:42,270 rydym yn mynd i gymryd yn ganiataol y y gofod ar y dde 770 00:36:42,270 --> 00:36:44,080 yn mynd i gael ei padded gyda sero. 771 00:36:44,080 --> 00:36:50,316 Mewn geiriau eraill, 1 gadawodd sifft 7 yn mynd i roi i mi bod 1, wedi'i ddilyn gan 1, 2, 3, 772 00:36:50,316 --> 00:36:54,060 4, 5, 6, 7 sero. 773 00:36:54,060 --> 00:36:57,380 Felly, mewn ffordd, mae'n eich galluogi i gymryd nifer bach fel 1, 774 00:36:57,380 --> 00:37:00,740 ac yn gwneud yn glir ei fod yn llawer llawer, llawer mwy yn y ffordd hon, 775 00:37:00,740 --> 00:37:06,460 ond rydym yn wir yn mynd i weld dulliau mwy glyfar ar ei gyfer 776 00:37:06,460 --> 00:37:08,080 yn lle hynny, yn ogystal, 777 00:37:08,080 --> 00:37:08,720 >> Iawn. 778 00:37:08,720 --> 00:37:10,060 Dyna ni am wythnos tri. 779 00:37:10,060 --> 00:37:11,400 Byddwn yn gweld y tro nesaf i chi. 780 00:37:11,400 --> 00:37:12,770 Roedd hyn yn CS50. 781 00:37:12,770 --> 00:37:17,270 782 00:37:17,270 --> 00:37:22,243 >> [CHWARAE CERDDORIAETH] 783 00:37:22,243 --> 00:37:25,766 >> SIARADWR 1: Yr oedd ar y byrbryd bar bwyta Syndi cyffug poeth. 784 00:37:25,766 --> 00:37:28,090 Roedd ganddo ei fod i gyd dros ei wyneb. 785 00:37:28,090 --> 00:37:30,506 Mae'n gwisgo y siocled fel barf 786 00:37:30,506 --> 00:37:31,756 SIARADWR 2: Beth ydych chi'n ei wneud? 787 00:37:31,756 --> 00:37:32,422 SIARADWR 3: Hmmm? 788 00:37:32,422 --> 00:37:33,500 Beth? 789 00:37:33,500 --> 00:37:36,800 >> SIARADWR 2: Oeddech chi'n jyst dip dwbl? 790 00:37:36,800 --> 00:37:38,585 Rydych dwbl trochi y sglodion. 791 00:37:38,585 --> 00:37:39,460 SIARADWR 3: Esgusodwch fi. 792 00:37:39,460 --> 00:37:44,440 SIARADWR 2: Rydych gostwng y sglodion, yr ydych Cymerodd brathiad, ac rydych yn gostwng eto. 793 00:37:44,440 --> 00:37:44,940 SIARADWR 3: 794 00:37:44,940 --> 00:37:48,440 SIARADWR 2: Felly dyna fel rhoi eich hawl ceg cyfan yn y pant. 795 00:37:48,440 --> 00:37:52,400 Y tro nesaf byddwch yn cymryd sglodion, jyst dipio unwaith, ac yn y pen iddo. 796 00:37:52,400 --> 00:37:53,890 >> SIARADWR 3: Rydych yn gwybod beth, Dan? 797 00:37:53,890 --> 00:37:58,006 Rydych dip y ffordd yr ydych am ei dipio. 798 00:37:58,006 --> 00:38:01,900 'N annhymerus' trochi y ffordd yr wyf am ei dipio. 799 00:38:01,900 --> 00:38:03,194