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ść
jagm
zielony żul



Dołączył: 01 Lut 2006
Posty: 1421
Przeczytał: 0 tematów


PostWysłany: Sob 1:00, 01 Kwi 2006    Temat postu:

trywialna napisał:
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..

Tutaj szukamy tej mediany median. A select odpalamy tylko dla tego fragmentu tablicy, w któyrym znajdują się wcześniej znalezione mediany piątek.
Gdy już otrzymamy element a, wówczas to on jest elementem, na podstawie którego dzielimy w algorytmie Hoare'a
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: Sob 1:03, 01 Kwi 2006    Temat postu:

Źle to zrozumiałaś. Za 'a' podstawiasz wynik działania funkcji Select dla tablicy M. Wtedy 'a' jest znalezioną medianą tablicy M zawierającej mediany zbioru S, czyli a jest medianą median wejściowego zbioru S.

Później to a podstawiasz do algorytmu Hoara opisanego w wykładzie punkt wyżej. W zasadzie to kroki 2-5, czyli to całe liczenie mediany median, jest tylko po to, żeby zapewnić liniowy czas działania Hoara nawet w pesymistcznym przypadku.
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: Sob 1:12, 01 Kwi 2006    Temat postu:

Madras napisał:
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.


Niech to... ! Szkoda, że nie czytałem uważniej :/ , miałbym to już dawno z głowy... !
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Spectro
Mistrz grilla



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

Skąd: Kurdwanów

PostWysłany: Sob 16:10, 01 Kwi 2006    Temat postu:

Heh, też miałem TLE. Wprowadziłem jednak pewne poprawki:
- zrandomizowałem wczytywanie danych,
- dla przedziałów <=1000 wstrzelam się piwotem w środek, dla większych bawię się w medianę median,
- dodałem uses Buffering (wreszcie się przydał :P ).

Athina program o dziwo zaakceptowała O_o .
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: Pon 21:54, 03 Kwi 2006    Temat postu:

Takie pytanie. W algorytmie Hoare zapuszczamy rekurencje wiec czy starczy nam pamięci? Jak ciągle generujemy nowe tablice S1 S2 S3 no to nie wydaje mi sie:/
Powrót do góry
Zobacz profil autora
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: Pon 22:12, 03 Kwi 2006    Temat postu:

Ale tablicę przekazujesz przez vara i tylko podajesz l,r jako zakres, na którym operujesz.
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: Pon 22:17, 03 Kwi 2006    Temat postu:

No tak.. :roll: ja już nie moge z tym zadaniem:/
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 23:41, 03 Kwi 2006    Temat postu:

@Trywialna - po dokonaniu podziału na trzy części nie musimy robić wywołania rekurencyjnego, bo interesuje nas tylko jedna z części - lew lub prawa. W takim razie rekurencje można zastąpić pętlą.

Natomiast jeżeli chodzi o tablice median piątek, to można tworzyć nowe tablice bez problemu. Każda nowa tablica jest okolo 5 razy mniejsza od poprzedniej, więc w sumie zużyjemy nie więcej niż 5/4 rozmiaru tablicy wejściowej.
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: Pon 23:45, 03 Kwi 2006    Temat postu:

No ale jak to zrobic w pascalu? Tu rozmiar tablicy musi byc znany w chwili kompilacji wiec za kazdym razem w rekurencji musimy powolywac do zycia tablice o rozmiarze n/5. Tak mi sie przynajmniej wydaje :)
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: Wto 0:04, 04 Kwi 2006    Temat postu:

hmm no ale po co w ogole generowac/tworzyc jakiekolwiek nowe tablice? przeciez wszystko moznaladnie iszybko zrobic in-place, wystarczy mediany przerzucac na sam poczatek tablicy i wywoywac rekurencje zawsze dla tego kawalka :] szybko , latwo iprzyjemnie
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Spectro
Mistrz grilla



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

Skąd: Kurdwanów

PostWysłany: Wto 0:17, 04 Kwi 2006    Temat postu:

kap00ch napisał:
przeciez wszystko moznaladnie iszybko zrobic in-place, wystarczy mediany przerzucac na sam poczatek tablicy i wywoywac rekurencje zawsze dla tego kawalka :] szybko , latwo iprzyjemnie

Ja takie właśnie rozwiązanie zastosowałem, tyle że mam wersję iteracyjną. Tak czy siak, to jest bardzo łatwe do zakodowania, na pewno prostsze niż kombinowanie z przeskokami i sortowaniem piątkami tablicy wejściowej w miejscu.
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: Wto 0:26, 04 Kwi 2006    Temat postu:

no ba! iteracyjna podstawa sukcesu :]
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 1:20, 04 Kwi 2006    Temat postu:

Nie no, da się przecież zrobić tablicę dynamiczną. Może niepotrzebne kombinowanie, ale da się. Mnie tak było łatwiej niż przerzucać na początek tablicy.
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Skrobocik
[SKROBORANGA]



Dołączył: 29 Lis 2005
Posty: 2958
Przeczytał: 0 tematów

Skąd: Skarżysko , Kraków

PostWysłany: Czw 1:09, 06 Kwi 2006    Temat postu:

No dobra, tylko powiedzcie mi, jak się inicjuje tablice dynamiczne we Free Pascalu, bo to chyba nie chodzi o "new" :?: Nie mam pojęcia :cry:
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
oinopion
żul



Dołączył: 28 Lis 2005
Posty: 858
Przeczytał: 0 tematów

Skąd: Kraków

PostWysłany: Czw 2:04, 06 Kwi 2006    Temat postu:

