[Powered by Google Translate] [Lineyè Search] [Patrick Schmid, Inivèsite Harvard] [Sa a se CS50.] [CS50.TV] Rechèch se yon bagay ke ou pwobableman fè pi souvan pase ou panse. Li evidan, chak fwa ou louvri moute yon navigatè entènèt ak rechèch pou yon paj wèb - oubyen pou chache zanmi ou sou pi renmen sou sit rezo sosyal ou a - w ap chèche. Men, sa se sèlman yon ti pati nan rechèch la ke ou fè sou yon baz chak jou. Lè ou vle jwenn ke yon sèl ble chemiz nan klozèt la, oswa ki pafè kòsaj wouj pou okazyon an, w ap chèche. Lè ou ale nan yon magazen ke ou pa janm te ale anvan, epi ou ap chèche pou bwokoli a nan ale nan pwodwi w ap chèche. Ki sa ou ka te kòmanse avi se ke depann sou sa ki w ap chèche pou oswa ki jan bagay yo yo òganize lè w ap chèche pou yo li gen yon efè sou ki jan ou rechèch. Pou egzanp, si chemiz ou yo pandye nan klozèt la, ou ka pwobableman jis chwazi sa yo vle san yo pa anpil chèche. Si w ap asepte ou gen mache desann ale nan jwenn bwokoli a, ou pwobableman gen fè yon gade nan tout legim lòt ou anvan ou jwenn ki bwokoli. Search lineyè ki se yon egzanp yon metòd chache tankou - oswa algorithm. Kòm non an implique, metòd sa a fouy pou yon atik nan yon tan lineyè, youn apre lòt la. Se konsa, lè w ap chèche nan rezilta yo soti nan motè pi renmen rechèch ou an epi ou li desann lis la nan rezilta yo, w ap itilize lineyè rechèch. Oke. Se pou yo gade nan yon egzanp. Di nou gen yon lis nimewo - 2, 4, 0, 5, 3, 7, 8, ak 1 - epi nou ap chèche pou 0 a nimewo. Li evidan, ou ka jis wè ke 0 a se nan yon pozisyon nan twazyèm. Men, yon pwogram òdinatè se pa sa ki ere. Li ka sèlman "wè" yon sèl nimewo nan yon tan. Se konsa, kòmanse nan kòmansman an nan lis la, li sèlman "wè" 2 a. Pwogram nan Lè sa a, tcheke - se 2 egal a 0? Li evidan pa. Se konsa, li ale sou nimewo nan pwochen, 4. Èske 4 egal 0? Non. Youn nan pwochen, 0. Ah! Zewo ki egal a 0. Gen nou gen li! Li nan nan yon pozisyon nan twazyèm. Oke. Se pou yo gade nan kèk pseudocode. Li nan sèlman yon koup nan liy long, men kite a gade nan li yon liy nan yon moman. Premyèman, kite a defini fonksyon an - epi nou ap ale nan rele li lineyè rechèch - epi li pran de prèv - kle yo ak etalaj. Kle a se ke valè ke nou ap chèche pou yo, Se konsa nan egzanp lan anvan, sa ki te zewo a. Yon etalaj se yon lis nimewo ki gen tout valè sa yo ke nou ap ale nan rechèch. Se konsa,, ki sa nou vle fè se nou vle fè yon gade nan - ki sòti nan tout pozisyon, se konsa kòmanse nan kòmansman la anpil nan etalaj la til fen anpil nan etalaj la - se konsa longè nan etalaj la - gade nan chak pozisyon sèl ak tcheke chak youn. Se konsa, se sa ki di ke "pou" riban ap fè. Ak nan chak pozisyon, nou ap pral di "Eske se sa ke valè nan pozisyon sa aktyèl egal a kle a ke nou ap chèche pou?" Se konsa, - nan egzanp lan anvan ankò, kle te 0 - pou nou ap di "Èske etalaj la nan pozisyon mwen egal a zewo?" Si li se, nou pwal retounen 'mwen' paske sa se pozisyon aktyèl la nou ap nan. Se konsa, nan egzanp lan anvan, sa yo ki te pozisyon nan twazyèm. Si nou te ale nan etalaj nan tout epi nou pa jwenn anyen - kidonk kite pou nou di nou te kap chèche nimewo a 500 ki klèman pa t 'nan ke egzanp - nou dwe retounen yon bagay, e nou pral retounen -1. E nou jis ap retounen -1 paske sa a, se yon pozisyon ki pa egziste nan etalaj la. Se konsa, sa vle di lè ou jwenn li tounen soti nan yon fonksyon li di "O o, oke. Mwen devine mwen pa t 'jwenn anyen. Se konsa, ke 500 pa janm te la. " Bagay nan bon sou rechèch lineyè se ke sa ap travay sou nenpòt lis atik, kèlkeswa kantite atik yo ap bay lòd la. Li pa enpòtan kote bwokoli a se nan ale nan pwodwi. Osi lontan ke ou mache desann ale nan depi nan konmansman an nan fen a, w ap mare yo jwenn li, asepte magazen an pa te kouri soti nan bwokoli, nan kou. Men, fòs pi gran li nan tou se feblès pi gran li a. Di ou gen yon lis de san nimewo ki yo Ranje soti nan 1 rive nan 200. Si ou ap chèche pou yon nimewo pou la 198, ou gen nan rechèch prèske lis la tout antye nan nimewo ou anvan ou jwenn youn nan w ap chèche pou. Gen dwe yon fason pi bon! Rest te asire gen. Men,, sa se yon sijè pou yon lòt videyo. Epitou, pa enkyete! Jis paske rechèch lineyè se pa solisyon a pi bon nan tout sitiyasyon, li pa vle di ke li pa vini nan sou la men. Sinon, ki jan ou ta jwenn ke bwokoli nan ale nan pwodwi? Non mwen se Patrick Schmid, e sa se CS50. [CS50.TV]