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 D - ordery
Idź do strony Poprzedni  1, 2, 3, 4, 5  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ść
Crow
alkoholik



Dołączył: 14 Mar 2006
Posty: 497
Przeczytał: 0 tematów

Skąd: KRK-NH

PostWysł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 profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
h
pijak



Dołączył: 15 Lis 2005
Posty: 134
Przeczytał: 0 tematów


PostWysł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 profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
h
pijak



Dołączył: 15 Lis 2005
Posty: 134
Przeczytał: 0 tematów


PostWysł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 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: 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 profil autora
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

PostWysł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 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: 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 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: 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 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: 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 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: 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 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: 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 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: 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 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: 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 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: 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 profil autora
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

PostWysł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 profil autora
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

PostWysł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 profil autora
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

PostWysł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 profil autora
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

PostWysłany: Sob 0:02, 25 Mar 2006    Temat postu:

Ufff... sie udalo... mialem blad w Post + In -> Pre
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
h
pijak



Dołączył: 15 Lis 2005
Posty: 134
Przeczytał: 0 tematów


PostWysł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 profil autora
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

PostWysłany: Sob 2:00, 25 Mar 2006    Temat postu:

Zachwile zaczne strzelac poiorunami!!!
Powrót do góry
Zobacz profil autora
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

PostWysłany: Sob 10:42, 25 Mar 2006    Temat postu:

Find mam normalnie liniowo
Powrót do góry
Zobacz profil autora
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

PostWysłany: Sob 18:09, 25 Mar 2006    Temat postu:

Czy dziala komus prepost wg. instrukcji Rogala? :/
Powrót do góry
Zobacz profil autora
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

PostWysł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 profil autora
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

PostWysł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 profil autora
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

PostWysł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 profil autora
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

PostWysł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
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 Poprzedni  1, 2, 3, 4, 5  Następny
Strona 3 z 5

 
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