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

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

2024-09-13T00:09:13Z

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

← Старија измена		Верзија на датум 13. септембар 2024. у 02:09
Ред 105:		Ред 105:
	Kompaktnija forma ovog stabla može se dobiti tako što sve čvorove koji imaju samo jednu putanju do listova zamenimo sa listovima koji sadrže pokazivače na zapise na koje su listovi prethodno pokazivali i celu vrednost ključa. U tom slučaju ne mora da postoji čvor za kraj ključa.		Kompaktnija forma ovog stabla može se dobiti tako što sve čvorove koji imaju samo jednu putanju do listova zamenimo sa listovima koji sadrže pokazivače na zapise na koje su listovi prethodno pokazivali i celu vrednost ključa. U tom slučaju ne mora da postoji čvor za kraj ključa.

	<~~syntaxhighlight lang="milo"~~>		{{Милокод\|<nowiki>
	TRIE COMPACTION(root)		TRIE COMPACTION(root)
	if root ≠ nil then		if root ≠ nil then
Ред 113:		Ред 113:
	end_if		end_if
	end_if		end_if
	</~~syntaxhighlight~~>		</nowiki>}}
	<~~syntaxhighlight lang="milo"~~>		{{Милокод\|<nowiki>
	COMPACT(node, str)		COMPACT(node, str)
	if key(node) = '*' then		if key(node) = '*' then
Ред 131:		Ред 131:
	return nil		return nil
	end_if		end_if
	</~~syntaxhighlight~~>		</nowiki>}}

	== 4. zadatak ==		== 4. zadatak ==
Ред 138:		Ред 138:

	=== Rešenje ===		=== Rešenje ===
	<~~syntaxhighlight lang="milo"~~>		{{Милокод\|<nowiki>
	DELETE(root, m, key)		DELETE(root, m, key)
	parent = nil		parent = nil
Ред 185:		Ред 185:
	pointers(parent)[parent_index-1] = nil		pointers(parent)[parent_index-1] = nil
	end_if		end_if
	</~~syntaxhighlight~~>		</nowiki>}}

	== 5. zadatak ==		== 5. zadatak ==
Ред 263:		Ред 263:
	Struktura koja se ovde može upotrebiti je B+ stablo, jer nam dozvoljava lak sekvencijalni pristup (za izlistavanje svih studenata u rasponu od dve godine) kao i brzo pronalaženje prvog ključa (za prvog studenta iz raspona). Ključevi ovakvog stabla mogu biti kombinacija godine i broja indeksa studenta, tako da je godina primarni a broj indeksa sekundarni ključ.		Struktura koja se ovde može upotrebiti je B+ stablo, jer nam dozvoljava lak sekvencijalni pristup (za izlistavanje svih studenata u rasponu od dve godine) kao i brzo pronalaženje prvog ključa (za prvog studenta iz raspona). Ključevi ovakvog stabla mogu biti kombinacija godine i broja indeksa studenta, tako da je godina primarni a broj indeksa sekundarni ključ.

	<~~syntaxhighlight lang="milo"~~>		{{Милокод\|<nowiki>
	FIND STUDENTS IN RANGE(structure, year1, year2)		FIND STUDENTS IN RANGE(structure, year1, year2)
	p = structure		p = structure
Ред 300:		Ред 300:
	end_for		end_for
	return arr		return arr
	</~~syntaxhighlight~~>		</nowiki>}}

	== 7. zadatak ==		== 7. zadatak ==

KockaAdmiralac: PNG u SVG

2022-02-13T21:22:19Z

PNG u SVG

