Pabaisos gaudymas (2014)
Taškai: 9
Bebro pilies požemiuose gyvena pabaisa. Geltoni langeliai žymi pabaisos slapstymosi vietas. Pilki langeliai – tai sienos, pro kurias pabaisa negali praeiti.
Šio uždavinio interaktyvioje versijoje spustelėję geltoną langelį pamatysime, kad geltonų langelių sumažėjo. Pabaisa bus pagauta, kai liks tik vienas geltonas langelis – tada ji nebegalės niekur pasprukti.
Kiek mažiausiai spustelėjimų reikia, kad pagautume pabaisą?
Dvejetainės paieškos algoritmas yra vienas iš labiausiai žinomų ir dažnai taikomų algoritmų. Šį algoritmą naudojo daugelis žmonių, ieškodami žodžio žodyne ar pavardės telefonų knygelėje, kuomet žodynai ir įvairūs abėcėliniai žinynai dar tebuvo popierinės knygos.
Ši užduotis mokiniams suteikia galimybę patiems atrasti šį algoritmą ir intuityviai suprasti, kaip jis veikia.
Kad išspręstumėte šią užduotį ir puikiai pasirodytumėte, turite surasti gerą strategiją ar algoritmą.
Čia geriausia panaudoti dvejetainę paiešką: kiekvienu žingsniu dalinkite likusią sritį, kurioje yra slėpimosi vieta, iš dviejų ir spustelėkite langelį maždaug per vidurį.
Visame pabaisos slėpimosi take yra 127 langeliai. Spustelėję 64-ą langelį gauname du 63 langelių ilgio takus, iš kurių viename slepiasi pabaisa. Tuomet likusią dalį vėl galime dalinti iš dviejų ir gauti du 31 langelio takus, vėliau 15, 7, 3 ir galiausiai 1. Taip prireiks mažiausiai spustelėjimų – šešių.
