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

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

2024-09-13T00:09:08Z

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

← Старија измена		Верзија на датум 13. септембар 2024. у 02:09
Ред 23:		Ред 23:
	=== Rešenje ===		=== Rešenje ===
	Ovde nam je najpogodnije da ''postorder'' obilaskom određujemo da li su čvorovi binarna stabla pretraživanja, jer tako kad stignemo do viših čvorova već znamo da li su im deca ispravna binarna stabla pretraživanja. S tim u vidu, implementacija tražene funkcije za proveru izgleda ovako:		Ovde nam je najpogodnije da ''postorder'' obilaskom određujemo da li su čvorovi binarna stabla pretraživanja, jer tako kad stignemo do viših čvorova već znamo da li su im deca ispravna binarna stabla pretraživanja. S tim u vidu, implementacija tražene funkcije za proveru izgleda ovako:
	<~~syntaxhighlight lang="milo"~~>		{{Милокод\|<nowiki>
	IS BST(node, left_max, right_min)		IS BST(node, left_max, right_min)
	if left_max < key(node) < right_min then		if left_max < key(node) < right_min then
Ред 29:		Ред 29:
	end_if		end_if
	return false		return false
	</~~syntaxhighlight~~>		</nowiki>}}
	Kao pozivne argumente ove funkcije primamo najveći ključ iz levog podstabla i najmanji ključ iz desnog podstabla, što znači da bi trebalo da te podatke čuvamo u nekom redu kako bismo iz roditelja mogli da tim informacijama pristupimo. Obilazak kreće od reda listova i kreće se tako što svaki list gura svog roditelja u red, a duplikati roditelja se izbacuju iz reda prilikom njihovog obilaska.		Kao pozivne argumente ove funkcije primamo najveći ključ iz levog podstabla i najmanji ključ iz desnog podstabla, što znači da bi trebalo da te podatke čuvamo u nekom redu kako bismo iz roditelja mogli da tim informacijama pristupimo. Obilazak kreće od reda listova i kreće se tako što svaki list gura svog roditelja u red, a duplikati roditelja se izbacuju iz reda prilikom njihovog obilaska.
	<~~syntaxhighlight lang="milo"~~>		{{Милокод\|<nowiki>
	FIND BST(root)		FIND BST(root)
	if root = nil then		if root = nil then
Ред 83:		Ред 83:
	end_while		end_while
	return last_bst		return last_bst
	</~~syntaxhighlight~~>		</nowiki>}}

	== 3. zadatak ==		== 3. zadatak ==
Ред 99:		Ред 99:
	=== Rešenje ===		=== Rešenje ===
	Ovde se pretpostavlja da se ključevi u nizu ne mogu ponavljati.		Ovde se pretpostavlja da se ključevi u nizu ne mogu ponavljati.
	<~~syntaxhighlight lang="milo"~~>		{{Милокод\|<nowiki>
	ARR PRED SUCC(arr, k)		ARR PRED SUCC(arr, k)
	while (low ≤ high) do		while (low ≤ high) do
Ред 116:		Ред 116:
	return mid-1, mid		return mid-1, mid
	end_if		end_if
	</~~syntaxhighlight~~>		</nowiki>}}

	== 5. zadatak ==		== 5. zadatak ==
Ред 137:		Ред 137:
	=== Rešenje ===		=== Rešenje ===
	Pošto ne moramo da izračunavamo visine podstabla, ovaj zadatak se svodi na posećivanje svih čvorova kako bismo uporedili sve visine levih i desnih podstabala u jednom čvoru. Ukoliko se u nekom razlikuju za više od 1, stablo nije balansirano po AVL kriterijumu.		Pošto ne moramo da izračunavamo visine podstabla, ovaj zadatak se svodi na posećivanje svih čvorova kako bismo uporedili sve visine levih i desnih podstabala u jednom čvoru. Ukoliko se u nekom razlikuju za više od 1, stablo nije balansirano po AVL kriterijumu.
	<~~syntaxhighlight lang="milo"~~>		{{Милокод\|<nowiki>
	CHECK AVL BALANCED(bst)		CHECK AVL BALANCED(bst)
	INIT_STACK(S)		INIT_STACK(S)
Ред 154:		Ред 154:
	end_while		end_while
	return true		return true
	</~~syntaxhighlight~~>		</nowiki>}}

	== 7. zadatak ==		== 7. zadatak ==
