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

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

2024-09-13T00:09:07Z

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

← Старија измена		Верзија на датум 13. септембар 2024. у 02:09
Ред 42:		Ред 42:
	=== Rešenje ===		=== Rešenje ===
	Ovde prvo prebacujemo zadati niz u binarno stablo pretraživanja koristeći funkciju za umetanje čvora a zatim za svaki element niza pronalazimo sledbenika slično kao u [[АСП2/К1 2018#2. zadatak\|drugom zadatku sa prvog kolokvijuma 2018]].		Ovde prvo prebacujemo zadati niz u binarno stablo pretraživanja koristeći funkciju za umetanje čvora a zatim za svaki element niza pronalazimo sledbenika slično kao u [[АСП2/К1 2018#2. zadatak\|drugom zadatku sa prvog kolokvijuma 2018]].
	<~~syntaxhighlight lang="milo"~~>		{{Милокод\|<nowiki>
	ARR TRANSFORM(arr, n)		ARR TRANSFORM(arr, n)
	bst = nil		bst = nil
Ред 69:		Ред 69:
	end_if		end_if
	end_for		end_for
	</~~syntaxhighlight~~>		</nowiki>}}
	<~~syntaxhighlight lang="milo"~~>		{{Милокод\|<nowiki>
	BST-INSERT(bst, key)		BST-INSERT(bst, key)
	node = GETNODE		node = GETNODE
Ред 96:		Ред 96:
	end_while		end_while
	end_if		end_if
	</~~syntaxhighlight~~>		</nowiki>}}

	== 3. zadatak ==		== 3. zadatak ==
Ред 104:		Ред 104:
	=== Rešenje ===		=== Rešenje ===
	Ovaj problem se svodi na binarnu pretragu sa izmenjenim uslovima: sada detektujemo da li se nalazimo levo ili desno od tražene vrednosti poredeći se sa prvim elementom (ukoliko je trenutni element veći od prvog, levo smo od tražene vrednosti) a detekciju tražene vrednosti tako što proverimo da li je element levo od trenutnog veći od njega (to znači da smo došli na početak nerotiranog niza).		Ovaj problem se svodi na binarnu pretragu sa izmenjenim uslovima: sada detektujemo da li se nalazimo levo ili desno od tražene vrednosti poredeći se sa prvim elementom (ukoliko je trenutni element veći od prvog, levo smo od tražene vrednosti) a detekciju tražene vrednosti tako što proverimo da li je element levo od trenutnog veći od njega (to znači da smo došli na početak nerotiranog niza).
	<~~syntaxhighlight lang="milo"~~>		{{Милокод\|<nowiki>
	FIND MIN(arr, n)		FIND MIN(arr, n)
	low = 1		low = 1
Ред 121:		Ред 121:
	end_if		end_if
	end_while		end_while
	</~~syntaxhighlight~~>		</nowiki>}}

	== 4. zadatak ==		== 4. zadatak ==
Ред 275:		Ред 275:
	# Ovakva stabla, koja su najgori slučajevi AVL stabala, dobila su ime po Fibonačijevim brojevima <!--(koji su, pak, dobili naziv po poznatom srpskom glumcu Miljanu Fibonačiju Markoviću)--> čija se rekurzivna definicija veoma malo razlikuje od rekurzivne definicije broja čvorova ovakvih stabala u zavisnosti od njihove visine.		# Ovakva stabla, koja su najgori slučajevi AVL stabala, dobila su ime po Fibonačijevim brojevima <!--(koji su, pak, dobili naziv po poznatom srpskom glumcu Miljanu Fibonačiju Markoviću)--> čija se rekurzivna definicija veoma malo razlikuje od rekurzivne definicije broja čvorova ovakvih stabala u zavisnosti od njihove visine.
	</div>		</div>
	<~~syntaxhighlight lang="milo"~~>		{{Милокод\|<nowiki>
	AVL MIN NODES(h)		AVL MIN NODES(h)
	if h = 0 then		if h = 0 then
Ред 284:		Ред 284:
	return AVL_MIN_NODES(h - 1) + AVL_MIN_NODES(h - 2) + 1		return AVL_MIN_NODES(h - 1) + AVL_MIN_NODES(h - 2) + 1
	end_if		end_if
	</~~syntaxhighlight~~>		</nowiki>}}

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

KockaAdmiralac: PNG u SVG

2022-02-13T21:20:43Z

PNG u SVG

← Старија измена		Верзија на датум 13. фебруар 2022. у 23:20
Ред 256:		Ред 256:
	== 6. zadatak ==		== 6. zadatak ==
	=== Postavka ===		=== Postavka ===
	[[Датотека:ASP2 K1 2016 zadatak 6 stablo.~~png~~\|thumb\|Crveno-crno stablo iz postavke zadatka.]]		[[Датотека:ASP2 K1 2016 zadatak 6 stablo.svg\|thumb\|Crveno-crno stablo iz postavke zadatka.]]
	U crveno-crnom stablu sa slike se najpre izvrši brisanje ključa 35, a zatim umetanje ključeva 9, 43, 10. Prikazati izgled stabla nakon svake od navedenih promena.		U crveno-crnom stablu sa slike se najpre izvrši brisanje ključa 35, a zatim umetanje ključeva 9, 43, 10. Prikazati izgled stabla nakon svake od navedenih promena.

KockaAdmiralac: Aleksin postupak sa ispravkom na kraju

2020-11-03T00:10:40Z

Aleksin postupak sa ispravkom na kraju

@@ Ред 188: / Ред 188: @@
 === Rešenje ===
 Vidimo da su kritični čvorovi ovde 17 i 33. Prvo radimo desnu rotaciju oko čvora 17:
@@ Ред 216: / Ред 217: @@
    /  \    /  \     \
    17  22  27     55
 == 6. zadatak ==

TopOfKeks: Враћене измене корисника TopOfKeks (разговор) на последњу измену корисника KatarinaJocic

2020-11-02T23:20:59Z

Враћене измене корисника TopOfKeks (разговор) на последњу измену корисника KatarinaJocic

@@ Ред 188: / Ред 188: @@
 === Rešenje ===
 Vidimo da su kritični čvorovi ovde 17 i 33. Prvo radimo desnu rotaciju oko čvora 17:
@@ Ред 217: / Ред 216: @@
    /  \    /  \     \
    17  22  27     55
 == 6. zadatak ==

TopOfKeks: /* Rešenje */ Urađeno do kraja

2020-11-02T23:20:04Z

Rešenje: Urađeno do kraja

@@ Ред 188: / Ред 188: @@
 === Rešenje ===
 Vidimo da su kritični čvorovi ovde 17 i 33. Prvo radimo desnu rotaciju oko čvora 17:
@@ Ред 216: / Ред 217: @@
    /  \    /  \     \
    17  22  27     55
 == 6. zadatak ==

WikiEditor: /* 28 -> 25 */

2020-11-02T23:03:58Z

28 -> 25

← Старија измена		Верзија на датум 3. новембар 2020. у 01:03
Ред 150:		Ред 150:
	{\| class="wikitable"		{\| class="wikitable"
	\|+ Stanje povećane tabele nakon unosa ključa 29		\|+ Stanje povećane tabele nakon unosa ključa 29
	\| 5 \|\| 6 \|\| 6 \|\| 18 \|\| 22 \|\| 22 \|\| 23 \|\| 25 \|\| 28 \|\| 29 \|\| 38		\| 5 \|\| 6 \|\| 6 \|\| 18 \|\| 22 \|\| 22 \|\| 23 \|\| 25 \|\| 25 \|\| 29 \|\| 38
	\|-		\|-
	\| 1 \|\| 1 \|\| 0 \|\| 1 \|\| 0 \|\| 0 \|\| 0 \|\| 1 \|\| 0 \|\| 1 \|\| 1		\| 1 \|\| 1 \|\| 0 \|\| 1 \|\| 0 \|\| 0 \|\| 0 \|\| 1 \|\| 0 \|\| 1 \|\| 1

WikiEditor: /* 32 nije bio kritican cvor i fali ostatak resenja? */

2020-11-02T22:59:07Z

32 nije bio kritican cvor i fali ostatak resenja?

← Старија измена		Верзија на датум 3. новембар 2020. у 00:59
Ред 188:		Ред 188:

	=== Rešenje ===		=== Rešenje ===
	Vidimo da su kritični čvorovi ovde 17~~, 32~~ i 33. Prvo radimo desnu rotaciju oko čvora 17:		Vidimo da su kritični čvorovi ovde 17 i 33. Prvo radimo desnu rotaciju oko čvora 17:
	20		20
	/ \		/ \
Ред 208:		Ред 208:
	\		\
	55		55
	čime ~~čvorovi 32 i~~ 33 više ~~nisu kritični~~. Na kraju, radimo levu rotaciju oko čvora 20:		čime čvor 33 više nije kritičan. Na kraju, radimo levu rotaciju oko čvora 20:
	32		32
	/ \		/ \

KockaAdmiralac: Ispravljeno rešenje osmog zadatka

2020-11-02T17:37:55Z

Ispravljeno rešenje osmog zadatka

← Старија измена		Верзија на датум 2. новембар 2020. у 19:37
Ред 254:		Ред 254:

	=== Rešenje ===		=== Rešenje ===
	Cena podstabla ~~koje sadrži ključeve~~ <math>K_{i+1}~~, K_~~{i+2}, .~~..,~~ K_j</math> ~~označava se sa~~ <math>T_{ij}</math> ~~i ima vrednost~~ <math>~~q_i~~ + p_{i+1} + q_{i+1} + ~~...~~ + ~~p_j~~ + ~~q_j~~</math>, što je zapravo zbir verovatnoća pretraživanja svih internih i eksternih čvorova tog podstabla. Pošto jedan čvor ima svoju verovatnoću pretraživanja kao i dva podstabla, dobijamo da je cena celog stabla čiji je koren <math>~~K_r~~</math> ~~rekurzivno definisana sa~~ <math>T = T_{1,r} + ~~p_r + T_~~{~~r+1,n~~}</math>.		Cena podstabla se definiše kao:
			: <math>C_{ij} = \sum_{k = i+1}^j p_k (h_k + 1) + \sum_{k = i}^j q_k h_k</math>
			gde su <math>p_i</math> verovatnoće uspešnog, <math>q_i</math> neuspešnog pretraživanja a <math>h_i</math> visine čvorova <math>K_i</math>.

			Uzimamo da su prvi čvor levog podstabla i poslednji čvor desnog podstabla trenutnog čvora po ''inorder'' poretku <math>K_i</math> i <math>K_j</math> a trenutni čvor <math>K_k</math>. Pošto je visina u formuli za cene levog i desnog podstabla sada povećana za 1, dobijamo da je ukupna cena trenutnog čvora jednaka:
			: <math>C_{ij} = \left(\sum_{m = i+1}^{k-1} p_m (h_m + 2) + \sum_{m = i}^{k-1} q_m (h_m + 1)\right) + p_k + \left(\sum_{m = k+1}^{j} p_m (h_m + 2) + \sum_{m = k}^{j} q_m (h_m + 1)\right) =</math>
			: <math>= \left(\sum_{m = i+1}^{k-1} p_m (h_m + 1) + \sum_{m = i+1}^{k-1} p_m + \sum_{m = i}^{k-1} q_m h_m + \sum_{m = i}^{k-1} q_m\right) + p_k + \left(\sum_{m = k+1}^{j} p_m (h_m + 1) + \sum_{m = k+1}^{j} p_m + \sum_{m = k}^{j} q_m h_m + \sum_{m = k}^{j} q_m\right) =</math>
			: <math>= \left(\sum_{m = i+1}^{k-1} p_m (h_m + 1) + \sum_{m = i}^{k-1} q_m h_m\right) + \left(\sum_{m = k+1}^{j} p_m (h_m + 1) + \sum_{m = k}^{j} q_m h_m\right) + w_{ij} =</math>
			: <math>= C_{i,k-1} + C_{k,j} + w_{ij}</math>

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

KockaAdmiralac: Ispravke u trećem, četvrtom i sedmom zadatku

2020-11-02T14:43:27Z

Ispravke u trećem, četvrtom i sedmom zadatku

← Старија измена		Верзија на датум 2. новембар 2020. у 16:43
Ред 109:		Ред 109:
	high = n		high = n
	if arr[1] ≤ arr[n] then		if arr[1] ≤ arr[n] then
	return 1		return arr[1]
	end_if		end_if
	while low ≤ high do		while low ≤ high do
	mid = (high + low) / 2		mid = (high + low) / 2
	if arr[mid] < arr[mid-1] then		if arr[mid] < arr[mid-1] then
	return mid		return arr[mid]
	else if arr[mid] < arr[1] then		else if arr[mid] < arr[1] then
	high = mid - 1		high = mid - 1
Ред 150:		Ред 150:
	{\| class="wikitable"		{\| class="wikitable"
	\|+ Stanje povećane tabele nakon unosa ključa 29		\|+ Stanje povećane tabele nakon unosa ključa 29
	\| 5 \|\| 6 \|\| 6 \|\| 18 \|\| 22 \|\| 22 \|\| 23 \|\| 25 \|\| 29 \|\| 38 ~~\|\| 40~~		\| 5 \|\| 6 \|\| 6 \|\| 18 \|\| 22 \|\| 22 \|\| 23 \|\| 25 \|\| 28 \|\| 29 \|\| 38
	\|-		\|-
	\| 1 \|\| 1 \|\| 0 \|\| 1 \|\| 0 \|\| 0 \|\| 0 \|\| 1 \|\| 1 \|\| 1 \|\| 0		\| 1 \|\| 1 \|\| 0 \|\| 1 \|\| 0 \|\| 0 \|\| 0 \|\| 1 \|\| 0 \|\| 1 \|\| 1
			\|-
			\| colspan="11" \| Takođe je moguće da se, uz napomenu, pri nailasku na ključ veći od traženog gleda levo umesto desno.
	\|}		\|}
	{\| class="wikitable"		{\| class="wikitable"
Ред 159:		Ред 161:
	\|-		\|-
	\| 1 \|\| 1 \|\| 0 \|\| 1 \|\| 0 \|\| 0 \|\| 0 \|\| 1 \|\| 1 \|\| 1 \|\| 1		\| 1 \|\| 1 \|\| 0 \|\| 1 \|\| 0 \|\| 0 \|\| 0 \|\| 1 \|\| 1 \|\| 1 \|\| 1
			\|-
			\| colspan="11" \| Postoje dva načina na koji možemo da rešimo situaciju kad naiđemo na 38 i ne možemo da ga pomerimo udesno:
			* kažemo da se desila greška pošto ne možemo dalje da umećemo, ili
			* pomerimo ključ 29 ulevo (preporučeno).
	\|}		\|}
	{\| class="wikitable"		{\| class="wikitable"
Ред 229:		Ред 235:
	<div class="abc-list">		<div class="abc-list">
	# Pseudokod je dat ispod.		# Pseudokod je dat ispod.
	# ''ceil(h / 2)''		# ''ceil(h / 2)''. Ovo je zato što su podstabla Fibonačijevih stabala isto Fibonačijeva stabla, tako da se najmanja visina lista izračunava kao najmanja visina lista Fibonačijevog stabla čija je visina za 2 manja od trenutnog uvećana za 1.
	# Ovakva stabla, koja su najgori slučajevi AVL stabala, dobila su ime po Fibonačijevim brojevima <!--(koji su, pak, dobili naziv po poznatom srpskom glumcu Miljanu Fibonačiju Markoviću)--> čija se rekurzivna definicija veoma malo razlikuje ~~sa rekurzivnom definicijom~~ broja čvorova ovakvih stabala u zavisnosti od njihove visine.		# Ovakva stabla, koja su najgori slučajevi AVL stabala, dobila su ime po Fibonačijevim brojevima <!--(koji su, pak, dobili naziv po poznatom srpskom glumcu Miljanu Fibonačiju Markoviću)--> čija se rekurzivna definicija veoma malo razlikuje od rekurzivne definicije broja čvorova ovakvih stabala u zavisnosti od njihove visine.
	</div>		</div>
	<syntaxhighlight lang="milo">		<syntaxhighlight lang="milo">

Ivan Pešić: /* 9 -> 6 */

2020-11-02T11:47:49Z

9 -> 6

← Старија измена		Верзија на датум 2. новембар 2020. у 13:47
Ред 144:		Ред 144:
	{\| class="wikitable"		{\| class="wikitable"
	\|+ Stanje povećane tabele nakon unosa ključa 6		\|+ Stanje povećane tabele nakon unosa ključa 6
	\| 5 \|\| 6 \|\| 9 \|\| 18 \|\| 22 \|\| 22 \|\| 23 \|\| 25 \|\| 28 \|\| 38 \|\| 40		\| 5 \|\| 6 \|\| 6 \|\| 18 \|\| 22 \|\| 22 \|\| 23 \|\| 25 \|\| 28 \|\| 38 \|\| 40
	\|-		\|-
	\| 1 \|\| 1 \|\| 0 \|\| 1 \|\| 0 \|\| 0 \|\| 0 \|\| 1 \|\| 0 \|\| 1 \|\| 0		\| 1 \|\| 1 \|\| 0 \|\| 1 \|\| 0 \|\| 0 \|\| 0 \|\| 1 \|\| 0 \|\| 1 \|\| 0
Ред 150:		Ред 150:
	{\| class="wikitable"		{\| class="wikitable"
	\|+ Stanje povećane tabele nakon unosa ključa 29		\|+ Stanje povećane tabele nakon unosa ključa 29
	\| 5 \|\| 6 \|\| 9 \|\| 18 \|\| 22 \|\| 22 \|\| 23 \|\| 25 \|\| 29 \|\| 38 \|\| 40		\| 5 \|\| 6 \|\| 6 \|\| 18 \|\| 22 \|\| 22 \|\| 23 \|\| 25 \|\| 29 \|\| 38 \|\| 40
	\|-		\|-
	\| 1 \|\| 1 \|\| 0 \|\| 1 \|\| 0 \|\| 0 \|\| 0 \|\| 1 \|\| 1 \|\| 1 \|\| 0		\| 1 \|\| 1 \|\| 0 \|\| 1 \|\| 0 \|\| 0 \|\| 0 \|\| 1 \|\| 1 \|\| 1 \|\| 0
Ред 156:		Ред 156:
	{\| class="wikitable"		{\| class="wikitable"
	\|+ Stanje povećane tabele nakon unosa ključa 35		\|+ Stanje povećane tabele nakon unosa ključa 35
	\| 5 \|\| 6 \|\| 9 \|\| 18 \|\| 22 \|\| 22 \|\| 23 \|\| 25 \|\| 29 \|\| 35 \|\| 38		\| 5 \|\| 6 \|\| 6 \|\| 18 \|\| 22 \|\| 22 \|\| 23 \|\| 25 \|\| 29 \|\| 35 \|\| 38
	\|-		\|-
	\| 1 \|\| 1 \|\| 0 \|\| 1 \|\| 0 \|\| 0 \|\| 0 \|\| 1 \|\| 1 \|\| 1 \|\| 1		\| 1 \|\| 1 \|\| 0 \|\| 1 \|\| 0 \|\| 0 \|\| 0 \|\| 1 \|\| 1 \|\| 1 \|\| 1
Ред 162:		Ред 162:
	{\| class="wikitable"		{\| class="wikitable"
	\|+ Stanje povećane tabele nakon uklanjanja ključa 18		\|+ Stanje povećane tabele nakon uklanjanja ključa 18
	\| 5 \|\| 6 \|\| 9 \|\| 18 \|\| 22 \|\| 22 \|\| 23 \|\| 25 \|\| 29 \|\| 35 \|\| 38		\| 5 \|\| 6 \|\| 6 \|\| 18 \|\| 22 \|\| 22 \|\| 23 \|\| 25 \|\| 29 \|\| 35 \|\| 38
	\|-		\|-
	\| 1 \|\| 1 \|\| 0 \|\| 0 \|\| 0 \|\| 0 \|\| 0 \|\| 1 \|\| 1 \|\| 1 \|\| 1		\| 1 \|\| 1 \|\| 0 \|\| 0 \|\| 0 \|\| 0 \|\| 0 \|\| 1 \|\| 1 \|\| 1 \|\| 1