Бинардык издөө - жөнөкөй жолдор менен бир катар элемент издөө

белгилүү бир сан менен табышы керек сандардан турган топтому бар экенин Көп учурда програмисттер, чынында туш да, башталгыч,. Бул чогултуу бир катар деп саналат. Ал эми анда-ден табуу үчүн, ар кандай жолдор менен сансыз бар. Бирок, алардын көпчүлүгү жөнөкөй укугу бинардык издөө каралышы мүмкүн. Бул ыкма болуп саналат? Анан кантип бинардык издөөнү ишке ашыруу үчүн? Pascal мындай программа уюштуруу үчүн жөнөкөй чөйрө болуп саналат, ошондуктан, биз изилдөө үчүн колдоно аласыз.

Биринчиден, талдап, ушул ыкма менен кандай артыкчылыктары бар, аны биз түшүнө алат, деген темада изилдөө чекити болуп саналат. Ошондуктан, кээ бир табыш керек, жок эле дегенде, 100000000 элементтери өлчөм менен көптөгөн болсун. Албетте, бул маселе оной биз айлампасын тизилип экенин баары менен керектүү элемент салыштыруу колдонуп жаткан, жөнөкөй сызыктуу издөө аркылуу чечилиши мүмкүн. Маселе бул идеяны ишке ашыруу өтө көп убакытты талап кылат. негизги тексттин бир нече дарылоо, ошондой эле, үч катар бир жөнөкөй Pascal программасында сиз аны байкабай калат, бирок, биз бийлик бутактарынын жана жакшы иштөөсүнө көп саны менен аздыр-көптүр ири долбоорлорго келгенде, программа да көпкө жүктөлгөн даяр болот. Айрыкча, эгер ЭЭМ үчүн алсыз аткаруу болуп саналат. Ошон үчүн, жок эле дегенде, эки жолу издөө убактысын азайтып, бинардык издөө, бар.

Ошентип, бул ыкма менен иш принцип болуп эмне саналат? Ошол замат ал бинардык издөө иштери эч кандай тизилишти, ал эми сандардын сорттолгон жыйындысы гана эмес экенин айтыш керек. тизилип, орто элементи алынган ар бир кадам учурда (элементтин санын дегенди билдирет). зарыл болсо, саны көп болсо орто эсеп менен, андан кийин калган, ошонун баары, бул орточо клетканын аз болуп, жарактан ошол жерде карап эмес, болот. Тескерисинче, орточо кем болсо - укугу ушул сандардын арасында, сиз издөө жүргүзө аласыз. Андан кийин биринчи элементи толугу менен катар орто элементи, ошондой эле акыркы, ал эми акыркылар эркин боло турган жаңы издөө аянты, тандоо. жаңы тармагында орточо саны, бардык сегментинде, анын ¼ болот (акыркы элементи + бүт аскерин тизди орто элементтин) / 2. Дагы бир операция ишке ашырылат - тизилип орточо саны менен салыштырышкан. максаттуу орточо аз болсо, биз азыр бул орто элемент каалаган эмес, чейин, андан ары эмне кылуу, ошондой эле оң тарапка, четке кагуу.

Албетте, бинардык издөө жазуу үчүн кандай мисал карап жакшы. Pascal бул жерде эч кимге жаккан - версия маанилүү эмес. Бир жөнөкөй программа түзсөк көрөлү.

Бул боюнча д 1 аты бир катар болуп саналат "massiv", "verh" деп аталган "Нижнечуйское" деп аталган бир издөө төмөнкү чегин көрсөтүү менен өзгөрмөлүү, жогорку чеги, орточо издөө термин - "sredn"; жана керектүү сан - "ISK".

Ошентип, биз биринчи кезекте ар түрдүү издөө жогорку жана төмөнкү чектен жүктөлсүн:

Нижнечуйское: = 1;
verh: = ч + 1;

Андан кийин "төмөнкү жогорку чектен кем чейин" айлампасын уюштурат:

Нижнечуйское баштоо

Ар бир кадам, биз сегментти 2 бөлүп:

sredn: = (Нижнечуйское + verh) бөлүү 2; {Калган жок ажырымдан улам, милдети бөлүү колдонуу}

карап чыгуунун ар бир жолу. нерсе орто каалаган болсо табылган, анткени айлампасын үзгүлтүккө:

іf sredn = ISK анан бузууга;

Керектүү жыйынтыктары тизилип, орто элементи болсо, сол тарабын жокко чыгаруу, башкача айтканда, орто жана жогорку чек элементин дайындайт:

Эгерде massiv [sredn]> ISK анда verh: = sredn;

Тескерисинче болсо, анда ал төмөнкү чек кылат:

башка Нижнечуйское: = sredn;
жок;

Бул программага болот деген ушул.

Келгиле, ал иш жүзүндө бинардык ыкмасын карап карап көрөлү. Бул толгон карап көрөлү: 1, 3, 5, 7, 10, 12, 18 жана 12-санын издешет.

Баардыгыбыз 7 элементтер бар, ошондуктан, төртүнчү орто эркин, маани 7.

12 жылдан ашык жылдан бери, 7, 1,3 жана 5 элементтери, биз жокко чыгаруу мүмкүн. Андан кийин биз номерин алдым 4, 4/2 жок калган 2. Ошентип, жаңы элемент 10 орточо болот болот.

12 10 жогору болгондуктан, 7 10, 12 жана 18-бойдон калууда жокко чыгаруу.

Бул жерде, ортоңку элемент буга чейин, 12, ал талап кылынган саны. Бул тапшырма аяктады - саны 12 болду.