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 Poprzedni  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ść
Rogal
Zjeb z kaszanką



Dołączył: 13 Mar 2006
Posty: 1745
Przeczytał: 0 tematów

Skąd: koło podbiegunowe

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

hansu napisał:
@Rogal: Moglbys mi wytlumaczyc jak Ty tego counting sorta stosujesz? Bo albo myslimy o roznych algorytmach albo napisales program potrzebujacy 16 Gb pamieci...


Nie koniecznie. Najpierw puszcam Counting, żeby sprawdzić w jakim zakresie wartości jest liczba (albo inaczej: żeby wyznaczyć bardziej znaczące 16 bitów liczby) i która w kolejności jest w tym zakresie, a później puszczam jeszcze raz zliczając tylko liczby z danego zakresu (wyznaczam mniej znaczące 16 bitów).

Wystarcza 1 tablica [0..65535] longintów.
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: Śro 17:57, 29 Mar 2006    Temat postu:

Nie precyzuję, czym jest c. To po prostu stała czasowa.
Na czym dokładnie polega ten twój algorytm countsortowy? Bo coś mi się wydaje, że na doublach to już twój algorytm nie pociągnie.
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Lupus
pijak



Dołączył: 02 Lut 2006
Posty: 105
Przeczytał: 0 tematów

Skąd: Lea/Piastowska

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

Świetny pomysł z tymi countingiem ,'] Nie wiem dokladnie jak to napisaliście, ale pewnie chodzi o takiego radixsorta, tyle ze nie trzeba nawet sortowac calych ciagow.

No, mam nadzieje ze cwiczeniowcy beda takie rozwiazania przyjmowac. Niestety w grupie mgr Brońka _trzeba_ to napisac medianą median.
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: Śro 22:57, 29 Mar 2006    Temat postu:

Lupus napisał:
No, mam nadzieje ze cwiczeniowcy beda takie rozwiazania przyjmowac. Niestety w grupie mgr Brońka _trzeba_ to napisac medianą median.


Nie powinni. To jednak ma być mediana median. Może rzeczywiście jest to algorytm ciekawy tylko ze względów teoretycznych (realnie też stosuje się podział na 3 i wykonanie podzadania, tylko z prostszym wyborem pivotu), ale jednak warto go znać.

Counting sort/radix jest bardzo ograniczony, choć na intach o ograniczonym zakresie rzeczywiście świetny.
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: Śro 23:56, 29 Mar 2006    Temat postu:

Zgadzam se z Pawlem... Wiekszosc zadan ktore robimy i ktore maja jakies wymagania odnosnie stosowanego algorytmu moznaby zrobic jakos inaczej: szybciej, wydajniej pamieciowo, moze nawet prosciej (np. stos za pomoca stosu a nie dwoch kolejek ;)). Ale to nie o to chodzi, to nie zawody informatyczne. Te zadania sa takie, a nie inne po to, zeby nas czegos nauczyc...
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: Czw 1:01, 30 Mar 2006    Temat postu:

hansu napisał:
Wiekszosc zadan ktore robimy (...) moznaby zrobic jakos inaczej: szybciej, wydajniej pamieciowo, moze nawet prosciej

hansu napisał:
Te zadania sa takie, a nie inne po to, zeby nas czegos nauczyc...

.. po to by nauczyc nas je robic wolniej, z wiekszymi wymaganiami pamieciowymi i trudniej :lol:

Rogal napisał:
Wystarcza 1 tablica [0..65535] longintów.


w moim 3-przebiegowym wystarczaja 3 tablice : 16kb+4kb+4kb
czyli razem okolo 24kb :D


Ostatnio zmieniony przez domis86 dnia Czw 1:14, 30 Mar 2006, w całości zmieniany 1 raz
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: Czw 13:28, 30 Mar 2006    Temat postu:

To znaczy że ty mastah jesteś... :wink:
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 14:07, 30 Mar 2006    Temat postu:

domis86 napisał:
hansu napisał:
Wiekszosc zadan ktore robimy (...) moznaby zrobic jakos inaczej: szybciej, wydajniej pamieciowo, moze nawet prosciej

hansu napisał:
Te zadania sa takie, a nie inne po to, zeby nas czegos nauczyc...

.. po to by nauczyc nas je robic wolniej, z wiekszymi wymaganiami pamieciowymi i trudniej :lol:


Nie, zeby nauczyc nas myslec algorytmicznie, rozwiazywac problemy na rozne sposoby i pokazac ciekawe algorytmy... A nie wszystko pchac quicksortem...
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: Czw 15:24, 30 Mar 2006    Temat postu:

hansu napisał:
A nie wszystko pchac quicksortem...


wole HeapSorta jak juz cos :D
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: Czw 17:14, 30 Mar 2006    Temat postu:

