BEBRO konkurso užduotys 2018

 

Ilgiausia žodžių grandinė

Taškai: 9

Du bebrai žaidžia žodžių grandinės žaidimą. Vienas bebras pradeda pasakydamas žodį. Tada kiekvienas paeiliui sako po dar nepanaudotą žodį, prasidedantį trečia ankstesnio žodžio raide. Deja, bebrai žino labai nedaug žodžių – visą jų žodyną galima pavaizduoti taip:

Padėkite bebrams sužaisti kuo ilgesnį žaidimą, iš eilės sužymėdami jų sakomus žodžius.

Paaiškinimas

Bebrai gali panaudoti daugiausiai 8 žodžius. Galima žodžių seka:

kasa→sesija→sūrelis→robotas→baterija→tarka→raštas→šarka

Yra ir kitų tokio pat ilgio sekų. Turime pavyzdį iš 8 žodžių, bet dar nežinome, ar įmanoma sudaryti 9 žodžių seką. Tokiu atveju mums reikėtų panaudoti visus žodyno žodžius. Kadangi žodyne nėra žodžio, kurio trečia raidė k, turėtume pradėti nuo žodžio „kasa“. Pabandę įvairius variantus, pamatome, kad visais atvejais seka pasibaigia ties 8 žodžiais. Tad neįmanoma viename žaidime panaudoti visų 9 žodžių.

----

Spręsdami šį uždavinį turime suprasti taisyklių rinkinį, aiškų ir patogų duomenų vaizdavimą (grafą) ir tada surasti optimalų sprendimą duotoje sistemoje (žodyne). Grafai dažnai naudojami informatikoje. Jais modeliuojamos įvairiausios struktūros iš objektų ir jų ryšių, pavyzdžiui, traukinių maršrutų arba vandentiekių išdėstymo schemos.

Turėdami daugiau informatikos žinių, galėtume pakeisti uždavinį, pavyzdžiui, ilgiausio maršruto paieška grafe. Tai glaudžiai susiję su žinomu Keliaujančio pirklio uždaviniu (https://lt.wikipedia.org/wiki/Keliaujan%C4%8Dio_pirklio_u%C5%BEdavinys).

Informatikos mokslininkai teigia, kad surasti ilgiausią žaidimą didžiausiame žodyne (turint galvoje, kad žinome tūkstančius žodžių!) nėra įmanoma. Tai užimtų per daug laiko net su geriausiu algoritmu.

Atsakymas

Bebrai gali panaudoti daugiausiai 8 žodžius. Galima žodžių seka:

kasa→sesija→sūrelis→robotas→baterija→tarka→raštas→šarka

Interaktyvi užduotis

 

 
Informacija atnaujinta 2017-11-13 16:52:39
Informuojame, kad nuo 2019 m. rugsėjo 2 d. Ugdymo plėtotės centro veiklas vykdo Nacionalinė švietimo agentūra. Ši interneto svetainė toliau nebus atnaujinama, tačiau visa informacija išliks aktyvi ir prieinama tol, kol bus perkelta į Nacionalinės švietimo agentūros interneto svetainę www.nsa.smm.lt.