A-sort

Odeslat odpověď

Smajlíci
:D :) :( :o :shock: :? 8) :lol: :x :P :oops: :cry: :evil: :twisted: :roll: :wink: :!: :?: :idea: :arrow: :| :mrgreen:
BBCode je zapnutý
[img] je zapnutý
[flash] je vypnutý
[url] je zapnuté
Smajlíci jsou zapnutí
Přehled tématu
   

Rozšířit náhled Přehled tématu: A-sort

Re: A-sort

od Kuba » 5. 2. 2008 14:39

No, co cert nechtel, dneska jsem to dostal u zkousky. Kdyz to tam clovek napise tak jak to je v textu, tak je to ok. A je to tedy tak, ze kdyz to neni definovane, tak je to PRV.

Teda, abyste to spatne nepochopili, ja si nestezuju ze sem to dostal :) Myslim ze A-sort je jedna z nejjednodussich otazek.

Re: A-sort

od Che » 4. 2. 2008 16:17

Já si taky myslím, že tam je chyba... Podle mne by ten začátek měl vypadat takhle:

Kód: Vybrat vše

if Prv <> kořen T then
  t := otec(Prv) { listy nemají definováno Ht }
else
  t := Prv
endif

while t <> kořen T a Ht(1) < x do
  t := otec(t)
enddo

{ i kdyby předchozí cyklus skončil kvůli tomu, že jsme došli až ke kořeni, tak mohlo už začit platit také: Ht(1) >= x }
if t = kořen T a Ht(1) < x then
  { nedělej nic }
else
  t = St(1)
endif

{ Nyní je jisté, že v nasledujícím cyklu se i inkrementuje alespoň jednou (pokud t není list, to se pak přeskočí celý cyklus)
  protože bude platit Ht(1) < x a proto v bude definováno korektně }

while t <> list do
  i := 1
  while Ht(i) < x a i < Ro(t) do i := i + 1 enddo
  if i > 1 then
    v := St(i-1)
  else
    v := Sv(Ro(v))
  endif
  t := St(i)
enddo

Re: A-sort

od rastik » 4. 2. 2008 00:59

Kuba píše:Jo, ale kdyz dojdes na to misto, kde Ht(1) > x, tak pak je tam i :=1, while Ht(1) < x (coz neni) tak i++, takze i je stale 1. A pak je tam if i > 1 (coz neni) else v := Sv(ro(v)). A v tomto okamziku jeste v nebylo definovano, takze kde se vezme Sv a ro(v)?
V tom úvodnom príspevku to nie je odsadené, ale všetko to čo píšeš je obalené v

Kód: Vybrat vše

while t <> list do
Takže sa tam vôbec nedostane, pretože sa nedostal z prvého listu.

Re: A-sort

od Kuba » 3. 2. 2008 21:53

Jo, ale kdyz dojdes na to misto, kde Ht(1) > x, tak pak je tam i :=1, while Ht(1) < x (coz neni) tak i++, takze i je stale 1. A pak je tam if i > 1 (coz neni) else v := Sv(ro(v)). A v tomto okamziku jeste v nebylo definovano, takze kde se vezme Sv a ro(v)?

Re: A-sort

od rastik » 3. 2. 2008 20:42

IMHO je ten algoritmus OK. Začínaš v liste a ideš nahor, kým Ht(1) < x. Teda buď dojdeš na miesto, kde Ht(1) >= x, alebo si stále na začiatku, v prvom liste. A vtedy sa celá ta vetva preskočí a v sa vôbec nijako nedefinuje. A ani nemusí, pretože pri tejto kombinácii sa v algoritme nepoužije - nový prvok nepôjde na začiatok listu.

Re: A-sort

od Kuba » 3. 2. 2008 16:28

Jo, takhle by to asi slo. No... skripta by si zaslouzila mensi revizi...

Re: A-sort

od chucky » 3. 2. 2008 16:27

