FONForum

Hvala Vlacke. :>

Objasniti na ovaj nacin (bez crtanja) malo je nezahvalno ali pokusacu...
1. korak: svi cvorovi na istom nivou se spajaju (vezama istim kao dete-roditelj)
2. korak: na svakom od cvorova raskidamo vezu sa roditeljem osim za prvi cvor
3. korak: sada svaki cvor ima 2 veze, jednu sa roditeljem (koji mu je ranije bio brat) i sa svojim bratom (naknadno povezanim)
4. korak: okrecemo stablo i ono izgleda kao klasicno binarno stablo

Preporucila bih da crtate uz ove korake, po mogucstvu u dve boje za nove i stare veze (meni je pomoglo).

_________________
"Kroz otprilike dve godine prestace da bude nimfica i pretvorice se u "mladu devojku", a onda u "studentkinju" - taj uzas nad uzasima!" - Vladimir Nabokov

Ja bih ovde samo nesto malo drugacije uradio, ali ne znam da li je moj nacin tacan. Prvi deo mi je ok, ali ovako bih ja uradio drugi:

while (current.sledeci!=root)
current=current.sledeci;// znaci sve dok ne dodje do korena da ide na sledeceg. A kada dodje ide sledece:

CvorListe novi = new CvorListe(current, root, p);
current.sledeci=novi;
root.prethodni=novi;

Odnosno mislim da ovo if (current.sledeci==null) nema smisla, jer ono nikad nece biti null, posto je u pitanju ciklicna lista. Mozda i ja gresim, bilo dobro kada bi nas ovi maheri u programiranju ispravili, da znamo 100 %.

P.S. Hvala April za prethodni odgovor.

_________________
"Some will win, some will lose, Some were born to sing the blues" - Journey, "Don' stop believing"

Evo kakao sam ja resio 5.zadatak. Neki delovi su mi sumnjivi, ali to je otprilike ideja.
//prvo imam metodu kojka mi racuna prosek elemenata desnog podstabla


//sada ide metoda koja prebrojava broj elemenata

_________________
"Some will win, some will lose, Some were born to sing the blues" - Journey, "Don' stop believing"

@Vlacke:
Desno podstablo za neki cvor podrazumeva svu decu desnog sina. U tvojoj metodi double Prosek(cvorStabla t) obuhvaceni su samo desni sinovi desnog cvora, a nisi racunao, na primer levog sina desnog sina, odnosno tvoj kod ce obuhvatiti samo desne sinove desnog sina, a ne i leve sinove desnog sina. Iterativno ce kood uvek ici do desnog sina, a zanemarivace leve sinove desnog sina cvora za kog treba da izracunamo prosek.

Takodje, u metodi double Count (cvorStabla t) metoda Prosek mora da primi neki argument, tacnije argumet tipa cvorStabla.
I da bi uopste mogao da pozoves metodu na ovaj nacin, ona mora da bude static. Ne static metode se pozivaju nad objektom neke klase(klase u kojoj je definisana), dok za static metode nije neophodno da se kreira objekat te klase.

Ja bih zadatak uradio malo drugacije.

Prvo bih napisao metodu koja broji cvorove u nekom stablu:

Zatim bih definisao metodu koja racuna zbir u nekom stablu:

Metoda koja racuna prosek elemenata desnog podstabla nekog cvora:

Finally bih napisao metodu koja prebrojava cvorove ciji je prosek veci od njegove vrednosti:


Hmmm, moracu da snizim nivo apstrakcije.

_________________
"The bird fights its way out of the egg. The egg is the world. Whoever wants to be born must destroy a world. The bird flies to God. That God's name is Abraxas" H.H.

drzi li neko casove ovog predmeta?!?!
neka se javi hitno je!

Vlacke, u pravu si sto se mog koda tice. Tvoj je u redu.
Nemo, hvala za resenje zadatka.
:>

@nemo
Da, hvala za zadatak. Nisam stavaljao static, jer to mislim da nismo tako radili na vezbama, pa nisam ni razmisljao o tome, ali ok.

_________________
"Some will win, some will lose, Some were born to sing the blues" - Journey, "Don' stop believing"

Moze li neko da objasni onaj tip zadataka sa kloniranjem steka ili sa redom? Razbih glavu i opet ne razumem. Ako moze neko da napise ful kod za kloniranje steka, i za obrnuti red, bio bih mu beskrajno zahvalan. Znam da sam vec pitao ovo, ali mi opet nije jasno.