Ред 166:		Ред 166:
	=== Rešenje ===		=== Rešenje ===
	Određivanje suboptimalnog stabla binarnog pretraživanja zasnovanog na težinama podstabala, gde je težina podstabla koje uključuje čvorove na pozicijama od <math>i+1</math> do <math>j</math> u tabeli definisana kao <math>w_{ij} = q_i + p_{i+1} + q_{i+1} + ... + p_j + q_j</math>, se vrši tako što se prvo odredi ključ koji, kad postavljen za koren, daje najmanju razliku težina levog i desnog podstabla, a zatim se taj proces primeni rekurzivno na levo i desno podstablo (podniz) kako bi se i njihovi koreni odredili.		Određivanje suboptimalnog stabla binarnog pretraživanja zasnovanog na težinama podstabala, gde je težina podstabla koje uključuje čvorove na pozicijama od <math>i+1</math> do <math>j</math> u tabeli definisana kao <math>w_{ij} = q_i + p_{i+1} + q_{i+1} + ... + p_j + q_j</math>, se vrši tako što se prvo odredi ključ koji, kad postavljen za koren, daje najmanju razliku težina levog i desnog podstabla, a zatim se taj proces primeni rekurzivno na levo i desno podstablo (podniz) kako bi se i njihovi koreni odredili.
	<~~syntaxhighlight lang="milo"~~>		{{Милокод\|<nowiki>
	FIND ROOT(P, Q, n)		FIND ROOT(P, Q, n)
	min_key = 1		min_key = 1
Ред 182:		Ред 182:
	end_for		end_for
	return min_key		return min_key
	</~~syntaxhighlight~~>		</nowiki>}}

	== 8. zadatak ==		== 8. zadatak ==

KockaAdmiralac: Tražena datoteka

2022-02-13T21:33:27Z

Tražena datoteka

← Старија измена		Верзија на датум 13. фебруар 2022. у 23:33
Ред 88:		Ред 88:
	{{делимично решено}}		{{делимично решено}}
	=== Postavka ===		=== Postavka ===
	[[Датотека:ASP2 K1 2018 zadatak 3 stablo.~~png~~\|thumb\|Crveno-crno stablo iz postavke zadatka.]]		[[Датотека:ASP2 K1 2018 zadatak 3 stablo.svg\|thumb\|Crveno-crno stablo iz postavke zadatka.]]
	Neka se posmatra crveno-crno stablo sa slike. Prikazati izgled stabla po koracima nakon umetanja ključeva 7 i 10.		Neka se posmatra crveno-crno stablo sa slike. Prikazati izgled stabla po koracima nakon umetanja ključeva 7 i 10.

Etfsibg: /* Rešenje */

2021-11-01T10:37:49Z

Rešenje

← Старија измена		Верзија на датум 1. новембар 2021. у 12:37
Ред 182:		Ред 182:
	end_for		end_for
	return min_key		return min_key
	~~end_for~~
	</syntaxhighlight>		</syntaxhighlight>

KockaAdmiralac: Delimično rešeno

2021-06-27T21:42:54Z

Delimično rešeno

← Старија измена		Верзија на датум 27. јун 2021. у 23:42
Ред 86:		Ред 86:

	== 3. zadatak ==		== 3. zadatak ==
			{{делимично решено}}
	=== Postavka ===		=== Postavka ===
	[[Датотека:ASP2 K1 2018 zadatak 3 stablo.png\|thumb\|Crveno-crno stablo iz postavke zadatka.]]		[[Датотека:ASP2 K1 2018 zadatak 3 stablo.png\|thumb\|Crveno-crno stablo iz postavke zadatka.]]

Mladen Žurkić: /* Zapis while uslova, kao što je kod svage bin pr.*/