← Старија измена		Верзија на датум 13. фебруар 2022. у 23:22
Ред 27:		Ред 27:

	Da je stablo bilo obično B stablo reda 4, u drugom koraku bi se pozajmljivalo od desnog brata umesto od levog brata, jer B stabla nemaju pravilo da se prvo pozajmljuje od pravog brata. Takođe, ključevi 21 i 57 ne bi stajali u središnjem polju čvora, već najlevljem.		Da je stablo bilo obično B stablo reda 4, u drugom koraku bi se pozajmljivalo od desnog brata umesto od levog brata, jer B stabla nemaju pravilo da se prvo pozajmljuje od pravog brata. Takođe, ključevi 21 i 57 ne bi stajali u središnjem polju čvora, već najlevljem.
	<gallery>		<gallery class="transparent-svg">
	ASP2 K2 2019 zadatak 1 stablo.~~png~~ \| Originalno crveno-crno stablo		ASP2 K2 2019 zadatak 1 stablo.svg \| Originalno crveno-crno stablo
	ASP2 K2 2019 zadatak 1 korak 1.~~png~~ \| Crveno-crno stablo nakon brisanja čvora 63		ASP2 K2 2019 zadatak 1 korak 1.svg \| Crveno-crno stablo nakon brisanja čvora 63
	ASP2 K2 2019 zadatak 1 korak 2.~~png~~ \| Crveno-crno stablo nakon brisanja čvora 60		ASP2 K2 2019 zadatak 1 korak 2.svg \| Crveno-crno stablo nakon brisanja čvora 60
	</gallery>		</gallery>

Etfsibg: /* Rešenje */

2021-12-06T15:41:56Z

Rešenje

← Старија измена		Верзија на датум 6. децембар 2021. у 17:41
Ред 296:		Ред 296:
	i = i + 1		i = i + 1
	j = j + 1		j = j + 1
	~~end_for~~		end_while
	p = next(p)		p = next(p)
	~~end_while~~		end_for
	return arr		return arr
	</syntaxhighlight>		</syntaxhighlight>

KockaAdmiralac: +pretpostavka u sedmom zadatku

2021-02-18T21:47:24Z

+pretpostavka u sedmom zadatku

← Старија измена		Верзија на датум 18. фебруар 2021. у 23:47
Ред 312:		Ред 312:
	Tako je veličina jednog čvora stabla u prvoj varijanti jednaka <math>(m-1) \cdot (32 + 64) + m \cdot 64 = m \cdot 96 + m \cdot 64 - 96 = m \cdot 160 - 96</math>. Ako pretpostavimo da je ovo jednako veličini bloka, dobijamo <math>m \cdot 160 = 16480 \implies m = \frac{16480}{160} = 103</math>.		Tako je veličina jednog čvora stabla u prvoj varijanti jednaka <math>(m-1) \cdot (32 + 64) + m \cdot 64 = m \cdot 96 + m \cdot 64 - 96 = m \cdot 160 - 96</math>. Ako pretpostavimo da je ovo jednako veličini bloka, dobijamo <math>m \cdot 160 = 16480 \implies m = \frac{16480}{160} = 103</math>.

	U drugoj varijanti, veličina čvora je jednaka <math>(m-1) \cdot 256 + m \cdot 64 = m \cdot 256 - 256 + m \cdot 64 = m \cdot 320 - 256</math>. Sa istom pretpostavkom dobijamo <math>m \cdot 320 = 16640 \implies m = \frac{16640}{320} = 52</math>.		U drugoj varijanti, ako pretpostavimo da se ključ može zaključiti iz strukture pa se ne čuva odvojeno, veličina čvora je jednaka <math>(m-1) \cdot 256 + m \cdot 64 = m \cdot 256 - 256 + m \cdot 64 = m \cdot 320 - 256</math>. Sa istom pretpostavkom dobijamo <math>m \cdot 320 = 16640 \implies m = \frac{16640}{320} = 52</math>.

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

KockaAdmiralac: Ispravka algoritma za 6. zadatak od `<@619874529057177620>`

2021-01-20T15:35:16Z

Ispravka algoritma za 6. zadatak od `<@619874529057177620>`

← Старија измена		Верзија на датум 20. јануар 2021. у 17:35
Ред 150:		Ред 150:
	found = true		found = true
	break		break
	else if keys(p) > key then		else if keys(p)[i] > key then
	parent = p		parent = p
	parent_index = i		parent_index = i
