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

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

2024-09-13T00:09:07Z

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

← Старија измена		Верзија на датум 13. септембар 2024. у 02:09
Ред 80:		Ред 80:
	=== Rešenje ===		=== Rešenje ===
	Koristi se modifikovana binarna pretraga koja se izvršava dok se tačka ne nađe na kružnici ili dok je greška manja od <code>err</code>. Parametar <code>err</code> je prosleđen funkciji.		Koristi se modifikovana binarna pretraga koja se izvršava dok se tačka ne nađe na kružnici ili dok je greška manja od <code>err</code>. Parametar <code>err</code> je prosleđen funkciji.
	<~~syntaxhighlight lang="milo"~~>		{{Милокод\|<nowiki>
	INTERSECT(K, D, err)		INTERSECT(K, D, err)
	low = T1		low = T1
Ред 98:		Ред 98:
	prev = mid		prev = mid
	end_while		end_while
	</~~syntaxhighlight~~>		</nowiki>}}
	<~~syntaxhighlight lang="milo"~~>		{{Милокод\|<nowiki>
	DISTANCE(A, B)		DISTANCE(A, B)
	return sqrt(pow(x(A) - x(B), 2) + pow(y(A) - y(B), 2))		return sqrt(pow(x(A) - x(B), 2) + pow(y(A) - y(B), 2))
	</~~syntaxhighlight~~>		</nowiki>}}

	== 3. zadatak ==		== 3. zadatak ==
Ред 116:		Ред 116:
	# U svakom čvoru stabla se čuva niz čvorova koje imaju istu vrednost ključa - ovim se postiže da se struktura stabla ne povećava.		# U svakom čvoru stabla se čuva niz čvorova koje imaju istu vrednost ključa - ovim se postiže da se struktura stabla ne povećava.
	# Čvorovi sa istom vrednošću se tretiraju kao veći, odnosno čuvaju u desnom podstablu - ovim se postiže veća pogodnost kod korišćenja za realizaciju struktura poput prioritetnog reda.		# Čvorovi sa istom vrednošću se tretiraju kao veći, odnosno čuvaju u desnom podstablu - ovim se postiže veća pogodnost kod korišćenja za realizaciju struktura poput prioritetnog reda.
	<~~syntaxhighlight lang="milo"~~>		{{Милокод\|<nowiki>
	BST INSERT MOD(root, x)		BST INSERT MOD(root, x)
	node = GETNODE		node = GETNODE
Ред 142:		Ред 142:
	end_if		end_if
	end_while		end_while
	</~~syntaxhighlight~~>		</nowiki>}}

	== 4. zadatak ==		== 4. zadatak ==
Ред 154:		Ред 154:
	=== Rešenje ===		=== Rešenje ===
	Crna visina nekog čvora je broj crnih čvorova na putu od tog čvora do listova, i po definiciji crveno-crnog stabla je jednaka za sve puteve do listova.		Crna visina nekog čvora je broj crnih čvorova na putu od tog čvora do listova, i po definiciji crveno-crnog stabla je jednaka za sve puteve do listova.
	<~~syntaxhighlight lang="milo"~~>		{{Милокод\|<nowiki>
	BH CALC(x)		BH CALC(x)
	p = x		p = x
Ред 165:		Ред 165:
	end_while		end_while
	return bh		return bh
	</~~syntaxhighlight~~>		</nowiki>}}

	== 5. zadatak ==		== 5. zadatak ==
Ред 219:		Ред 219:
	=== Rešenje ===		=== Rešenje ===
	Prvo proveravamo da li čvor ima levo podstablo. Ukoliko ima, vraćamo najdesniji čvor u levom podstablu kao prethodnika čvora. Ukoliko nema, penjemo se uz stablo poredeći ključ čvora ''x'' sa ključevima njegovih roditelja i ako nađemo čvor sa manjim ključem vratimo ga.		Prvo proveravamo da li čvor ima levo podstablo. Ukoliko ima, vraćamo najdesniji čvor u levom podstablu kao prethodnika čvora. Ukoliko nema, penjemo se uz stablo poredeći ključ čvora ''x'' sa ključevima njegovih roditelja i ako nađemo čvor sa manjim ključem vratimo ga.
	<~~syntaxhighlight lang="milo"~~>		{{Милокод\|<nowiki>
	PRED NODE(x)		PRED NODE(x)
	if left(x) = nil then		if left(x) = nil then
Ред 237:		Ред 237:
	return p		return p
	end_if		end_if
	</~~syntaxhighlight~~>		</nowiki>}}

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

