>> [Daqq tal-mużika]
>> ZAMYLA Chan: L-ewwel ħaġa inti tista ' avviż dwar jsibu hi li aħna diġà
jkunu kodiċi miktub għalina.
Din tissejjaħ kodiċi distribuzzjoni.
Allura aħna mhux biss bil-miktub tagħna stess kodiċi mill-bidu aktar.
Pjuttost, aħna qed timla l-vojt f'xi kodiċi pre-eżistenti.
>> Il-programm find.c iqajjem għal numri biex timla l-haystack, tfittxijiet-
Haystack għal utent sottomessa labra, u dan tagħmlu billi ċċempel it-tip u
tiftix, il-funzjonijiet definiti fil helpers.c.
Allura find.c hija diġà bil-miktub.
Xogħol tiegħek huwa li tikteb helpers.
>> Allura dak li qed nagħmlu?
Aħna qed timplimenta żewġ funzjonijiet.
Search, li jirritorna minnu jekk valur jinstab fil-haystack, jirritornaw
falz jekk il-valur huwa mhux fil-haystack.
U allura aħna qed timplimenta wkoll sort li xorta l-array imsejħa valuri.
>> Mela ejja tindirizza search.
Fittex bħalissa hija implimentata bħala tfittxija lineari, imma int tista 'tagħmel ħafna
aħjar minn dik.
Tfittxija lineari hija implimentata O ta 'żmien n, li huwa pjuttost bil-mod.
Għalkemm, tista 'tfittex kull lista mogħtija lilha.
Xogħol tiegħek huwa li timplimenta tfittxija binarju, li tkun run time O ta 'log n.
Li pretty fast.
>> Iżda hemm stipulazzjoni.
Tfittxija Binarju tista 'tfittex biss permezz ta 'listi magħżula minn qabel.
Għaliex huwa li?
>> Well ejja nħarsu lejn eżempju.
Minħabba l-firxa ta 'valuri, il-haystack, aħna qed tmur biex tkun tfittex
għal labra.
U f'dan l-eżempju, n-numru sħiħ tlieta.
Il-mod li tfittxija binarju jaħdem huwa li inqabblu l-valur medju ta '
il-firxa tal-labra, ferm simili kif aħna fetħet phonebook għall-nofs
paġna żero ġimgħa.
>> Allura wara tqabbil tal-valur medju biex il-labra, inti tista 'jarmi jew il-
xellug jew in-nofs lemini tal-array billi issikkar limiti tiegħek.
F'dan il-każ, la darba tlieta, labra tagħna, huwa anqas minn 10, il-valur tan-nofs, il-
dritt marbut jistgħu jnaqqsu.
Iżda jippruvaw jagħmlu limiti tiegħek stretta daqs kemm possibbli.
Jekk il-valur tan-nofs mhuwiex il-labra, imbagħad inti taf li inti m'għandekx bżonn li
tinkludih fit-tfittxija tiegħek.
Allura int dritt bound tista issikka l- limiti tat-tiftix biss ftit żgħira aktar,
u hekk u ibqa 'sejjer hekk sakemm issib labra tiegħek.
>> Allura dak li l pseudocode look like?
Well filwaqt li aħna qed għadhom tfittex permezz il-lista u għad għandhom l-elementi għall-
tħares, nieħdu l-nofs tal-lista, u jqabblu dak il-valur medju biex
labra tagħna.
Jekk dawn qed ugwali, allura dan ifisser konna sabu l-labra u nistgħu
ritorn vera.
>> Inkella, jekk il-labra tkun inqas minn il-valur tan-nofs, allura dan ifisser li aħna
jistgħu jeħilsu in-nofs lemini, u biss tfittxija ix-xellug tal-array.
Inkella, aħna ser tfittex il- lemin tal-array.
U fl-aħħar, jekk inti ma għandekx xi aktar elementi xellug ta 'tiftix imma int
ma sabu labra għadu tiegħek, allura inti ritorn foloz għaliex il-labra
definittivament mhux fil-haystack.
>> Issa ħaġa pulita dwar dan pseudocode fit-tfittxija binarju huwa li tista 'tkun
interpretata jew bħala iterattiv jew l-implimentazzjoni rikursiv.
Għalhekk ikun rikursivi jekk inti imsejħa il-funzjoni ta 'tfittxija fil-search
jiffunzjonaw fuq kull nofs il-firxa.
Aħna ser ikopru recursion daqsxejn aktar tard fil- naturalment, iżda nafu li dan huwa
għażla jekk inti tixtieq li jippruvaw.
>> Issa ejja nħarsu lejn tip.
Sort jieħu firxa u n-numru sħiħ n, li huwa d-daqs tal-array.
Issa hemm tipi differenti varji ta 'tipi, u inti tista' tħares lejn xi
xorts għall demos u spjegazzjonijiet.
It-tip ritorn għall tagħna funzjoni sort huwa null.
Allura dan ifisser li aħna ma tkunx qed tmur jibagħtu lura kull array minn tip.
Aħna fil-fatt se jibdlu l-ħafna array li kienet għaddiet fil us.
>> U li jista 'jkun minħabba arrays huma għadda b'riferenza C. Issa aħna ser
tara aktar dwar din aktar tard, iżda l- differenza essenzjali bejn tgħaddi
fil xi ħaġa simili integer u t-trasferiment fil-firxa, hija li meta inti
jgħaddu integer, C huwa biss se jagħmel kopja ta 'dak integer u jgħaddu
lill-funzjoni.
Il-varjabbli oriġinali mhux se tinbidel ladarba l-funzjoni huwa lest.
Ma 'firxa, min-naħa l-oħra, huwa mhux se tagħmel kopja, u tkun taf
attwalment jiġu editjar ħafna array innifsu.
>> Allura tip wieħed ta 'tip huwa t-tip ta 'għażla.
Il sort għażla jaħdem billi jibda il-bidu, u allura inti jtenni
fuq u jsibu l-element iżgħar.
U allura inti tpartit li iżgħar element bl-ewwel wieħed.
U allura inti timxi għat-tieni element , Isibu l-iżgħar li jmiss
element, u mbagħad tpartit li bl- tieni element fil-firxa minħabba
l-ewwel element huwa diġà magħżula.
U hekk allura inti tkompli għal kull element fl-identifikazzjoni l-iżgħar
valur u jagħmlu skambju out.
>> Għall I ikun egwali għal 0, l-ewwel element li n minus 1, int ser iqabblu
kull valur li jmiss wara dik u jsibu l-indiċi tal-valur minimu.
Ladarba ssib l-indiċi tal-valur minimu, inti tista 'tpartit li l-valur tal-firxa
firxa minima u I.
>> Tip ieħor ta 'tip li inti tista' jimplimentaw huwa tip bubble.
Allura ttenni sort buzzieqa fuq il-lista jitqabblu elementi biswit u
iskambji l-elementi li huma fl-ordni żbaljata.
U b'dan il-mod, l-akbar element se bubble sa l-aħħar.
U l-lista huwa magħżul darba mhux aktar elementi ġew skambjati.
>> Għalhekk dawn huma żewġ eżempji ta 'tip algoritmi li inti tista 'timplimenta għall-
il-programm ssib.
Ladarba inti finitura sort, u inti stajt jsir tiftix, int lest.
Jisimni Zamyla, u dan huwa CS50.
>> [Daqq tal-mużika]