4. naloga
Pisalni stroj
Imamo pisalni stroj, ki deluje tako, da se ob vsakem izpisu znaka nujno pomakne za eno mesto v desno. (Eden od teh znakov je tudi presledek, ki sicer ne izpiše ničesar, nas pa ravno tako premakne za eno mesto v desno.) Poleg tega obstaja tudi tipka za pomik na začetek trenutne vrstice (carriage return). Drugih možnosti za premik v levo nimamo. Radi bi napisali neko vrstico tako, da bo ponekod na istem mestu več črk ena čez drugo (npr. da kaj podčrtamo z znakom _, prekrižamo z znakom x, dodamo kakšno naglasno znamenje nad črko in podobno). Recimo, da bo vrstica na koncu dolga n znakov, pri čemer hočemo na mestu i natipkati ai znakov. Opiši postopek, ki iz teh podatkov (torej števil n, a1, a2, ... , an) izračuna, kolikšno je najmanjše število pritiskov na tipke (med pritiske šteje tudi pomik na začetek vrstice), ki jih potrebujemo, da natipkamo to vrstico. Pri tem ni pomembno, kje v vrstici se nahajamo na koncu tipkanja. Tvoja rešitev naj bo čim bolj učinkovita, da bo delovala hitro tudi v primerih, ko so n in števila ai zelo velika.
Primer. Recimo, da hočemo natipkati takšno vrstico dolžine n = 6:
Tabela a bi bila torej v tem primeru takšna:
| i | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| ai | 2 | 1 | 3 | 0 |
2 | 1 |
4. naloga
Pisalni stroj
Imamo pisalni stroj, ki deluje tako, da se ob vsakem izpisu znaka nujno pomakne za eno mesto v desno. (Eden od teh znakov je tudi presledek, ki sicer ne izpiše ničesar, nas pa ravno tako premakne za eno mesto v desno.) Poleg tega obstaja tudi tipka za pomik na začetek trenutne vrstice (carriage return). Drugih možnosti za premik v levo nimamo. Radi bi napisali neko vrstico tako, da bo ponekod na istem mestu več črk ena čez drugo (npr. da kaj podčrtamo z znakom _, prekrižamo z znakom x, dodamo kakšno naglasno znamenje nad črko in podobno). Recimo, da bo vrstica na koncu dolga n znakov, pri čemer hočemo na mestu i natipkati ai znakov. Opiši postopek, ki iz teh podatkov (torej števil n, a1, a2, ... , an) izračuna, kolikšno je najmanjše število pritiskov na tipke (med pritiske šteje tudi pomik na začetek vrstice), ki jih potrebujemo, da natipkamo to vrstico. Pri tem ni pomembno, kje v vrstici se nahajamo na koncu tipkanja. Tvoja rešitev naj bo čim bolj učinkovita, da bo delovala hitro tudi v primerih, ko so n in števila ai zelo velika.
Primer. Recimo, da hočemo natipkati takšno vrstico dolžine n = 6:
Tabela a bi bila torej v tem primeru takšna:
| i | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| ai | 2 | 1 | 3 | 0 |
2 | 1 |