Forum Informatyka UJ forum Strona Główna Informatyka UJ forum
Rocznik 2005 - czyli najlepsze forum w sieci
 
 FAQFAQ   SzukajSzukaj   UżytkownicyUżytkownicy   GrupyGrupy   GalerieGalerie   RejestracjaRejestracja 
 ProfilProfil   Zaloguj się, by sprawdzić wiadomościZaloguj się, by sprawdzić wiadomości   ZalogujZaloguj 

Zadanie K - Adelson-Velsky & Landis
Idź do strony 1, 2, 3, 4  Następny
 
Napisz nowy temat   Odpowiedz do tematu    Forum Informatyka UJ forum Strona Główna -> Archiwum / 1 rok / 2 i 3 semestr - Algorytmy i Struktury Danych
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Pandunia
Gość






PostWysłany: Pon 21:35, 03 Kwi 2006    Temat postu: Zadanie K - Adelson-Velsky & Landis

[deleted]

Ostatnio zmieniony przez Pandunia dnia Pią 5:40, 10 Lis 2006, w całości zmieniany 2 razy
Powrót do góry
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Skrobocik
[SKROBORANGA]



Dołączył: 29 Lis 2005
Posty: 2958
Przeczytał: 0 tematów

Skąd: Skarżysko , Kraków

PostWysłany: Pon 22:24, 03 Kwi 2006    Temat postu: Re: Zadanie K - Adelson-Velsky & Landis

Pandunia napisał:
korzystajac z okazji ze moge cos napisac przy okazji pojawienia sie nowego zadania prosze wszystkich o przeczytanie mojego postu w dziale Analiza Matematyczna

A mówiąc dokładniej chodzi o dział Algebra Liniowa :P
Szymek gapcia :wink:
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
smas
Okrutny Admin



Dołączył: 20 Paź 2005
Posty: 1634
Przeczytał: 0 tematów


PostWysłany: Wto 18:34, 04 Kwi 2006    Temat postu:

To może się przydać. [link widoczny dla zalogowanych] [trochę się wiesza]
[link widoczny dla zalogowanych] [a ten jest sprawny;)]
Symulacja, jak działają drzewa AVL.
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Skrobocik
[SKROBORANGA]



Dołączył: 29 Lis 2005
Posty: 2958
Przeczytał: 0 tematów

Skąd: Skarżysko , Kraków

PostWysłany: Śro 15:11, 05 Kwi 2006    Temat postu:

Ostatnio Lembasik zapodał nam na ćwiczeniach swój program właśnie z afałelami. Fajnie to wygląda
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
hansu
Nieomylny Admin



Dołączył: 17 Lis 2005
Posty: 1990
Przeczytał: 0 tematów

Skąd: przychodzimy? Czym jestesmy? Dokad zmierzamy?

PostWysłany: Śro 18:40, 05 Kwi 2006    Temat postu:

Hehe, taki w delphi? Pokazywal go na ostatnim wykladzie z WDP... Wie ktos moze skad go wziac?
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
jagm
zielony żul



Dołączył: 01 Lut 2006
Posty: 1421
Przeczytał: 0 tematów


PostWysłany: Śro 18:48, 05 Kwi 2006    Temat postu:

Proponuję przeszukać softlaba ;]
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Skrobocik
[SKROBORANGA]



Dołączył: 29 Lis 2005
Posty: 2958
Przeczytał: 0 tematów

Skąd: Skarżysko , Kraków

PostWysłany: Śro 19:25, 05 Kwi 2006    Temat postu:

jagm napisał:
Proponuję przeszukać softlaba ;]

A ja proponuję przeszukać Lembasa :wink:
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
mateo
pijak



Dołączył: 08 Mar 2006
Posty: 296
Przeczytał: 0 tematów

Skąd: Krk - Biały Prądnik

PostWysłany: Śro 23:25, 12 Kwi 2006    Temat postu:

Jakby ktos byl zainteresowany to dodalem wlasnie do testerki AVLe + generator testow.
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Robson
zielony żul



Dołączył: 21 Paź 2005
Posty: 1274
Przeczytał: 0 tematów

Skąd: Z Lasu :]

PostWysłany: Czw 2:54, 13 Kwi 2006    Temat postu:

No właśnie - dzięki Mateo - znalazłem multum małych głupich bledów, typu nie zainicjowanie zmiennej czy nie dopiecie wskaxnika, czy chocby pisanie TAK zamiast YES ( :P ) dzieki tym testom... ale delete i tak nie chce działać :(
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Robson
zielony żul



Dołączył: 21 Paź 2005
Posty: 1274
Przeczytał: 0 tematów

Skąd: Z Lasu :]