Ред 267:		Ред 267:
	p = structure		p = structure
	while (not IS_LEAF(p)) do		while (not IS_LEAF(p)) do
	if ~~key~~(p) < year1 then		for i = 1 to num(p) do
	p = ~~right~~(p)		if keys(p)[i] > year1 then
	~~else~~		p = pointers(p)[i-1]
	p = ~~left~~(p)		break
			end_if
			end_for
			if i = num(p)+1 then
			p = pointers(p)[num(p)]
	end_if		end_if
	end_while		end_while
	length = 0		length = 0
	q = p		q = p
	while (q ≠ nil) and (~~year~~(q) ≤ year2) do		key_index = 1
			while (q ≠ nil) and (years(q)[key_index] ≤ year2) do
	length = length + 1		length = length + 1
	q = next(q)		if node_index = num(q) then
			key_index = 1
			q = next(q)
			else
			key_index = key_index + 1
			end_if
	end_while		end_while
	arr = ALLOCATE(length)		arr = ALLOCATE(length)
	for i = 1 to length do		for i = 1 to length do
	arr[i] = p		j = 1
			while j < num(p) and i < length do
			arr[i] = students(p)[j]
			i = i + 1
			j = j + 1
			end_for
	p = next(p)		p = next(p)
	end_while		end_while

KockaAdmiralac: Prosledi nepromenjeni string u COMPACT za brata

2021-01-20T13:27:08Z

Prosledi nepromenjeni string u COMPACT za brata

← Старија измена		Верзија на датум 20. јануар 2021. у 15:27
Ред 125:		Ред 125:
	return compacted_child		return compacted_child
	else		else
	COMPACT(right(node))		COMPACT(right(node), str)
	if compacted_child ≠ nil then		if compacted_child ≠ nil then
	left(node) = compacted_child		left(node) = compacted_child

KockaAdmiralac: left -> right; right -> left

2021-01-20T13:24:35Z

left -> right; right -> left

← Старија измена		Верзија на датум 20. јануар 2021. у 15:24
Ред 120:		Ред 120:
	return str		return str
	end_if		end_if
	compacted_child = COMPACT(~~right~~(node), str + key(node))		compacted_child = COMPACT(left(node), str + key(node))
	if ~~left~~(node) = nil then		if right(node) = nil then
	FREENODE(node)		FREENODE(node)
	return compacted_child		return compacted_child
	else		else
	COMPACT(~~left~~(node))		COMPACT(right(node))
	if compacted_child ≠ nil then		if compacted_child ≠ nil then
	~~right~~(node) = compacted_child		left(node) = compacted_child
	end_if		end_if
	return nil		return nil

Ivan Pešić: /* typo*/

2020-12-14T01:35:21Z

typo

← Старија измена		Верзија на датум 14. децембар 2020. у 03:35
Ред 135:		Ред 135:
	== 4. zadatak ==		== 4. zadatak ==
	=== Postavka ===		=== Postavka ===
	Napisati u pseudokodu funkciju koja iz '<nowiki />''top-down''' stabla ''m''-arnog pretraživanja ~~briše~~ na čiji koren pokazuje pokazivač ''root'' briše zadati ključ key.		Napisati u pseudokodu funkciju koja iz '<nowiki />''top-down''' stabla ''m''-arnog pretraživanja na čiji koren pokazuje pokazivač ''root'' briše zadati ključ key.

	=== Rešenje ===		=== Rešenje ===

KockaAdmiralac: Rešenje 8. zadatka

2020-12-14T00:12:54Z

Rešenje 8. zadatka

@@ Ред 308: / Ред 308: @@
 === Rešenje ===
 [[Категорија:АСП2]]
 [[Категорија:Рокови]]

IvnSvc: /* Rešenje */ Преправио 61 у 64. 64 се нигде не појављује у задатку па је врв грешка у куцању

2020-11-21T21:48:40Z

