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

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

Задатак

#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;
}

Питања

Питање 1

• Из ограничења мантисе можемо видети да се ради о ВАX стандарду.
• $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$

Можемо видети на основу цифара мантисе броја $C$ да би p морало да буде барем 9 како би све цифре стале.

Такође, на основу експонената бројева $A$, $B$ и $C$ можемо закључити да $E$ мора да укључује 5, 6 и 7 у свој опсег. Испробавањем различитих вредности $k$ добијамо да за вредност $k = 4$ вишак има вредност $v = 2^3 = 8$ а вредности $e$ на четири бита иду од 0 до 15, па је опсег $E \in [0-v, 15-v] \implies E \in [-8, 7]$ и вредности 5, 6 и 7 јесу у том опсегу.

Тачан одговор је стога под А.

Питање 3

• a := 0
• b := 15
• k := 32
• n := 15
• Услов b < 16 је испуњен а услов b % 3 се евалуира на 0, тако да се извршава else грана унутрашњег if-а, тако да је k := 5.
• n := n + k = 15 + 5 = 20

Извршавање петље тече овако:

• i = 0
  • i % b = 0 % 15 = 0 па падамо на default и настављамо у следећу итерацију. Ово се дешава за сваки број чији модуо по 15 није 4, 9 или 14.
• i = 4 (падамо у case 4)
  • a := a + 2 = 2
  • a := a / 2 = 1
• i = 9 (падамо у case 9)
  • a := a + 3 = 4
  • a := a / 2 = 2
• i = 14 (падамо у case 14)
  • a := a + 4 = 6 (падамо у case 9)
  • a := a + 3 = 9
  • a := a / 2 = 4
• i = 19 (падамо у case 4)
  • a := a + 2 = 6
  • a := a / 2 = 3

Крајњи резултат је a = 3, тако да је тачан одговор под Б.

Питање 4

• Стање низа arr на почетку је [40, 17, 14, 21, 0]. Пошто нам више одговара када би овај низ био у бинарном формату (због бинарних операција које ћемо над њим извршавати), можемо га изразити као [00101000, 00010001, 00001110, 00010101, 00000000].
• n := 5
• Можемо приметити да се петља неће извршавати над елементима низа који су непарни (последњи бит им је 1).

Извршавање петље тече овако:

• i = 0
  • c := 1
  • v := arr[i] = 00101000
  • v & 0xff = 00101000 & 11111111 = 101000 != 0 (први if се неће извршити)
  • v & 0xf = 00101000 & 00001111 = 1000 != 0 (други if се неће извршити)
  • v & 0x3 = 00101000 & 00000011 = 0 (трећи if ће се извршити)
  • v := v >> 2 = 1010 (v := 10)
  • c := c + 2 = 3
  • c := c - (v & 0x1) = 3 - (1010 & 0001) = 3 - 0 = 3
  • Исписује се 3.
• i = 1
  • Број је непаран па се прескаче
• i = 2
  • c := 1
  • v := arr[i] = 00001110
  • v & 0xff = 00001110 & 11111111 = 00001110 != 0 (први if се неће извршити)
  • v & 0xf = 00001110 & 00001111 = 1110 != 0 (други if се неће извршити)
  • v & 0x3 = 00001110 & 00000011 = 10 != 0 (трећи if се неће извршити)
  • c := c - (v & 0x1) = 1 - (1110 & 0001) = 1 - 0 = 1
  • Исписује се 1.
• i = 3
  • Број је непаран па се прескаче
• i = 4
  • c := 1
  • v := arr[i] = 0
  • Сви if-ови ће се извршити јер је битовско I са нулом увек нула.
  • c := c + 8 + 4 + 2 = 15
  • c := c - (v & 0x1) = 15 - 0 = 15
  • Исписује се 15.

На крају је исписано 3 1 15 тако да је тачан одговор под Б.