Hauek komeriak! Ditxosozko COVID-19-ak etxealdian sartu gintuen udaberriaren hasieran, oraindik udaberrian ginela konturatu gabe geundela eta atera garenerako ia uda dugu gainean! Galtza motzak, tirantedun kamiseta eta sandaliak jantzi nahi izan ditut, baina iazko sandaliak txikituta daude, ezin dira erabili!
Zapata dendara iritsi naiz eta gustuko sandaliak aurkitutakoan dendariarengana joan naiz poz pozik nire zenbakiaren bila. Kontua da zapataria erabat desesperatuta aurkitu dudala. Zapata kutxa bete palea zeukan parean. 100 zapata kutxa bata bestearen gainean pilatuta.
- Kutxa bakoitzean zein zenbaki den jartzea ahaztu egin zaie. Hau lana! Kutxa bakoitza ireki eta zenbakia jarri beharko diot apaletan jarri aurretik! Itxoin beharko duzue.
- Esan digu.
- Poz bakarra da behintzat kutxak ordenaturik daudela badakidala. Goian txikienak eta azpian handienak.
Buruari ongi eragin eta gero proposamena bota diot zapatariari:
- Eta nire zenbakia aurkitu bitartean lagunduko banizu, aurkitutakoan nireak eraman ahal izango ditut? - Galdetu diot nik.
- Bai, noski!
Segituan jarri naiz lanean. Noski, nire zenbakia lehenbailehen aurkitzeko asmoarekin. Ez dut ahaztu behar kutxak ordenaturik daudela eta azpian dagoela zenbakirik handiena eta goian txikiena.
Nire zenbakia topatu aurretik, zenbat kutxa ireki eta zenbakitu beharko dut gehienez, ahalik eta kutxa gutxien ireki nahi baditut?
Badakizue, emaitza ostiralean https://guaixe.eus/komunitatea/EdurneLarraza helbidean.
ERANTZUNA (2020/06/16an gehituta):
Lehenik eta behin barkamena eskatu behar dizuet erantzun honekin berandutzeagatik, ostiralean idatzi behar nuen hau eta astearteraino ezin izan dut jarri. Barkatu!
Eta hori eginda, ebazpena azaltzea dagokit. Hemen azaldu behar dudana algoritmo bat da, hain zuzen ere bilaketa dikotomikoaren algoritmoa edo bilaketa dikotomikoa egin ahal izateko eman behar diren urrats guztien azalpena.
Oso garrantzitsua da enuntziatuan adierazi zaigun datu bat, kutxak ordenaturik daudela esan digute. Horrek esan nahi du sandalia kutxen artean erdikoa ireki eta gure zenbakia aurkitu ez badugu, gero bilatu beharreko kutxen kopurua erdia izatera lortu dugula. 100 sandalia kutxa ditugunez 50.a irekiko dugu. Gure zenbakia aurkitutakoa baino txikiagoa bada, goiko 49 kutxa izango ditugu bilatzeko, handiagoa bada ordea, beheko 50 kutxa. Gera gaitezen kopuru handienarekin. Horren erdiko kutxa irekiko dugu (eta dagoeneko 3 kutxa ireki ditugu). Berriro gure zenbakiarekin konparatuko dugu eta txikiagoa bada 24 kutxa izango ditugu batetik eta 25 bestetik. 4. kutxa irekitzean 12 geratuko dira txikiagoen artean eta beste 12 handiagoen artean. 12ren erdikoa hartuz gero, 5 izango ditugu txikiagoen artean eta beste 6 handiagoen artean. 5. kutxa irekitakoan, 2 geratuko zaizkigu txikiagoen artean eta 3 handiagoen artean eta 6. kutxa irekita bana geratuko zaizkigu. Beraz, 7 kutxa ireki beharko ditugu gehienez gure neurriko sandalia, egotekotan, aurkitzeko. Kasurik hoberenean zapata kutxa bat irekitzearekin nahikoa izango litzateke.
Linealki bilatu behar izan bagenu, adibidez kutxak ordenaturik ez daudelako, orduan kasurik hoberenean kutxa bakarra ireki beharko genuke, baina kasurik txarrenean 100 kutxa ireki beharko genituzke.
Hau izaten da errazen ulertzen den algoritmoa eta horregatik kontatzen lehenengoa ere. Normalean gauza bera egiteko, hainbat algoritmo posible egoten dira eta oso garrantzitsua izaten da antzematea une bakoitzean horietako zein izango den eraginkorrena. Gaur egun oso sonatua den algoritmoa Google-ek Interneten dauden datu guztien bilaketak egiteko erabiltzen duena.
Ikus dezakezuenez egoera arrunten artean topatzen ditugu arazo konputazionalak, konputagailuek oso azkar kalkulatuko dituzten ebazpenak konputagailuok hori egiteko ongi programaturik egonez gero.
Hurrengora arte!
Edurne
