Naloga: unbreak

Odstranite uporabo break v naslednjem programu:

i = 2;
while (i < n) {
    if (n % i == 0) {
        break;
    } else { }
    i := i + 1;
}
if (i == n) {
    print("je praštevilo");
} else {
    print("ni praštevilo");
}

Rešitev

i = 2;
stop = false;
while (!stop && (i < n)) {
    if (n % i == 0) {
        stop = true;
    } else { }
    if (!stop) {
        i := i + 1;
    } else { }
}
stop = false;
if (i == n) {
    print("je praštevilo");
} else {
    print("ni praštevilo");
}

Naloga: kako odpravimo aritmetični pogojni stavek?

V programskem jeziku C poznamo operator

p ? a : b

katerega intuitivni pomen je "če velja p, potem je vrednost a, sicer je vrednost b".

Obravnavajmo primer, ko sta a in b celoštevilska izraza, p pa je oblike u == 0, kjer je u celoštevilski izraz, se pravi

(u == 0) ? a : b

Ali lahko zapišemo enakovredni izraz, ki uporablja samo operacije +, -, *, max in min?

Rešitev

(u == 0) ? a : b → (1-min(u², 1))*a + min(u², 1)*b

Naloga: Timotej izumi when

Timotej je definiral nov pogojni stavek when, ki je kakor običajni pogojni stavek, le da nima else. Se pravi, stavek pišemo takole:

when ⟨pogoj⟩ do ⟨ukaz⟩ done

Podnaloga: Razširite abstraktno sintakso ukaznega jezika (najdete jo v zapiskih s predavanj) tako, da bo vsebovala tudi pravilo za stavek when.

Podnaloga: Razširite operacijsko semantiko ukaznega jezika (najdete jo v zapiskih s predavanj) tako, da bo vsebovala tudi pravilo za izvajanje stavka when.

Naloga: Peter se znebi if

Peter je ugotovil, da lahko stavek when is prešnje naloge izrazi s pomočjo if. Namreč,

when ⟨pogoj⟩ do ⟨ukaz⟩ done

je ekvivalentno

if ⟨pogoj⟩ then ⟨ukaz⟩ else skip end

A velja tudi, da lahko program, ki uporablja stavke if predelamo v ekvivalentni program, ki uporablja samo stavke when. Petru pojasni, kako to naredimo.

Rešitev

unif(if p then a else b) =
    p' = p ;
    when p do a done ;
    when (!p') do b done

Pogoj p skopiramo, ker se lahko znotraj ukaza a spremeni.

Naloga: Boolova logika s števili

Andrej ne mara Boolovih vrednosti, zato uporablja število 0 namesto false in število 1 namesto true. To pa pomeni, da mora namesto logičnih operacij && in || uporabljati ustrezne aritmetične izraze. Pomagajte mu!

Podnaloga: Denimo, da število x in y predstavljata Boolovi vrednosti. Zapišite aritmetični izraz, ki predstavlja:

  1. disjunkcijo x in y
  2. konjunkcijo x in y
  3. negacijo x.

Uporabljati smete x, y, seštevanje, odštevanje, množenje in konstante.

Podnaloga: Denimo, da sta a in b celi števili. Zapišite aritmetični izraz, ki predstavlja enakost a in b. To pomeni, da mora biti izraz enak 1, če sta a in b enaka, sicer mora biti enak 0. Uporabiti smete a, b, seštevanje, odštevanje, množenje, min, max in konstante.

Podnaloga: Ali bi nalogo lahko rešili brez uporabe min in max?

Rešitev

unbool(x ∧ y) = x * y
unbool(x ∨ y) = x + y - x*y
unbool(¬x) = 1 - x

unbool(a == b) = 1 - min((a-b)*(a-b), 1)

Naloge ne moremo rešiti brez uporabe min ali max. Z ostalimi operacijami (seštevanje, množenje in konstante) lahko namreč definiramo samo polinome – zato ne moremo definirati funkcije, ki bi imela vrednost nič povsod razen v eni točki (pri a == b).

마지막 수정됨: 금요일, 3 3월 2023, 11:18 AM