Duha search - usa sa mga labing sayon nga paagi sa pagpangita sa usa ka elemento sa usa ka gubat

Kasagaran, programmers, bisan sa mga magsusugod, nag-atubang sa kamatuoran nga adunay usa ka hugpong sa mga numero, nga kinahanglan makakaplag sa usa ka piho nga gidaghanon. Kini mao ang kini nga koleksyon mao ang gitawag nga usa ka gubat. Ug sa pagpangita sa mga butang diha niini, adunay usa ka myriad sa mga paagi. Apan ang labing yano nga kanila ang mahimong giisip nga usa ka duha search sa too nga. Unsa kini nga pamaagi mao ang? Ug sa unsa nga paagi sa pag-implementar duha search? Pascal mao ang labing sayon nga palibot alang sa mga organisasyon sa maong usa ka programa, mao nga kita mogamit niini sa pagtuon.

Una, pag-analisar, unsa ang mga bentaha sa niini nga paagi, kini mao nga aron kita makasabut, unsa ang punto sa pagtuon sa hilisgutan. Busa, himoa nga adunay ni sa usa ka gubat uban sa usa ka kabahin sa sa labing menos 100000000 elemento, nga kinahanglan sa pagpangita sa pipila. Siyempre, kini nga problema mahimo nga dali ra masulbad pinaagi sa usa ka yano nga linear search, sa diin kita sa paggamit sa pagbalik-balik nga itandi sa gikinahanglan nga elemento sa tanan nga mga nga anaa sa gubat. Ang problema mao nga ang pagpatuman sa niini nga ideya mokuha usab sa daghan nga panahon. Sa usa ka yano nga Pascal nga programa ngadto sa pipila ka mga paagi sa pagtambal, ug sa tulo ka mga linya sa mga nag-unang teksto, dili kamo makamatikod niini, apan sa diha nga moabut kita sa usa ka mas o dili kaayo dako nga proyekto sa uban sa usa ka dako nga gidaghanon sa mga sanga ug sa maayo nga katuyoan, ang programa mahimong andam nga loaded sa dugay na nga panahon. Ilabi na kon ang computer mao ang usa ka huyang nga performance. Busa, adunay usa ka duha search, nga pagmobu, pagminus sa panahon search sa labing menos kaduha.

Busa, unsa ang working baruganan sa niini nga paagi? Diha-diha dayon kini kinahanglan nga moingon nga duha search nagtrabaho dili sa bisan unsa nga gubat, apan lamang sa usa ka lainlainon hugpong sa mga numero. Sa matag lakang nga gikuha tunga-tunga nga elemento sa gubat (nga nagpasabot sa gidaghanon sa mga elemento). Kon ang gikinahanglan nga gidaghanon mao ang labaw pa kay sa aberids, nan ang tanan nga nahibilin, nga mao ang dili kaayo kay sa average cell, mahimong gilabay ug dili sa pagtan-aw didto. Sa laing bahin, kon dili kaayo kay sa average - sa taliwala sa mga numero sa tuo, kamo dili sa pagpangita. Unya pagpili sa usa ka bag-o nga search nga dapit, diin ang unang elemento mao ang tunga-tunga nga elemento sa tibuok gubat, ug ang katapusan ug ang katapusan nga kabubut-on. Ang average nga gidaghanon sa mga bag-o nga kapatagan mahimong ¼ sa tanan nga mga bahin, nga mao, (ang katapusan nga elemento + sa tunga-tunga nga elemento sa sa tibuok gubat) / 2. Pag-usab, sa mao usab nga operasyon gipahigayon - sa usa ka pagtandi sa average nga gidaghanon sa mga gubat. Kon ang target nga bili mao ang dili kaayo kay sa average, atong isalikway sa too nga kiliran, ug usab sa pagbuhat sa sunod, hangtud karon kining tunga-tunga nga elemento nga dili gitinguha.

Siyempre, kini mao ang labing maayo sa pagtan-aw sa usa ka panig-ingnan kon sa unsang paagi sa pagsulat duha search. Pascal dinhi ilisan bisan kinsa - version dili importante. ni pagsulat sa usa ka yano nga programa Himoa.

Kini mao ang usa ka gubat sa 1 ngadto sa h sa ilalum sa ngalan "massiv", usa ka baryable nga nagpakita sa ubos nga utlanan sa search, nga gitawag "niz", ang ibabaw nga utlanan, nga gitawag "verh", ang aberids nga termino search - "sredn"; ug sa gikinahanglan nga gidaghanon - "isk".

Busa, una assign kita sa ibabaw ug sa ubos utlanan sa laing search:

niz: = 1;
verh: = h + 1;

Unya organisar sa cycle "hangtud sa ubos mao ang dili kaayo kay sa ibabaw nga utlanan":

Samtang niz magsugod

Sa matag lakang, bahinon kita sa bahin 2:

sredn: = (niz + verh) div 2; {Gamita ang function div, tungod kay ang Divide nga walay nahibilin}

Ang matag panahon sa review. Tungod kay ang butang na nakaplagan kon ang medium nga gitinguha, pahunong siklo:

іf sredn = isk unya paglapas;

Kon sa tunga-tunga nga elemento sa gubat labaw pa kay sa gitinguha, ilabay sa wala nga kiliran, nga mao, ang ibabaw nga utlanan sa mga average pagtudlo elemento:

kon massiv [sredn]> isk unya verh: = sredn;

Ug kong sa sukwahi, kini naghimo sa ubos nga utlanan:

pa niz: = sredn;
matapos;

Nga ang tanan nga anaa sa programa.

Atong hisgotan kon sa unsang paagi kini nga tan-awon sa mga duha nga pamaagi diha sa buhat. Tagda kini nga gubat: 1, 3, 5, 7, 10, 12, 18 ug kini sa pagpangita sa gidaghanon 12.

Sa kinatibuk-kita adunay 7 elemento, sa ingon nga ang ikaupat nga medium, ang bili 7.

Tungod kay labaw pa kay sa 12, 7, 1.3 ug 5 elemento, kita isalikway. Unya kita sa gidaghanon 4, 4/2 walay salin mao 2. Busa, ang usa ka bag-o nga elemento mahimong usa ka average nga 10.

Sukad sa 12 mas labaw pa kay sa 10, isalikway kita 7. nagpabilin lamang 10, 12 ug 18.

Dinhi, sa tunga-tunga nga elemento mao ang na 12, kini mao ang gikinahanglan nga gidaghanon. tahas Kini nga nahuman - gidaghanon 12 nakaplagan.