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 

F - Mediana median
Idź do strony 1, 2, 3, 4  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ść
Pandunia
Gość






PostWysłany: Nie 22:14, 19 Mar 2006    Temat postu: F - Mediana median

[deleted]

Ostatnio zmieniony przez Pandunia dnia Pią 5:31, 10 Lis 2006, w całości zmieniany 1 raz
Powrót do góry
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: Nie 22:56, 19 Mar 2006    Temat postu:

to ja podpowiem, że sugerowane rozwiązanie będzie podane w notatkach sortowanie_3 :]
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
mateo
pijak



Dołączył: 08 Mar 2006
Posty: 296
Przeczytał: 0 tematów

Skąd: Krk - Biały Prądnik

PostWysłany: Pon 18:52, 20 Mar 2006    Temat postu:

Jakby cos to dodalem do testerki generator testow do F - poki co mozna testowac w trybie 0, bo mi sie juz quota skonczyla....

swoja droga to fajnie debuguje sie to zadanko :)... naprawde mozna sie pogubic w tych wszystkich wywolaniach rekurencyjnych... mi sie naszczescie udalo to jakos przepchnac.
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
domis86
[świeżak]



Dołączył: 17 Mar 2006
Posty: 23
Przeczytał: 0 tematów

Skąd: Brzesko

PostWysłany: Pon 18:58, 20 Mar 2006    Temat postu:

Ja bym powiedział tak:
Counting sort rulez :lol:
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: Pon 21:49, 20 Mar 2006    Temat postu:

Ja wymiękam przy tym zadaniu. Znowu będzie ze 30 TLE-bomb :?

Bardzo jestem ciekaw jak wyglądają wzorcówki do zadań F,G i jak obliczają limit czasowy w oparciu o wnie. Bo o ile z moich dotychczasowych obserwacji wynikało, że średnio ambitne algorytmy bez specjalnej optymalizacji spokojnie mieściły się w czasie, o tyle dla tych zadań staję na głowie i TLE :?
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Pawel Str.
pijak



Dołączył: 06 Lut 2006
Posty: 429
Przeczytał: 0 tematów

Skąd: Ze starszego roku / Z Gorlic

PostWysłany: Pon 21:57, 20 Mar 2006    Temat postu:

Ja może podpowiem, że próba kombinowania ze współczynnikiem gęstości tablicy nie działała (TLE). Należało po prostu tworzyć nową tablicę, 5 razy mniejszą (+jeden element więcej) i kopiować mediany piątek.
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
kap00ch
Mistrz grilla



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

Skąd: ja sie tu wzialem?

PostWysłany: Pon 23:00, 20 Mar 2006    Temat postu:

a ja dla odmiany mam RD8 ;/ a na sprawdzarce mateo mam wszystko OK ;/ lipa...
swoja droga...ktos wie czemu sprawdzaramateo nie ma ochoty zapisywac testow ktore byly bledne?
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 0:06, 21 Mar 2006    Temat postu:

Moze dlatego ze sie mu skonczylo miejsce na quocie??
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
mateo
pijak



Dołączył: 08 Mar 2006
Posty: 296
Przeczytał: 0 tematów

Skąd: Krk - Biały Prądnik

PostWysłany: Wto 0:10, 21 Mar 2006    Temat postu:

Pawel Str. napisał:
Ja może podpowiem, że próba kombinowania ze współczynnikiem gęstości tablicy nie działała (TLE). Należało po prostu tworzyć nową tablicę, 5 razy mniejszą (+jeden element więcej) i kopiować mediany piątek.


Hmm a co to jest ten wspolczynnik gestosci tablicy?.. moze to na wykladach bylo... ja tam nie wiem - w kazdym razie niewiele mi to mowi.

A od siebie to moge podpowiedziec tyle ze da sie to zadanie zrobic bez tworzenia zadnych dodatkowych tablic. Ja przynajmniej tak mam, ze wszystko jest obliczane w miejscu i bez problemu zmiescilem sie w timelimicie.

a jesli chodzi o:
kap00ch napisał:
swoja droga...ktos wie czemu sprawdzaramateo nie ma ochoty zapisywac testow ktore byly bledne?