KockaAdmiralac: PNG u SVG

2022-02-13T21:20:27Z

PNG u SVG

← Старија измена		Верзија на датум 13. фебруар 2022. у 23:20
Ред 208:		Ред 208:
	{{делимично решено}}		{{делимично решено}}
	=== Postavka ===		=== Postavka ===
	[[Датотека:ASP2 K1 2015 zadatak 6 stablo.~~png~~\|thumb\|Crveno-crno stablo iz postavke zadatka.]]		[[Датотека:ASP2 K1 2015 zadatak 6 stablo.svg\|thumb\|Crveno-crno stablo iz postavke zadatka.]]
	U crveno-crno stablo sa slike se najpre vrši umetanje ključa 50, a zatim vrši brisanje ključa 13. Prikazati izgled stabla nakon svake od navedenih promena.		U crveno-crno stablo sa slike se najpre vrši umetanje ključa 50, a zatim vrši brisanje ključa 13. Prikazati izgled stabla nakon svake od navedenih promena.

KockaAdmiralac: Delimično rešeno

2021-06-27T21:42:27Z

Delimično rešeno

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

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

KockaAdmiralac: Pri umetanju je zaboravljen ključ 61, ali to izgleda ne menja mnogo strukturu stabla

2021-01-30T01:32:43Z

Pri umetanju je zaboravljen ključ 61, ali to izgleda ne menja mnogo strukturu stabla

← Старија измена		Верзија на датум 30. јануар 2021. у 03:32
Ред 178:		Ред 178:
	/ \ / \		/ \ / \
	35 51 75 80		35 51 75 80
	\ /		\ / \
	39 48		39 48 61
	Po brisanju čvora 65, njegov sledbenik čvor 75 dolazi na njegovo mesto:		Po brisanju čvora 65, njegov sledbenik čvor 75 dolazi na njegovo mesto:
	75		75
Ред 186:		Ред 186:
	/ \ \		/ \ \
	35 51 80		35 51 80
	\ /		\ / \
	39 48		39 48 61
	Zatim se briše čvor 44 i njegov sledbenik čvor 48 dolazi na njegovo mesto:		Zatim se briše čvor 44 i njegov sledbenik čvor 48 dolazi na njegovo mesto:
	75		75
Ред 194:		Ред 194:
	/ \ \		/ \ \
	35 51 80		35 51 80
	\		\ \
	39		39 61
	Na kraju, briše se čvor 80 čime čvor 75 postaje kritičan čvor pa radimo rotaciju ulevo oko njega:		Na kraju, briše se čvor 80 čime čvor 75 postaje kritičan čvor pa radimo rotaciju ulevo oko njega:
	48		48
Ред 202:		Ред 202:
	\ / \		\ / \
	39 51 77		39 51 77
			\
			61

	== 6. zadatak ==		== 6. zadatak ==

WikiEditor: /* Nema cvora 60 */

2020-11-02T23:43:56Z

Nema cvora 60

← Старија измена		Верзија на датум 3. новембар 2020. у 01:43
Ред 178:		Ред 178:
	/ \ / \		/ \ / \
	35 51 75 80		35 51 75 80
	\ / \		\ /
	39 48 60		39 48
	Po brisanju čvora 65, njegov sledbenik čvor 75 dolazi na njegovo mesto:		Po brisanju čvora 65, njegov sledbenik čvor 75 dolazi na njegovo mesto:
	75		75
Ред 186:		Ред 186:
	/ \ \		/ \ \
	35 51 80		35 51 80
	\ / \		\ /
	39 48 60		39 48
	Zatim se briše čvor 44 i njegov sledbenik čvor 48 dolazi na njegovo mesto:		Zatim se briše čvor 44 i njegov sledbenik čvor 48 dolazi na njegovo mesto:
	75		75
Ред 194:		Ред 194:
	/ \ \		/ \ \
	35 51 80		35 51 80
	\ \		\
	39 60		39
	Na kraju, briše se čvor 80 čime čvor 75 postaje kritičan čvor pa radimo rotaciju ulevo oko njega:		Na kraju, briše se čvor 80 čime čvor 75 postaje kritičan čvor pa radimo rotaciju ulevo oko njega:
	48		48
Ред 202:		Ред 202:
	\ / \		\ / \
	39 51 77		39 51 77
	\
	60

	== 6. zadatak ==		== 6. zadatak ==

WikiEditor: /* Rešenje */

2020-11-02T23:40:40Z

Rešenje

← Старија измена		Верзија на датум 3. новембар 2020. у 01:40
Ред 161:		Ред 161:
	if (black(p)) then		if (black(p)) then
	bh = bh + 1		bh = bh + 1
			end_if
	p = left(p)		p = left(p)
	end_while		end_while

WikiEditor: /* black(p) */

2020-11-02T23:39:28Z

black(p)

← Старија измена		Верзија на датум 3. новембар 2020. у 01:39
Ред 159:		Ред 159:
	bh = 0		bh = 0
	while p ≠ nil do		while p ≠ nil do
	if (~~color~~(p) ~~= 0~~) then ~~// pretpostavili smo da je bit boje za crne čvorove jednak 0~~		if (black(p)) then
	bh = bh + 1		bh = bh + 1
	p = left(p)		p = left(p)

WikiEditor: /* Crni cvorovi */

2020-11-02T23:38:36Z

Crni cvorovi

← Старија измена		Верзија на датум 3. новембар 2020. у 01:38
Ред 153:		Ред 153:

	=== Rešenje ===		=== Rešenje ===
	Crna visina nekog čvora je broj čvorova na putu od tog čvora do listova, i po definiciji crveno-crnog stabla je jednaka za sve puteve do listova.		Crna visina nekog čvora je broj crnih čvorova na putu od tog čvora do listova, i po definiciji crveno-crnog stabla je jednaka za sve puteve do listova.
	<syntaxhighlight lang="milo">		<syntaxhighlight lang="milo">
	BH CALC(x)		BH CALC(x)
Ред 159:		Ред 159:
	bh = 0		bh = 0
	while p ≠ nil do		while p ≠ nil do
	bh = bh + 1		if (color(p) = 0) then // pretpostavili smo da je bit boje za crne čvorove jednak 0
			bh = bh + 1
	p = left(p)		p = left(p)
	end_while		end_while

KockaAdmiralac: Dodato rešenje za 4. zadatak; ispravljeno rešenje za 8. zadatak; nema potrebe da proveravamo jednakost prilikom dodavanja jednakog čvora kao sledbenika

2020-11-02T21:17:28Z

Dodato rešenje za 4. zadatak; ispravljeno rešenje za 8. zadatak; nema potrebe da proveravamo jednakost prilikom dodavanja jednakog čvora kao sledbenika

← Старија измена		Верзија на датум 2. новембар 2020. у 23:17
Ред 99:		Ред 99:
	end_while		end_while
	</syntaxhighlight>		</syntaxhighlight>

	<syntaxhighlight lang="milo">		<syntaxhighlight lang="milo">
	DISTANCE(A, B)		DISTANCE(A, B)
Ред 127:		Ред 126:
	p = root		p = root
	while true do		while true do
	if key(p) ~~= x then~~		if key(p) ≤ x then
	~~right(node) = right(p)~~
	~~right(p) = node~~
	~~break~~
	~~else if key(p) <~~ x then
	if right(p) = nil then		if right(p) = nil then
	right(p) = node		right(p) = node
Ред 158:		Ред 153:

	=== Rešenje ===		=== Rešenje ===
			Crna visina nekog čvora je broj čvorova na putu od tog čvora do listova, i po definiciji crveno-crnog stabla je jednaka za sve puteve do listova.
			<syntaxhighlight lang="milo">
			BH CALC(x)
			p = x
			bh = 0
			while p ≠ nil do
			bh = bh + 1
			p = left(p)
			end_while
			return bh
			</syntaxhighlight>

	== 5. zadatak ==		== 5. zadatak ==
Ред 195:		Ред 201:
	39 51 77		39 51 77
	\		\
	61		60

	== 6. zadatak ==		== 6. zadatak ==
