BEBRO konkurso užduotys 2018

 

Įjunkite šviesas!

Taškai: 12

Kambaryje yra jungikliai, kuriuos spaudžiant įjungiamos lemputės. Paspaudus jungiklį, trys lemputės, su kuriomis tas jungiklis sujungtas, pakeis būsenas: jei lemputės buvo įjungtos, jos išjungiamos, jei buvo išjungtos – ims šviesti.

Įjunkite visas lemputes! Spustelėdami po vieną jungiklį, įjunkite visas lemputes.

Paaiškinimas

Daugelyje užduočių žinome užduoties tikslą ir pradinę būseną. Šios užduoties tikslas – įjungti visas lemputes, o pradinė būsena: įjungtos 3-a, 5-a ir 7-a lemputės, o likusios lemputės išjungtos.

Kol dirbtinis intelektas dar buvo neišplėtotas, problemų sprendimas, naudojant kompiuterines sistemas, dažnai buvo suprantamas kaip veiksmų seka, vedanti nuo pradinės būsenos prie tikslo. Tokia samprata turi prasmę, jei yra baigtinė galimų veiksmų seka ir baigtinė aibė objektų, kurių būseną galima keisti, atliekant nurodytus veiksmus. Buvo sukurta daug įvairių tokią paiešką realizuojančių strategijų. Pavyzdžiui, „daugelio pabaigos būsenų analizė“ pasirenka veiksmą, kuris sumažina skirtumą tarp dabartinės ir galutinės būsenos. O šiame uždavinyje pravartu taip pat ieškoti veiksmų, kurie pakeistų kažkurią kitą būseną galutine būsena. Jei paieška atliekama tiek iš pradinės, tiek iš galutinės būsenos, tokia paieška vadinama „dvikrypte paieška“.

https://en.wikipedia.org/wiki/Bidirectional_search

Raktiniai žodžiai: kompiuterinė sistema, logika, grandinės, paieška.

Atsakymas

Teisingas sprendimas: jungikliai, esantys šalia lempučių, kurių numeriai 1, 2, 3,ir 7, gali būti spustelėti bet kuria tvarka, norint įjungti visas lemputes.

Galima pradėti nuo galutinės tikslo būsenos (tikslo) ir ieškoti sprendinio, einant nuo tikslo pradinės būsenos link. Spustelėjus paskutinį jungiklį, jis įjungs tris lemputes tik tokiu atveju, jei trys lemputės prieš tai buvo išjungtos. Taigi pirmiausia mums reikia išjungti keletą lempučių. Spustelime jungiklius, esančius arti 1-os lemputės, o tada – esančius šalia 2-os ir 7-os lempučių, o paskui šalia 1-os, 2-os ir 3-os lempučių. Galiausiai lieka įjungta tik 5-a lemputė. Dabar galima spustelėti jungiklius, esančius šaliai 3-os ir 7-os lemputės, ir bus uždegtos visos lemputės.

Ieškant sprendinio gali pagelbėti šie pastebėjimai:

  • Neverta du kartus (ar lyginį skaičių kartų...) spustelėti jungiklį, nes antrasis spustelėjimas panaikina pirmojo spustelėjimo rezultatą;
  • Jei spustelime jungiklį X ir po to jungiklį Y, rezultatas bus tas pats, kai spustelėtume pirma Y, o paskui X.

Todėl galimų jungiklių spustelėjimų sekų skaičius ribotas: blogiausiu atveju visi septynių jungiklių poaibiai. Tokie poaibiai128, jei iš viso yra 7 elementai aibėje. Panaudojus kiekvieną poaibį, gausime skirtingą rezultatą. Kadangi yra tik 27 (= 128) skirtingos tinklo konfigūracijos, kiekviena jų gali būti gaunama iš pradinės konfigūracijos.

 

Interaktyvi užduotis

 

 
Informacija atnaujinta 2017-11-13 16:52:39