Doszly testy do zadania F na gronostaju, jesli bedziecie miec TLE, to pretensje do hansa za tak szybkie wzorcowki :P
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 22:33, 30 Mar 2006    Temat postu:

Mam takie pytanko:) w tym przykładowym wejściu jest napisane ze dla ciagu 0 0 1 1 czwartym co do wielkosci jest 1 wiec chyba czegoś nie rozumiem bo moim zdaniem nie ma czwartego co do wielkosci elementu. tylko jest pierwszy i drugi...
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 22:52, 30 Mar 2006    Temat postu:

Hehe, no i znowu rozbijamy sie o definicje :D No de facto patrzac z perspektywy jezyka naturalnego to nie ma czwartego co do wielkosci elementu. Ale tu chodzi o to zeby podac co bedzie na k-tym miejscu po posortowaniu tych liczb ktore dostajemy... Po matematycznemu to sie nazywa k-ta statystyka pozycyjna (ble! okropna nazwa :) No w kazdym razie w tym ciagu ktory podalas element 4 i 3 to 1 a 1 i 2 to 0 :D
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 23:00, 30 Mar 2006    Temat postu:

Ok to w takim razie zadam jeszcze głupsze pytanie :D jeżeli chodzi o k-te miejsce to niewystarczy napisac ze jest ono rowne tablica[k]? :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: Czw 23:07, 30 Mar 2006    Temat postu:

No ale zauwaz ze dostajesz ciag nieposortowany... A ta liczba to ma byc ta z k-tego miejsca po posortowaniu...
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 23:12, 30 Mar 2006    Temat postu:

No tak ale moge ten ciag najpierw posortowac tak jak w zadaniu G:)
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Source
pijak



Dołączył: 26 Paź 2005
Posty: 92
Przeczytał: 0 tematów

Skąd: Zmc

PostWysłany: Czw 23:17, 30 Mar 2006    Temat postu:

No ale musisz pamietac ze posortowanie całej talicy to TLE murowane. Musisz sprytnie wyszukać, w której części jest element szukany i tylko na niej wykonać partition. I dalej rekurencyjnie.
Warto też jest użyć tego ulepszonego partition z 3 częściami, które hansu podawał w poście do zadania G.
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 23:19, 30 Mar 2006    Temat postu:

No w sumie mozesz i jak masz dobrego quicksorta to Ci to nawet athina przepusci... Ale w tresci zadania jest napisane, ze algorytm ma dzialac w pesymistycznym czasie liniowym i ponadto jest napisane aby uzyc algorytmu mediany median... Wprawdzie roznie to ludzie przepychali, i quicksortem, i jakims radixem, ale mimo wszystko polecam zrobic to tym wlasnie algorytmem, chocby dlatego ze jest ciekawy, a i cwiczeniowiec Ci sie nie przyczepi ;)
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Krisowski
pijak



Dołączył: 05 Mar 2006
Posty: 218
Przeczytał: 0 tematów

Skąd: z nikąd

PostWysłany: Pią 12:20, 31 Mar 2006    Temat postu:

Niech to szlag... ! Na testerce mateo mam same OK i dostałem 140 punktów, a ta cholerna athina mi mówi TLE! Jak ktoś potrafi mi odpowiedzieć dlaczego to bardzo byłbym wdzięczny za tą informację.
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: Pią 12:34, 31 Mar 2006    Temat postu:

Ja podejrzewam, ze twoj program jest prawie dobry.... tylko moze sie wychrzaniac dla szczegolnych przypadkow (tzn po prostu moze sie zapetlac). Ja naprzyklad tak mialem, ze moj program dzialalo ok ale czasem (bardzo rzadko) mi sie zapetlal. Chodzilo o to ze w partition moglo sie zdarzyc, ze dokonywal on podzilu w ktorym jedna podtalblica miala rozmiar 0 - moze sie tak stac gdy jako element podzialu wezmie sie ostatni element tablicy ktory jednoczesnie musi byc najwiekszym elementem (mowa tutaj oczywiscie nie o lumoto partition), ale w lumoto tez sie tak moze stac tylko inaczej wyglada ten szczegolny przeypadek.... juz nie pamietam jak... W kazdym razie nalezy pamietac ze mediana median moze byc najwiekszym elementem w tablicy jak rowniez elementem najmniejszym i moze sie znajdywac na samym poczatku tablicy i na koncu takze. Moze to cos pomoze?
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ą 19:11, 31 Mar 2006    Temat postu:

Krisowski napisał:
Niech to szlag... ! Na testerce mateo mam same OK i dostałem 140 punktów, a ta cholerna athina mi mówi TLE! Jak ktoś potrafi mi odpowiedzieć dlaczego to bardzo byłbym wdzięczny za tą informację.