@dying bride - mislim da tvoje resenje za obrnut red nije dobar jer sama metoda mora da ima dva argumenta (red 1, red 2), a tvoj ima samo jedan.

_________________
"Some will win, some will lose, Some were born to sing the blues" - Journey, "Don' stop believing"

Vlacke,
Koliko sam ja razumela zadatak, r2 treba tek da bude napravljen i da bude izlaz. Bilo mi je nelogicno da to isto bude i ulaz.

Hm, pa ja imama bas papir sa ispita i pise da treba da se napravi metoda Inv(Red r1, Red r2), odnosno metoda ima dva argumenta, ali mozda moze i tako. Kod kloniranja stekova takodje metoda ima dva argumenta, odnosno prosledjujemo dva steka kao parametre.

_________________
"Some will win, some will lose, Some were born to sing the blues" - Journey, "Don' stop believing"

To sa kloniranjem sam ja radio u junu - mozhe da se uradi sa rekurzijom, ali ja ne volim rekurziju pa sam radio malo komplikovanije.

Prvo prebacim sve chlanove u drugi red i usput izbrojim koliko ih ima, neka to bude N; onda ih vratim u prvi red. Onda vrtim prvi red sam sa sobom (r1.push(r1.pop)) N-1 puta, tako da ce prvi na redu biti poslednji chlan. Zaboravio sam tachno koje funkcije postoje u zadatku, ali onda taj poslednji chlan iskopiram u drugi red i opet ga vratim u prvi, tako da ce prvi biti u prvobitnom stanju, dok ce u drugom biti samo poslednji chlan. Onda opet izvrtim prvi red, sada N-2 puta, tako da ce pretposlednji chlan biti prvi, njega iskopiram u drugi red, i izvrtim prvi da se vrati na pochetno stanje. I tako dok ne prebacim sve chlanove. Nadam se da sam dobro objasnio, ako nisam, napishite pa cu da probam malo slikovitije

P.S. U junu nisam upisao ocenu, jel treba da idem 13.09. da to zavrshim (to je zakazano kao usmeni za "Strukture podataka")? Ili ce se mozhda znati tek posle ispita? Hvala unapred!

Poz i srecno svima!

@Vlacke-Ja sam te zadatke uradila ovako...Nadam se da su kodovi jasni posto me malo mrzi da ih objasnjavam, ali ako nekome bas treba potrudicu se.

Kloniranje Stack-a

void Kloniranje(Stack S1, Stack S2) {
if ( !S1.Prazan()){

int a = S1.Izbaci();
Kloniranje(S1,S2);
S2.Ubaci (a);
S1.Ubaci (a);
}
}

Kloniranje reda (ovo mi je bilo malo teze ako neko jos ima neku ideju neka napise)

void Kloniranje (Red R1, Red R2) {
if ( !R1.Prazan ()) {

int a = R1.Izbaci ();
R2.Ubaci (a);
Kloniranje (R1, R2);

int b = R2.Izbaci ();
R1.Ubaci (b);
R2.Ubaci (b);
}
}

Moze li neko ko je bio II grupa u junu da okaci zadatke, a posebno me zanima algoritam sortiranja koji je ta grupa imala.

Koja je razlika izmedju AVL i B stabla?
Kako se ubacuju elementi u B stablo?

@Gauco

Ima dosta razlika, počev od broja ključeva- kod binarnih, tj.AVL je samo jedan, dok B stabla mogu imati više ključeva...AVL stabla mogu imati najviše dvoje djece, dok kod B stabala broj djece stabla reda n+1 mora biti najmanje n/2...
Sve ovo, kao i postupak ubacivanja elementa imaš u skripti.

_________________
Nomi Malone: Life sucks, you know.
James Smith: "Life sucks," "Shit happens." Where do you get this stuff, off of T-shirts?

neko je vec okacio, imas na prethodnoj strani.

_________________
"Some will win, some will lose, Some were born to sing the blues" - Journey, "Don' stop believing"

3. Dat je red celih brojeva r1. Napisati f-ju Inv(Red r1, Red r2) koja ce napraviti novi red r2 koj je inverzan datom redu.Po zavrsetku algoritma pocetni red treba da ostane nepromenjen. Nije dozvoljeno koriscenje nikakvih pomocnih struktura!Moguce je koriscenje samo sledecih operacija nad redom : Ubaci(int), Izbaci() i boolean Prazan().
(15 poena)

