Informatyka UJ forum

hansu · Wysłany: Pią 3:11, 17 Mar 2006 Temat postu: Zadanie D - ordery

Wiem ze wiekszosc z Was zajeta jest jeszcze zadaniami A lub C ale pozwolilem sobie nieco wybiec przed orkiestre i oto otwieram ten watek.

News egoistyczny: Udalo sie mi i bratu mojemu Insane'owi przepchnac to zadanie. Obu nam poszlo "na czysto" wiec balsamowy bilans bez zmian :D

News altruistyczny: Nie chcialo mi sie juz dzis za Robsona (Robson no offence :P) zabierac wiec wygrzebalem jakies stare programy do drzew ktore pisalem na WDP i posklejalem z nich i mojego kodu do D generator losowych testow do tego zadania. Znajdziecie go tutaj:

[link widoczny dla zalogowanych]

Jako ze jest to program napisany napredce, jest on mocno niedoskonaly i w sumie malo testowany (ale powinien byc OK bo zywcem wkleilem caly kod z D). Wiec powiedzmy ze to jest beta wersja. Wybiorcze testy wykazuja pelna zgodnosc zarowno z wynikami generowanymi przez kod moj jak i Insa...

Co do strony technicznej... Jest to program bardzo toporny, losuje trzy razy calkowicie autonomicznie jakiego porzadku uzyc... Wiec sytuacje te ktore nas interesuja czyli 3 rozne porzadki trafiaja sie dosc rzadko. Dlatego do powaznych testow proponuje genrowac min 100-200 zestwawow. Kazdy zestwa polega na:

1. Wylosowaniu liczby wierzcholkow
2. Calkowicie losowym zbudowaniu struktury drzewa i wypelnienie jej w trakcie tworzenia losowymi liczbmi z podanego zakresu.
3. Wylosowaniu 2 porzadkow i wypisaniu ich nazw i "tresci" do pliku.
4. Wylosowaniu trzeciego porzadku i zapisaniu nazwy do pliku.

Po skonczonej generacji wejscia program przepuszcza je przez moj algorytm i wypisuje wyjscie.

Niestety program pkatycznie nie sprawdza najtrudniejszego warunku czyli Preorder + Postorder -> Inorder. Szansa na wylosowanie pelnego drzewa i jednoczesnie takiego wlasnie zetawu orderow jest bliska 0. Jak bede mial chwilke to postaram sie dodac opcje generowania tych wlasnie testow na pelnych drzewach...

To tyle, ew. uwagi co do dzialania generatora wrzucajcie tutaj albo lapci mnie na GG (raczej tutaj - zeby wszystkie wiadomosci byly dostepne dla ogolu)

No i zostaje mi juz tylko zyczyc Wam powodzenia w pisaniu tego zadania. Jest bardzo ciekawe ale do najlatwiejszych nie nalezy...

domis86 · Wysłany: Pią 10:37, 17 Mar 2006 Temat postu:

No właśnie:) Skąd wiadomo, że jak jest Post i Pre to da się zrobić In?

Fidel · Wysłany: Pią 10:41, 17 Mar 2006 Temat postu:

hansu · Wysłany: Pią 13:35, 17 Mar 2006 Temat postu:

Oczywiscie ze jest inny sposob... Rekurencyjnie robi sie to tak:
Bierzesz pierwszy element z preorder i ostatni z postorder. To jest korzen drzewa. I teraz patrzysz na drugi z pre (wierzcholek lewego poddrzewa, jesli istnieje) i przedostatni z post (wierzcholek prawego poddrzewa, jesli istnieje). Jesli te dwie liczby sa takie same to znaczy ze korzen ma tylko jedno dziecko i w tym momencie wiesz juz ze drzewa nie wypiszesz. A jesli sa rozne to szukasz powiedzmy lewego wierzcholka w postorderze i juz masz wydzileone dokladnie poddrzewa... I na nich puszczasz to rekurencyjnie....

Robson · Wysłany: Sob 21:20, 18 Mar 2006 Temat postu:

Rekurencyjnie... właśnie powiedzcie czy poszła wam zwykła rekurencja czy robiliście jakieś stosy?

hansu · Wysłany: Sob 21:49, 18 Mar 2006 Temat postu:

Stosy? Nie, zadnych stosow. Najzwyczajniejsza w swiecie rekurencja... Ja mam procedury a czterech argumentach, wskazujacych odpowiednio poczatek i koniec jednego i drugiego danego orderu. Do tego funkcja find ktora szuka danego elementu w tablicy i tyle. Smiga az milo :D

Rogal · Wysłany: Sob 22:31, 18 Mar 2006 Temat postu:

hansu: a w jaki sposób zwracasz wynik?

Ja mam procedurki z 7 (! wiem że dużo) parametrami. 3 pierwsze to wskaźniki na tablice w których są ordery, 3 następne to początki tych fragmentów porządków które mnie w obecnym wywołaniu procedurki interesują, ostatni parametr to długość fragmentu drzewa (tj. ilość wierzchołków) przeglądanego w danym wywyołaniu.

