Temat: Zadanie K - Adelson-Velsky & Landis
To może się przydać. http://www.cs.jhu.edu/~goodrich/dsa/trees/avltree.html [trochę się wiesza]
http://webpages.ull.es/users/jriera/Docencia/AVL/AVL%20tree%20applet.htm [a ten jest sprawny;)]
Symulacja, jak działają drzewa AVL.
Źródło: matinfuj.fora.pl/a/a,369.html
Temat: J* - Punkty
Cormen s. 1013 i po zadaniu Albo Diks s. 272 (dla tych ktorzy preferuja drzewa AVL :P) ja tam jednak wole metode dziel i zwyciezaj bo jest prosta w implementacji i jak widac mozna bez problemu bez gwiazdki przepchnac. PS. w testerce na virgo zrobilem podobnie jak przy zadaniu F ze jest udostepniony generator losowych testow oraz kwadratowa wzorcowka (zeby byla pewnosc ze wyniki beda poprawne), wiec jak cos to mozna sobie generowac testy z n <= 10000
Źródło: matinfuj.fora.pl/a/a,308.html
Temat: Force Script Language
Wow, nie wiedziałem, że uda mi się zainspirować do takiego off topica. Cubimeister: ja piszę po to aby go używać w projektach, takie mam założenia, poza tym dziś już oddałem jako projekt na kompilatory. No ale nie o tym tu chciałem.. Wyszła nowa wersja, ma case-a, pliki pośrednie, definiowanie wartości stałych i zmiennych wyrażaniami matematycznymi i różne poprawki. Case używa drzewa AVL, na FP nie pójdzie pewnie no ale trzeba mieć case-a szybszego niż if-y. Wszystko w linku ze stopki wraz ze złotą radą na ten wiek
Źródło: forum.unit1.pl/index.php?showtopic=2470
Temat: zadanie 5 z poprawki
Mysle ze pouczajace bedzie gdy umieszcze tu informacje o wynikach zadania 5, Jacek Lembas Ocena zadania 5 kolokwium poprawkowego z ASD1 0-11.09.06 Rozwiazanie wzorcowe. Dane: n,a[1],...,a[n] (ciag calkowitych co najwyzej log n roznych liczb) Wynik: ciag posortowany. Pole info drzewa AVL zawiera wartosc i liczbe wystapien elementu, stad liczba wezlow
Źródło: forum.tcs.uj.edu.pl/viewtopic.php?t=305
Temat: Pomoc dla naszych !
Pomoc dla naszych to zestaw pytan jakie byly na egzaminie, wspolnymi silami odtworzymy caly egzamin: ( pomijamy pytania, ktore udostepnil dr Slusarek ) 1. Zlozonosc Dijkstry 2. W 200-elementowym kopcu wykonujemy operację insert .Pesymistyczna liczba porównań kluczy wynosi: 3. Jezeli wstawimy do drzewa AVL elementy: 1,2,3,4,5,67, to ile razy wykonaja sie rotacje( podwoja liczmy jako raz ) 4. Majac dane 4 elementy, chcemy je posortowac najszybszym algorytmem, ile wykona sie porownan 5. Dany jest kopiec, aby odczytac elementy rosnaco nalezy: (odczytac inorder lub preorder ... itp, jest tez zadne z pozostalych :) ) 6. Mam dany pewne liczby np ( 535, 245,421, 611 ) sortujemy je radix sortem wedlug bitu najmniej znaczacego, liczb 421...
Źródło: matinfuj.fora.pl/a/a,719.html
Temat: struktury danych
Witam, Poznalem zasade dzialanie drzewa AVL i wszyztko jest jasne ale mam problem nie znam zbyt dobrze php i nie zabardzo weim jak zabrac sie do zrobienia bazy z taka struktura Prosze was o pomoc o linki, obojetnie co zwiazanego z php i drzewkiem AVL bardzo bym chcial zobaczyc jak takie cos wyglada na jakims przykladzie konkretnym bo wtedy najlepiej sie ucze. Pozdrawiam, Rafal Kucharzak ---------------------- Glownie chodzi o to ze ma na informatyce omowic takie cos P O M O C Y
Źródło: forum.php.pl/index.php?showtopic=28674
Temat: [OpenGL] Jak rysować oteksturowane rzeczy
...co pisze grę w tym silniku czy silnik powinien? Pytanie numer 2: Jeśli silnik to jak to powinien zrobić. Czy może gdy wywołujemy metodę render na obiekcie to wrzuca obiekt do listy, która jest zawsze posortowana i gdy wywołujemy metodę w silniku np. EndRender to rysowane jest wszystko z tej listy i lista jest czyszczona i co klatkę zapełniana od nowa. Tu wg mnie czasochłonne byłoby wrzucanie w odpowiednie miejsce na liście obiektu, chyba, że się użyje drzewa AVL no i czy takie czyszczenie co klatką też jest dobre. Może już w tym miejscu gdzie jest EndRender dopiero się sortuje raz całą listę, wyświetla i kasuje. Może każdy rodzaj tekstury ma własną listę obiektów, więc nie ma sortowania? Może też macie jakieś inne rozwiązania lub czytaliście o takowych?
Źródło: forum.unit1.pl/index.php?showtopic=2505
Temat: Pomoc dla naszych !
...sortowania przez zliczanie: (Wypisane jakieś własności typu "nie zależy od danych wejściowych", "jest kwadratowa", "nie zależy od zakresu kluczy", wskaż poprawną) 10. Dana jest funkcja: f(0)=0; f(2x)=2*f(x) + x + 1 Która z własności nie zachodzi: (Do wyboru 5 przynależności typu f należy do O(n), f należy do O(n^2), f należy do theta(n log n)) 11. Realizujemy kolejkę priorytetową za pomocą drzewa AVL. Jakie są minimalne złożoności operacji: Insert, FindMin, RemoveMin 12. Losowy wybór elementu dzielącego w QuickSorcie: (Wypisane jakieś opcje typu "uniezależnia działanie algorytmu od danych wejściowych", "zmienia złożoność pesymistyczną", wskaż poprawną)
Źródło: matinfuj.fora.pl/a/a,719.html
Temat: Zadania L i M.
...nie widziałem i za chiny bym nie zgadł ze służy do znajdowania cykli eulera gdzyby nie nazwa(w Banachowskim-Diksie było chyba dużo bardzeij zamotane) :) czyli dobrze myslałem ze ten graf bedzie taki kopnięty - znaczy sie krawedzie beda robic za wierzcholki a wierzcholki za krawedzie ;) także chciałem podziekowac za przesunięcie terminów. Bardzo to pomoze szczególnie ze ciagle wiszą nademną (i zapewne nad wieloma innymi osobami) złowieszcze drzewa AVL. Wiec Wesołych swiąt! PS. Tak sie zastanawiam co bedzie jak nie ma cykli eulera... bo zeby tak bylo to z kazdego wierzcholka musi wychodzić parzysta liczba krawedzi....
Źródło: forum.tcs.uj.edu.pl/viewtopic.php?t=102
Temat: Zadanie K - Adelson-Velsky & Landis
...tak:
if cos <> nil then cos^.jakiespole := costam;
Naprawde, trzeba bardzo uwazac na to, zwlasza przy wersji z parentami. Bo jak na przyklad w rotacji przepinamy jakies drzewo to musimy zmienic mu parenta. A to drzewo moze byc puste. Tak samo przy usuwaniu. Ogolnie wersja z parentami to duuuuzo ifow ale mam wrazenie wiekszej kontroli nad tym wszystkim niz gdybym robil ze stosem... ALe to tylko wrazenie. 3. Uwaga na roota. Drzewa AVL bylyby naprawde super struktura danych gdyby nie mialy roota. W poblizu roota czesto dzieja sie roooozne dziwne rzeczy i trzeba to wszystko oczywiscie wyifowac. Glownie chodzi mi o usuwanie. 4. Chyba najpaskudniejsza rzecza z jaka musialem sie zmierzyc jest przywracanie balansu po delecie. Ogolnie da sie to zrobic w miare elegancko (czyt <20 ifow :P) przy pomocy jednego while'a. Ale jest jeden przypadek rotacji pojedynczej (gdy rotowane...
Źródło: matinfuj.fora.pl/a/a,369.html
Temat: petycja
...Fakt faktem ze regulamin ASD jest bardzo twadry, zwalszcza z ta poprawka za nieoddane zadania, i ogolnie poprzeczka jest ustawiona bardzo wysoko, tak wysoko, ze Ci ktorzy nigdy wczesniej przed przyjsciem na te studia nie programowali praktycznie z miejsca stoja na straconej pozycji... hmmm Juz sam nie wiem co o tym myslec.... Boje sie po prostu ze moze byc jeszcze gorzej... P.S. A na koniec jeszcze jedna wesola wiadomosc - bedzie jedno zadanie ale beda nim.... drzewa AVL :/ I tu mam zarzut - idziemy z programem stanowczo za szybko...
Źródło: matinfuj.fora.pl/a/a,289.html
Temat: Zadanie K - Adelson-Velsky & Landis
O ile dobrze pamiętam, to nasz ćwiczeniowiec mówił, że sobie musiał przypomnieć przed zajęciami drzewa AVL, bo ostatni raz miał z nimi styczność na I roku :P
Źródło: matinfuj.fora.pl/a/a,369.html
Temat: Egzamin od kuchni;)
...wskaźnikowa stosu i tablicowa kolejki 3.rekurencja niejawna (podać 7-my wyraz ciągu) ZESTAW 8 1.definicja drzewa, implementacja drzewa binarnego, implementacja lewy syn, prawy brat , ograniczenie na liczbę liści 2.przepływy z dolnymi i górnymi ograniczeniami (def sieci itd) + przykład 3.znaleść liczby pierwsze z przedziału <20,200> ZESTAW 9 1.podstawowe metody projektowanie algorytmów 2.zdefiniować drzewa AVL i rotacje w tych drzewach 3.efektywna metoda wyszukiwania podanej liczby w ciągu Fibonacciego ZESTAW 10 1.NWD 2.wstaw element w liście jednokierunkowej 3.tw o przepływie w sieci z dolnym i górnym ograniczeniem ZESTAW 11 1.implementacja kursorowa tablicy i funkcja wstaw element 2.Tw Forda Fulkersona 3.problem plecakowy ciągły ZESTAW 12 1.algorytm Prima na przykładzie 2.implementacja...
Źródło: wmsgr1.fora.pl/a/a,85.html
Temat: AVL
Szczegół który wyszedł na moich ćwiczeniach - książki Knutha, Diksa i notatki z wykładu omawiają szczegółowo wstawianie do drzewa AVL i rotacje występujące przy wstawianiu, a usuwanie opisują jako analogiczne. Tymczasem przy usuwaniu pojawiają się odrobinę inne przypadki rotacji: przy wstawianiu omówione są przypadki rotacji pojedynczej ......+2............-2 ....../............./... ..+1.....C.......C....-1 ../...................../... A......B..............B.....A i podwójnej ......+2............-2...
Źródło: forum.tcs.uj.edu.pl/viewtopic.php?t=87