2014 2015 2016 2017 2018
BEBRO konkurso užduotys 2017

 

Vilkas, avis ir ropė

Taškai: 9

Tai klasikinis uždavinys. Žmogus stovi kairiajame upės krante drauge su vilku, avimi ir rope. Jis turi mažą valtį: joje telpa jis pats ir tik kuris nors vienas iš trijulės. Tačiau vilkas negali būti paliktas vienas su avimi, o avis negali būti palikta viena su rope. Kaip žmogui perkelti visus tris valtimi į kitą upės krantą?

Sprendimas gali būti aprašomas grafu:

  • Koordinatėmis vaizduojama: (vilko pozicija, avies pozicija, ropės pozicija),
  • 0 reiškia kairįjį upės krantą, 1 - dešinįjį.

Pavyzdžiui, ėjimas iš (0,0,0) į (0,0,1) reiškia, kad ropė perkeliama į dešinįjį krantą, o ėjimas iš (0,0,1) į (0,0,0) rodo, kad ropė perkeliama atgal į kairįjį krantą.


Reikia pašalinti „uždraustas“ briaunas – kad vilkas neliktų vienas su avimi arba avis neliktų viena su rope.

Kurias briaunas (linijas) reikia pašalinti? Spustelėkite jas.

Paaiškinimas

Kompiuterių moksle svarbu duomenis atvaizduoti sutartinėmis struktūromis, kad kompiuteris galėtų jas lengviau apdoroti. Tada uždaviniui spręsti kompiuteris galės naudoti sukurtus algoritmus.
Grafas yra dažnai taikoma struktūra, kuri padeda spręsti daugelį uždavinių. Šiuo atveju aprašę uždavinį grafu galime atvaizduoti judėjimo būsenas ir jas keisti. Kiekviena būsena vaizduojama grafo viršūne. Kiekvienu žingsniu galime eiti nuo vienos viršūnės prie kitos grafo briaunomis. Grafu galime pasinaudoti ir spręsdami kitus uždavinius, pavyzdžiui, kai norime rasti optimalų kelią (trumpiausią, pigiausią ir pan.) nuo vienos viršūnės iki kitos.

Raktiniai žodžiai: atvaizdavimas, interaktyvumas, grafas, algoritmas.

Atsakymas

Reikia pašalinti šias keturias briaunas:
(0,0,0) – (0,0,1)
(0,0,0) – (1,0,0)
(0,1,1) – (1,1,1)
(1,1,0) – (1,1,1)
Tai yra briaunos, kurios jungia viršūnes, kai vilkas ir avis (arba avis ir ropė) yra tame pačiame upės krante be žmogaus.
Algoritmo eiga galėtų būti tokia:
1. Perkelk avį į kitą upės krantą.
2. Perkelk ropę į kitą upės krantą.
3. Pasiimk avį atgal.
4. Perkelk vilką į kitą upės krantą.
5. Perkelk avį į kitą upės krantą.
2 ir 4 žingsniai gali būti sukeisti vietomis.

Kitas sprendimo variantas galėtų būti sudarant lentelę:
kairysis krantas dešinysis krantas
(1,1,1)                (0,0,0)   pradžia
(1,0,1)                (0,1,0)   avis perkeliama į dešinįjį krantą
(1,0,0)                (0,1,1)   ropė perkeliama į dešinįjį krantą
(1,1,0)                (0,0,1)    avis perkeliama į kairįjį krantą
(0,1,0)                (1,0,1)   vilkas perkeliamas į dešinįjį krantą
(0,0,0)                (1,1,1)   avis perkeliama į dešinįjį krantą - baigta

Interaktyvi užduotis