Rešenje: Преправио 61 у 64. 64 се нигде не појављује у задатку па је врв грешка у куцању

← Старија измена		Верзија на датум 21. новембар 2020. у 23:48
Ред 52:		Ред 52:
	/ \| \| \		/ \| \| \
	[ 6\|20\| ]->[22\|25\|33]->[42\|64\| ]->[71\|81\| ]		[ 6\|20\| ]->[22\|25\|33]->[42\|64\| ]->[71\|81\| ]
	Ključ 21 se umeće levo od ključa 22. Dolazi do preloma, 21 i 22 ostaju u čvoru, 22 ide u roditeljski čvor, a 25 i 33 se odvajaju u novi čvor. Pošto u roditelju nema mesta, i on se prelama tako da koren postaje čvor sa 22, levi čvor sa 20 i desni sa 33 i 61.		Ključ 21 se umeće levo od ključa 22. Dolazi do preloma, 21 i 22 ostaju u čvoru, 22 ide u roditeljski čvor, a 25 i 33 se odvajaju u novi čvor. Pošto u roditelju nema mesta, i on se prelama tako da koren postaje čvor sa 22, levi čvor sa 20 i desni sa 33 i 64.
	(22\| \| )		(22\| \| )
	/ \		/ \
	(20\| \| ) (33\|61\| )		(20\| \| ) (33\|64\| )
	/ \| / \| \		/ \| / \| \
	[ 6\|20\| ]->[21\|22\| ]->[25\|33\| ]->[42\|64\| ]->[71\|81\| ]		[ 6\|20\| ]->[21\|22\| ]->[25\|33\| ]->[42\|64\| ]->[71\|81\| ]
Ред 61:		Ред 61:
	(22\| \| )		(22\| \| )
	/ \		/ \
	(20\| \| ) (33\|61\| )		(20\| \| ) (33\|64\| )
	/ \| / \| \		/ \| / \| \
	[ 6\|20\| ]->[21\|22\| ]->[25\|27\|33]->[42\|64\| ]->[71\|81\| ]		[ 6\|20\| ]->[21\|22\| ]->[25\|27\|33]->[42\|64\| ]->[71\|81\| ]
Ред 67:		Ред 67:
	(22\| \| )		(22\| \| )
	/ \		/ \
	(20\| \| ) (27\|61\| )		(20\| \| ) (27\|64\| )
	/ \| / \| \		/ \| / \| \
	[ 6\|20\| ]->[21\|22\| ]->[25\|27\| ]->[42\|64\| ]->[71\|81\| ]		[ 6\|20\| ]->[21\|22\| ]->[25\|27\| ]->[42\|64\| ]->[71\|81\| ]
Ред 73:		Ред 73:
	(22\| \| )		(22\| \| )
	/ \		/ \
	(20\| \| ) (61\| \| )		(20\| \| ) (64\| \| )
	/ \| / \|		/ \| / \|
	[ 6\|20\| ]->[21\|22\| ]->[25\|42\|64]->[71\|81\| ]		[ 6\|20\| ]->[21\|22\| ]->[25\|42\|64]->[71\|81\| ]
	Pri uklanjanju ključa 6, ostaje manje nego dovoljno ključeva u tom čvoru. Pozajmica od brata nije moguća, i zato se taj čvor spaja sa svojim desnim bratom. U tom procesu roditeljski čvor ostaje prazan, tako da se spajaju svi unutrašnji čvorovi u jedan, čime se dobija konačno stablo:		Pri uklanjanju ključa 6, ostaje manje nego dovoljno ključeva u tom čvoru. Pozajmica od brata nije moguća, i zato se taj čvor spaja sa svojim desnim bratom. U tom procesu roditeljski čvor ostaje prazan, tako da se spajaju svi unutrašnji čvorovi u jedan, čime se dobija konačno stablo:
	(22\|61\| )		(22\|64\| )
	/ \| \		/ \| \
	[20\|21\|22]->[25\|42\|64]->[71\|81\| ]		[20\|21\|22]->[25\|42\|64]->[71\|81\| ]