Kod:
Var 
  A : TByteArray; 
 
begin 
  SetLength(A,1000);


[link widoczny dla zalogowanych]
referencja przyjacielem programisty

Swoją drogą, ciekawe czemu to nie jest obiekt? B nie ma przeladowania operator[]? Dziwne rzeczy...
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 2:18, 06 Kwi 2006    Temat postu:

Bo Pascal na szczescie nie jest Java i tutaj tak proste typy jak tablica bajtow nie jest obiektem. W Javie Integer jako obiekt to juz jest szczyt szczytow, przerost formy nad trescia.

Java powinna byc zakazana w srodowisku akademickim, o tak!
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 2:22, 06 Kwi 2006    Temat postu:

Popieram!!! TAK!!! Swiete slowa!!! Brawo Exeman!!!! Java won!!!! Jest beznadziejna, wolna, mulasta nieintuicyjna, obiektowa na sile i w ogole do dupy. :)

Btw. dzisiaj z jagmem na so wymyslilismy joke: dlaczego java zostala stworzona prze zespol programistow? Bo jeden nie bylby w stanie sam takich glupot nawymyslac :P
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Spectro
Mistrz grilla



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

Skąd: Kurdwanów

PostWysłany: Czw 20:54, 06 Kwi 2006    Temat postu:

Jak pazabo zobaczy wasze teksty o javie, to pewnie aż się wysili coś napisać na forum :twisted: .
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
chlebek
alkoholik



Dołączył: 04 Lut 2006
Posty: 556
Przeczytał: 0 tematów

Skąd: Siedlce\Kraków

PostWysłany: Pią 1:12, 07 Kwi 2006    Temat postu:

Czy ktos z robiacych to zadanie z Cormena tez mial problem z TLE i jakos sobie poradzil ? Moze caly problem tkwi w Partiotion Hoare'a ?
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Skrobocik
[SKROBORANGA]



Dołączył: 29 Lis 2005
Posty: 2958
Przeczytał: 0 tematów

Skąd: Skarżysko , Kraków

PostWysłany: Pią 1:44, 07 Kwi 2006    Temat postu:

Przeszło mi właśnie. W końcu nie bawiłem się w dynamiczną tablicę, tylko zrobiłem typ Sequence(ciąg), który składa się z 6mln, a nie 5mln elementów i po prostu medianki wrzucałem na koniec, czyli od miejsca 5000001 :D
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
chlebek
alkoholik



Dołączył: 04 Lut 2006
Posty: 556
Przeczytał: 0 tematów

Skąd: Siedlce\Kraków

PostWysłany: Pią 1:55, 07 Kwi 2006    Temat postu:

tez tak mialem i dalej TLE, cos musi byc nie tak skoro na 3 ostatnich testach na gronostaju ma TLE, a reszta wszystko OK, rowniez na Virgo same OK.
Tylko nie wiem czemu jak zmienilem z 2 tablicy { 5 mln i 1mln } na jedna tablice 6 mln to czasy sa gorsze na gronostaju { dla 3 ostatnich wciaz TLE }
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ą 2:09, 07 Kwi 2006    Temat postu:

@chlebek: jesli uzywasz partition hoare'a i nie masz go uodpornionego w zaden sposob na ciagi stale lub prawie stale, to nic dziwnego ze dostajesz TLE. Ja tak robilem quicksorta na poczatku (tzn. lomuto, ale na 2 a nie na 3) i dla maksymalnego ciagu stalego mieszal nim i mieszal podan 20 (!!!) sekund. Podejrzewam ze tu jest podobnie. Dlatego goraco polecam przepisanie tego na lomuto na 3, tan algorytm jest naprawde prosty (IMHO duzo prostszy od hoare'a) a i juz tutaj na forum byl kilkakrotnie opisywany. I powinno byc git :)
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
chlebek
alkoholik



Dołączył: 04 Lut 2006
Posty: 556
Przeczytał: 0 tematów

Skąd: Siedlce\Kraków

PostWysłany: Pią 12:26, 07 Kwi 2006    Temat postu:

Dzieki, w wolnej chwili pomiedzy ASD i ASD sprobuje poprawic to :lol:
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: Nie 17:45, 09 Kwi 2006    Temat postu:

Może niektórzy z was pisali to zadanie bardzo krótko i ich zdaniem jest to zadanie proste, ale powiem wam że żadne zadanie mnie tak nie wykończylo psychicznie jak ta mediana:/ już nawet magiczną siódemke pisało mi sie lepiej. błąd na błędzie, poprostu zwiariować można:[. Na szczęście koniec tego koszmaru..

I bardzo dziekuje Mateuszowi za testerke na virgo, bez niej bym sobie napewno nie poradziła:)
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: Nie 17:51, 09 Kwi 2006    Temat postu:

No trudno mi sie z Toba nie zgodzic... Chociaz moze tyle czasu co A to mi to zadanie nie zajelo.... Ale jak sobie przypomne analizowanie 1.5 megowych "logow" z dzialania mojego programu - po kazdym najmniejszym kroku wypisywalem cala tablice i wszystkie zmienne... A zeby jeszcze wylapac bledy to tesy musialy byc dosc duze bo jakis taki upierdliwy blad mialem... W kazdym razie cos kilkaset elementow te moje tablice mialy... No HORROR to byl po prostu... Ale nauczylem sie na tym zadaniu baaaardzo duzo o debugowaniu - moze nie tyle nauczylem ile nabralem wprawy... Natomiast juz drze na mysl o debugowaniu K :/
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 3 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