evo kako sam ja to resio.. nov sam u svemu ovom, pa je moguce da sam nesto propustio...
recimo, ne znam sta vam znaci ovo Kloniraj (Izvor, Klon) u sred koda...
koliko sam shvatio, potrebno je resiti zadatak bez koriscenja ikakvih pomocnih struktura (znaci - nema nizova...)
koristio sam enqueue()-ubaci(), dequeue()-izbaci(), IsEmpty()-Prazan(), i par int promenljivih.





gore nije moglo da stane, al evo ovde napomena

[1] radi samo ako prvi red nije prazan
[2] promenljiva 'b' nam nosi vrednost prvog dequeue()-ovanog elementa
[3] puni Red2 inverzno u odnosu na prvi
[4] 'c' preuzima vrednost prethodno enqueue()-ovanog
[5] 'd' preuzima vrednost sveze dequeue()-ovanog
[6] ceo ovaj 'if' je "ako je d = a, u R2 ubaci prethodno dequeue()-ovani clan
[7] promenljiva 'e' ce nam u drugoj 'while' petlji govoriti koji dequeue()-ovani clan je indikator da treba da prekinemo sa sredjivanjem (to je isti clan koji se prvi ubacuje u R2, i ovaj 'if' nam sluzi iskljucivo za to)
[10] odavde 'a' pocinje da ukazuje na sledeci potreban element
[11] b = f (uslov 'while' petlje) nam govori da smo u R2 ubacili i poslednji potreban clan
[12] sredjuje Red1 u prvobitno stanje tako sto se prekida kada je poslednji enqueue()-ovani element jednak prvom enqueue()-ovanom u R2

^uh, ja ovaj tvoj kod apsolutno ne mogu da razumem. Previse si ga komplikovano napisao, super ako ga ti razumes. Kloniraj (izvor, klon) je pozivanje rekurzije. Meni je kloniranje jasno, malo kasnije cu raditi i red. Generalno kada razumes rekurziju (hvala Nemu na ovome), zadatak stavrno nije tezak.

_________________
"Some will win, some will lose, Some were born to sing the blues" - Journey, "Don' stop believing"

Da, ali to je samo I grupa.

da probam da prepricam ideju koda... priznajem da je malo komplikovano, ali je jako logicno... ako se potrudis sigurno ces shvatiti...


pokazivacu 'a' u pocetku damo vrednost prvog izbacenog clana R1 (na skici je to 4)...

=> 1 2 3 4 => 4 1 2 3 => .... 2 3 4 1 => 1 2 3 4 => kada naidjemo na 4 (kada obrnemo pun krug), znamo da je prethodni izbaceni onaj koji nama treba za R2, (i samo pomerimo pokazivac sa 4 na sledeci (1))


princip je da je 4ci koju prvobitno izbacujemo, prethodi 1, i, kada vidimo 4, znacemo da prethodno izbaceni clan (1) ide u R2. i onda, kada ubacimo 1, samo pomerimo pokazivac na sledeci clan (na 1 umesto na 4), kako bi ovaj do njega isao u R2 (tj. kako bi 2 koja je do 1 sledeca isla u R2).... pokazivac je u nasem slucaju promenljiva 'a'
uprvoj while-if petlji obrcemo R1 samog u sebe dok ponovo ne naidjemo na 4 sto nam govori da je clan izbacen neposredno pre 4 onaj koji sledeci ide u R2 (posle u okviru 'if' pomerimo pokazivac sa 4 na 1, pa sa 1 na 2, sa 2 na 3, i kada pomerimo sa 3 na 4 (tj obrnemo pun krug u punjenju R2) zadovoljicemo uslov za izlazak iz prve while petlje)

mislim da postoji fazon sa kartama koji koristi isti princip...



evo sta to znaci u samom kodu,

1 izbacujemo prvi clan R1, i vracamo ga na kraj tog istog reda, i dodeljujemo trima promenljivama vrednost tog clana (ovo ce nam trebati kasnije).

2 takodje, iniciramo tri promenljive i dodeljujemo im pocetnu vrednost null (cisto da bi mogli da vrsimo poredjenje u while pitalici).

3 u okviru prve while petlje redom izbacujemo vrednosti sa kraja R1, vracamo ih na pocetak R1, i idemo u 'if'. ('c' ce uvek biti jednaka pretposlednjem izbacenom, a 'd' poslednjem izbacenom.)