PostWysłany: Czw 12:55, 13 Kwi 2006    Temat postu:

Przyrzekam że już nigdy ale to nigdy przenigdy NIE będe KOPIOWAŁ kodu w programi, nawet gdzyby to było 1000 linijek.... ehhh... w koncu sie jednak udało :D

PS. W czasie robienia zadanka udało mi sie zapełnić 5 kartek różnistymi rysunkami z tych drzew. Mam narysowane wszstkie mozliwości i wszystkie przypadki symetryczne. Jesli ktoś by chciał to moge udostepnić, a jak odzew bedzie duzy to moge to na czysto przerysować.
Ale dostepny bede dopiero chyba w poniedizałek...

PS2. Warto sobie zrobic procedurke która rekurencyjnie liczy wysokości drzew i balase, i jak cos sie w drzewku nie zgadza to krzyczy. Mi pomogła bardzo...
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
ostoj
Przewijak Tasmy



Dołączył: 08 Lis 2005
Posty: 883
Przeczytał: 0 tematów

Skąd: Tychy

PostWysłany: Czw 13:10, 13 Kwi 2006    Temat postu:

Robson napisał:
PS. W czasie robienia zadanka udało mi sie zapełnić 5 kartek różnistymi rysunkami z tych drzew. Mam narysowane wszstkie mozliwości i wszystkie przypadki symetryczne. Jesli ktoś by chciał to moge udostepnić, a jak odzew bedzie duzy to moge to na czysto przerysować.

taaaaaak, prosiiiiimy :) chociazby tylko o wypisanie wszystkich przypadkow :)
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Robson
zielony żul



Dołączył: 21 Paź 2005
Posty: 1274
Przeczytał: 0 tematów

Skąd: Z Lasu :]

PostWysłany: Czw 13:30, 13 Kwi 2006    Temat postu:

No to chyba jednak w wolnej chwili przerysuje to na czysto i bedzie spokój. Mi sie to pewnei tez keidys przyda. Umieszcze to jak bede w domu i bede miał dostep do skanera/aparatu cyfrowego - tak kolo niedzieli moze sie uda :)
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
ostoj
Przewijak Tasmy



Dołączył: 08 Lis 2005
Posty: 883
Przeczytał: 0 tematów

Skąd: Tychy

PostWysłany: Czw 13:48, 13 Kwi 2006    Temat postu:

dzie-ku-je-my :)
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Robson
zielony żul



Dołączył: 21 Paź 2005
Posty: 1274
Przeczytał: 0 tematów

Skąd: Z Lasu :]

PostWysłany: Pią 21:35, 14 Kwi 2006    Temat postu:

Mam nadzieje ze pomoze:
[link widoczny dla zalogowanych]
Na razie tylko usuwanie ogólne, ale moze za niedługo dam wszystkie mozliwości usuwania dla liści i inserta (insert jest dobrze omowiony na wykladzie, wiec kazdy sobie powinien dać rade na razie).
PS. Proponuje żeby każdy sam sobie rozrysował jak to dziala - tylko tak mozna to zrozumieć całkowicie.
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
trywialna
pijak



Dołączył: 12 Mar 2006
Posty: 257
Przeczytał: 0 tematów

Skąd: z kontowni:)

PostWysłany: Pią 21:54, 14 Kwi 2006    Temat postu:

Dzieki Robson za te instrukcje:)

Mam jeszcze pytanie, czy to zadanie jest bardzo trudne i czasochłonne? Bo zaczynam je pisać i troche sie go boje=)
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Makros
pijak



Dołączył: 01 Gru 2005
Posty: 420
Przeczytał: 0 tematów

Skąd: Kraków

PostWysłany: Pią 22:43, 14 Kwi 2006    Temat postu:

@Robson:

BIG THX !!!
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Robson
zielony żul



Dołączył: 21 Paź 2005
Posty: 1274
Przeczytał: 0 tematów

Skąd: Z Lasu :]

PostWysłany: Sob 14:05, 15 Kwi 2006    Temat postu:

Trudne nie jest - jest za to bardzo czasochłonne i wymaga wiele ostrożności - każdy mały błędzik czy nie uwzglednienie jednego przypadku sprawia ze wszystko moaze sie wywalić w najbardziej niespodziewanym momęcie. Dlatego tak ważne jest narysowanie sobiw wszystkich mozliwości.

PS. Musze powiedziec ze w czasie robienia tego zadania z każdym krokiem te drzewka coraz bardziej mi sie podobały :)
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
kap00ch
Mistrz grilla



Dołączył: 09 Mar 2006
Posty: 1840
Przeczytał: 0 tematów

