2. naloga

Luči

Dano je zaporedje n luči; znano je njihovo začetno stanje (katere so prižgane in katere ugasnjene) ter želeno končno stanje. Osnovna operacija, ki jo lahko nad lučmi izvajamo, je, da si izberemo števili i in j (z območja 1 ≤ i ≤ j ≤ n) in spremenimo stanje vseh luči od vključno i-te do vključno j-te (torej ugasnemo tiste med njimi, ki so bile prej prižgane, in prižgemo tiste, ki so bile prej ugasnjene).

Napiši podprogram (oz. funkcijo) Luci(n, zacetno, koncno), ki izpiše zaporedje čim manj takšnih operacij, s katerimi lahko luči iz začetnega stanja spravimo v želeno končno stanje. Za vsako operacijo naj izpiše števili i in j, torej številko prve in zadnje spremenjene luči (luči so oštevilčene od 1 do n). Če obstaja več enako dobrih rešitev z najmanjšim možnim številom operacij, je vseeno, katero izpiše. Kot parametra zacetno in koncno naj tvoj podprogram sprejme niza n znakov, ki opisujeta začetno in končno stanje luči (znak ’P’ predstavlja prižgano luč, znak ’U’ pa ugasnjeno).

Dobro tudi utemelji, zakaj tvoja rešitev res najde najmanjše možno število operacij.

Primer: če imamo n = 7 luči in je začetno stanje UUPPPUP, končno pa UPPUPPU, potrebujemo vsaj tri operacije. Eno od možnih zaporedij treh operacij je: i = 2, j = 5 (dobimo UPUUUUP); i = 4, j = 7 (dobimo UPUPPPU); i = 3, j = 4 (dobimo UPPUPPU).