2020-11-03T13:39:36Z

Zapis while uslova, kao što je kod svage bin pr.

← Старија измена		Верзија на датум 3. новембар 2020. у 15:39
Ред 100:		Ред 100:
	<syntaxhighlight lang="milo">		<syntaxhighlight lang="milo">
	ARR PRED SUCC(arr, k)		ARR PRED SUCC(arr, k)
	while high ~~>= low~~ do		while (low ≤ high) do
	mid = (high + low) / 2		mid = (high + low) / 2
	if arr[mid] = k then		if arr[mid] = k then

KockaAdmiralac: Ovde bi trebalo da čuvamo maksimum levog i minimum desnog podstabla i sa time poredimo pri proveri

2020-11-03T01:55:29Z

Ovde bi trebalo da čuvamo maksimum levog i minimum desnog podstabla i sa time poredimo pri proveri

← Старија измена		Верзија на датум 3. новембар 2020. у 03:55
Ред 24:		Ред 24:
	Ovde nam je najpogodnije da ''postorder'' obilaskom određujemo da li su čvorovi binarna stabla pretraživanja, jer tako kad stignemo do viših čvorova već znamo da li su im deca ispravna binarna stabla pretraživanja. S tim u vidu, implementacija tražene funkcije za proveru izgleda ovako:		Ovde nam je najpogodnije da ''postorder'' obilaskom određujemo da li su čvorovi binarna stabla pretraživanja, jer tako kad stignemo do viših čvorova već znamo da li su im deca ispravna binarna stabla pretraživanja. S tim u vidu, implementacija tražene funkcije za proveru izgleda ovako:
	<syntaxhighlight lang="milo">		<syntaxhighlight lang="milo">
	IS BST(node, ~~left_child_valid_bst~~, ~~right_child_valid_bst~~)		IS BST(node, left_max, right_min)
	if ~~(not left_child_valid_bst) or (not right_child_valid_bst) or (node = nil) then~~		if left_max < key(node) < right_min then
	~~return false~~
	~~end_if~~
	~~if key(left(node))~~ < key(node) < ~~key(right(node))~~ then
	return true		return true
	end_if		end_if
	return false		return false
	</syntaxhighlight>		</syntaxhighlight>
	Kao pozivne argumente ove funkcije primamo ~~da li su nam levo~~ i ~~desno dete čvora validni BST~~, što bi ~~značilo da treba~~ da te podatke čuvamo u nekom redu kako bismo iz roditelja mogli da tim informacijama pristupimo. Obilazak kreće od reda listova i kreće se tako što svaki list gura svog roditelja u red, a duplikati roditelja se izbacuju iz reda prilikom njihovog obilaska.		Kao pozivne argumente ove funkcije primamo najveći ključ iz levog podstabla i najmanji ključ iz desnog podstabla, što znači da bi trebalo da te podatke čuvamo u nekom redu kako bismo iz roditelja mogli da tim informacijama pristupimo. Obilazak kreće od reda listova i kreće se tako što svaki list gura svog roditelja u red, a duplikati roditelja se izbacuju iz reda prilikom njihovog obilaska.
	<syntaxhighlight lang="milo">		<syntaxhighlight lang="milo">
	FIND BST(root)		FIND BST(root)
Ред 43:		Ред 40:
	QUEUE_INIT(Q_nodes)		QUEUE_INIT(Q_nodes)
	QUEUE_INIT(Q_inv_nodes)		QUEUE_INIT(Q_inv_nodes)
			QUEUE_INIT(Q_max)
			QUEUE_INIT(Q_min)
	INSERT(Q_nodes, root)		INSERT(Q_nodes, root)
	while (not QUEUE_EMPTY(Q_nodes)) do		while (not QUEUE_EMPTY(Q_nodes)) do
