>> [CHWARAE CERDDORIAETH]
>> ZAMYLA Chan: Y peth cyntaf y byddwch efallai rhybudd am ddarganfyddiad yw ein bod eisoes
wedi cod a ysgrifennwyd ar ein cyfer.
Gelwir hyn yn cod dosbarthu.
Felly, nid ydym yn unig yn ysgrifennu ein hunain cod o'r dechrau anymore.
Yn hytrach, rydym yn llenwi'r unedau gwag mewn rhai cod sydd eisoes yn bodoli.
>> Mae'r rhaglen find.c awgrymiadau ar gyfer rhifau i lenwi'r das wair, chwilio'r
tas wair am nodwydd defnyddiwr a gyflwynwyd, ac mae'n gwneud hyn drwy ffonio didoli a
chwilio, swyddogaethau a ddiffinnir yn helpers.c.
Felly find.c ei ysgrifennu yn barod.
Eich gwaith chi yw ysgrifennu gynorthwywyr.
>> Felly beth ydyn ni'n ei wneud?
Rydym yn gweithredu dwy swyddogaeth.
Chwilio, sy'n dychwelyd wir os yw gwerth i'w gael yn y tas wair, gan ddychwelyd
ffug os yw'r gwerth yn nid yn y tas wair.
Ac yna rydym hefyd yn gweithredu math sy'n didoli'r amrywiaeth a elwir gwerthoedd.
>> Felly, gadewch i ni fynd i'r afael â chwilio.
Chwilio yn cael ei weithredu ar hyn o bryd fel chwiliad llinol, ond gallwch wneud llawer
yn well na hynny.
Chwiliad llinol yn cael ei weithredu yn O o amser n, sy'n eithaf araf.
Er, gall chwilio unrhyw restr a roddir iddo.
Eich swydd yw gweithredu chwiliad deuaidd, sydd wedi rhedeg amser O o log n.
Dyna 'n bert gyflym.
>> Ond mae amod.
Gall chwiliad deuaidd yn unig chwilio drwy restrau cyn ei ddidoli.
Pam hynny?
>> Wel gadewch i ni edrych ar enghraifft.
O ystyried amrywiaeth o werthoedd, y das wair, rydym yn mynd i fod yn edrych
am nodwydd.
Ac yn yr enghraifft hon, y cyfanrif tri.
Mae'r ffordd y chwiliad deuaidd yn gweithio yw bod rydym yn cymharu gwerth canol
yr amrywiaeth i'r nodwydd, yn debyg iawn i sut y rydym yn agor llyfr ffôn i ganol
dudalen yn wythnos sero.
>> Felly, ar ôl cymharu gwerth canol i y nodwydd, gallwch daflu naill ai'r
chwith neu i'r dde hanner y rhesi drwy dynhau eich ffiniau.
Yn yr achos hwn, gan fod tri, ein nodwydd, yn llai na 10, mae'r gwerth canol, y
Gall dde rhwymo lleihau.
Ond ceisiwch wneud eich ffiniau mor dynn ag y bo modd.
Os nad yw'r gwerth canol yn y nodwydd, yna rydych yn gwybod nad oes angen i chi wneud
gynnwys yn eich chwiliad.
Felly, rydych chi'n iawn rhwymo gall dynhau'r chwilio terfynau dim ond ychydig bach yn fwy,
ac yn y blaen ac yn y blaen hyd nes y i chi ddod o hyd i'ch nodwydd.
>> Felly beth mae'r pseudocode yn edrych?
Wel er ein bod yn dal i chwilio drwy y rhestr ac yn dal i gael elfennau i
edrych i mewn, rydym yn cymryd ganol y rhestr, a chymharu hynny gwerth canol i
ein nodwydd.
Os ydynt yn gyfartal, yna mae hynny'n golygu ein bod i wedi dod o hyd i'r nodwydd a gallwn
dychwelyd yn wir.
>> Fel arall, os bydd y nodwydd yn llai na gwerth canol, yna mae hynny'n golygu ein
Gall thaflwch y hanner cywir, a dim ond chwilio'r ochr chwith y rhesi.
Fel arall, byddwn yn chwilio'r ochr dde y rhesi.
Ac ar y diwedd, os nad oes gennych unrhyw i chi mwy o elfennau i'r chwith i chwilio ond
nad ydynt wedi dod o hyd i'ch nodwydd eto, yna rydych dychwelyd ffug oherwydd bod y nodwydd
yn bendant nid yw yn y tas wair.
>> Erbyn hyn, mae peth daclus am pseudocode hwn mewn chwiliad deuaidd yw y gall fod yn
ddehongli fel naill ai ailadroddol neu weithredu ailadroddus.
Felly byddai'n recursive os ydych yn galw y swyddogaeth chwilio o fewn y chwiliad
gweithredu ar y naill hanner y rhesi.
Byddwn yn ymdrin recursion ychydig yn ddiweddarach yn y gwrs, ond ddim yn gwybod ei bod yn
opsiwn os hoffech roi cynnig arnynt.
>> Nawr, gadewch i ni edrych ar fath.
Trefnu yn cymryd amrywiaeth a'r cyfanrif n, sef maint y rhesi.
Erbyn hyn mae yna wahanol fathau gwahanol o ryw fath, a gallwch edrych ar rai
siorts ar gyfer arddangosiadau ac esboniadau.
Y math gyfnewid am ein swyddogaeth fath yn ddi-rym.
Felly mae hynny'n golygu nad ydym yn mynd i ddychwelyd unrhyw amrywiaeth o'r math.
Rydym yn wir yn mynd i newid yr union amrywiaeth a ddaeth yn ni.
>> Ac mae hynny'n bosibl oherwydd araeau yn pasio drwy gyfeirio yn C. Nawr rydym fe
weld mwy am hyn yn ddiweddarach, ond mae'r gwahaniaeth hanfodol rhwng pasio
mewn rhywbeth fel cyfanrif a pasio mewn amrywiaeth, yw bod pan fyddwch yn
pasio mewn cyfanrif, C yn jyst yn mynd i gwneud copi o'r cyfanrif ac yn pasio
i'r swyddogaeth.
Ni fydd y newidyn gwreiddiol yn cael ei newid unwaith y bydd y swyddogaeth yn cael ei orffen.
Gydag amrywiaeth, ar y llaw arall, mae'n ddim yn mynd i wneud copi, a wnewch chi helpu
mewn gwirionedd yn golygu'r y iawn amrywiaeth ei hun.
>> Felly, un math o fath yn y math dethol.
Y math ddethol yn gweithio trwy ddechrau yn y dechrau, ac yna byddwch yn ailadrodd
drosodd a dod o hyd i'r elfen lleiaf.
Ac yna byddwch yn cyfnewid y lleiaf elfen sydd â'r un cyntaf.
Ac yna byddwch yn symud i'r ail elfen , Dod o hyd i'r lleiaf nesaf
elfen, ac yna cyfnewid bod gyda ail elfen yn yr arae oherwydd
yr elfen cyntaf eisoes yn cael ei datrys.
Ac felly, yna byddwch yn parhau ar gyfer pob elfen o ran adnabod y lleiaf
gwerth a chyfnewid allan.
>> Canys mi hafal i 0, yr elfen gyntaf un i n minws 1, ydych yn mynd i gymharu
pob gwerth nesaf ar ôl hynny a dod o hyd i y mynegai o werth lleiaf.
Ar ôl i chi ddod o hyd i'r mynegai gwerth lleiaf, gallwch gyfnewid y gwerth amrywiaeth
isafswm ac amrywiaeth I.
>> Math arall o fath y gallwch gweithredu yn fath swigen.
Felly ailadrodd fath swigen dros y rhestr cymharu elfennau cyfagos a
cyfnewid elfennau sy'n yn y drefn anghywir.
Ac mae hyn yn ffordd, mae'r elfen fwyaf Bydd swigen at y diwedd.
Ac mae'r rhestr yn cael ei datrys unwaith heb fod yn fwy elfennau wedi cael eu cyfnewid.
>> Felly, y rhai yn ddwy enghraifft o'r math algorithmau y gallwch yn gweithredu ar gyfer
y rhaglen darganfyddiad.
Unwaith i chi orffen didoli, ac nad ydych wedi gwneud chwilio, rydych yn gorffen.
Fy enw i yw Zamyla, ac mae hyn yn CS50.
>> [CHWARAE CERDDORIAETH]