BEBRO konkurso užduotys 2017

 

„Skydas ir kardas“

Taškai: 9

Bronius su 7 draugais žaidžia žaidimą „Skydas ir kardas“. Paveiksluose parodyta kiekvieno draugo mėgstama pozicija:

Iš savo nuotraukų draugai rengia stendą mokyklai. Nuotraukose kiekvienas kardas turi būti nukreiptas į gretimą bebrą, o šis turi prisidengti skydu. Broniaus nuotrauka jau stende.

       
     

Sudėkite bebrų nuotraukas pagal nurodytą taisyklę.

Paaiškinimas

Tai gana sudėtingas galvosūkis. Atsitiktinis nuotraukų dėliojimas užimtų labai daug laiko, nes reikėtų patikrinti daugybę kombinacijų, kurių dauguma būtų neteisingos. Jei į 6 nuotraukų galvosūkį įtraukiama dar viena nuotrauka, gaunama šešis kartus daugiau galimybių padėti 7-ąją nuotrauką į tuščią vietą.

Jei turime n nuotraukų, išeina (n-1)! = 1 * 2 * 3 * … * (n-2) * (n-1) skirtingų sprendinių. Taigi šiuo atveju yra 720 skirtingų sprendinių (tačiau beveik visi iš jų neteisingi).

Logiškai mąstydami galime paiešką labai susiaurinti. Atkreipkime dėmesį, kad visi bebrai, kurių kardai nukreipti žemyn, turi būti rikiuojami viršutinėje eilėje ir tėra tik vieno bebro nuotrauka, kurią galima padėti virš Broniaus nuotraukos.

Išsamioji paieška atliekama taikant grįžties algoritmą. Tačiau tada reikia labai daug atminties, todėl būtina sumažinti ieškomų atvejų skaičių atmetant logiškai netinkamus.

http://www.inf-schule.de/grenzen/komplexitaet/affenpuzzle/einstieg_affenpuzzle

https://it.wikipedia.org/wiki/Backtracking

Raktiniai žodžiai: loginis mąstymas, dedukcija, grįžties algoritmas.

Atsakymas

Teisingas atsakymas

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.