Algoritmi in podatkovne strukture (2021-22)

Imamo bombo, ki prav nadležno tiktaka. Na bombi je n stikal, ki jih lahko premikamo gor ali dol. Določene kombinacije teh stikal sprožijo bombo, le ena kombinacija pa jo onesposobi.

Naša naloga je premakniti stikala iz trenutne pozicije v pozicijo, ki bombo onesposobi, ne da bi ta medtem eksplodirala. Stikala so velika in nerodna, tako da lahko premikamo le eno stikalo naenkrat.

Imamo, recimo n=4 stikala, ki so trenutno v poziciji ^vvv. Spraviti jih moramo v pozicijo ^v^^. Prepovedane pozicije so vvv^, ^vv^, ^v^v in ^^^v.

1. Ročno poišči čim krajše zaporedje premikov stikal, ki reši nalogo.

2. Prepričaj me -- pisno, računsko, slikovito, kakorkoli želiš --, da je to res najkrajše možno zaporedje premikov.

3. Napiši program, ki odgovori na gornje vprašanje. Program naj bo splošen, tako da bi deloval tudi pri drugem številu stikal in drugih začetnih, končnih in prepovedanih kombinacijah; končnih in prepovedanih kombinacij je lahko tudi več ali manj. Zagotovo vemo le, da imajo stikala le dva položaja. Predvidi tudi možnost, da je želeno stanje nedosegljivo; v tem primeru naj program to seveda pove.

4. Kakšna je časovna zahtevnost programa?

5. Poišči (ročno ali s programom) kakšno daljše zaporedje, ki reši nalogo, ne da bi pri tem kakšno kombinacijo ponovili večkrat.

6. Če imamo n stikal, je možnih kombinacij 2ⁿ. Od tega odštejmo prvo in vseh k prepovedanih. Ob predpostavki, da obstaja le ena kombinacija, ki onesposobi bombo, je najdaljša pot (brez ponavljanja kombinacij) dolga 2ⁿ - k - 1. Vendar ni rečeno, da takšna pot v resnici obstaja; morda se vseh možnih kombinacij (z dano začetno, končno in prepovedanimi kombinacijami) preprosto ne da prehoditi, ne da bi katero ponovili. Napiši program, ki preveri, ali takšna kombinacija obstaja.

Nekaj primerov

# Tri stikala
zacetno = "^vv"
koncno = "^^^"
prepovedana = {"^^v", "^v^"}

# Štiri stikala
zacetno = "^vvv"
koncno = "^v^^"
prepovedane = {"vvv^", "^vv^", "^v^v", "^^^v"}

# Pet stikal
zacetno = "vv^^^"
koncno = "^^^v^"
prepovedana = {
    "vv^v^", "^vvv^", "^v^vv", "v^^v^", "^^vv^", "^^^vv",
    "v^^^^", "^v^^^", "^^^^v", "^vv^^", "v^v^^"}

(Tole pa ignorirajte, samo nekaj preskušam... ( x^n + y^n = z^n ) in ( x = {-b \pm \sqrt{b^2-4ac} \over 2a} ) )