Informatyka UJ forum Rocznik 2005 - czyli najlepsze forum w sieci    FAQ   Szukaj   Użytkownicy   Grupy   Galerie   Rejestracja   Profil   Zaloguj się, by sprawdzić wiadomości   Zaloguj  Zadanie D - ordery Idź do strony Poprzedni  1, 2, 3, 4, 5  Następny          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ść Crow alkoholik Dołączył: 14 Mar 2006 Posty: 497 Przeczytał: 0 tematów Skąd: KRK-NH Wysłany: Pią 14:43, 24 Mar 2006    Temat postu: KURNAAA! Ma ktos jakie inne testy do tego zadania?! Bo ja juz nie widze bledow u siebie! Albo jakies sugestie nietypowych przypadkow Powrót do góry Zobacz poprzedni temat :: Zobacz następny temat   Autor Wiadomość h pijak Dołączył: 15 Lis 2005 Posty: 134 Przeczytał: 0 tematów Wysłany: Pią 15:36, 24 Mar 2006    Temat postu: ekhm, jak sprawdzacie czy drzewo jest pełne przy PRE-POST ? wystarczy że sprawdzę czy przedostatni element z POST jest taki sam jak drugi z PRE? (znaczy to wtedy, że węzeł ma tylko jedno dziecko). tak właśnie robię, ale dostaję TLE :/ można to jakoś przyspieszyć? tablice dynamicznie alokujecie? (nie wiem czy to może znacząco czas zwiększać, ale tak robię). Powrót do góry Zobacz poprzedni temat :: Zobacz następny temat   Autor Wiadomość h pijak Dołączył: 15 Lis 2005 Posty: 134 Przeczytał: 0 tematów Wysłany: Pią 15:42, 24 Mar 2006    Temat postu: [quote="Rogal"]Co do sprawdzania czy drzewo jest pełne... ja zrobiłem to tak, że przy każdym wywołaniu procedury sprawdzam czy s+2 jest naturalną potęgą 2. Mam do tego specjalną funkcję, która dopóki (s and 1=0) robi (s shr 1), czyli dopóki s jest podzielne przez 2 dzieli je przez 2 8) . I jeśli na końcu s=1 to znaczy że na początku było potęgą 2 a jeśli nie to znaczy że nie. Sprawdzanie, czy drzewo może być pełne po ilości wierzchołków powinno być między punktem 1 i 2 tego co napisałem[/quote] jak to? a dajmy na to takie drzewko: 1 / \ 2 3 / \ 4 5 s = 4, s + 2 = 6, 6 nie jest potęgą dwójki, a drzewo jest pełne? 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 Wysłany: Pią 16:14, 24 Mar 2006    Temat postu: h napisał: Rogal napisał: Co do sprawdzania czy drzewo jest pełne... ja zrobiłem to tak, że przy każdym wywołaniu procedury sprawdzam czy s+2 jest naturalną potęgą 2. Mam do tego specjalną funkcję, która dopóki (s and 1=0) robi (s shr 1), czyli dopóki s jest podzielne przez 2 dzieli je przez 2 8) . I jeśli na końcu s=1 to znaczy że na początku było potęgą 2 a jeśli nie to znaczy że nie. Sprawdzanie, czy drzewo może być pełne po ilości wierzchołków powinno być między punktem 1 i 2 tego co napisałem jak to? a dajmy na to takie drzewko: 1 / \ 2 3 / \ 4 5 s = 4, s + 2 = 6, 6 nie jest potęgą dwójki, a drzewo jest pełne? Przecież to drzewo nie jest pełne, pełne byłoby, gdyby było: Kod:      1    /   \   2     3  / \   / \ 4   5 6   7 A przynajmniej tak mi się wydaje :wink: Powrót do góry Zobacz poprzedni temat :: Zobacz następny temat   Autor Wiadomość exeman Mistrz grilla Dołączył: 03 Lut 2006 Posty: 1603 Przeczytał: 0 tematów Skąd: znienacka Wysłany: Pią 16:27, 24 Mar 2006    Temat postu: Crow: sprawdz posty, testy na gronostaju do D sa zrypane (tzn nie ma post'ow) poprawie dzisiaj wieczorem. Powrót do góry 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? Wysłany: Pią 18:55, 24 Mar 2006    Temat postu: Niewazne czy to drzewo jest pelne czy nie wazne ze da sie dla niego odtworzyc inorder majac post i preordera... Powrót do góry Zobacz poprzedni temat :: Zobacz następny temat   Autor Wiadomość smas Okrutny Admin Dołączył: 20 Paź 2005 Posty: 1634 Przeczytał: 0 tematów Wysłany: Pią 19:04, 24 Mar 2006    Temat postu: hansu: Twój generator jest zły. Chodzi o ten najgorszy przypadek (pre, post->in) w wielu testach mój program generował inne wyniki a jednak sprawdzarka zaakceptowała. Ostatnio zmieniony przez smas dnia Pią 19:12, 24 Mar 2006, w całości zmieniany 1 raz Powrót do góry Zobacz poprzedni temat :: Zobacz następny temat   Autor Wiadomość smas Okrutny Admin Dołączył: 20 Paź 2005 Posty: 1634 Przeczytał: 0 tematów Wysłany: Pią 19:11, 24 Mar 2006    Temat postu: h napisał: ekhm, jak sprawdzacie czy drzewo jest pełne przy PRE-POST ? wystarczy że sprawdzę czy przedostatni element z POST jest taki sam jak drugi z PRE? (znaczy to wtedy, że węzeł ma tylko jedno dziecko). tak właśnie robię, ale dostaję TLE :/ można to jakoś przyspieszyć? tablice dynamicznie alokujecie? (nie wiem czy to może znacząco czas zwiększać, ale tak robię). Wystarczy sprawdzić, tak jak mówisz czy tab[post_end-1]=tab[pre_start+1], jeśli tak to ERROR. TLE dostawać musisz z innego pytania. Ja zrobiłem wersje z odtwarzaniem drzew, normalna rekurencja. Powrót do góry 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? Wysłany: Pią 19:11, 24 Mar 2006    Temat postu: A z ktorej wersji genaratora korzystales?? Bo poprzednia faktycznie byla bledna... Natomiast ta zawiera moj kod wklejony wiec jesli tylko dobrze generuje in to i outy powinna dawac dobre... Powrót do góry Zobacz poprzedni temat :: Zobacz następny temat   Autor Wiadomość smas Okrutny Admin Dołączył: 20 Paź 2005 Posty: 1634 Przeczytał: 0 tematów Wysłany: Pią 19:16, 24 Mar 2006    Temat postu: hansu napisał: A z ktorej wersji genaratora korzystales?? Bo poprzednia faktycznie byla bledna... Natomiast ta zawiera moj kod wklejony wiec jesli tylko dobrze generuje in to i outy powinna dawac dobre... Ściągnąłem ją jakieś 3 lub 4 dni temu. Powrót do góry 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? Wysłany: Pią 19:41, 24 Mar 2006    Temat postu: No to powinna byc dobra... Z tymze pamietaj ze to jest binarka spod windy i ona zamyka kazda linie przy pomocy #13#10. Moze to tutaj tkwi problem?? Powrót do góry Zobacz poprzedni temat :: Zobacz następny temat   Autor Wiadomość smas Okrutny Admin Dołączył: 20 Paź 2005 Posty: 1634 Przeczytał: 0 tematów Wysłany: Pią 19:51, 24 Mar 2006    Temat postu: hansu napisał: No to powinna byc dobra... Z tymze pamietaj ze to jest binarka spod windy i ona zamyka kazda linie przy pomocy #13#10. Moze to tutaj tkwi problem?? Nie:) Po pierwsze mój porgram generował większe outputy, po drugie w tym przypadku z pre i post w wielu miejscach miałem zupełnie inne ułożenie ciągów:) Powrót do góry 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? Wysłany: Pią 21:00, 24 Mar 2006    Temat postu: skad wytrzasnac algorytmy tworzenia preordera z post i inordera... i na odwrot? wiem, ze mozna samemu wykombinowac, ale jakos nie mam juz sily myslec ;P wiec, czy moglby ktos strescic idee tych algorytmow? bylbym wdzieczny :) Powrót do góry Zobacz poprzedni temat :: Zobacz następny temat   Autor Wiadomość Crow alkoholik Dołączył: 14 Mar 2006 Posty: 497 Przeczytał: 0 tematów Skąd: KRK-NH Wysłany: Pią 22:36, 24 Mar 2006    Temat postu: exeman: PLIZ popraw Gronostaja jak najszybciej bo mnie tu zaraz cos trafi! Dalej ANS Powrót do góry Zobacz poprzedni temat :: Zobacz następny temat   Autor Wiadomość exeman Mistrz grilla Dołączył: 03 Lut 2006 Posty: 1603 Przeczytał: 0 tematów Skąd: znienacka Wysłany: Pią 22:50, 24 Mar 2006    Temat postu: Crow: sam nad D siedze, Crow, poprawie naprawde, jak troche czasu znajde, ale jednak priorytetem jest D niz testy. Kurwa dendrologiem zostane, jak to zadanie zrobie. Powrót do góry Zobacz poprzedni temat :: Zobacz następny temat   Autor Wiadomość Crow alkoholik Dołączył: 14 Mar 2006 Posty: 497 Przeczytał: 0 tematów Skąd: KRK-NH Wysłany: Pią 22:53, 24 Mar 2006    Temat postu: No ja zaraz chyba kur**cy dostane z tym zadaniem! Powrót do góry Zobacz poprzedni temat :: Zobacz następny temat   Autor Wiadomość Crow alkoholik Dołączył: 14 Mar 2006 Posty: 497 Przeczytał: 0 tematów Skąd: KRK-NH Wysłany: Sob 0:02, 25 Mar 2006    Temat postu: Ufff... sie udalo... mialem blad w Post + In -> Pre Powrót do góry Zobacz poprzedni temat :: Zobacz następny temat   Autor Wiadomość h pijak Dołączył: 15 Lis 2005 Posty: 134 Przeczytał: 0 tematów Wysłany: Sob 1:47, 25 Mar 2006    Temat postu: a tak btw. jakiego macie tam finda? zwykła iteracja? Powrót do góry Zobacz poprzedni temat :: Zobacz następny temat   Autor Wiadomość exeman Mistrz grilla Dołączył: 03 Lut 2006 Posty: 1603 Przeczytał: 0 tematów Skąd: znienacka Wysłany: Sob 2:00, 25 Mar 2006    Temat postu: Zachwile zaczne strzelac poiorunami!!! Powrót do góry Zobacz poprzedni temat :: Zobacz następny temat   Autor Wiadomość Crow alkoholik Dołączył: 14 Mar 2006 Posty: 497 Przeczytał: 0 tematów Skąd: KRK-NH Wysłany: Sob 10:42, 25 Mar 2006    Temat postu: Find mam normalnie liniowo Powrót do góry Zobacz poprzedni temat :: Zobacz następny temat   Autor Wiadomość exeman Mistrz grilla Dołączył: 03 Lut 2006 Posty: 1603 Przeczytał: 0 tematów Skąd: znienacka Wysłany: Sob 18:09, 25 Mar 2006    Temat postu: Czy dziala komus prepost wg. instrukcji Rogala? :/ Powrót do góry Zobacz poprzedni temat :: Zobacz następny temat   Autor Wiadomość r4ku żul Dołączył: 09 Lut 2006 Posty: 722 Przeczytał: 0 tematów Skąd: klikash? :D Wysłany: Sob 20:30, 25 Mar 2006    Temat postu: u mnie nie dziala, czy moglby ktos wskazac co tam jest nie tak i jak powinno byc? bo mnie juz krew zalewa przez to zadanie :/ Powrót do góry Zobacz poprzedni temat :: Zobacz następny temat   Autor Wiadomość exeman Mistrz grilla Dołączył: 03 Lut 2006 Posty: 1603 Przeczytał: 0 tematów Skąd: znienacka Wysłany: Sob 20:40, 25 Mar 2006    Temat postu: r4tku, jak narazie odkrylem jeden blad, ten indeks ma nie byc od poczatku, ale wzglednie od niewiem czego. :/ Powrót do góry Zobacz poprzedni temat :: Zobacz następny temat   Autor Wiadomość Rogal Zjeb z kaszanką Dołączył: 13 Mar 2006 Posty: 1745 Przeczytał: 0 tematów Skąd: koło podbiegunowe Wysłany: Sob 21:16, 25 Mar 2006    Temat postu: Rogal napisał: Crow: Zakładam, że dane wejściowe i wyjściowe tj porządki trzymasz po prostu w tablicach, nie warto bawić się w żadną konstrukcję drzewa czy czegoś w tym stylu. Zakładam, że drzewo jest pełne, ale ty musisz to sprawdzić :wink: jako Pre,Post,In oznaczam tablice z porządkami, jako l1,l2,l3,s odpowienio lewe początki porządków Pre,Post,In (tj. w którym miejscu tablicy zaczynają się drzewa), a jako s - ilość wierzchołków drzewa nie licząc korzenia. Na początku wywołujesz procedurę z parametrami l1=1,l2=1,l3=1,s=n-1 (n - zczytana ilość wierzchołków całego drzewa) - czyi w skrócie (1,1,1,n-1) 1. Jeśli s=0 to znaczy że masz tylko korzeń. Więc In[l3]:=Pre[l1] i wychodzisz. Jeśli nie to do punktu 2. 2. Szukasz w tablicy Post elementu, który jest równy elementowi o indeksie l1+1 (licząc od początku) tablicy Pre. Indeks tego znalezionego oznaczamy jako i. Ale uwaga, nie liczymy od początku tablicy ale od elementu l2. Więc jeśli l2=4, a element znaleźliśmy na miejscu 6-tym to i=3 (6-4+1), jeśli l2=1, a znaleziona pozycja to 9 to i=9 (9-1+1). 3. Wiadomo teraz, że lewe poddrzewo ma i wierzchołków. Więc na l3+i tym miejscu tablicy In wstawiasz korzeń (czyli np. Pre[l1]): In[l3+i]:=Pre[l1]; 4. Wywołujesz to rekurencyjnie dwa razy, tj dla lewego i prawego poddrzewa. Dla lewego poddrzewa z parametrami (l1+1,l2,l3,i-1), dla prawego poddrzewa z parametrami (l1+i+1,l2+i,l3+i+1,s-i-1) Co do sprawdzania czy drzewo jest pełne... ja zrobiłem to tak, że przy każdym wywołaniu procedury sprawdzam czy s+2 jest naturalną potęgą 2. Mam do tego specjalną funkcję, która dopóki (s and 1=0) robi (s shr 1), czyli dopóki s jest podzielne przez 2 dzieli je przez 2 8) . I jeśli na końcu s=1 to znaczy że na początku było potęgą 2 a jeśli nie to znaczy że nie. Sprawdzanie, czy drzewo może być pełne po ilości wierzchołków powinno być między punktem 1 i 2 tego co napisałem Wiem że nie potrafię tłumaczyć. Dla jasności zobrazuję to przykładem. Weźmy jakieś pełne drzewo, np. takie: -------a------- ---b-------c--- -d--e----f--g-- Teraz dla tego drzewa Pre=[a,b,d,e,c,f,g], Post=[d,e,b,f,g,c,a], n=7 (liczba wierzchołków) Pierwszy raz wykonujemy procedurkę z parametrami (1,1,1,6) (bo 7-1=6) Więc l1=1, l2=1, l3=1, s=6 W pierwszym kroku sprawdzamy, czy s=0. Ponieważ nie to idziemy do kroku 2. Dalej szukamy w tablicy Post elementu, który jest równy elementowi z tablicy Pre indeksie l1+1 (czyli 2 bo l1+1=1+1=2) - Pre[2]=b. Więc szukamy w tablicy Post elementu b. Jego indeks to 3. Więc i:=3; Kolejny, trzeci krok. Z własności porządków Pre i Post wynika, że lewe poddrzewo ma i wierzchołków (czyli 3), prawe poddrzewo ma s-i wierzchołków (czyli też 3). Więc korzeń w porządku In będzie pomiędzy tymi drzewami. Łatwo wyliczyć jego indeks - będzie to l3+i, czyli 4. Więc In[4]:=Pre[l1] -> In[4]:=Pre[1] -> In[4]:=a I czwarty krok. Wywołujemy to rekurencyjnie dla lewego i prawego poddrzewa. W tym przypadku dla wywołania 'lewego' parametry będą: l1=2, l2=1, l3=1, s=2; dla wywołania 'prawego': l1=5, l2=4, l3=5, s=2 W czasie pisania tego posta zauważyłem, że rzeczywiście są błędy i niejasności, wynikające z tego, że za bardzo wzorowałem się na swoim kodzie w Pascalu. To co jest w tym poście jest już, mam nadzieję, poprawne. Na wszelki wypadek poprawiłem też poprzedniego posta. I uwaga druga. Jeśli ktoś wcześniej sprawdzi czy drzewo jest pełne to krok drugi można pominąć. W takim wypadku i jest zawsze równe s/2. Jednak pisanie tego w taki sposób jak przedstawiłem umożliwia łatwe sprawdzanie pełności drzewa nie pisząc do tego osobnego algorytmu. Ostatnio zmieniony przez Rogal dnia Sob 23:20, 25 Mar 2006, w całości zmieniany 1 raz Powrót do góry Zobacz poprzedni temat :: Zobacz następny temat   Autor Wiadomość exeman Mistrz grilla Dołączył: 03 Lut 2006 Posty: 1603 Przeczytał: 0 tematów Skąd: znienacka Wysłany: Sob 23:11, 25 Mar 2006    Temat postu: Dzieki Rogal! Rogal! W opisie masz inaczej a w przykladzie inaczej! Napisales, ze ta pozycj a (w wyszukiwaniu) jest de facto [pozycja_znalezionego] - l2. Zatem w przykladzie, dlaczego i = 3, czy nie powinno byc i = 2, bo 3 - 1 = 2. To jak w koncu? :> Pozdrawiam Powrót do góry Wyświetl posty z ostatnich: Wszystkie Posty1 Dzień7 Dni2 Tygodnie1 Miesiąc3 Miesiące6 Miesięcy1 Rok Najpierw StarszeNajpierw Nowsze         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 Poprzedni  1, 2, 3, 4, 5  Następny Strona 3 z 5   Skocz do: Wybierz forum Rozrywka----------------ImprezyAle jajaSport Ogólny----------------WitamyArchiwumKomunikaty, sekretariat naszego Forum3 semestr - Sieci Komputerowe3 semestr - Inżynieria Oprogramowania3 semestr - Matematyka Dyskretna4 semestr - Bazy danych4 semestr - Metody numeryczne 14 semestr - Organizacja i architektura komputerów4 semestr - Rachunek prawdopodobieństwa i statystyka4 semestr - Teoria języków i automatów5 semestr - Kompilatory5 semestr - Symulacja komputerowa5 semestr - Metody Numeryczne 21 semestr - Matematyka1 semestr - Informatyka2 i 3 semestr - Analiza Matematyczna2 semestr - Algebra Liniowa2 semestr - Systemy Operacyjne2 i 3 semestr - Algorytmy i Struktury Danych2 i 3 semestr - Programowanie1 rok2 rok3 rok4 rok5 rok Przedmioty----------------Systemy relacyjne baz danychObiektowe projektowanie interfejsuPodstawy cybernetykiAplikacje Rozproszone i BiznesoweProtokoły Internetowe5 semestr - Grafika KomputerowaBezpieczeństwo systemów komputerowychProgramowanie w sieciach komputerowychProgramowanie w środowisku rozproszonymMagisterka"Odchamiacze"Inne Inne----------------OfftopicTwórczośćSpamowisko Nauka----------------MatematykaInformatyka  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 Na skróty:RozrywkaOgólnyPrzedmiotyInneNaukaArchiwum1 rokImprezyOfftopic2 i 3 semestr - Algorytmy i Struktury DanychKomunikaty, sekretariat naszego ForumAle jaja2 rokSportSpamowisko3 rok2 i 3 semestr - ProgramowanieInformatyka2 i 3 semestr - Analiza MatematycznaInne1 semestr - Matematyka2 semestr - Systemy Operacyjne2 semestr - Algebra LiniowaTwórczość4 semestr - Rachunek prawdopodobieństwa i statystyka4 semestr - Metody numeryczne 15 semestr - Kompilatory"Odchamiacze"5 semestr - Grafika Komputerowa4 semestr - Teoria języków i automatów