3 u if petlju upadamo kada je poslednji izbaceni iz R1 jednak 'a' ('a' je na samom pocetku prvi izbaceni iz R1. znaci, on nam govori da smo obrnuli pun krug, sto znaci da pretposlednji izbaceni ('c') upada u R2. i, pred kraj 'if' petlje, 'a' dodeljujemo vrednost 'c' kako bi mogli da ponovimo ciklus za sledeci clan.
(na kraju 'f' dodeljujemo vrednost 'c' zbog 4te tacke...).

(3.1 jako bitna stvar za kasije sredjivanje R1 je ugnjezdena 'if' petlja. ona ce funkcionisati samo da dodeli promenljivoj 'e' vrednost prvog clana ubacenog u R2! videces zasto ovo kasnije treba..)

4 prva while petlja sljaka dok god je vrednost b razlicita od f.
'b' ce nam kroz ceo kod biti prva ikada izbacena vrednost iz R1
'f' cemo uvek izjednaciti sa poslednjim clanom ubacenim u drugi red, i kada 'f' bude bio jednak prvom ikada izbacenom iz R1 ('b'), nas R2 je sredjen! dakle, kada poslednji clan prvobitnog r1 bude bio jednak prvom r2. tada izlazimo iz prve while petlje.

5 posto R1 verovatno (sigurno) nece biti u pocetnom stanju nakon izlaska iz prve petlje i sredjivanja R2, u drugoj while petlji cemo srediti R1...
tako sto ga obrcemo u samog sebe dok ne naidjemo da je clan koji smo vratili u R1 jednak 'e', (a to je, ako se secas, prvi clan koji smo stavili u R2) i tada se program zavrsava...



reci ako imas konkretnijih nejasnoca..
ispravio sam malo kod
izbacio 3 reda da bi bilo sazetije...
sada, kad ponovo pogledam, kod je bas jednostavan..

Ne, nije. Uzas je ostavio obe grupe. Imas link, mislim da je rar fajl. Ako ne mozes da nadjes, a vidim da te zanima sortiranje, jednoj grupi je bio selection sort, a drugoj insertion sort.

@grk - pazi, nisam ja rekao da ti kod nije tacan. Ja sam to samo skapirao na neki drugi nacin i ne mogu sada da taj tvoj studiram (nemam vremena)i i da se dodatno bunim pred ispit. Veceras cu raditi taj zadataka, pa ako uspem da resim, okacic moj nacin.

_________________
"Some will win, some will lose, Some were born to sing the blues" - Journey, "Don' stop believing"

Hvala puno, Vlacke.

niko nije pominjao netacnost - naravno da je tacan!
samo je dobro sto se nisam bez veze cimao da sto jasnije napisem citav esej o kodu...

uzgred, mislim da BittyX-jev princip isto drzi vodu, pa probajte i tako da radite...

Problem je što ti ideš samo u skroz desnu granu - a valjda se pod desnim podstablom podrazumeva sve sa desne strane, a ne samo skroz desno . . . ti ideš samo B.desno, B.desno.desno, B.desno.desno.desno itd . . . a trebalo bi B.desno, B.desno.levo, B.desno.desno itd . . .

ne shvatam kako se prolazi kroz celo to podstablo, a da se pritom zadrže vrednosti npr. brojača . .sličan zadatak je pogrešno rešen u Userovoj skripti:
Dat je pokazivač na koren binarnog stabla čiji čvorovi sadrže cele brojeve. Napišite funkciju koja će vratiti broj čvorova koji su po sadržaju veći od svih svojih potomaka.

ja sam nešto brljo ali neke stvari ne mogu da mi se slože . . .



ideja je da metoda poredi izbroji u koliko je slučaja vrednost veća od vrednosti potomaka . . . ako je taj broj jednak sa dubinom, onda se taj slučaj broji . . .

problem je što u metodi ''poredi'' neće ostati vrednost tog korena koji hoću, nego će se mesnjati kako se poziva rekurzija . . ne znam kako da zadržim onu prvu vrednost -> onu koja treba da je veća od svih ostalih . ..

6 ujutru je .. verovatno postoji još grešaka, ali ne mogu više . . .

BTW - Hvala Vlacke na ovoj fori za brojanje sa if bla return 1+rekurzija else return samo rekurzija!

_________________
Don't act your age - act your shoe size!