Robson · Wysłany: Sob 22:36, 18 Mar 2006 Temat postu:

Tez mam 4 parametry dokładnie takie same :P ;)

Tylko na razie mam ANS :(
Musze poszukac jakiegos parszywego przykładu...

hansu · Wysłany: Sob 23:05, 18 Mar 2006 Temat postu:

Rogal: u mnie talbice sa zmiennymi globalnymi, zreszta procedure rekurencyjna mam jako podprogram innej procedury i ona korzysta i ze zmiennych globalnych i ze zmiennych tej "gornej" procedury.

Jesli ktos bylby zainteresowany dziejami generatora (choc nie widze jakiegos specjalnego odzewu - zadnego szczerze mowiac) to informuje ze dodalem obsluge pelnych drzew (teraz generuje na przemian pelne i niepelne) oraz poprawilem wrednego buga ktory wywalal caly program.

Robson · Wysłany: Sob 23:11, 18 Mar 2006 Temat postu:

Nie ma odzewu, bo malo osob robi to zadanie... tak mysle.
A co do programiku - spoko jest tylko że teraz potrzebuje raczej czegoś co by dalo rade debugować - jakiś wrednych testów...
Aha taka mała uwaga(moze o tego buga chodziło): czasami losuje rozmiar danych 0.

hansu · Wysłany: Sob 23:23, 18 Mar 2006 Temat postu:

Robson · Wysłany: Nie 0:58, 19 Mar 2006 Temat postu:

juz sam nie wiem, pusciłem 50000 testów i nie ma żadnych różnic miedzy moim programem a twoim :( no moze pozaym ze u Ciebie są spacje na koncach linii... ale raczej to chyab nie powinno na nic wpływać...

hansu · Wysłany: Nie 1:02, 19 Mar 2006 Temat postu:

To nie spacje tylko #13. Bo to jest program kompilowany pod windowsem i on wstawia #13#10 na koncu kazdej linii...

kap00ch · Wysłany: Nie 1:15, 19 Mar 2006 Temat postu:

mam to samo...niczym sie nie roznia moje odpowiedzi od tych z generatora i ciagle ans...i taka stagnacja trwa juz ponad 2h;/ tak czy siak thx za gena :]

Robson · Wysłany: Nie 1:20, 19 Mar 2006 Temat postu:

A są jakieś przypadki (poza n=1) kiedy mając tylko preorder/inorder/postorder mozemy wyznaczyć inorder albo postorder/postorder albo preorder/preorder albo inorder?

Juz nie mam siły do tego zadania :(

kap00ch · Wysłany: Nie 1:25, 19 Mar 2006 Temat postu:

pomysl nad drzewem 2 elementowym :> // ale mimo to i tak mam ansa;/

hansu · Wysłany: Nie 1:29, 19 Mar 2006 Temat postu:

Jesli n = 2 i mamy tylko preorder to mozemy wyznaczyc postorder i na odwrot. Po prostu przestawiajac elementy...

kap00ch · Wysłany: Nie 1:30, 19 Mar 2006 Temat postu:

hmm a taka mysl mnie naszla...czy taka glupota jak to ze czasem jak wypisuje drzewo przed koncem linii trafi mi sie spacja moze miec na cokolwiek wplyw?? bo juz po prostu nie mam pojecia co moze sie walic...

hansu · Wysłany: Nie 2:11, 19 Mar 2006 Temat postu:

Nie powinno miec wplywu. Ja tak nie robie, ale Insane zdaje sie tak ma i mu przeszlo bez bolu wiec to chyba nie to...

kap00ch · Wysłany: Nie 3:18, 19 Mar 2006 Temat postu:

no ku$%^$%^$^$ to sa juz jaja...w ogole zaczelo mi cos testowac jak dorobilem tablice buforowania charow zeby nie miec spacji na koncach....i co qfa?? mam TLE :O no nie moge po prostu...4h przez spacje...ja nie wiem czy to tylko mnie nie lubi sprawdzarka...

Fidel · Wysłany: Nie 3:32, 19 Mar 2006 Temat postu:

mateo · Wysłany: Nie 4:15, 19 Mar 2006 Temat postu:

No wreszcie przepchnalem to D. Musze przyznac ze piszac je nauczylem sie jednej rzeczy... a raczej nie tyle nauczylem co upewnilem: nie ma bardziej popier******** i poj******* jezyka niz Pascal. Kto jeszcze nie doszedl do tego wniosku to mysle ze z pewnoscia dojdzie do niego w trakcie pisania programow na ASD. Szkoda tylko ze trzeba sie caly semestr meczyc z tym pascalem.... przeciez to jest jakies nieporozumienie wogole, no ale co poradzic:/

kap00ch · Wysłany: Nie 14:27, 19 Mar 2006 Temat postu:

zakladam ze wszystkie glowne procedury macie rekurencyjnie? czy moze jakies super optymalizacje? bo sam juz nie wiem co z tym TLE;/

Madras · Wysłany: Nie 15:08, 19 Mar 2006 Temat postu:

Skrobocik · Wysłany: Nie 17:39, 19 Mar 2006 Temat postu: