Գուշակիր թիվը

Արի մի փոքրիկ խաղ խաղանք, որպեսզի ավելի լավ պատկերացնես, թե ինչպես են տարբեր ալգորիթմներն աշխատում նույն խնդրի վրա։ Համակարգիչն ընտրելու է 1-ից 16 կամայական ամբողջ թիվ։Դու անընդհատ փորձիր գուշակել թիվը, իսկ համակարգիչը կասի՝ թիվը մեծ է, թե փոքր․

Թիվը գուշակելուց հետո փորձիր հասկանալ, թե ինչ եղանակով փորձեցիր գտնել թիվը (խաղն անգլերեն է)։

Հնարավոր է՝ դու գուշակել ես 1, հետո 2, հետո 3, հետո 4, և այդպես շարունակ, մինչև թիվը կգտնես։ Այսպիսի մոտեցումը կոչվում է գծային որոնում, քանի որ դու հերթականությամբ գուշակում ես թվերը։ Դա կաշխատի։ Բայց առավելագույնը քանի՞ քայլ հետո կգտնես թիվը։ Եթե համակարգիչն ընտրի 16 թիվը, կգտնես այն 16 քայլ հետո։ Կարող ես, իհարկե, հաջողակ գտնվել, եթե համակարգիչը պահի 1 թիվը, և միանգամից կգուշակես այն։ Սակայն եթե դիտարկում ենք ընդհանուր տեսանկյունից, համակարգիչը հավասարապես կարող է ընտրել 1-ից 16 թվերը, և միջինում թիվը կգուշակես 8 քայլ հետո։

Դու կարող ես 1, 2, 3, 4,․․․-ից ավելի օպտիմալ եղանակով գտնել թիվը։ Քանի որ համակարգիչն ասում է, թե թիվն ավելի մեծ է, ավելի փոքր, թե հավասար, դու կարող ես սկսել՝ 8 թիվը գուշակելուց: Եթե համակարգչի թիվը փոքր է 8-ից, ապա, քանի որ դու գիտես, որ 8-ը մեծ է, միանգամից շարքից դուրս են գալիս 8-ից 16 թվերը։ Եթե համակարգչի թիվը մեծ է 8-ից, ապա, քանի որ դու գիտես, որ 8-ը փոքր է, այս անգամ շարքից դուրս են գալիս 1-ից 7 թվերը։ Յուրաքանչյուր դեպքում էլ արտաքսվում է թվերի մի ամբողջ կեսը։ Հաջորդ քայլին նույն տրամաբանությամբ ընտրիր մեջտեղի թիվը՝ շարունակ ջնջելով թվերի կեսը։ Այդպես շարունակիր ամեն քայլին, մինչև կգտնես համակարգչի պահած թիվը։ Այս մոտեցումը կոչվում է երկուական որոնում, և անկախ նրանից, թե համակարգիչը 1-ից 16 թվերից որը կընտրի, այս եղանակով դու թիվը կգտնես առավելագույնը 4 քայլից։

Փորձիր այդ եղանակը 1-ից 300 թվերի համար։ Դու պետք է չանցնես 9 քայլից։

Քանի՞ քայլից գտար թիվը։ Ինչո՞ւ երբեք չես անցնի 9 քայլը։ Կարո՞ղ ես դրան մաթեմատիկական բացատրություն տալ։

Մենք կվերադառնանք երկուական որոնմանը և կտեսնենք, թե ինչպես օպտիմալ կերպով օգտագործել այն՝ JavaScript-ի զանգվածի մեջ տարր գտնելու համար։ Մինչ այդ արի ավելի բարդ խնդրի վրա կիրառենք ալգորիթմը։

Նյութը ստեղծվել է Դարթմութի համակարգչային գիտությունների դասախոսներ Թոմաս Քորմենի և Դեվին Բալկքոմի, ինչպես նաև «Քան» ակադեմիայի ծրագրավորման թիմի կողմից։ Նյութը լիցենզավորվել է CC-BY-NC-SA-ի կողմից։