АСП1/К1 2020

Zadaci na sajtu predmeta.

1. zadatak

Postavka

Neka je data funkcija random() koja vraća broj 0 ili 1 sa podjednakom verovatnoćom. Objasniti i ilustrovati primerom kako bi se korišćenjem zadate funkcije implementirala funkcija koja vraća vrednost 0 sa verovatnoćom 25%, a sa 1 verovatnoćom od 75%.

Rešenje

U okviru naše nove funkcije pozivamo funkciju random dva puta, i samo u jednom od četiri slučaja, na primer kada oba puta funkcija vrati nulu (00), naša nova funkcija vraća nulu, a za sve ostale slučajeve (01, 10, 11) vraća jedan. Na taj način je obezbeđeno da funkcija vraća 0 sa verovatnoćom 25%, a 1 sa verovatnoćom 75%.

NEW RANDOM()
if (random() = 0) and (random() = 0) then
    return 0
else
    return 1
end_if

2. zadatak

Postavka

Neka je dat stek s1 na kome se nalaze celi brojevi. Korišćenjem dodatnog steka s2, transformisati sadržaj steka s1 tako da on postane neopadajuće uređen niz. Smatrati da su operacije za rad sa stekom već implementirane.

Rešenje

Ideja jeste da na steku s1 imamo sortirani i nesortirani deo. Na početku svi elementi su u nesortiranom delu i određujemo dubinu steka i trenutni maksimum na njemu. Svakom narednom iteracijom sve elemente koji su manji od maksimuma prebacujemo na stek s2, dok sve maksimume izbacujemo sa steka, a zatim naknadno ubacujemo onoliko puta koliko su se pojavili. Na kraju, vraćamo sve ne-maksimalne elemente sa steka s2 nazad u nesortirani deo steka s1, pritom ponovo određujući maksimalni element u nesortiranom delu. Proces se ponavlja dok ima elemenata u maksimalnom delu.

SORT STACK(s1)
max = TOP(s1)
cnt = 0
while (not STACK_IS_EMPTY(s1)) do
    x = POP(s1)
    if (x > max) then
        max = x
    end_if
    PUSH(s2, x)
    cnt = cnt + 1
end_while
while (not STACK_IS_EMPTY(s2)) do
    x = POP(s2)
    PUSH(s1, x)
end_while
while (cnt > 0) do
    num = cnt
    tmp = 0
    while (num > 0) do
        x = POP(s1)
        if (x < max) then
            PUSH(s2, x)
        else
            cnt = cnt - 1
            tmp = tmp + 1
        end_if
        num = num - 1
    end_while
    for i = 1 to tmp do
        PUSH(s1, max)
        i = i + 1
    end_for
    if (cnt > 0) then
        max = TOP(s2)
        while (not STACK_IS_EMPTY(s2)) do
            x = POP(s2)
            if (x > max) then
                max = x
            end_if
            PUSH(s1, x)
        end_while
    end_if
end_while

5. zadatak

Postavka

Data je retko popunjena kvadratna matrica 2N x 2N. Nepodrazumevani elementi matrice smeštaju se u memoriji po vrstama. Indeksiranje kreće od 1, a svaki element matrice zauzima po 2 reči.
a) Izvesti adresnu funkciju za pristup proizvoljnom elementu matrice.
b) Implementirati funkciju GET koja vraća vrednost traženog elementa koji odgovara indeksima i i j matrice A.

Rešenje

$a)$
$A_{ij} = ((i-1)*2+\left\lfloor{(j-1)/N)}\right\rfloor)*2$ ∧ $(i=j$ ∨ $i+j=2N+1)$
$A_{ij} = 0$ ∧ $(i$≠$j$ ∧ $i+j$≠$2N+1)$
$b)$

GET(A, i, j, N)
if (i = j or i + j = 2 * N + 1) then
    return A[i, j]
else 
    return 0
end_if