Програмирање 2/К1П 2017

Popravni prvi kolokvijum 2017. godine održan je 24. aprila. Zadaci i rešenja su dostupni sa stranice predmeta.

Pitanja

Pitanje 1

Pošto nemamo mnogo izbora za $p$ i $k$ (zbog uslova da $k + p = 6$) možemo da probamo svako od ponuđenih rešenja da vidimo koje radi. Iz uslova da je $1 \leq M \leq 2$ dobijamo da se u zadatku radi o IEEE standardu.

U slučaju da je $p = 2$ dobijamo:

• $k = 4$
• $v = 2^3 - 1 = 7$
• $m_A = 01_2$, $M_A = 1.01_2$
• $e_A = 1101_2 = 13$, $E_A = e_A - v = 6$
• $A = 1.01_2 \cdot 2^6$
• $m_B = 00_2$, $M_B = 1_2$
• $e_B = 0111_2 = 7$, $E_B = e_B - v = 0$
• $B = 1 = 0.000001_2 \cdot 2^6$

Uočimo da se sabiranjem ova dva broja ne može dobiti broj čija mantisa može stati u dva bita i nastavimo na sledeći izbor.

U slučaju da je $p = 3$ dobijamo:

• $k = 3$
• $v = 2^2 - 1 = 3$
• $m_A = 101_2$, $M_A = 1.101_2$
• $e_A = 110_2 = 6$, $E_A = e_A - v = 3$
• $A = 1.101_2 \cdot 2^3$
• $m_B = 100_2$, $M_B = 1.100_2$
• $e_B = 011_2 = 3$, $E_B = e_B - v = 0$
• $B = 1.1_2 = 0.001100 \cdot 2^3$
• $C = A + B = 1.111100_2 \cdot 2^3$

Pošto mantisa broja C ne može stati u tri bita, nastavljamo na sledeći izbor.

U slučaju da je $p = 4$ dobijamo:

• $k = 2$
• $v = 2^1 - 1 = 1$
• $m_A = 0101_2$, $M_A = 1.0101_2$
• $e_A = 11_2 = 3$, $E_A = e_A - v = 2$
• $A = 1.0101_2 \cdot 2^2$
• $m_B = 1100_2$, $M_B = 1.11_2$
• $e_B = 01_2 = 1$, $E_B = e_B - v = 0$
• $B = 1.11 = 0.0111 \cdot 2^2$
• $C = A + B = 1.11_2 \cdot 2^2$

Pošto se ovaj broj može sačuvati na zadatim širinama tačno rešenje je pod C.

Pitanje 2

Iz postavke zadatka imamo:

• $k = 5$
• $p = 6$
• $v = 15 = 2^4 - 1 \implies$ IEEE standard

Prvi korak je pretvaranje brojeva u njihov binarni oblik:

• $A = 23.875 = 23 + 0.875 = 10111_2 + 0.111_2 = 10111.111_2 = 1.0111111_2 \cdot 2^4 \approx 1.1_2 \cdot 2^4$
• $B = 5.999 = 101.111_2... = 1.01111_2... \cdot 2^2 \approx 1.1_2 \cdot 2^4 = 0.011_2 \cdot 2^4$
• $A + B = (1.1_2 + 0.011_2) \cdot 2^4 = 1.111_2 \cdot 2^4 = 11110_2 = 30$

Tačan rezultat sabiranja 23.875 i 5.999 je 29.875, a razlika 29.875 i 30 je 0.126, pa je tačan odgovor pod A.

Pitanje 3

• Na osnovu strukture op možemo zaključiti da će vrednosti njenih članova biti mul = 0, div = 1, add = 2 i sub = 3.
• Vrednosti u nizu niz na početku biće [5, 10, 12, 18, 31, ?, ?, ?, ?, ?].
• Unutrašnja petlja je napravljena da gurne sve elemente niza trenutno manje od x udesno i onda ubaci x na jedno mesto ispred poslednjeg broja manjeg od x. Nakon toga se poveća n, što bi trebalo da označava dužinu niza do koje elementi postoje.

Iteracija kroz petlju teče ovako:

• i = 0
  • niz[i] % 4 = 5 % 4 = 1 tako da padamo u case div.
  • x := niz[i] * niz[i + 1] = 5 * 10 = 50 (padamo na default)
  • niz[0] := niz[0] - 1 = 4, niz[1] := niz[1] + 1 = 11
  • Pošto je vrednost x (50) veća od svih ostalih vrednosti u nizu ona se gura na kraj niza. Stanje niza je: [4, 11, 12, 18, 31, 50, ?, ?, ?, ?].
  • n := n + 1 = 6
• i = 1
  • niz[i] % 4 = 11 % 4 = 3 tako da padamo na case sub.
  • x := x / (2 * 10) = 2
    • U ovom koraku se pretpostavi da je veličina short tipa jednaka 2 bajta (iako to nigde nije naglašeno i ne piše u standardu)
  • i := i + 1 = 2 (broj iteracija se smanjuje za jedan)
  • Unutrašnja petlja gurne sve elemente niza na desno i postavi 2 na početak. Trenutno stanje niza je [2, 4, 11, 12, 18, 31, 50, ?, ?, ?].
• i = 3
  • niz[i] % 4 = 12 % 4 = 0 tako da padamo u case mul.
  • x := niz[i + 1] - niz[i] = 18 - 12 = 6
  • Stanje niza je isto kao i ranije.
• i = 4
  • niz[i] % 4 = 18 % 4 = 2 tako da padamo na case add.
  • x := niz[i] + niz[i + 1] = 49 (padamo na case sub i odavde se stvari nastavljaju slično kao za i = 1)
  • x := x / 20 = 2
  • i := i + 1
  • Unutrašnja petlja ponovo dodaje 2 na početak niza tako da je trenutno stanje niza: [2, 2, 4, 11, 12, 18, 31, 50, ?, ?]

Krajnji ispis biće poznate vrednosti u nizu: 2 2 4 11 12 18 31 50 (odgovor pod B).

Pitanje 4

• M = 8, N = 5
• mask := (1 << 3) - 1 = 4 - 1 = 3
• arr = [53, 156, 86, 13, 4]
  • Za potrebe zadatka nam je lakše da izrazimo ovaj niz kao binarne brojeve, pa dobijamo: arr = [00110101, 10011100, 01010110, 00001101, 00000100].
• Nakon prve petlje dobijamo stanje niza c = [2, 2, 0, 1, 0, 0, 0, 0].
• Prvi član p je nula a svi ostali zbir prošlog elementa p i njemu odgovarajućeg elementa iz c pa je stanje niza p = [0, 2, 4, 4, 5, 5, 5, 5].
• Zatim se radi ispis elemenata p sličnom operacijom kao u prvoj petlji (dva puta će se ispisati prva dva elementa a jednom četvrti) s tim što se ispisani članovi niza povećavaju za jedan pri svakom ispisu.

Krajnji ispis je 2 0 4 3 1, tako da je tačan odgovor pod B.