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

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

2024-09-13T00:09:09Z

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

← Старија измена		Верзија на датум 13. септембар 2024. у 02:09
Ред 72:		Ред 72:
	# kada čvor sa ključem ''key'' ima desno podstablo, znamo da se u njemu sigurno nalazi njegov sledbenik kao najlevlje dete desnog podstabla, i		# kada čvor sa ključem ''key'' ima desno podstablo, znamo da se u njemu sigurno nalazi njegov sledbenik kao najlevlje dete desnog podstabla, i
	# kada taj čvor nema desno podstablo, uzimamo poslednji čvor kod koga smo utvrdili da mu je ključ veći od ključa koji tražimo (poslednji čvor kod koga smo "otišli levo").		# kada taj čvor nema desno podstablo, uzimamo poslednji čvor kod koga smo utvrdili da mu je ključ veći od ključa koji tražimo (poslednji čvor kod koga smo "otišli levo").
	<~~syntaxhighlight lang="milo"~~>		{{Милокод\|<nowiki>
	FIND BST SUCC(root, key)		FIND BST SUCC(root, key)
	p = root		p = root
Ред 92:		Ред 92:
	end_if		end_if
	return succ		return succ
	</~~syntaxhighlight~~>		</nowiki>}}

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

	Ideja je na stek guramo decu čvorova za koje odredimo da upadaju u granice pretrage po stablu binarnog pretraživanja, a ako ne upadaju smestimo ih u jednu od dve promenljive i nakon toga zamenimo, pazeći da zamenimo i pokazivače na roditelje i roditeljske pokazivače.		Ideja je na stek guramo decu čvorova za koje odredimo da upadaju u granice pretrage po stablu binarnog pretraživanja, a ako ne upadaju smestimo ih u jednu od dve promenljive i nakon toga zamenimo, pazeći da zamenimo i pokazivače na roditelje i roditeljske pokazivače.
	<~~syntaxhighlight lang="milo"~~>		{{Милокод\|<nowiki>
	CORRECT BST(root)		CORRECT BST(root)
	STACK_INIT(S_nodes)		STACK_INIT(S_nodes)
Ред 155:		Ред 155:
	right(parent(second)) = second		right(parent(second)) = second
	end_if		end_if
	</~~syntaxhighlight~~>		</nowiki>}}

	== 5. zadatak ==		== 5. zadatak ==
Ред 176:		Ред 176:
	=== Rešenje ===		=== Rešenje ===
	Ovde se radi obična binarna pretraga s tim što se uslovi za odlazak ulevo ili udesno menjaju: ukoliko je ''x'' koordinata trenutne tačke veća od tražene, ili ukoliko su iste ali je ''y'' koordinata veća od tražene, ide se ulevo, a ukoliko je ''x'' koordinata trenutne tačke manja od tražene, ili ukoliko su iste ali je ''y'' koordinata manja od tražene, ide se udesno.		Ovde se radi obična binarna pretraga s tim što se uslovi za odlazak ulevo ili udesno menjaju: ukoliko je ''x'' koordinata trenutne tačke veća od tražene, ili ukoliko su iste ali je ''y'' koordinata veća od tražene, ide se ulevo, a ukoliko je ''x'' koordinata trenutne tačke manja od tražene, ili ukoliko su iste ali je ''y'' koordinata manja od tražene, ide se udesno.
	<~~syntaxhighlight lang="milo"~~>		{{Милокод\|<nowiki>
	CHECK VERTEX(M, n, T)		CHECK VERTEX(M, n, T)
	low = 1		low = 1
Ред 191:		Ред 191:
	end_while		end_while
	return false		return false
	</~~syntaxhighlight~~>		</nowiki>}}
	Postupak se mogao pojednostaviti ukoliko se pretpostavi da ne može postojati više od dve tačke sa istom ''x'' koordinatom, jer bi u tom slučaju te tačke bile kolinearne i ne bi mogle da budu temena ''n''-tougla.		Postupak se mogao pojednostaviti ukoliko se pretpostavi da ne može postojati više od dve tačke sa istom ''x'' koordinatom, jer bi u tom slučaju te tačke bile kolinearne i ne bi mogle da budu temena ''n''-tougla.

Ред 199:		Ред 199:

	=== Rešenje ===		=== Rešenje ===
	<~~syntaxhighlight lang="milo"~~>		{{Милокод\|<nowiki>
	SEARCH(A, K, n, m)		SEARCH(A, K, n, m)
	for i = 1 to 100 do		for i = 1 to 100 do
Ред 230:		Ред 230:
	return sum/num		return sum/num
	end_if		end_if
	</~~syntaxhighlight~~>		</nowiki>}}

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

KockaAdmiralac: PNG u SVG

2022-02-13T21:20:56Z

PNG u SVG

← Старија измена		Верзија на датум 13. фебруар 2022. у 23:20
Ред 97:		Ред 97:
	{{делимично решено}}		{{делимично решено}}
	=== 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 81 i 79 i uklanjanja ključa 23.		Neka se posmatra crveno-crno stablo sa slike. Prikazati izgled stabla po koracima nakon umetanja ključeva 81 i 79 i uklanjanja ključa 23.

KockaAdmiralac: Delimično rešeno

2021-06-27T21:43:12Z

Delimično rešeno

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

	== 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.]]

KockaAdmiralac: Dodata ostala dva moguća stabla u prvom zadatku

2020-11-03T02:37:01Z

Dodata ostala dva moguća stabla u prvom zadatku

