„Skydas ir kardas“
Taškai: 12
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ę.
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.
Teisingas atsakymas