АСП1/К1 2020 - Историја измена

KockaBot: Замена начина истицања милокода.

2024-09-13T00:08:44Z

Замена начина истицања милокода.

← Старија измена		Верзија на датум 13. септембар 2024. у 02:08
Ред 8:		Ред 8:
	=== Rešenje ===		=== 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%.		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%.
	<~~syntaxhighlight lang="milo"~~>		{{Милокод\|<nowiki>
	NEW RANDOM()		NEW RANDOM()
	if (random() = 0) and (random() = 0) then		if (random() = 0) and (random() = 0) then
Ред 15:		Ред 15:
	return 1		return 1
	end_if		end_if
	</~~syntaxhighlight~~>		</nowiki>}}

	== 2. zadatak ==		== 2. zadatak ==
Ред 23:		Ред 23:
	=== Rešenje ===		=== 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.		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.
	<~~syntaxhighlight lang="milo"~~>		{{Милокод\|<nowiki>
	SORT STACK(s1)		SORT STACK(s1)
	max = TOP(s1)		max = TOP(s1)
Ред 67:		Ред 67:
	end_if		end_if
	end_while		end_while
	</~~syntaxhighlight~~>		</nowiki>}}

	== 3. zadatak ==		== 3. zadatak ==
Ред 74:		Ред 74:

	=== Rešenje ===		=== Rešenje ===
	<~~syntaxhighlight lang="milo"~~>		{{Милокод\|<nowiki>
	REFORMAT SPARSE MAT(A, N, M, Ra, Ca, R, C, V)		REFORMAT SPARSE MAT(A, N, M, Ra, Ca, R, C, V)
	cnt = 1		cnt = 1
Ред 89:		Ред 89:
	R[N + 1] = cnt + 1		R[N + 1] = cnt + 1
	return cnt		return cnt
	</~~syntaxhighlight~~>		</nowiki>}}

	== 4. zadatak ==		== 4. zadatak ==
Ред 138:		Ред 138:
	0 & i \neq j \land i+j \neq 2N+1		0 & i \neq j \land i+j \neq 2N+1
	\end{array}\right.</math>		\end{array}\right.</math>
	# <~~syntaxhighlight lang="milo"~~>		# {{Милокод\|<nowiki>
	GET(A, i, j, N)		GET(A, i, j, N)
	if (i = j or i + j = 2 * N + 1) then		if (i = j or i + j = 2 * N + 1) then
Ред 145:		Ред 145:
	return 0		return 0
	end_if		end_if
	</~~syntaxhighlight~~>		</nowiki>}}
	</div>		</div>

Ред 173:		Ред 173:
	=== Rešenje ===		=== Rešenje ===
	Pretpostavljamo da je ''node'' validan pokazivač na element koji se nalazi u listi ''list''.		Pretpostavljamo da je ''node'' validan pokazivač na element koji se nalazi u listi ''list''.
	<~~syntaxhighlight lang="milo"~~>		{{Милокод\|<nowiki>
	INSERT BEFORE D(list, node, x)		INSERT BEFORE D(list, node, x)
	new_node = Node(x)		new_node = Node(x)
Ред 183:		Ред 183:
	node.prev.next = new_node		node.prev.next = new_node
	node.prev = new_node		node.prev = new_node
	</~~syntaxhighlight~~>		</nowiki>}}

	[[Категорија:Рокови]]		[[Категорија:Рокови]]
	[[Категорија:АСП1]]		[[Категорија:АСП1]]

Lukahrvacevic: /* 8. zadatak */

2022-02-20T15:48:04Z

8. zadatak

← Старија измена		Верзија на датум 20. фебруар 2022. у 17:48
Ред 172:		Ред 172:

	=== Rešenje ===		=== Rešenje ===
	~~{{delimično rešeno}}~~		Pretpostavljamo da je ''node'' validan pokazivač na element koji se nalazi u listi ''list''.
	<syntaxhighlight lang="milo">		<syntaxhighlight lang="milo">
	INSERT BEFORE D(list, node, x)		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
	</syntaxhighlight>		</syntaxhighlight>

	[[Категорија:Рокови]]		[[Категорија:Рокови]]
	[[Категорија:АСП1]]		[[Категорија:АСП1]]

KockaAdmiralac: Delimično rešeno

2021-12-12T20:37:50Z