Skąd: ja sie tu wzialem?

PostWysłany: Sob 14:09, 15 Kwi 2006    Temat postu:

a mi w cale nie w o juz drugi dzien z rzedu mam inna liczbe rotacji na delete niz trzeba...w dziala dobrze:P

ps. OMG ide sie powiesci! w jednym mijescu mialem 1 zamiast 0 i wszystko poszlo :PPPPP

ps2. uffff....oficjalnie przepchnalem:> coz moge poradzic...po pierwsze wszystkoladnie rozrysowac...nawet jesli robson dal swoje rysunki ktoresa bdb to i tak polecam rozrysowanie chociby zeby lepiej zrozumiec. Po drugie NIE KOPIUJCIE KODU :P zgubilo to jak wiadomo i robsona i rowniez mnie:P.
Po trzecie pamietac o dispose przy delete. Po czwarte nie probowac robic tego ze stosem :P w kazdym razieja robilemi sie zamotalem...latwiej, szybciej i ladniej jest rekurencja. Chyba tyle z ogolnikow...zycze powodzenia;]
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
trywialna
pijak



Dołączył: 12 Mar 2006
Posty: 257
Przeczytał: 0 tematów

Skąd: z kontowni:)

PostWysłany: Sob 22:12, 15 Kwi 2006    Temat postu:

Hmm czy my mamy napisac procedure rotacji podwojnej, tylko liczyc ilosc rotacji jako 2 pojedyncze? czy 2x uzywac rotacji pojedynczej? bo mi sie wydawalo ze to piersze ale jak teraz patrze na te notatki Robsona to juz\sama niewiem:/
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
kap00ch
Mistrz grilla



Dołączył: 09 Mar 2006
Posty: 1840
Przeczytał: 0 tematów

Skąd: ja sie tu wzialem?

PostWysłany: Sob 22:15, 15 Kwi 2006    Temat postu:

praktycznie jest to bez znaczenia...zamiast podwojnej mozna wykonacdwie pojedyncze..jedyne co sie liczy to zliczanie ilosci rotacji...tak czy siak przy podwojnej liczymy +1lewo +1prawo wiec wychodzi na to samo jakby je miec osobno;]
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
ostoj
Przewijak Tasmy



Dołączył: 08 Lis 2005
Posty: 883
Przeczytał: 0 tematów

Skąd: Tychy

PostWysłany: Nie 1:50, 16 Kwi 2006    Temat postu:

1 - Robson, te przypadki usuwania obejmuja wszystkie mozliwe? (poza liscmi)
2 - jak aktualizujecie balance po rotacjach? jest na to jakis wzorek czy trzeba recznie zawsze ustawiac wszelkie balansy w tych 2-3 wezlach w zaleznosci od tego jakie one maja balanse i rozpatrywac w kazdej rotacji kilka przypadkow? bo zrobilem sobie wstawianie z perfidnym recznym ustalaniem balansow w procedurkach rotacyjnych ale widze ze albo mam za malo przypadkow albo jest jakis wzorek, ktorego juz nie widze...
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
kg86
zielony żul



Dołączył: 22 Gru 2005
Posty: 1194
Przeczytał: 0 tematów

Skąd: pochodze?

PostWysłany: Nie 2:47, 16 Kwi 2006    Temat postu:

wlasnie przepchnalem K :) poszlo zdecydowanie szybciej niz A ;P
tak sobie poradzilem z usuwaniem:
ogolnie:
zmieniamy balans rodzica wtedy, gdy w wyniku usuniecia, oraz rotacji zmniejszyla sie wysokosc poddrzewa... jesli to bylo prawe poddrzewo, to balans rodzica zmniejszamy o 1... jesli lewe poddrzewo, to zwiekszamy o 1 :)
szczegolowo:
chyba najwygodniej stworzyc sobie procedurke, np: zbalansuj(p:wierzcholek) ktora zbada balans rodzica, po tym, jak juz mu ustawimy nowy balans:
1) bal(p)=0 // oznacza to, ze zmienilismy balans z 1-->0 lub z -1-->0 wiec wysokosc drzewa sie zmniejszyla, wiec:
a) jesli p jest prawym synem, to balans(p^.parent) zmniejszamy o jeden i wywolujemy zbalansuj(p^.parent);
b) jesli p jest lewym synem, to balans(p^.parent) zwiekszamy o jeden i wywolujemy zbalansuj(p^.parent);
2) bal(p)=2 // oznacza to, ze zmniejszylismy lewe poddrzewo, a balans zmienilismy z 1-->2, wiec:
a) jesli balans(p^.right)=1 to wykonujemy rotacje pojedyncza w lewo, wysokosc drzewa sie zmniejsza, wiec z rodzicem postepujemy analogicznie jak w 1a lub 1b
b) jesli balans(p^.right)=-1 to wykonujemy rotacje podwojna w lewo, wysokosc drzewa sie zmniejsza, wiec z rodzicem postepujemy analogicznie jak w 1a lub 1b
c) jesli balans(p^.right)=0 to wykonujemy rotacje pojedyncza w lewo, ale z ta roznica, ze po tej rotacji balans(p)=-1, a balans(p^.left)=1 ['normalna' rotacja ustawilaby te balanse na 0], a wysokosc drzewa sie nie zmieni, wiec w tym miejscu przerywamy dzialanie procedury, balans rodzica pozostawiamy bez zmian
3) bal(p)=-2 //oznacza to, ze zmniejszylismy prawe poddrzewo, a balans zmienilismy z -1-->-2, wiec:
a) symetrycznie: balans(p^.right)=1 --> balans(p^.left)=-1; rotacja poj. w lewo --> rotacja poj. w prawo
b) symetrycznie: balans(p^.right)=-1 --> balans(p^.left)=1; rotacja podw. w lewo --> rotacja podw. w prawo
c) symetrycznie: balans(p^right)=0 --> balans(p^.left)=0; rotacja poj. w lewo --> rot poj. w prawo; balans(p)=-1 --> balans(p)=1; balans(p^.left)=1 --> balans(p^.right)=-1
4) bal(p)=+-1 // nic nie robimy, wysokosc drzewa nie ulegla zmianie

x --> y oznacza: tak samo, z tym ze, zamiast x powinno byc y :)

nalezy pamietac, ze jesli p='korzen glowny', to parametrem w rotacji bedzie ten korzen, a nie wskaznik z rodzica na ten element, oraz oczywiscie nie trzeba rozpatrywac warunku, czy p jest lewym, czy prawym synem... bo nie ma ojca ;)

zycze wszystkim powodzenia :)
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
krzycho
pijak



Dołączył: 09 Lis 2005
Posty: 151
Przeczytał: 0 tematów

Skąd: Radom

PostWysłany: Nie 14:56, 16 Kwi 2006    Temat postu:

Cytat:
Po czwarte nie probowac robic tego ze stosem Razz w kazdym razieja robilemi sie zamotalem...


wlasnie .. ktora wersje wybrac ze stosem czy rekurencyjna ??
Dlaczego akurat wersja ze stosem jest taka trudna ?
Moze jakies plusy i minusy ktos by przestawil .. wolalbym uniknac podwojnego algorytmu.

[Edit] chyba jednak zostane przy wersji z parent'em w wezle. Bardzo zgrabne rozwiazanie.
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
trywialna
pijak



Dołączył: 12 Mar 2006
Posty: 257
Przeczytał: 0 tematów

Skąd: z kontowni:)

PostWysłany: Nie 23:02, 16 Kwi 2006    Temat postu:

:( Właśnie napisałam program, wysłalam i... mam blad RD8:/

Chcialam testowac na virgo i... napisalo mi ze mam za duzy kod zrodlowy.

Okazalo sie ze przez robienie wciec te spacje tak mi zabraly pamiec ze moj program ma 115kb:/

wie ktos moze jak mozna szybko usunac te wciecia bo jakos recznie z 500linijek kodu mi sie nie chce zmieniac, zreszta pewnie by mi sie pomylilo w trakcie:/ help :cry:
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Ethlinn
Szatanica



Dołączył: 13 Lis 2005
Posty: 424
Przeczytał: 0 tematów

Skąd: Katowice

PostWysłany: Nie 23:20, 16 Kwi 2006    Temat postu:

Otwórz plik w edytorze tekstu (Edycja-> Zamień) i podmień dużą ilość spacji na jedną, dwie... czy coś koło tego.
Powrót do góry
Zobacz profil autora
Wyświetl posty z ostatnich:   
Napisz nowy temat   Odpowiedz do tematu    Forum Informatyka UJ forum Strona Główna -> Archiwum / 1 rok / 2 i 3 semestr - Algorytmy i Struktury Danych Wszystkie czasy w strefie EET (Europa)
Idź do strony 1, 2, 3, 4  Następny
Strona 1 z 4

 
Skocz do:  
Nie możesz pisać nowych tematów
Nie możesz odpowiadać w tematach
Nie możesz zmieniać swoich postów
Nie możesz usuwać swoich postów
Nie możesz głosować w ankietach

fora.pl - załóż własne forum dyskusyjne za darmo
Powered by phpBB © 2001, 2005 phpBB Group
Regulamin