ASP1/K1 2020
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
3. zadatak
Postavka
Posmatra se retka matrica A veličine NxM. Matrica je data u vidu kružnih ulančanih listi sa zaglavljima RA i CA. Napisati efikasnu iterativnu funkciju u pseudokodu koja datu matricu pretvara u vektorski format sa tri posebna vektora R, C i V. Funkcija takođe treba da vrati broj nenultih elemenata u matrici. Smatrati da je za sve vektore inicijalno rezervisano dovoljno prostora.
Rešenje
REFORMAT SPARSE MAT(A, N, M, Ra, Ca, R, C, V)
cnt = 1
for i = 1 to N do
curr = next(Ra[i])
R[i] = cnt
while (curr ≠ Ra[i]) do
C[cnt] = col(curr)
V[cnt] = val(curr)
cnt = cnt + 1
curr = next(curr)
end_while
end_for
R[N + 1] = cnt + 1
return cnt
4. zadatak
Postavka
Transformisati izraz u infiksnom obliku
- A+C^(D-E!)!^F*B-C+G*H
u ekvivalentni izraz u postfiksnoj formi. Tabelu prioriteta operatora dopuniti odgovarajućim vrednostima, pri čemu je operacija faktorijel ! unarna operacija koja se grupiše sleva na desno i ima najveći prioritet od svih aritmetičkih operacija, a operacija ^ je operacija stepenovanja i grupiše se sdesna na levo. Transformaciju izraza prikazati po koracima.
Rešenje
| operator | ul. pr | stek pr. | R |
|---|---|---|---|
| +, - | 2 | 2 | -1 |
| *, / | 3 | 3 | -1 |
| ^ | 5 | 4 | -1 |
| ! | 6 | 6 | 0 |
| ( | 7 | 0 | - |
| ) | 1 | - | - |
Postfiksna forma datog infiksnog izraza koji se dobije primenom algoritma za konverziju iz infiksa u postfiks je:
- ACDE!-!F^^B*+C-GH*+
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.
- Izvesti adresnu funkciju za pristup proizvoljnom elementu matrice.
- Implementirati funkciju GET koja vraća vrednost traženog elementa koji odgovara indeksima i i j matrice A.
Rešenje
- GET(A, i, j, N)
if (i = j or i + j = 2 * N + 1) then
return A[i, j]
else
return 0
end_if
6. zadatak
Postavka
U nekom azilu za životinje su zbrinuti psi, mačke i kanarinci. Kada neko želi da usvoji životinju, on se može izjasniti da li želi psa, mačku, kanarinca ili mu je svejedno. Nije moguće uputiti zahtev za određenom (pojedinačnom) životinjom već u skladu sa odabirom vrste, biće dodeljena ili životinja tražene vrste koja je najduže u azilu, ako takva postoji, ili životinja koja je tu duže od svih drugih. Takođe, azil prihvata nove životinje dok se ne popuni kapacitet.
- Ukratko objasniti koja struktura se koristi za modelovanje azila i kako se ona održava sa dolaskom i usvajanjem životinja.
- Prikazati kako će struktura usvojena pod a) izgledati nakon usvajanja jednog psa, ako je prikazano trenutno stanje životinja u azilu po boksovima u kojima su smešteni. Pored vrste životinje, radi ilustracije, u zagradi se nalazi i trenutno vreme boravka životinje u azilu.
- M(2) K(1) P(6) P(3) M(6) M(7) K(5) P(3)
Rešenje
- Овај задатак није решен. Помозите SI Wiki тако што ћете га решити.
7. zadatak
Postavka
U nekom programu je potrebno prestaviti skup celih brojeva u opsegu od 0 do 999. Neka su u programskom jeziku koji se koristi na raspolaganju celobrojni tipovi na 4 bajta širine, a pokazivači zauzimaju 4 bajta. Objasniti na koje načine se ovakav skup može predstaviti sekvencijalnom i ulančanom reprezantacijom, a zatim odrediti prosečno zauzeće prostora u oba slučaja pod pretpostavkom da se u skupu u proseku nalazi 10 elemenata.
Rešenje
- Овај задатак није решен. Помозите SI Wiki тако што ћете га решити.
8. zadatak
Postavka
Napisati u pseudokodu implementaciju funkcije koja u dvostruko ulančanu listu celih brojeva na koju ukazuje pokazivač list ubacuje vrednost x ispred elementa na koji ukazuje pokazivač node. Voditi računa da lista ostane u potpuno konzistentnom stanju.
Rešenje
Pretpostavljamo da je node validan pokazivač na element koji se nalazi u listi list.
INSERT BEFORE D(list, node, x) new_node = Node(x) new_node.prev = node.prev new_node.next = node if node.prev == null list = new_node else node.prev.next = new_node node.prev = new_node