to swoja droga ja wiem czemu sie tak dzieje :D. Jeszcze wczoraj bylo tak ze wogole testerka w trybie 0 sie nie zatrzymywala na testach gdzie wasz program zwracal RTE. Dzisiaj to poprawilem ale zapomnialem o tym zeby nie kasowac testow. Teraz juz powinno byc OK. Po prostu nie chcialo mi sie z tym bawic bo planowalem postawic moja testerke ktora pisalem jakis rok po tej pierwszej wersji ktora teraz jest dostepna i ta drua wersja ma juz to wszystko poprawione lecz dziala ona zdecydowanie inaczej niz ta wersja i musze tam dopisac pare rzeczy (parser zrodel itp.) zeby sie zabezpieczyc przed zlosliwymi osobami.... No kiedys moze ja udostepnie ale poki co to strasznie mi sie nei chce z tym bawic.
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: Wto 1:13, 21 Mar 2006    Temat postu:

Ktoś mnie przed chwilą uratował przed chorobą psychiczną. :twisted:

W każdym razie mogę powiedzieć, że samą medianą median to raczej ciężko będzie to przejść. Polecam zastosowanie Counting Sorta dla dużych danych (np. n>100000). 8)
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: Wto 2:40, 21 Mar 2006    Temat postu:

Algorytm Hoare'a czy jakmu tam było (tego od kwiksorta). Tylko tyle powiem :)



Swoją droga jak ktoś ma kwiksorta zrobionego nie tak jak na wykładzie, tylko z wybieraniem srodkowego elementu to ma juz 70% zadania....
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 3:11, 21 Mar 2006    Temat postu:

Przykro mi to mowic Robson, ale zastosowales zly algorytm... Moze i przeszlo ale cwiczeniowiec nie powinien Ci tego zaliczyc (chociaz ja Ci tam dobrze zycze :D). Trzeba zastosowac algoytm ktory dziala w PESYMISTYCZNYM czasie liniowym, a Hoare dziala w pesymistycznym kwadratowym... Trzeba uzyc tej paskudnej mediany median...

Polecam: [link widoczny dla zalogowanych]
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: Wto 10:26, 21 Mar 2006    Temat postu:

No cóż, tak to jest jak się robi zadania do przodu znanymi ale nie Jedynymi Słusznymi Algorytmami.
Ale skoro przeszło, to chyba się za bardzo nie przyłożyli do testów, bo powinnien być jakiś na którym sie takie rozwiazanie wyłoży...
No ale, zobaczymy co dr Kawa dzisiaj na to powie ;)
Swoją drogą to zastosowałem ten algorytm, bo skoro jesteśmy przy dziel i zwyciężaj, to myslałemże o niecgo chodzi, zreszta po głowie chodziła mi jego złozonoś - 4n, ale to chyba średni przypadek... hmmmm.

Dobra to kodujcie tą medianę median, zapomnijcie o tym Hoare :)
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: Wto 12:08, 21 Mar 2006    Temat postu:

A ja polecam "Wprowadzenie do algorytmów" Cormena, s. 225 ;].
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ą 20:05, 24 Mar 2006    Temat postu:

a przeszlo komus to zadanie mediana median? a dokladniej to tym algorytmem podanym przez Madrasa z Cormena?

Bo ja mam to i TLE :?
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: Pią 21:37, 24 Mar 2006    Temat postu:

Jak pisałem wyżej polecam counting sorta dla dużych danych. Ja też miałem TLE po zaimplementowaniu algorytmu z Cormena więc to chyba norma. Inna sprawa, że ja lamka jestem i pewnie totalnie zwaliłem tą implementację ale cóż... :roll:
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ą 23:53, 24 Mar 2006    Temat postu:

A ja napisalem tego z Cormena bez zadnych usprawnien, bezczelnie "do konca" tlukacego rekurencja i przeszlo. I tew wcale jakos szczegolnie optymalny nie jest. Jedyne co moze go przyspieszac to partition dzielacy na trzy czesci, ale to juz chyba standard po zadaniu G :)

@Rogal: Moglbys mi wytlumaczyc jak Ty tego counting sorta stosujesz? Bo albo myslimy o roznych algorytmach albo napisales program potrzebujacy 16 Gb pamieci...
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: Sob 0:29, 25 Mar 2006    Temat postu:

hansu napisał:
Jedyne co moze go przyspieszac to partition dzielacy na trzy czesci, ale to juz chyba standard po zadaniu G :)


ale uzywales takiego partition?

ja w G tego nie mialem wiec nie standard :)
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: Sob 1:27, 25 Mar 2006    Temat postu:

