2. naloga

Zaboji

V skladišču stoji v vrsti n zabojev, ki so oštevilčeni s števili od 1 do n (nobena dva zaboja nimata enake številke), vendar v nekem premešanem vrstnem redu. Na voljo imamo tri operacije, ki jih za nas izvaja sistem robotskih rok v skladišču:

  • zamakni vse zaboje ciklično za eno mesto v levo (pri tem torej zaboj, ki je bil prej najbolj levi, postane najbolj desni);
  • zamakni vse zaboje ciklično za eno mesto v desno (pri tem torej zaboj, ki je bil prej najbolj desni, postane najbolj levi);
  • poberi zadnji zaboj (najbolj desnega) in ga pošlji iz skladišča (npr. v proizvodnjo).

Radi bi s čim manj operacijami pobrali vse zaboje iz skladišča in to v naraščajočem vrstnem redu; najprej hočemo torej dobiti zaboj številka 1, nato zaboj številka 2 in tako naprej, nazadnje pa zaboj številka n. Opiši postopek (ali napiši program ali podprogram oz. funkcijo, če ti je lažje), ki kot vhodne podatke dobi začetni vrstni red zabojev v skladišču in izračuna najmanjše število zgoraj omenjenih operacij, s katerim lahko poberemo vse zaboje iz skladišča v naraščajočem vrstnem redu.

Zaželeno je, da je tvoj postopek čimbolj učinkovit, da bo hitro izračunal potrebno število operacij tudi pri velikih n (npr. več deset tisoč zabojev).

Primer: recimo, da je začetno zaporedje zabojev (od leve proti desni) 4, 1, 3, 5, 2. Najkrajše zaporedje operacij, s katerim lahko dobimo vse zaboje iz skladišča v naraščajočem vrstnem redu, je potem takšno:


Operacija Stanje po njej
(začetno stanje) 4, 1, 3, 5, 2
zamik v levo 1, 3, 5, 2, 4
zamik v levo 3, 5, 2, 4, 1
poberi zadnji zaboj 3, 5, 2, 4
zamik v desno 4, 3, 5, 2
poberi zadnji zaboj 4, 3, 5
zamik v desno 5, 4, 3
poberi zadnji zaboj 5, 4
poberi zadnji zaboj 5
poberi zadnji zaboj (prazno)

Odgovor, ki ga mora v tem primeru izračunati tvoja rešitev, je torej ta, da potrebujemo 9 operacij. Pozor: tvoja rešitev mora delovati za skladišča s poljubnim številom zabojev, ne le s točno petimi zaboji, kolikor jih je pri tem primeru.