Ред 238:		Ред 244:
	# Možemo formirati suboptimalno binarno stablo pretraživanja odabiranjem korena sa najmanjom razlikom težina između podstabala i rekurzivno ponavljati proces za oba podstabla.		# Možemo formirati suboptimalno binarno stablo pretraživanja odabiranjem korena sa najmanjom razlikom težina između podstabala i rekurzivno ponavljati proces za oba podstabla.
	#		#
	## Kandidati za koren su nam K3 i K4. K3 nam daje razliku 0.1 između težina podstabla, a K4 0.05, pa zato biramo K4 i proces nastavljamo za [1, 2~~, 3~~] i [5, 6].		## Kandidati za koren su nam K3 i K4. K3 nam daje razliku -0.05 između težina podstabla, a K4 0.1, pa zato biramo K3 i proces nastavljamo za [1, 2] i [4, 5, 6].
	## ~~Jedini kandidat za koren~~ levog podstabla ~~nam~~ je K2, ~~i zato njega~~ postavljamo kao koren~~, K1 njegovo levo dete a K3 njegovo desno~~.		## Sa K1 u korenu razlika između levog i desnog podstabla od levog suboptimalnog podstabla je -0.05 a sa K2 je 0.3, tako da postavljamo K1 kao koren levog podstabla.
	## ~~Kandidat~~ K6 je ~~bolji od~~ K5 ~~jer omogućava razliku od~~ 0.~~05 između težina podstabala za razliku od~~ 0.1, ~~pa njega~~ postavljamo kao koren a K5 kao ~~njegovo levo dete i~~ dobijamo ~~konačno stablo:~~		## Sa K6 u korenu razlika između levog i desnog podstabla od desnog suboptimalnog podstabla je 0, sa K5 -0.25 a sa K4 -0.4, tako da postavljamo K6 kao koren desnog podstabla.
			## Na kraju, sa K5 kao korenom levog podstabla od desnog podstabla dobijamo da je razlika težina 0.05, a sa K4 -0.1, tako da K5 postavljamo za koren levog podstabla od desnog podstabla.
	</div>		</div>
	4		3
	/ \		/ \
	2 6		1 6
	/ \ /		\ /
	1 3 5		2 5
			/
			4

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

Ivan Pešić: /* 2. zadatak */

2020-11-02T18:36:59Z

2. zadatak

← Старија измена		Верзија на датум 2. новембар 2020. у 20:36
Ред 79:		Ред 79:

	=== Rešenje ===		=== Rešenje ===
	~~Ovde je ideja da nagađamo~~ na ~~kom se delu duži, u procentima, nalazi presek s kružnicom. Za svako nagađanje računamo razdaljinu od centra i ako~~ je ~~veća~~ od ~~poluprečnika to znači da smo van kruga, odnosno da treba da idemo bliže tački T1, u suprotnom treba da idemo bliže tački T2~~. Parametar <code>p</code> ~~nam ovde označava preciznost aproksimacije u procentima dužine duži~~.		Koristi se modifikovana binarna pretraga koja se izvršava dok se tačka ne nađe na kružnici ili dok je greška manja od <code>err</code>. Parametar <code>err</code> je prosleđen funkciji.
	<syntaxhighlight lang="milo">		<syntaxhighlight lang="milo">
	INTERSECT(K, D)		INTERSECT(K, D, err)
	~~p = 0.05~~		low = T1
	low = 0		high = T2
	high = 1		prev = low
	~~mid_x~~ = 0		while true do
	~~mid_y = 0~~		x(mid) = (x(low) + x(high)) / 2
	while ~~high - low ≥ p~~ do		y(mid) = (y(low) + y(high)) / 2
	mid ~~= (high + low~~) ~~/ 2~~		dist = distance(C, mid)
	~~mid_x~~ = (x(T2) - x(T1)) * mid + x(T1)		if (dist = r) or (distance(mid, prev) < err) then
	~~mid_y = (~~y(T2) - y(T1)~~) * mid~~ + y(T1)		return mid
	~~diff~~ = ~~sqrt((mid_x - x~~(C)) * (~~mid_x - x(C~~)~~) +~~ (~~mid_y - y~~(~~C)) * (mid_y - y(C)~~))		else if dist > r then
	if ~~diff =~~ r then		high = mid
	~~return mid_x, mid_y~~		else
	else ~~if diff < r then~~
	low = mid		low = mid
	~~else~~
	~~high = mid~~
	end_if		end_if
			prev = mid
	end_while		end_while
	return ~~mid_x~~, ~~mid_y~~		</syntaxhighlight>

			<syntaxhighlight lang="milo">
			DISTANCE(A, B)
			return sqrt(pow(x(A) - x(B), 2) + pow(y(A) - y(B), 2))
	</syntaxhighlight>		</syntaxhighlight>