Delimično rešeno

@@ Ред 147: / Ред 147: @@
 </syntaxhighlight>
 </div>
 [[Категорија:Рокови]]
 [[Категорија:АСП1]]

KockaAdmiralac: Formatiranje

2021-09-06T00:33:07Z

Formatiranje

← Старија измена		Верзија на датум 6. септембар 2021. у 02:33
Ред 71:		Ред 71:
	== 3. zadatak ==		== 3. zadatak ==
	=== Postavka ===		=== Postavka ===
	Posmatra se retka matrica ~~<math>~~A~~</math>~~ veličine ~~<math>N</math>x<math>M</math>~~. 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.		Posmatra se retka matrica A veličine NxM. Matrica je data u vidu kružnih ulančanih listi sa zaglavljima R<sub>A</sub> i C<sub>A</sub>. 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 ===
	<syntaxhighlight lang="milo">		<syntaxhighlight lang="milo">
	REFORMAT SPARSE MAT(A, N, M, Ra, Ca, R, C, V)		REFORMAT SPARSE MAT(A, N, M, Ra, Ca, R, C, V)
	cnt = 1		cnt = 1
	for i = 1 to N do		for i = 1 to N do
	curr = ~~right~~(Ra[i])		curr = next(Ra[i])
	R[i] = cnt		R[i] = cnt
	while (curr ≠ Ra[i]) do		while (curr ≠ Ra[i]) do
Ред 82:		Ред 84:
	V[cnt] = val(curr)		V[cnt] = val(curr)
	cnt = cnt + 1		cnt = cnt + 1
	curr = ~~right~~(curr)		curr = next(curr)
	end_while		end_while
	end_for		end_for
Ред 91:		Ред 93:
	== 4. zadatak ==		== 4. zadatak ==
	=== Postavka ===		=== Postavka ===
	Transformisati izraz u infiksnom obliku A+C^(D-E!)!^FB-C+GH 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.		Transformisati izraz u infiksnom obliku
			: A+C^(D-E!)!^FB-C+GH
			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 ===
	{\| class="wikitable"		{\| class="wikitable"
	! operator		! operator
Ред 114:		Ред 120:
	\| 1 \|\| - \|\| -		\| 1 \|\| - \|\| -
	\|}		\|}

	~~=== Rešenje ===~~
	Postfiksna forma datog infiksnog izraza koji se dobije primenom algoritma za konverziju iz infiksa u postfiks je:		Postfiksna forma datog infiksnog izraza koji se dobije primenom algoritma za konverziju iz infiksa u postfiks je:
	ACDE!-!F^^B+C-GH+		: ACDE!-!F^^B+C-GH+

	== 5. zadatak ==		== 5. zadatak ==
	=== Postavka ===		=== 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.		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.
	<br>a) Izvesti adresnu funkciju za pristup proizvoljnom elementu matrice.		<div class="abc-list">
	~~<br>b)~~ Implementirati funkciju GET koja vraća vrednost traženog elementa koji odgovara indeksima i i j matrice A.		# 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''.
			</div>

	=== Rešenje ===		=== Rešenje ===
	<~~math>a)</math><br~~><math>A_{ij} = A_{11} + ((i-1)2+\left\lfloor{(j-1)/N)}\right\rfloor)2~~</math> ∧ <math>(~~i=j~~</math> ∨ <math>~~i+j=2N+1~~)</math> <br>~~		<div class="abc-list">
	~~<math>A_{ij} =~~ 0~~</math> ∧ <math>(~~i~~</math>≠<math>~~j~~</math> ∧ <math>~~i+j~~</math>≠<math>~~2N+1~~)</math>~~		# <math>A_{ij} = \left\{
	~~<br><br><math>b)~~</math>		\begin{array}{ll}
	~~<br>~~		A_{11} + ((i-1) \cdot 2+\left\lfloor{(j-1)/N)}\right\rfloor) \cdot 2 & i=j \lor i+j=2N+1 \\
	<syntaxhighlight lang="milo">		0 & i \neq j \land i+j \neq 2N+1
			\end{array}\right.</math>
			# <syntaxhighlight lang="milo">
	GET(A, i, j, N)		GET(A, i, j, N)
	if (i = j or i + j = 2 * N + 1) then		if (i = j or i + j = 2 * N + 1) then
