2014 2015 2016 2017 2018
BEBRO konkurso užduotys 2018

 

Nutekėjimų paieška

Taškai: 12

Gatvėje, kurioje 16 namų, įrengta vamzdynų magistralė. Pastebėtas vandens nutekėjimas. Pareigūnai bando surasti pažeistą vietą, todėl gyventojai išjungė vandenį visoje gatvėje.

Norėdami surasti nutekėjimą, pareigūnai užsuka vožtuvą tarp dviejų namų ir stebi, ar vamzdyje esantis skaitiklis vis tiek rodo vandens naudojimą. Jei jie pradėtų vožtuvo užsukimą tarp 8 ir 9 namo, ir skaitiklis rodytų, kad vanduo tebenaudojamas, jie žinotų, kad nutekėjimas yra tarp 1 ir 8 namo (priešingu atveju – tarp 9 ir 16 namo).

Tarkime, kad vamzdynų magistralėje yra tik vienas nutekėjimas. Kiek mažiausiai vožtuvų turi užsukti pareigūnai, kad įsitikintų, jog jie surado nuotėkį, nesvarbu, kur jis yra?

Paaiškinimas

Tai yra klasikinis paieškos algoritmas: dvejetainė paieška, kai elemento ieškoma surikiuotame sąraše jį dalijant pusiau. Pirmiausia palyginamas ieškomas elementas su elementu, esančiu sąrašo viduryje. Jeigu jie sutampa, paieška baigiama. Jeigu nesutampa, sąrašas padalijamas į dvi dalis ir toliau ieškoma toje dalyje, kurioje galėtų būti ieškomasis elementas. O tai nustatoma iš palyginimo rezultatų: ar ieškomasis elementas buvo didesnis,ar mažesnis už vidurinį. Algoritmą kartojant, paieškos sritis kaskart dvigubai sumažėja, kol pagaliau randamas elementas.

Raktiniai žodžiai: dvejetainė paieška.

Atsakymas

Atsakymas: 4. Tai labai praktinis pavyzdys, kaip dvejetainės paieškos algoritmas naudojamas ne informatikoje.

Kai nutekėjimas gali būti bet kurioje vietoje, geriausia pasikliauti ne sėkme, norint jį surasti, bet kiekvieną kartą padalyti paieškos lauką į dvi lygias dalis. Tai parodys, kurioje paieškos pusėje yra nuotėkis. Kartojant šį procesą, galima surasti nuotėkį.

Pavyzdžiui, pirmą kartą tikriname tarp 8 ir 9 namo, antrą kartą tarp 4 ir 5 namo, trečią kartą tarp 2 ir 3 namo ir ketvirtą kartą tarp 1 ir 2 namo.

Toks pats dvejetainis paieškos algoritmas gali būti naudojamas knygos paieškai bibliotekoje ir pan.

Interaktyvi užduotis