Dział zablokowany Ten wątek jest zablokowany. Nie możesz w nim pisać ani edytować postów.  [ Posty: 50 ]  Przejdź na stronę Poprzednia strona  1, 2, 3, 4, 5  Następna strona
Jaś robaczek - testy 
Autor Wiadomość
Gwiazda 2Gwiazda 2Gwiazda 2

Dołączył(a): 16 lis 2009, o 22:34
Posty: 35
Post Re: Jaś robaczek - testy
Potwierdzam wszystkie testy, lecz...

rand() może działać też inaczej na różnych architekturach i tak na 64-bitowej maszynie z Linuksem mam inne testy od 32-bitowej.
Rozwiązanie: prosty rand to 3 linijki

Ponadto czasy są bardzo relatywne:
Na netbooku 1.5Ghz 32-bit mam czas 32s - z KDE4
Po przesłaniu pliku na szkolny serwer,
czyli 64-bit Xeon 4x2Ghz wychodzi 6s - praktycznie cały rdzeń dla mnie.


16 paź 2010, o 19:41
Zobacz profil
Gwiazda 3

Dołączył(a): 20 lis 2009, o 10:05
Posty: 154
Lokalizacja: Bydgoszcz
Post Re: Jaś robaczek - testy
Niniejszym potwierdzam wszystko w tym temacie :)


16 paź 2010, o 21:17
Zobacz profil YIM
Gwiazda 2Gwiazda 2Gwiazda 2

Dołączył(a): 28 maja 2010, o 15:52
Posty: 60
Post Re: Jaś robaczek - testy
Zakładamy, że nie ma limitu na stos?


17 paź 2010, o 15:02
Zobacz profil
Gwiazda 2Gwiazda 2Gwiazda 2

Dołączył(a): 23 lis 2009, o 23:00
Posty: 101
Post Re: Jaś robaczek - testy
Michał Błaziak napisał(a):
Zakładamy, że nie ma limitu na stos?

viewtopic.php?f=27&t=732


17 paź 2010, o 16:00
Zobacz profil
Gwiazda 3

Dołączył(a): 20 lis 2009, o 10:05
Posty: 154
Lokalizacja: Bydgoszcz
Post Re: Jaś robaczek - testy
Jestem tylko bardzo ciekawy testów w tym zadaniu, bo chyba nie dało się tego zrobić szybciej niż w O(n lg n)...


17 paź 2010, o 18:14
Zobacz profil YIM
Gwiazda 2Gwiazda 2Gwiazda 2Gwiazda 2Gwiazda 2

Dołączył(a): 17 lis 2009, o 18:24
Posty: 121
Post Re: Jaś robaczek - testy
Xeon da radę ;)
A jakie macie rozwiązania? Ja olewam zdarzenia i najpierw robię całe drzewo a potem obsługę zapytań.


17 paź 2010, o 18:39
Zobacz profil
Gwiazda 2Gwiazda 2

Dołączył(a): 20 lis 2009, o 14:15
Posty: 106
Post Re: Jaś robaczek - testy
A O(n lg n) to jak?


17 paź 2010, o 18:42
Zobacz profil
Gwiazda 3
Avatar użytkownika

Dołączył(a): 23 lis 2009, o 08:40
Posty: 175
Post Re: Jaś robaczek - testy
Najpierw wczytuję sobie całe drzewo, dfsem (iteracyjnym!) obliczam sobie dla każdego wierzchołka czasy wejścia/wyjścia. Dalej dla zapytań mam 3 możliwe przypadki:
- wierzchołek docelowy jest wierzchołkiem obecnym - nie robię nic
- wierzchołek docelowy nie znajduje się w poddrzewie obecnego wierzchołka (co można sprawdzić w O(1) porównując czasy wejść/wyjść) - idę do rodzica
- wierzchołek docelowy znajduje się w poddrzewie obecnego wierzchołka - wyszukuję binarnie po dzieciach obecnego wierzchołka w którym poddrzewie jest wierzchołek docelowy

Zdecydowanie najprostsze zadanie :) Już z Mistrzostwami było więcej kombinowania.


17 paź 2010, o 18:46
Zobacz profil
Gwiazda 2Gwiazda 2Gwiazda 2Gwiazda 2Gwiazda 2
Avatar użytkownika

Dołączył(a): 30 maja 2010, o 20:46
Posty: 69
Post Re: Jaś robaczek - testy
1. budujemy drzewo.
2. puszczamy DFS(1) z numeracją post (lub pre) order.
3. obsługujemy po kolei zdarzenia:
- jeśli numer szukanego jest większy niż aktualny to idziemy do rodzica
- jeśli taki sam to stoimy ;)
- jeśli mniejszy to szukamy lower_bound odpowiedniego wierzchołka (po postorderach).


17 paź 2010, o 18:46
Zobacz profil
Gwiazda 2Gwiazda 2Gwiazda 2Gwiazda 2Gwiazda 2

Dołączył(a): 17 lis 2009, o 18:24
Posty: 121
Post Re: Jaś robaczek - testy
Ale chyba może być DFS rekurencyjny?


17 paź 2010, o 18:47
Zobacz profil
Wyświetl posty nie starsze niż:  Sortuj wg  
Dział zablokowany Ten wątek jest zablokowany. Nie możesz w nim pisać ani edytować postów.  [ Posty: 50 ]  Przejdź na stronę Poprzednia strona  1, 2, 3, 4, 5  Następna strona


Kto przegląda forum

Użytkownicy przeglądający ten dział: Brak zidentyfikowanych użytkowników i 2 gości


Nie możesz rozpoczynać nowych wątków
Nie możesz odpowiadać w wątkach
Nie możesz edytować swoich postów
Nie możesz usuwać swoich postów
Nie możesz dodawać załączników

Skocz do:  
cron


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group. Forum style based on STSoftware Hestia.
Przyjazne użytkownikom polskie wsparcie phpBB3 - phpBB3.PL