Užtvankos statyba

Taškai: 9

Bebrai nori užtvenkti upę, todėl konstruoja užtvankų sistemą. Šiai sistemai svarbios upės salos.
Plane pažymėtos visos galimos užtvankų vietos. Skaičiai rodo, kiek rąstų reikia užtvankai vienoje ar kitoje vietoje pastatyti. 

Parodykite bebrams, kaip užtvenkti upę su kuo mažiau rąstų!
Spustelėkite tas plano vietas, kur bebrai turi statyti užtvankas.
Pastatytą užtvanką galite pašalinti spustelėdami dar kartą.
Viršuje rodoma, kiek reikės rąstų bebrų suplanuotoms užtvankoms pastatyti.

Paaiškinimas

Šį uždavinį, kuriame reikia pastatyti užtvanką panaudojant kuo mažiau rąstų, galima suformuluoti ir kitaip. Rąstų skaičius, būtinas užtvankai pastatyti, gali būti suprantamas kaip vientisas „rąstinis“ kelias. Tada bebrai turės spręsti tokį uždavinį: rasti trumpiausią kelią nuo vieno kranto iki kito palei statomus rąstus.
Algoritmą, kuris rastų trumpiausią kelią, 1959 m. pasiūlė olandų informatikas Edsger W. Dijkstra. Bebrai gali pasinaudoti šiuo algoritmu, kad įveiktų upę panaudodami kuo mažiau rąstų.
Informatikoje (ir ne tik) naudinga pirma gerai išanalizuoti užduotį, permąstyti, ar nėra kokio panašaus mums žinomo uždavinio sprendimo. Jei pavyktų uždavinį ar jo dalį performuluoti į žinomą uždavinį, tai žinomą sprendimą beliktų pritaikyti naujoje situacijoje.

Atsakymas

Teisingas atsakymas:

Jei bebrai nori pastatyti užtvanką būtent taip, kaip pažymėta plane, jiems prireiks 4 + 3 + 4 + 4 = 15 rąstų. Visi kiti bandymai pastatyti užtvanką reikalaus daugiau rąstų (įsitikinkite!) arba liks tarpas, pro kurį bėgs vanduo.

Interaktyvi užduotis

 

 
Informacija atnaujinta 2015-12-03 07:50:57
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.