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

Prvi kolokvijum 2017. godine održan je 20. marta. Zadaci i rešenja su dostupni sa stranice predmeta.

Zadatak

#include <stdio.h>
#define LIMIT 30

int main() {

	char num[LIMIT] = { 0 }, c;
	int cnt = 0, dotOccured= 0;

	while (cnt <= LIMIT) {
		do {
			c = getchar();
		} while (c!='1' && c!='0' && c!='.' && c!='\n' || dotOccured && c=='.'); //1 0 . '\n' su dozvoljeni
		
		if (c == '\n')
			break;
		else if (!dotOccured && c == '.' ) {
			dotOccured = 1;
		}
		num[cnt++] = c;
	}
	printf("%s", num);
	
	//obrada

	double whole = 0;

	for (int i = 0; i < cnt && num[i] !='.'; i++) {
		whole = whole * 2 + num[i] - '0';
	}
	double frac = 0;
	if (dotOccured) {
		
		for (int i = cnt - 1; i >= 0 && num[i] != '.'; i--) {
			frac = (double)(frac + num[i] - '0') / 2;
		}
	}
	
	printf("\n%.3lf", whole + frac);
	
	return 0;
}

Pitanja

Pitanje 1

• Iz ograničenja mantise možemo videti da se radi o VAX standardu.
• $A = 37.375 = 37 + 0.375 = 100101_2 + 0.011_2 = 100101.011_2 = 0.100101011 \cdot 2^6$
• $B = 29.25 = 29 + 0.25 = 11101_2 + 0.01_2 = 11101.01_2 = 0.1110101_2 \cdot 2^5 = 0.01110101_2 \cdot 2^6$
• $C = A + B = (0.1110101_2 + 0.01110101_2) \cdot 2^6 = 1.000010101_2 \cdot 2^6 = 0.1000010101_2 \cdot 2^7$

Možemo videti na osnovu cifara mantise broja $C$ da bi p moralo da bude barem 9 kako bi sve cifre stale.

Takođe, na osnovu eksponenata brojeva $A$, $B$ i $C$ možemo zaključiti da $E$ mora da uključuje 5, 6 i 7 u svoj opseg. Isprobavanjem različitih vrednosti $k$ dobijamo da za vrednost $k = 4$ višak ima vrednost $v = 2^3 = 8$ a vrednosti $e$ na četiri bita idu od 0 do 15, pa je opseg $E \in [0-v, 15-v] \implies E \in [-8, 7]$ i vrednosti 5, 6 i 7 jesu u tom opsegu.

Tačan odgovor je stoga pod A.

Pitanje 3

• a := 0
• b := 15
• k := 32
• n := 15
• Uslov b < 16 je ispunjen a uslov b % 3 se evaluira na 0, tako da se izvršava else grana unutrašnjeg if-a, tako da je k := 5.
• n := n + k = 15 + 5 = 20

Izvršavanje petlje teče ovako:

• i = 0
  • i % b = 0 % 15 = 0 pa padamo na default i nastavljamo u sledeću iteraciju. Ovo se dešava za svaki broj čiji moduo po 15 nije 4, 9 ili 14.
• i = 4 (padamo u case 4)
  • a := a + 2 = 2
  • a := a / 2 = 1
• i = 9 (padamo u case 9)
  • a := a + 3 = 4
  • a := a / 2 = 2
• i = 14 (padamo u case 14)
  • a := a + 4 = 6 (padamo u case 9)
  • a := a + 3 = 9
  • a := a / 2 = 4
• i = 19 (padamo u case 4)
  • a := a + 2 = 6
  • a := a / 2 = 3

Krajnji rezultat je a = 3, tako da je tačan odgovor pod B.

Pitanje 4

• Stanje niza arr na početku je [40, 17, 14, 21, 0]. Pošto nam više odgovara kada bi ovaj niz bio u binarnom formatu (zbog binarnih operacija koje ćemo nad njim izvršavati), možemo ga izraziti kao [00101000, 00010001, 00001110, 00010101, 00000000].
• n := 5
• Možemo primetiti da se petlja neće izvršavati nad elementima niza koji su neparni (poslednji bit im je 1).

Izvršavanje petlje teče ovako:

• i = 0
  • c := 1
  • v := arr[i] = 00101000
  • v & 0xff = 00101000 & 11111111 = 101000 != 0 (prvi if se neće izvršiti)
  • v & 0xf = 00101000 & 00001111 = 1000 != 0 (drugi if se neće izvršiti)
  • v & 0x3 = 00101000 & 00000011 = 0 (treći if će se izvršiti)
  • v := v >> 2 = 1010 (v := 10)
  • c := c + 2 = 3
  • c := c - (v & 0x1) = 3 - (1010 & 0001) = 3 - 0 = 3
  • Ispisuje se 3.
• i = 1
  • Broj je neparan pa se preskače
• i = 2
  • c := 1
  • v := arr[i] = 00001110
  • v & 0xff = 00001110 & 11111111 = 00001110 != 0 (prvi if se neće izvršiti)
  • v & 0xf = 00001110 & 00001111 = 1110 != 0 (drugi if se neće izvršiti)
  • v & 0x3 = 00001110 & 00000011 = 10 != 0 (treći if se neće izvršiti)
  • c := c - (v & 0x1) = 1 - (1110 & 0001) = 1 - 0 = 1
  • Ispisuje se 1.
• i = 3
  • Broj je neparan pa se preskače
• i = 4
  • c := 1
  • v := arr[i] = 0
  • Svi if-ovi će se izvršiti jer je bitovsko I sa nulom uvek nula.
  • c := c + 8 + 4 + 2 = 15
  • c := c - (v & 0x1) = 15 - 0 = 15
  • Ispisuje se 15.

Na kraju je ispisano 3 1 15 tako da je tačan odgovor pod B.