Fidel napisał:
ale uzywales takiego partition?


Ma sie rozumiec... Lekko zmodyfikowany lomuto partition z podzialem na 3 "sektory". Cos jak problem flagi o ktorym byla mowa na wykladach...
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: 1601
Przeczytał: 0 tematów

Skąd: znienacka

PostWysłany: Nie 18:58, 26 Mar 2006    Temat postu:

Czytalem ten algorytm od poczatku, od konca, od lewej, od prawej. Ale za cholere nie widze, jakim cudem mialby on dzialac w czasie liniowym!!

Przeciez nawet jesli wyznaczymy juz ta mediane median, oraz bedziemy mieli L oraz R (lewe i prawe elementy wzgledem tej mediany), to potem zeby znalesc te elementy znow trza bedzie ostro pojechac jakims polowkowym wyszukiwaniem, zatem wracamy do punktu wyjscia, jedyne co to bedziemy mieli mniejsza stala, ale rzad zlozonosci dalej niezadowalajacy (nie liniowy dla pesym.).

Gdzie mam blad w rozumowaniu, o co chodzi!
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
wuodi
pijak



Dołączył: 10 Lis 2005
Posty: 140
Przeczytał: 0 tematów


PostWysłany: Nie 22:35, 26 Mar 2006    Temat postu:

mam takie pytanie...
wlasciwie to co trzeba zrobic bo na wykladzie nie bylem? (nie z lenistwa tylkom chory byl)
Zadanie wyglada na banalne - posortowac sobie tablice i podac k-ty element a jaki haczyk?
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: Nie 23:00, 26 Mar 2006    Temat postu:

haczyk jest taki ze ma on dzialac liniowo w pesymistycznym przypadku

polecam s.225 Cormen chociaz trzeba dodac pewne optymalizacje ktorych jeszcze mi sie nie udalo zrobic :wink:

lub jak podawal Rogal sortowanie kubelkowe
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: Wto 23:20, 28 Mar 2006    Temat postu:

widze ze zniknely testy do tego zadania na virgo :(

mateo to tylko tymczasowo czy juz na stale?
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Pawel Str.
pijak



Dołączył: 06 Lut 2006
Posty: 429
Przeczytał: 0 tematów

Skąd: Ze starszego roku / Z Gorlic

PostWysłany: Wto 23:30, 28 Mar 2006    Temat postu:

exeman napisał:
Czytalem ten algorytm od poczatku, od konca, od lewej, od prawej. Ale za cholere nie widze, jakim cudem mialby on dzialac w czasie liniowym!!

Przeciez nawet jesli wyznaczymy juz ta mediane median, oraz bedziemy mieli L oraz R (lewe i prawe elementy wzgledem tej mediany), to potem zeby znalesc te elementy znow trza bedzie ostro pojechac jakims polowkowym wyszukiwaniem, zatem wracamy do punktu wyjscia, jedyne co to bedziemy mieli mniejsza stala, ale rzad zlozonosci dalej niezadowalajacy (nie liniowy dla pesym.).

Gdzie mam blad w rozumowaniu, o co chodzi!


Zakładając, że już masz element dzielący m, rozkład na 3 pasy robisz liniowo. I teraz rekurencyjnie wywołujesz szukanie tylko dla jednego pasa (albo wcale, jeżeli szukany element wypadł w środkowym).

A dlaczego liniowe? Mniej więcej tak:
Niech T(n) to złożoność zadania (pesymistyczna)
T(n/5) - koszt wyznaczenia środka spośród piątek (szukanie m)

A wiemy, że jak tak wybraliśmy element dzielący, to w pasie, który za chwilę zbadamy będzie nie więcej niż 3/4n elementów. Czyli

T(n)=T(n/5) + T(3n/4). To teraz indukcyjnie się dowodzi, że jest to liniowe (tj dowodzi się, że T(n) <=20*c*n)
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
domis86
[świeżak]



Dołączył: 17 Mar 2006
Posty: 23
Przeczytał: 0 tematów

Skąd: Brzesko

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

Pawel Str. napisał:
T(n) <=20*c*n)


Lol

to moj algorytm countsortowy ( :D ) trzyprzebiegowy ma gdzies pesymistyczny czas 3,5*c*n (c to czas porownania) czyli jakies 6*szybciej , a jest mniej skomplikowany
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 1, 2, 3, 4  Następny
Strona 1 z 4

 
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