Ред 56:		Ред 55:
	node = DELETE(Q_inv_nodes)		node = DELETE(Q_inv_nodes)
	if left(node) = nil then		if left(node) = nil then
	~~left_valid~~ = true		valid_bst = true
	~~right_valid~~ = ~~true~~		curr_max = key(node)
			curr_min = key(node)
	else		else
	DELETE(Q_inv_nodes)		DELETE(Q_inv_nodes)
	left_valid = DELETE(Q_valid_bst)		left_valid = DELETE(Q_valid_bst)
	right_valid = DELETE(Q_valid_bst)		right_valid = DELETE(Q_valid_bst)
			left_min = DELETE(Q_min)
			right_min = DELETE(Q_min)
			left_max = DELETE(Q_max)
			right_max = DELETE(Q_max)
			if left_valid and right_valid and IS_BST(node, left_max, right_min) then
			valid_bst = true
			else
			valid_bst = false
			end_if
			curr_max = max(key(node), left_max, right_max)
			curr_min = min(key(node), left_min, right_min)
	end_if		end_if
	~~valid_bst = IS_BST(node, left_valid, right_valid)~~
	if valid_bst then		if valid_bst then
	last_bst = node		last_bst = node
Ред 69:		Ред 79:
	INSERT(Q_valid_bst, valid_bst)		INSERT(Q_valid_bst, valid_bst)
	INSERT(Q_inv_nodes, parent(node))		INSERT(Q_inv_nodes, parent(node))
			INSERT(Q_min, curr_min)
			INSERT(Q_max, curr_max)
	end_while		end_while
	return last_bst		return last_bst

WikiEditor: /* Pisalo je 49 umesto 43 */

2020-11-02T21:20:46Z

Pisalo je 49 umesto 43

← Старија измена		Верзија на датум 2. новембар 2020. у 23:20
Ред 113:		Ред 113:
	60		60
	/ \		/ \
	49 72		43 72
	/ \ \		/ \ \
	2 55 89		2 55 89

KockaAdmiralac: Možda bolje da ne prekidamo algoritam ovde

2020-11-02T18:04:11Z

Možda bolje da ne prekidamo algoritam ovde

← Старија измена		Верзија на датум 2. новембар 2020. у 20:04
Ред 166:		Ред 166:
	min_diff = diff		min_diff = diff
	min_key = i		min_key = i
	~~else~~
	~~break~~
	end_if		end_if
	end_for		end_for

KockaAdmiralac: Malo manje zbunjujuć pseudokod u sedmom zadatku

2020-11-02T14:49:28Z

Malo manje zbunjujuć pseudokod u sedmom zadatku

← Старија измена		Верзија на датум 2. новембар 2020. у 16:49
Ред 157:		Ред 157:
	min_key = 1		min_key = 1
	left = Q[1]		left = Q[1]
	~~min_diff~~ = ~~abs(~~1 - 2 * left - P[1])		right = 1 - left - P[1]
			min_diff = abs(right - left)
	for i = 2 to n do		for i = 2 to n do
	left = left + Q[i] + P[i-1]		left = left + Q[i] + P[i-1]
	~~diff~~ = ~~abs(~~1 - 2 * left - P[i])		right = 1 - left - P[i]
			diff = abs(right - left)
	if diff < min_diff then		if diff < min_diff then
	min_diff = diff		min_diff = diff

Ivan Pešić: /* Rešenje */

2020-11-02T10:13:14Z

Rešenje

← Старија измена		Верзија на датум 2. новембар 2020. у 12:13
Ред 89:		Ред 89:
	ARR PRED SUCC(arr, k)		ARR PRED SUCC(arr, k)
	while high >= low do		while high >= low do
	mid = (high + low) / 2;		mid = (high + low) / 2
	if arr[mid] = k then		if arr[mid] = k then
	return mid-1, mid+1;		return mid-1, mid+1
	else if arr[mid] < k then		else if arr[mid] < k then
	low = mid + 1;		low = mid + 1
	else		else
	high = mid - 1;		high = mid - 1
	end_if		end_if
	end_while		end_while
	if arr[mid] < k then		if arr[mid] < k then
	return mid, mid+1;		return mid, mid+1
	else		else
	return mid-1, mid;		return mid-1, mid
	end_if		end_if
	</syntaxhighlight>		</syntaxhighlight>