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ść
Spectro
Mistrz grilla



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

Skąd: Kurdwanów

PostWysłany: Nie 20:24, 19 Mar 2006    Temat postu:

hansu, czy Twój generator losuje jakiś porządek typu POSTORDER? Bo już od paru minut generuję różne testy, a tego porządku ani razu w pliku wejściowym nie znalazłem :/ .
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: Nie 20:45, 19 Mar 2006    Temat postu:

Hmmmmmm, chyba masz racje.... A to dalem ciala.... Przepraszam Was za to az mi glupio normalnie... Mialem w programie random(2) bo zapomnialem jak to dziala. Jeszcze raz Was bardzo przepraszam. Jest juz poprawiona wersja.
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Spectro
Mistrz grilla



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

Skąd: Kurdwanów

PostWysłany: Nie 21:28, 19 Mar 2006    Temat postu:

hansu, jesteś wielki!

Dzięki temu Twojemu generatorowi znalazłem konkretny test, przez który miałem RD8. I co się okazało? W mojej rekurencji nie uwzględniłem sytuacji, kiedy funkcja schodziła do podtablicy zerowego rozmiaru. Po 3 gwiazdkach wreszcie mi zadanie przeszło ;) .
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: Pon 1:01, 20 Mar 2006    Temat postu:

No i właśnie uświadomiłem że sobie że jestem głupi, totalnie głupi. Bo kto widział żeby jak wczytuje jeden element to rozbijac to na wszystkie możliwe przypadki. No i okazało się że w kodzie zawieruszyły się jakieś dziwne ify, ktry wypisywały nie to co trzeba... bleee... wyzucenie sprawdzania czy n=1 na poczatek naprawiło wszystkie błędy :P
No ale tylu gwiazdek to chyba nie zaliczyłem jeszcze :P
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: Wto 20:40, 21 Mar 2006    Temat postu:

tylko takie małe pytanko. czy zawsze poza przypadkami n <= 2 trzeba rekonstruować drzewo, a następnie je odczytywać w zadanym porządku?
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: Wto 21:24, 21 Mar 2006    Temat postu:

W tym zadaniu w ogole nie musisz rekonstruowac drzewa... Mozna to tak sprytnie zrobic zeby od razu wspisywac poszukiwany porzadek do wynikowej tablicy.
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Spectro
Mistrz grilla



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

Skąd: Kurdwanów

PostWysłany: Wto 21:27, 21 Mar 2006    Temat postu:

I właśnie dlatego uważam zadanie D prostsze od R6 (którego do tej pory nie zrobiłem).
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: Wto 21:28, 21 Mar 2006    Temat postu:

r6 zrobiłem w jakieś pół h, nad tym już trochę siedzę, wciąż bez pomysłu, więc chyba nie. a można rekonstruować, zawsze to tak zadziała? ktoś tak ma?
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: Wto 22:03, 21 Mar 2006    Temat postu:

h napisał:
r6 zrobiłem w jakieś pół h, nad tym już trochę siedzę, wciąż bez pomysłu, więc chyba nie. a można rekonstruować, zawsze to tak zadziała? ktoś tak ma?

Mi też R6 nie za dużo zajęło, ale D jeszcze nie ruszałem, ale trzeba będzie trochę pokombinować :wink:
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: Śro 22:08, 22 Mar 2006    Temat postu:

Czy moglby mi ktos naszkicowac algorytm jak mam dane PREORDER i POSTORDER i mam wyprodukowac INORDER? Zakladam ze drzewo jest pelne, tzn. da sie to zrobic.
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Ewka
pijak



Dołączył: 15 Mar 2006
Posty: 44
Przeczytał: 0 tematów

Skąd: Rzeszów/Kraków- Ruczaj

PostWysłany: Śro 22:29, 22 Mar 2006    Temat postu:

hhmmm no to jak zrobić bez rekonstrukcji drzewa??
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: Śro 22:52, 22 Mar 2006    Temat postu:

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, liczymy nie od początku tablicy, ale od miejsca 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.
3. Wiadomo teraz, że lewe poddrzewo ma i wierzchołków. Więc na l2+i miejsce 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


Ostatnio zmieniony przez Rogal dnia Sob 23:18, 25 Mar 2006, w całości zmieniany 3 razy
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: Śro 22:54, 22 Mar 2006    Temat postu:

Dzieki... ale zanim napisales ta odpowiedz to juz zrobilem. Okazalo sie ze mialem blad w danych testowych ktore liczylem recznie i stad rozne odpowiedzi.