aha, jasne, na to som zabudol.

V tom pripade snad nevadi, ze v nie je na zaciatku definovane. Staci predpokladat, ze

Kód: Vybrat vše

v := Sv(ro(v))
nevyhodi Null Pointer Exception, ale v zostane nedefinovane.
A ked by v zostalo nedefinovane az do konca, tak

Kód: Vybrat vše

Nasl(v):=t'
by malo znamenat

Kód: Vybrat vše

Prv:=t'

Re: A-sort

od Kuba » 3. 2. 2008 16:18

Toho potrebujes, abys mohl updatovat ten spojak listu (Next(v) = t), kdyz t je nejlevejsi prvek toho podstromu do ktereho pridavas

Re: A-sort

od chucky » 3. 2. 2008 16:17

ja to vidim takto:
tento kod mi najde vrchol, do ktoreho podstromu budem pridavat:

Kód: Vybrat vše

t := Prv
while t <> koren T a Ht(1) < x do
t := otec(t)
enddo
a potom uz len leziem dolu po ceste, kde by som x hladal. Nejako mi nie je jasne, kde by som potreboval laveho brata.. Podla mna ked i = 1, tak pridavam do podstromu St(1).

Re: A-sort

od Kuba » 3. 2. 2008 16:06

chucky píše:No zrejme tam bude chyba.
Neviem, co tym

Kód: Vybrat vše

if i > 1 then
v := St(i − 1)
else
v := Sv(ro(v))
endif
malo byt myslene, ale ja by som tento usek kodu uplne vynechal (opravte ma, ak v tom vidite problem).
No tim bylo myslene, ze kdyz i = 1, tak predchudce Ht(1) (v lex. usp.) se musi hledat jako maximalni prvek jeho leveho bratra (ktery je vzdy drzen v promenne v - az na prvni kolo, kdy prave neni inicializovan)

Re: A-sort

od chucky » 3. 2. 2008 16:03

No zrejme tam bude chyba.
Neviem, co tym

Kód: Vybrat vše

if i > 1 then
v := St(i − 1)
else
v := Sv(ro(v))
endif
malo byt myslene, ale ja by som tento usek kodu uplne vynechal (opravte ma, ak v tom vidite problem). vrochol v sa potom dalej nikde nepouziva.(EDIT: sorry, predsa len sa pouziva :) )
A podmienku predchadzajuceho while cyklu by som prerovnal na

Kód: Vybrat vše

while i < Ro(t) a Ht(i) < x
, lebo Ht(Ro(t)) nie je definovane (a predpokladam skratene vyhodnocovanie).

Ale celkovo som tie kody velmi nestudoval, algoritmy by som popisal skor svojimi slovami, alebo nejakym este viac pseudo kodom.

Inak chyba je uz na druhom riadku algoritmu:

Kód: Vybrat vše

t := Prv
while t <> koren T a Ht(1) < x do
Prv je list a pre listy Ht() nie je definovane.
Asi na prvom riadku malo byt t:=otec(Prv).
Ale este raz, velmi by som sa nesnazil ucit tie kody naspamat.

A-sort

od Kuba » 3. 2. 2008 15:24

Kód: Vybrat vše

A-Insert(x):
t := Prv
while t <> koren T a Ht(1) < x do
t := otec(t)
enddo
while t <> list do
i := 1
while Ht(i) < x a i < Ro(t) do i := i + 1 enddo
if i > 1 then
v := St(i − 1)
else
v := Sv(ro(v))
endif
t := St(i)
enddo
Zda se mi to, nebo je tam mensi chybka?
Konkretne: Zacinam v prv. lezu nahoru, dokud Ht(1) < x, z whileu vyskocim kdyz Ht(1) > x, i:=1, ten while neudelam, protoze Ht(1) > x, cili i = 1, skocim do Else vetve, ale ted nevim co je vrchol v...

Nahoru