[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]