@@ Ред 13: / Ред 13: @@
 Formula je napisana i objašnjena u [[АСП2/К1 2019#8. zadatak|osmom zadatku na prvom kolokvijumu 2019. godine]].
-Postoje tri rasporeda ovih čvorova (<math>p_i</math> označavaju ključeve a <math>q_i</math> eksterne čvorove stabla):
+Postoji pet rasporeda ovih čvorova (<math>p_i</math> označavaju ključeve a <math>q_i</math> eksterne čvorove stabla):
      p1
     /  \
@@ Ред 42: / Ред 42: @@
 : <math>+ 3 \cdot 0.15 + 3 \cdot 0.2 + 2 \cdot 0.1 + 1 \cdot 0.2 =</math>
 : <math>= 0.6 + 0.1 + 0.1 + 0.45 + 0.6 + 0.2 + 0.2 = 2.25</math>
 Ovim dobijamo da je optimalno stablo binarnog pretraživanja za ova tri ključa stablo u kojem je <math>K_2</math> u korenu.

WikiEditor: /* Rešenje */

2020-11-02T19:30:51Z

Rešenje

← Старија измена		Верзија на датум 2. новембар 2020. у 21:30
Ред 23:		Ред 23:
	: <math>C = 1 \cdot 0.2 + 2 \cdot 0.05 + 3 \cdot 0.1 +</math>		: <math>C = 1 \cdot 0.2 + 2 \cdot 0.05 + 3 \cdot 0.1 +</math>
	: <math>+ 1 \cdot 0.15 + 2 \cdot 0.2 + 3 \cdot 0.1 + 3 \cdot 0.2 =</math>		: <math>+ 1 \cdot 0.15 + 2 \cdot 0.2 + 3 \cdot 0.1 + 3 \cdot 0.2 =</math>
	: <math>= 0.2 + 0.1 + 0.3 + 0.15 + 0.4 + 0.3 + 0.6 = 2.25</math>		: <math>= 0.2 + 0.1 + 0.3 + 0.15 + 0.4 + 0.3 + 0.6 = 2.05</math>
	p2		p2
	/ \		/ \

WikiEditor: /* Rešenje */

2020-11-02T19:30:20Z

Rešenje

← Старија измена		Верзија на датум 2. новембар 2020. у 21:30
Ред 23:		Ред 23:
	: <math>C = 1 \cdot 0.2 + 2 \cdot 0.05 + 3 \cdot 0.1 +</math>		: <math>C = 1 \cdot 0.2 + 2 \cdot 0.05 + 3 \cdot 0.1 +</math>
	: <math>+ 1 \cdot 0.15 + 2 \cdot 0.2 + 3 \cdot 0.1 + 3 \cdot 0.2 =</math>		: <math>+ 1 \cdot 0.15 + 2 \cdot 0.2 + 3 \cdot 0.1 + 3 \cdot 0.2 =</math>
	: <math>= 0.4 + 0.1 + 0.3 + 0.15 + 0.4 + 0.3 + 0.6 = 2.25</math>		: <math>= 0.2 + 0.1 + 0.3 + 0.15 + 0.4 + 0.3 + 0.6 = 2.25</math>
	p2		p2
	/ \		/ \

KockaAdmiralac: Valjda ovako ide rešenje prvog zadatka

2020-11-02T01:32:17Z

Valjda ovako ide rešenje prvog zadatka

@@ Ред 11: / Ред 11: @@
 === Rešenje ===
 == 2. zadatak ==
@@ Ред 54: / Ред 86: @@
 === Rešenje ===
-Ovde se pretpostavlja da se pod zamenom čvorova ne misli samo na zamenu ključeva u tim čvorovima već na zamenu zajedno da podstablima, tako da jedna zamena ne može imati kaskadne posledice već će samo dva čvora ostati nekonzistentna.
+Pod zamenom čvorova se ne misli samo na zamenu ključeva u tim čvorovima već na zamenu zajedno sa podstablima, tako da jedna zamena ne može imati kaskadne posledice već će samo dva čvora ostati nekonzistentna.
 Ideja je na stek guramo decu čvorova za koje odredimo da upadaju u granice pretrage po stablu binarnog pretraživanja, a ako ne upadaju smestimo ih u jednu od dve promenljive i nakon toga zamenimo, pazeći da zamenimo i pokazivače na roditelje i roditeljske pokazivače.
@@ Ред 122: / Ред 154: @@
 === Rešenje ===
-Ovde se radi obična binarna pretraga s tim što se uslovi za odlazak ulevo ili udesno menjaju: ukoliko je x koordinata trenutne tačke veća od tražene, ili ukoliko su iste ali je y koordinata veća od tražene, ide se ulevo, a ukoliko je x koordinata trenutne tačke manja od tražene, ili ukoliko su iste ali je y koordinata manja od tražene, ide se udesno.
+Ovde se radi obična binarna pretraga s tim što se uslovi za odlazak ulevo ili udesno menjaju: ukoliko je ''x'' koordinata trenutne tačke veća od tražene, ili ukoliko su iste ali je ''y'' koordinata veća od tražene, ide se ulevo, a ukoliko je ''x'' koordinata trenutne tačke manja od tražene, ili ukoliko su iste ali je ''y'' koordinata manja od tražene, ide se udesno.
 <syntaxhighlight lang="milo">
 CHECK VERTEX(M, n, T)
@@ Ред 139: / Ред 171: @@
 return false
 </syntaxhighlight>
 == 7. zadatak ==

Mladen Žurkić: /* 168 -> 160 */

2020-11-01T17:49:45Z

168 -> 160

← Старија измена		Верзија на датум 1. новембар 2020. у 19:49
Ред 193:		Ред 193:
	## 87 → 158, low = 87, high = +∞		## 87 → 158, low = 87, high = +∞
	## 158 → 348, low = 158, high = +∞		## 158 → 348, low = 158, high = +∞
	## 348 → ~~168~~, low = 158, high = 348		## 348 → 160, low = 158, high = 348
	## 160 → 200, low = 160, high = 348		## 160 → 200, low = 160, high = 348
	## 200 → 150, 150 < low => ⚡		## 200 → 150, 150 < low => ⚡

KockaAdmiralac: Šta

2020-11-01T17:40:11Z

Šta

← Старија измена		Верзија на датум 1. новембар 2020. у 19:40
Ред 128:		Ред 128:
	high = n		high = n
	while low ≤ high do		while low ≤ high do
	mid = (high - low) / 2		mid = (high + low) / 2
	if (x(M[mid]) = x(T)) and (y(M[mid]) = y(T)) then		if (x(M[mid]) = x(T)) and (y(M[mid]) = y(T)) then
	return true		return true

KockaAdmiralac: +rešenje za 7. zadatak

2020-10-19T01:48:58Z

+rešenje za 7. zadatak

@@ Ред 147: / Ред 147: @@
 <syntaxhighlight lang="milo">
 SEARCH(A, K, n, m)
 </syntaxhighlight>