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

Поправни први колоквијум 2017. године одржан је 24. априла. Задаци и решења су доступни са странице предмета.

Питања

Питање 1

Пошто немамо много избора за $p$ и $k$ (због услова да $k + p = 6$) можемо да пробамо свако од понуђених решења да видимо које ради. Из услова да је $1 \leq M \leq 2$ добијамо да се у задатку ради о ИЕЕЕ стандарду.

У случају да је $p = 2$ добијамо:

• $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$

Уочимо да се сабирањем ова два броја не може добити број чија мантиса може стати у два бита и наставимо на следећи избор.

У случају да је $p = 3$ добијамо:

• $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$

Пошто мантиса броја C не може стати у три бита, настављамо на следећи избор.

У случају да је $p = 4$ добијамо:

• $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$

Пошто се овај број може сачувати на задатим ширинама тачно решење је под C.

Питање 2

Из поставке задатка имамо:

• $k = 5$
• $p = 6$
• $v = 15 = 2^4 - 1 \implies$ ИЕЕЕ стандард

Први корак је претварање бројева у њихов бинарни облик:

• $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$

Тачан резултат сабирања 23.875 и 5.999 је 29.875, а разлика 29.875 и 30 је 0.126, па је тачан одговор под А.

Питање 3

• На основу структуре op можемо закључити да ће вредности њених чланова бити mul = 0, div = 1, add = 2 и sub = 3.
• Вредности у низу niz на почетку биће [5, 10, 12, 18, 31, ?, ?, ?, ?, ?].
• Унутрашња петља је направљена да гурне све елементе низа тренутно мање од x удесно и онда убаци x на једно место испред последњег броја мањег од x. Након тога се повећа n, што би требало да означава дужину низа до које елементи постоје.

Итерација кроз петљу тече овако:

• i = 0
  • niz[i] % 4 = 5 % 4 = 1 тако да падамо у case div.
  • x := niz[i] * niz[i + 1] = 5 * 10 = 50 (падамо на default)
  • niz[0] := niz[0] - 1 = 4, niz[1] := niz[1] + 1 = 11
  • Пошто је вредност x (50) већа од свих осталих вредности у низу она се гура на крај низа. Стање низа је: [4, 11, 12, 18, 31, 50, ?, ?, ?, ?].
  • n := n + 1 = 6
• i = 1
  • niz[i] % 4 = 11 % 4 = 3 тако да падамо на case sub.
  • x := x / (2 * 10) = 2
    • У овом кораку се претпостави да је величина short типа једнака 2 бајта (иако то нигде није наглашено и не пише у стандарду)
  • i := i + 1 = 2 (број итерација се смањује за један)
  • Унутрашња петља гурне све елементе низа на десно и постави 2 на почетак. Тренутно стање низа је [2, 4, 11, 12, 18, 31, 50, ?, ?, ?].
• i = 3
  • niz[i] % 4 = 12 % 4 = 0 тако да падамо у case mul.
  • x := niz[i + 1] - niz[i] = 18 - 12 = 6
  • Стање низа је исто као и раније.
• i = 4
  • niz[i] % 4 = 18 % 4 = 2 тако да падамо на case add.
  • x := niz[i] + niz[i + 1] = 49 (падамо на case sub и одавде се ствари настављају слично као за i = 1)
  • x := x / 20 = 2
  • i := i + 1
  • Унутрашња петља поново додаје 2 на почетак низа тако да је тренутно стање низа: [2, 2, 4, 11, 12, 18, 31, 50, ?, ?]

Крајњи испис биће познате вредности у низу: 2 2 4 11 12 18 31 50 (одговор под Б).

Питање 4

• M = 8, N = 5
• mask := (1 << 3) - 1 = 4 - 1 = 3
• arr = [53, 156, 86, 13, 4]
  • За потребе задатка нам је лакше да изразимо овај низ као бинарне бројеве, па добијамо: arr = [00110101, 10011100, 01010110, 00001101, 00000100].
• Након прве петље добијамо стање низа c = [2, 2, 0, 1, 0, 0, 0, 0].
• Први члан p је нула а сви остали збир прошлог елемента p и њему одговарајућег елемента из c па је стање низа p = [0, 2, 4, 4, 5, 5, 5, 5].
• Затим се ради испис елемената p сличном операцијом као у првој петљи (два пута ће се исписати прва два елемента а једном четврти) с тим што се исписани чланови низа повећавају за један при сваком испису.

Крајњи испис је 2 0 4 3 1, тако да је тачан одговор под Б.