← Старија измена		Верзија на датум 21. новембар 2020. у 23:48
Ред 52:		Ред 52:
	/ \| \| \		/ \| \| \
	[ 6\|20\| ]->[22\|25\|33]->[42\|64\| ]->[71\|81\| ]		[ 6\|20\| ]->[22\|25\|33]->[42\|64\| ]->[71\|81\| ]
	Ključ 21 se umeće levo od ključa 22. Dolazi do preloma, 21 i 22 ostaju u čvoru, 22 ide u roditeljski čvor, a 25 i 33 se odvajaju u novi čvor. Pošto u roditelju nema mesta, i on se prelama tako da koren postaje čvor sa 22, levi čvor sa 20 i desni sa 33 i 61.		Ključ 21 se umeće levo od ključa 22. Dolazi do preloma, 21 i 22 ostaju u čvoru, 22 ide u roditeljski čvor, a 25 i 33 se odvajaju u novi čvor. Pošto u roditelju nema mesta, i on se prelama tako da koren postaje čvor sa 22, levi čvor sa 20 i desni sa 33 i 64.
	(22\| \| )		(22\| \| )
	/ \		/ \
	(20\| \| ) (33\|61\| )		(20\| \| ) (33\|64\| )
	/ \| / \| \		/ \| / \| \
	[ 6\|20\| ]->[21\|22\| ]->[25\|33\| ]->[42\|64\| ]->[71\|81\| ]		[ 6\|20\| ]->[21\|22\| ]->[25\|33\| ]->[42\|64\| ]->[71\|81\| ]
Ред 61:		Ред 61:
	(22\| \| )		(22\| \| )
	/ \		/ \
	(20\| \| ) (33\|61\| )		(20\| \| ) (33\|64\| )
	/ \| / \| \		/ \| / \| \
	[ 6\|20\| ]->[21\|22\| ]->[25\|27\|33]->[42\|64\| ]->[71\|81\| ]		[ 6\|20\| ]->[21\|22\| ]->[25\|27\|33]->[42\|64\| ]->[71\|81\| ]
Ред 67:		Ред 67:
	(22\| \| )		(22\| \| )
	/ \		/ \
	(20\| \| ) (27\|61\| )		(20\| \| ) (27\|64\| )
	/ \| / \| \		/ \| / \| \
	[ 6\|20\| ]->[21\|22\| ]->[25\|27\| ]->[42\|64\| ]->[71\|81\| ]		[ 6\|20\| ]->[21\|22\| ]->[25\|27\| ]->[42\|64\| ]->[71\|81\| ]
Ред 73:		Ред 73:
	(22\| \| )		(22\| \| )
	/ \		/ \
	(20\| \| ) (61\| \| )		(20\| \| ) (64\| \| )
	/ \| / \|		/ \| / \|
	[ 6\|20\| ]->[21\|22\| ]->[25\|42\|64]->[71\|81\| ]		[ 6\|20\| ]->[21\|22\| ]->[25\|42\|64]->[71\|81\| ]
	Pri uklanjanju ključa 6, ostaje manje nego dovoljno ključeva u tom čvoru. Pozajmica od brata nije moguća, i zato se taj čvor spaja sa svojim desnim bratom. U tom procesu roditeljski čvor ostaje prazan, tako da se spajaju svi unutrašnji čvorovi u jedan, čime se dobija konačno stablo:		Pri uklanjanju ključa 6, ostaje manje nego dovoljno ključeva u tom čvoru. Pozajmica od brata nije moguća, i zato se taj čvor spaja sa svojim desnim bratom. U tom procesu roditeljski čvor ostaje prazan, tako da se spajaju svi unutrašnji čvorovi u jedan, čime se dobija konačno stablo:
	(22\|61\| )		(22\|64\| )
	/ \| \		/ \| \
	[20\|21\|22]->[25\|42\|64]->[71\|81\| ]		[20\|21\|22]->[25\|42\|64]->[71\|81\| ]