tez tak mialem... w sumie u mnie sie okazalo ze jak przekazywalem indeks mediany do partition to partition wykonywalem nie wedlug mediany tylko wedlug indeksu :P a u mateo wszystko bylo ok... ja bym szukal bledu raczej np sprawdzajac ile rekursji sie wywoluje - robisz sobie przyklad na kartce, patrzysz ile powinno a ile wykonuje twoj program... wartosc mediany median musisz przed parition przypisac do jakiejs zmiennej bo w tablicy ona sie moze przemieszczac... tyle mi do glowy przychodzi

edited: to "czesc" mialo byc na gg :P
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Krisowski
pijak



Dołączył: 05 Mar 2006
Posty: 218
Przeczytał: 0 tematów

Skąd: z nikąd

PostWysłany: Pią 21:38, 31 Mar 2006    Temat postu:

Uff. poszło :) ... Szczerze mówiąc, to nie potrafię powiedzieć co to było. Moja pierwsza wersja korzystała z partition Hoare'a i na Virgo dostała 140 pkt (max :D ), natomiast na Gronostaju jeszcze nie dawno byłem dzięki niej pierwszy w rakingu F. Ale coż, to niestety nie zadowoliło Athiny i powiedziała, że to za wolno ;P . Przerobiłem program (a właściwie partition) na Lomuto z podziałem na trzy części (tak jak radził hansu). Co się okazało: na Gronostaju ten właśnie program dostał grubo ponad punkt mniej (to dość sporo biąrąc pod uwagę różnice pomiędzy miejscami w rankingu). Nie miałem więcej pomysłów, więc postanowiłem spróbowac na asd. Tym razem, mimo, że mój program był wyraźnie wolniejszy od pierwszej wersji, dostałem OK :shock: (przyznacie, że dziwna kobitka z tej Athiny 8) ).

A teraz wnioski :D . Zapewne rację miał Mateo. Pewnie mój pierwszy program (ten z Hoare'em) robił jakieś dziwne rzeczy dla pewnych danych :P . Niestety nie udało mi się znaleźć zestawu liczb, dla których coś nie działało. Moja rada dla tych, którzy jeszcze nie zrobili tego programu: dajcie sobie spokój z Hoare'em i zróbcie Lomuto dzielące na trzy części (trzeba trochę pomysleć w przeciwieństwie do gotowego Hoare'a, ale to się opłaci).

P.S. Dzięki za wszystkie porady, zarówno na tym forum jak i poza nim :) .
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: Pią 21:50, 31 Mar 2006    Temat postu:

Gdzie można znaleźć ten Lomuto?
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Krisowski
pijak



Dołączył: 05 Mar 2006
Posty: 218
Przeczytał: 0 tematów

Skąd: z nikąd

PostWysłany: Pią 22:09, 31 Mar 2006    Temat postu:

Algorytm podziału wg Lomuto przedstawił na wykładzie dr Ślusarek. Trzeba go jednak zmodyfikować, aby dzielił tablicę na trzy części: liczby mnijesze od mediany (elementu dzielącego), liczbu równe medianie i liczby większe. Jak to zrobić opisywał hansu w poście do zadania G (przyznam, że jak dla mnie to trochę nie jasno :) , ale i tak się przydało). Jakbyś miała problemy, to mogę ci to jeszcze raz opisać (obawiam się jednak, że nie potrafię za dobrze tłumaczyć :P ).
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: Sob 0:52, 01 Kwi 2006    Temat postu:

Cytat:

(i) jeśli n<50 to posortuj i wypisz k-ty element
(ii) podziel S na 5-elementowe podzbiory
(iii) posortuj każdy podzbiór oddzielnie
(iv) M <- zbiór środkowych elementów (median) z każdego podzbioru
(v) a <- select (M, |M|/2) (rekurencja, oblicza medianę median)
(vi) dalej jak w metodzie nr 3.


to jest fragment wykładu, nie rozumiem dlaczego w punkcie V dajemy w procedurze select że k=|M|/2... przecież chyba wtedy uniezależniamy się od tej zmiennej k? bo niezależnie jakie weźmiemy na poczatku k to |M|/2 bedzie takie samo:/ hmm..
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: Sob 0:58, 01 Kwi 2006    Temat postu:

Ja to napsiałem czystą medianą median z Cormena i przeszło bez problemu na TCS, jedyne, na co trzeba tam uważać, to to, że cyt. "Gdyby (...) został użyty element A[r] i się okazało, że jest on największym elementem w podtablicy A[p..r], PARTITION zwróci (...) wartość q = r", co skutkuje zapętleniem SELECTa.
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  Następny
Strona 2 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