Informatyka UJ forum

Spectro · Wysł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 :/ .

hansu · Wysł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.

Spectro · Wysł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 ;) .

Robson · Wysł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

h · Wysł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?

hansu · Wysł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.

Spectro · Wysł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).

h · Wysł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?

Skrobocik · Wysłany: Wto 22:03, 21 Mar 2006 Temat postu:

Crow · Wysł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.

Ewka · Wysłany: Śro 22:29, 22 Mar 2006 Temat postu:

hhmmm no to jak zrobić bez rekonstrukcji drzewa??

Rogal · Wysł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

Crow · Wysł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!

Fidel · Wysł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

trywialna · Wysł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:(

trywialna · Wysłany: Śro 23:55, 22 Mar 2006 Temat postu:

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

trywialna · Wysłany: Czw 0:45, 23 Mar 2006 Temat postu:

Może wie ktoś co to za błąd RCA i jak sie go pozbyć?

hansu · Wysłany: Czw 0:46, 23 Mar 2006 Temat postu:

trywialna · Wysł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:)

Madras · Wysł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.

Fidel · Wysł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

Crow · Wysł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?

jagm · Wysł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?

Crow · Wysłany: Pią 12:36, 24 Mar 2006 Temat postu:

Zaraz zwariuje!

Na ile przypadkow i jakich rozbiliscie to wszystko?!

jagm · Wysł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