Tölvur, Forritun
Tvöfaldur leit - einn af the auðveldlega leiðir til að finna stak í fylki
Oft, forritari, jafnvel byrjendur, frammi fyrir þeirri staðreynd að það er sett af tölum, sem verður að finna ákveðna tölu. Það er þetta safn er kallað fylki. Og til að finna atriði í henni, það eru mýgrútur vegu. En einfaldasta þeirra geta talist tvöfaldur leit til hægri. Hvað er þessi aðferð er? Og hvernig á að framkvæma tvöfaldur leit? Pascal er auðveldasta umhverfi fyrir stofnun slíkrar áætlunar, þannig að við notum það til að læra.
Fyrst, greina, hvað eru kostir þessarar aðferðar, er það svo að við getum skilið,
Svo, hvað er að vinna meginreglunni um þessa aðferð? Strax það ætti að segja að tvöfaldur leit virkar ekki í hvaða fylki, en aðeins á raðaða setja af tölum. Í hverju skrefi tekin miðja þáttur af the array (þýðir þann fjölda af frumefni). Ef þörf fjöldi er meiri en að meðaltali, þá allt sem er eftir, sem er minna en meðaltal flokk, má farga og ekki að leita þar. Hins vegar ef minna en meðaltal - Meðal þessara talna til hægri, þú getur ekki leitað. Þá velja nýtt leitarsvæðið efst, þar sem fyrsti þáttur verður um miðja þáttur í öllu fylkinu, og síðast og síðasta vilja. Meðalfjöldi nýju sviði verður ¼ af öllum hluti, það er, (síðasta frumefni + miðjum þáttur í öllu fylkinu) / 2. Again, the sami aðgerð er framkvæmd - samanburð við aðgengi meðalfjölda af the array. Ef markgildið er minna en meðaltal höfnum við hægri hlið, og einnig til að gera næst, þar til nú á þessu miðja þáttur myndi ekki óskað.
Auðvitað, það er best að líta á dæmi um hvernig á að skrifa tvöfaldur leit. Pascal hér mun henta neinum - útgáfa er ekki mikilvæg. Við skulum skrifa einföld forrit.
Það er fylki af 1 til h undir nafninu "Massiv", breytu sem gefur til kynna neðri mörk leit, sem kallast "niz", efri mörk, sem kallast "verh", að meðaltali leitarorð - "sredn"; og þarf fjöldi - "Kr."
Svo fyrst við tengja efri og neðri mörk á svið leit:
niz: = 1;
verh: = H + 1;
Þá skipuleggja hringrás "þar til botninn er minna en efri mörk":
Þó niz
Í hverju skrefi, skipta við hluti 2:
sredn: = (niz + verh) div 2; {Nota aðgerðina DIV, vegna þess að skipta án eftir er}
Í hvert skipti sem við endurskoðun. Vegna þess að hluturinn hefur þegar fundist ef miðillinn er óskað, trufla hringrás:
іf sredn = kr þá brjóta;
Ef um miðja þáttur í fylkinu meira en óskað, fleygja vinstri hlið, það er, efri mörk að meðaltali skipa þáttur:
ef Massiv [sredn]> ISK þá er verh: = sredn;
Og ef á móti, gerir það neðri mörk:
annars niz: = sredn;
enda;
Það er allt sem verður á dagskrá.
Leyfðu okkur að íhuga hvernig það mun líta út tvöfaldur aðferð í reynd. Hugleiddu þetta array 1, 3, 5, 7, 10, 12, 18 og það mun leita númer 12.
Alls við höfum 7 þætti, svo mun fjórða miðlungs, gildi 7.
1 | 3 | 5 | 7 | 10 | 12 | 18 |
Þar sem meira en 12, 7, 1.3 og 5 þætti, getum við henda. Þá höfum við fengið fjölda 4, 2/4 engin leifar 2. Svo er nýr þáttur verður að meðaltali um 10.
7 | 10 | 12 | 18 |
Hér miðju þáttur er nú þegar 12, það er nauðsynlegt númer. Þetta verkefni er lokið - númer 12 sem finnast.
Similar articles
Trending Now