Ред 138:		Ред 146:
	end_if		end_if
	</syntaxhighlight>		</syntaxhighlight>
			</div>

	[[Категорија:Рокови]]		[[Категорија:Рокови]]
	[[Категорија:АСП1]]		[[Категорија:АСП1]]

Etfsibg у 13:23, 4. септембар 2021.

2021-09-04T13:23:44Z

@@ Ред 68: / Ред 68: @@
 end_while
 </syntaxhighlight>
 == 5. zadatak ==

Etfsibg: /* Rešenje */

2021-08-27T09:09:15Z

Rešenje

← Старија измена		Верзија на датум 27. август 2021. у 11:09
Ред 76:		Ред 76:

	=== Rešenje ===		=== Rešenje ===
	<math>a)</math><br><math>A_{ij} = ((i-1)2+\left\lfloor{(j-1)/N)}\right\rfloor)2</math> ∧ <math>(i=j</math> ∨ <math>i+j=2N+1)</math> <br>		<math>a)</math><br><math>A_{ij} = A_{11} + ((i-1)2+\left\lfloor{(j-1)/N)}\right\rfloor)2</math> ∧ <math>(i=j</math> ∨ <math>i+j=2N+1)</math> <br>
	<math>A_{ij} = 0</math> ∧ <math>(i</math>≠<math>j</math> ∧ <math>i+j</math>≠<math>2N+1)</math>		<math>A_{ij} = 0</math> ∧ <math>(i</math>≠<math>j</math> ∧ <math>i+j</math>≠<math>2N+1)</math>
	<br><br><math>b)</math>		<br><br><math>b)</math>

Etfsibg: /* Rešenje */

2021-08-27T09:08:37Z

Rešenje

← Старија измена		Верзија на датум 27. август 2021. у 11:08
Ред 78:		Ред 78:
	<math>a)</math><br><math>A_{ij} = ((i-1)2+\left\lfloor{(j-1)/N)}\right\rfloor)2</math> ∧ <math>(i=j</math> ∨ <math>i+j=2N+1)</math> <br>		<math>a)</math><br><math>A_{ij} = ((i-1)2+\left\lfloor{(j-1)/N)}\right\rfloor)2</math> ∧ <math>(i=j</math> ∨ <math>i+j=2N+1)</math> <br>
	<math>A_{ij} = 0</math> ∧ <math>(i</math>≠<math>j</math> ∧ <math>i+j</math>≠<math>2N+1)</math>		<math>A_{ij} = 0</math> ∧ <math>(i</math>≠<math>j</math> ∧ <math>i+j</math>≠<math>2N+1)</math>
	<br><math>b)</math>		<br><br><math>b)</math>
	~~<br>~~<br>		<br>
	<syntaxhighlight lang="milo">		<syntaxhighlight lang="milo">
	GET(A, i, j, N)		GET(A, i, j, N)

Etfsibg: /* Rešenje */

2021-08-27T09:08:21Z

Rešenje

← Старија измена		Верзија на датум 27. август 2021. у 11:08
Ред 79:		Ред 79:
	<math>A_{ij} = 0</math> ∧ <math>(i</math>≠<math>j</math> ∧ <math>i+j</math>≠<math>2N+1)</math>		<math>A_{ij} = 0</math> ∧ <math>(i</math>≠<math>j</math> ∧ <math>i+j</math>≠<math>2N+1)</math>
	<br><math>b)</math>		<br><math>b)</math>
	<br>		<br><br>
	<syntaxhighlight lang="milo">		<syntaxhighlight lang="milo">
	GET(A, i, j, N)		GET(A, i, j, N)

Etfsibg у 09:07, 27. август 2021.

2021-08-27T09:07:55Z

@@ Ред 67: / Ред 67: @@
      end_if
 end_while
 </syntaxhighlight>
 [[Категорија:Рокови]]
 [[Категорија:АСП1]]

KockaAdmiralac: Objašnjenje za drugi zadatak

2021-08-26T19:04:37Z

Objašnjenje za drugi zadatak

← Старија измена		Верзија на датум 26. август 2021. у 21:04
Ред 22:		Ред 22:

	=== Rešenje ===		=== 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.
	<syntaxhighlight lang="milo">		<syntaxhighlight lang="milo">
	SORT STACK(s1)		SORT STACK(s1)