Dzieki za dobre checi. Napewno przyda sie innym!
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Fidel
żul



Dołączył: 19 Lis 2005
Posty: 649
Przeczytał: 0 tematów

Skąd: Kraków

PostWysłany: Śro 23:11, 22 Mar 2006    Temat postu:

a komus bedzie sie chcialo napisac tez pre+in -> post i post+in -> pre :?:

jakies skrotowe rzucenie pomyslem... bo u nas na cwiczeniach niewiele bylo na ten temat
z gory dzieki
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: Śro 23:52, 22 Mar 2006    Temat postu:

Grrr Może mi ktoś powiedzieć dlaczego ten pieprzony pascal mnie nie slucha? mam test z 1000 zestawami danych (many_small z gronostaja) a mimo tego mój program chce liczyc dalej (1001 itd:/) niewiem czemu bo petelke mam normalna for i:=1 to length probowalam tez zmienic na while ale nic to nie daje:/ nic sie nie zmienia jak np. zmniejszylam powtarzanie do polowy z wczytanej liczby zestawu danych w moim zrodle chociaż w pliku .in dalej jest 1000 dalej pogram zatrzymuje sie na 1001 razie z errorem.. jak dopisze jakies zestawy w pliku many_small.in to je nadal liczy mimo ze na górze ma napisane 1000 niewiem co robic:(
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: Śro 23:55, 22 Mar 2006    Temat postu:

co za kretynizm... już wiem już wiem!! hehe aż sie wstyd przyznawać co mialam źle:)
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: Czw 0:45, 23 Mar 2006    Temat postu:

Może wie ktoś co to za błąd RCA i jak sie go pozbyć?
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: Czw 0:46, 23 Mar 2006    Temat postu:

trywialna napisał:
co za kretynizm... już wiem już wiem!! hehe aż sie wstyd przyznawać co mialam źle:)


No nie badz taka, pochwal sie ;)
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: Czw 0:49, 23 Mar 2006    Temat postu:

no coż... używalam zmiennej 'i' rownież w mniejszej pętelce w programie przy wypisywaniu ale ciii nikomu ani mru mru:)
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Madras
Omylny Admin



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

Skąd: Z Pokoju :]

PostWysłany: Czw 1:11, 23 Mar 2006    Temat postu:

Nie Ty pierwsza i nie ostatnia ;].
RCA - Runtime CA - Runtime 202 - Stack overflow error, zużywasz za dużo pamięci na stosie - albo włącza Ci się nieskończona rekurencja, albo po prostu algorytm jest zbyt pamięciożerny i trzeba wymyśleć coś innegp.
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Fidel
żul



Dołączył: 19 Lis 2005
Posty: 649
Przeczytał: 0 tematów

Skąd: Kraków

PostWysłany: Pią 11:40, 24 Mar 2006    Temat postu:

po nastepnej zarwanej nocy przeszlo mi D...

nie pamietam juz kto mowil ze D jest proste i latwiejsze od R6 ale dla mnie to bylo jedno z trudniejszych zadan jak dotychczas... na pewno C pisalo mi sie milej i przyjemniej

pewnie dlatego ze jakos nie trawie rekurencji w tak duzych ilosciach :P
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ą 12:07, 24 Mar 2006    Temat postu:

Ot zagwozdka:

Gronostaj mowi OK na wszystkich testach, a sprawdzarka: ANS

Co z tymi dodatkowymi spacjami na koncu przy wypisywaniu wyniku? Komus przeszlo z tymi spacjami?
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: Pią 12:14, 24 Mar 2006    Temat postu:

Mi przeszło ze spacjami na końcu :) Może jakiegoś specjalnego warunku nie obsługujesz?
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ą 12:36, 24 Mar 2006    Temat postu:

Zaraz zwariuje!

Na ile przypadkow i jakich rozbiliscie to wszystko?!
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: Pią 12:51, 24 Mar 2006    Temat postu:

- jeśli jest tylko jeden element to go wypisuję
- jeśli któryś z podanych porządków jest tym szukanym, to go wypisuję
- jeśli mam 2*post i szukam pre, a do tego długość =2, to odwrotna kolejność
- jeśli mam 2*pre i szukam post, a do tego długość =2, to odwrotna kolejność
- jeśli mam pre i in i szukam post, to wyznaczam post
- analogicznie post + in
- mam pre i post i szukam in, to próbuję wyznaczyć i jeśli się okaże, że drzewo jest pełne, to wypisuję
- pozostałe przypadki - error
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 2 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