Informatyka UJ forum

AMD · pijak Dołączył: 05 Mar 2006 Posty: 161 Przeczytał: 0 tematów

mam pytanie
jak zrobić w pascalu cos takiego:
mam tablice globalna a[n]
i teraz w funkcii uzywam tej tablicy i np ja sortuje
ale chce żeby ona była posortowana tylko dla tej funkcjii
czyli jezeli ja wypisze w funkcii to bedzie posortowana a jak ja wypisze w main'ie to bedzie taka jak ją wpisałem(nieposortowana)

//////////////////
czy w zadaniu F
jezeli szukam mediany to musze posortowac jakis fragment(i,j)
i w tym momencie jezeli korzystam z tablicy globalnej to automatycznie miesza sie kolejnosc i wychodzą złe odpowiedzzi
-----------niech mnie ktoś poprawi jesli sie myle

hansu

Co do zadania F... Jestem autorem podobno dosc pomocnego tutoriala do tego zadania, ktory to tutorial jest moja rozmowa na GG z exemanem... Niestety nie mam teraz dostepu do mojego "krakowskiego" kompa wiec apel do exemana (lub Reksia - bo tez korzystal ;)) - wklejcie to tutaj, przyda sie ludziom...

exeman

Udostepniam log z korepetycji jakich udzielil mi hansu. Wydzielilem Wstęp, aby zachęcić kolegów studentów do intensywnej i pracy nad tym wspanialym zadaniem ;P

I. WSTĘP

Ja (9-04-2006 21:16)

kurwa

[...]

h4nsu (9-04-2006 21:16)

fuck!

[...]

Ja (9-04-2006 21:17)

kurrwa, mam juz dosc tego jebanego asd

[...]

Ja (9-04-2006 21:17)

!@#$#@!!#

h4nsu (9-04-2006 21:17)

no kurwa jeszcze te AVLa

h4nsu (9-04-2006 21:17)

ale ins mowil ze to jest kurwa nie do napisania

h4nsu (9-04-2006 21:18)

nosz kurwa ile mozna?

h4nsu (9-04-2006 21:19)

a my kurwa stajemy na glowie

II. EPIZOD

h4nsu (9-04-2006 21:30)

otoz w takich powazniejszych algorytmach z rekurencja

h4nsu (9-04-2006 21:30)

trzeba do tego podchodzic w ten sposob

h4nsu (9-04-2006 21:30)

:

h4nsu (9-04-2006 21:30)

ze jak wewnatrz tego selecta odpalam selecta

h4nsu (9-04-2006 21:31)

to W OGOLE nie zastanawiam sie co on robi

h4nsu (9-04-2006 21:31)

zakladam ze DZIALA

Ja (9-04-2006 21:31)

:D

h4nsu (9-04-2006 21:31)

ze to jest taka czarna skrzynka ktora zwraca poprawny wynik

Ja (9-04-2006 21:31)

gorzej, jak nie dziala

h4nsu (9-04-2006 21:31)

sie czepiasz qtwa

h4nsu (9-04-2006 21:31)

:D

Ja (9-04-2006 21:31)

:D

h4nsu (9-04-2006 21:32)

no i podzielilem na piatki, posortowalem ,zrobilem extract

h4nsu (9-04-2006 21:32)

i teraz odpalam ta czrna skrzynke i ona cos zwraca

Ja (9-04-2006 21:32)

a co to jest ta czarna skrzynka

h4nsu (9-04-2006 21:32)

no to rekurencyjne odpalenie selecta

Ja (9-04-2006 21:32)

czekaj, zamotalem sie

Ja (9-04-2006 21:32)

ja mam to tak

Ja (9-04-2006 21:33)

1. wczytuje dane
2. dziele na piatki
3. sortuje piatki
4. wyszukuje jakims selectem mediane median, ktore przy okazji partitionuje

Ja (9-04-2006 21:33)

i na tym stanalem

h4nsu (9-04-2006 21:33)

no nie do konca

Ja (9-04-2006 21:33)

i ta czarna skrzynka dopiero przede mna? :D

h4nsu (9-04-2006 21:33)

co partitionujesz?

Ja (9-04-2006 21:34)

dobre pytanie

Ja (9-04-2006 21:34)

chwile

Ja (9-04-2006 21:34)

całę piątki

h4nsu (9-04-2006 21:34)

nie no ta "czarna skrzynka" to jest wlasnie ten punkt 4

h4nsu (9-04-2006 21:34)

nigdy w zyciu

Ja (9-04-2006 21:34)

traktuje piątkę jako element, o kluczu "mediana z niej"

Ja (9-04-2006 21:34)

no to juz zdazylem zjebac :D

h4nsu (9-04-2006 21:34)

nie cale piatki, nigdy

h4nsu (9-04-2006 21:34)

idziemy od drugiej strony

h4nsu (9-04-2006 21:34)

patrz:

h4nsu (9-04-2006 21:35)

robisz to normalnie jak qsort

h4nsu (9-04-2006 21:35)

wybierasz losowo pivot

h4nsu (9-04-2006 21:35)

robisz partition

h4nsu (9-04-2006 21:35)

i potem odpalasz rekurencyjnie dla jednej podtablicy

h4nsu (9-04-2006 21:35)

czy to jest na razie jasne

h4nsu (9-04-2006 21:35)

??

Ja (9-04-2006 21:35)

ale sortuje CALOSC cale dane, czy te medianki?

h4nsu (9-04-2006 21:36)

CALOSC

h4nsu (9-04-2006 21:36)

ale na razie nie mysl o medianach

h4nsu (9-04-2006 21:36)

wyobraz sobie ten algorytm w ten sposob co napisalem

Ja (9-04-2006 21:36)

to rozwali mi sie porzadek tych piatek, po co je w takim razie ukladalem po 5 ?

h4nsu (9-04-2006 21:36)

taki okrojony qsort

h4nsu (9-04-2006 21:36)

no pewnie ze sie rozwali

h4nsu (9-04-2006 21:36)

ma sie rozwalic

Ja (9-04-2006 21:36)

to po co nam byly te piatki??

h4nsu (9-04-2006 21:36)

o tym zaraz

h4nsu (9-04-2006 21:37)

na razie wrocmy do tego qsorta

Ja (9-04-2006 21:37)

aa, a te male medianki mam gdziesz trzymac w osobnej tablicy?

h4nsu (9-04-2006 21:37)

czaisz jak to ma dzialac?

Ja (9-04-2006 21:37)

hm

h4nsu (9-04-2006 21:37)

exe, przestan o tych medianach!!!

h4nsu (9-04-2006 21:37)

zaraz do tego dojdziemy :)

Ja (9-04-2006 21:37)

quicksort i ma rekurencyjnie dla jednej podtablicy - ktorej - lewej, prawej?

Ja (9-04-2006 21:37)

spoko ;]

h4nsu (9-04-2006 21:37)

no tej, w ktorej jest ten k-ty element

h4nsu (9-04-2006 21:37)

jak masz tablice 20 elementow

h4nsu (9-04-2006 21:38)

k = 15

h4nsu (9-04-2006 21:38)

i ci partirion podzieli np. 1-11, 12-20

h4nsu (9-04-2006 21:38)

to dla tej drugiej

h4nsu (9-04-2006 21:38)

a jak k byloby 10 to dla pierwszej

Ja (9-04-2006 21:38)

ok, przyjmuje na wiare, bo za cholere nie rozumiem czemu tak

Ja (9-04-2006 21:38)

czarna skrzynka, ok :P

h4nsu (9-04-2006 21:39)

czemu nie rozumiesz...

h4nsu (9-04-2006 21:39)

patrz

h4nsu (9-04-2006 21:39)

masz znalezc 15 co do wielkosci element

Ja (9-04-2006 21:39)

ok

Ja (9-04-2006 21:39)

juz cos mi swita

h4nsu (9-04-2006 21:39)

z 20 elementowej tablicy

Ja (9-04-2006 21:40)

ze np. jak mamy 1-11, 12-20, i zapuscimy rekurencje dla prawej, to po lewej bedziemy mieli nieposortowane, ale mniejsze niz w 12 elemencie, a od 12 - 20 teoretycznie posortowane

Ja (9-04-2006 21:40)

??

Ja (9-04-2006 21:40)

(tzn. nie cale prawe, bo znow sie bedzie wykluczac gdzie zapuscic rekurencje, ale tak pi * oko, to tak?)

h4nsu (9-04-2006 21:40)

no tak

Ja (9-04-2006 21:40)

ha :D

Ja (9-04-2006 21:40)

zajarzylem

Ja (9-04-2006 21:40)

;]

h4nsu (9-04-2006 21:41)

chodzi o to ze nie musisz posortowac calej tablicy jak w qsorcie tylko jedna jej czesc

Ja (9-04-2006 21:41)

nadawalbys sie na tcsowca, dobrze algosy tlumaczysz ;p

h4nsu (9-04-2006 21:41)

zdupcaj :P

Ja (9-04-2006 21:41)

:D

Ja (9-04-2006 21:41)

dobra ok, zarozumialem ten motyw z kfiksortem, co dalej

h4nsu (9-04-2006 21:41)

czyli to czaisz?

h4nsu (9-04-2006 21:41)

ok

h4nsu (9-04-2006 21:41)

i wszystko byloby pieknie w tym naszym chuj-quicksorcie

h4nsu (9-04-2006 21:41)

gdyby nie fakt

h4nsu (9-04-2006 21:42)

ze moze sie zdarzyc ze wybierzesz jako pivot skrajny element

Ja (9-04-2006 21:42)

mhm

Ja (9-04-2006 21:42)

i wtedy sie wali wszystko

h4nsu (9-04-2006 21:44)

sorki, tel mialem

Ja (9-04-2006 21:44)

ok ok :-)

h4nsu (9-04-2006 21:45)

no i teraz caly dynks polega na tym

h4nsu (9-04-2006 21:45)

zeby wybrac se dobrze ten pivot

h4nsu (9-04-2006 21:46)

tzn zeby miec pewnosc ze nie wybierzesz skrajnego

h4nsu (9-04-2006 21:46)

no i tu dochodzimy do sedna

h4nsu (9-04-2006 21:46)

czyli tej jebanej mediamy median

Ja (9-04-2006 21:46)

O

h4nsu (9-04-2006 21:47)

otoz dziala to tak

h4nsu (9-04-2006 21:47)

dzielimy na ne piatki, kazda sortujemy

h4nsu (9-04-2006 21:47)

i wybieramy mediany

Ja (9-04-2006 21:47)

dopiero teraz dzielimy na piatki?

h4nsu (9-04-2006 21:47)

nie nie nie

h4nsu (9-04-2006 21:47)

idziemy "od tylu"

Ja (9-04-2006 21:47)

aaaa :DD:D:D:D

Ja (9-04-2006 21:47)

ahaaaa :D

Ja (9-04-2006 21:47)

ok

h4nsu (9-04-2006 21:47)

tzn teraz staramy sie udoskonalic tego chuj-quicjksorta

h4nsu (9-04-2006 21:48)

cosmy o nim przed chwila gadali

Ja (9-04-2006 21:48)

tak

h4nsu (9-04-2006 21:48)

tak zeby caly algos byl liniowy

h4nsu (9-04-2006 21:48)

no

h4nsu (9-04-2006 21:48)

i wybieranie tego elementu "dobrego"

h4nsu (9-04-2006 21:49)

tj takiego ktory na pewno nie bedzie za bardzo skrajny to jest walsnie to dzielenie na piwtki itd.

h4nsu (9-04-2006 21:49)

mamy mediany piatek

h4nsu (9-04-2006 21:49)

wrzucamy je do osobnej tablicy

Ja (9-04-2006 21:49)

mhm

h4nsu (9-04-2006 21:49)

albo na poczatkek tej

h4nsu (9-04-2006 21:49)

to juz jest szczegol implementacyjny

h4nsu (9-04-2006 21:49)

i z nich wyieramy mediane

h4nsu (9-04-2006 21:50)

czyli srodkowy element

Ja (9-04-2006 21:50)

no czyli musimy te medianki posortowac?

h4nsu (9-04-2006 21:50)

i teraz mamy pewnosc ze ten element nie jest skrajny

Ja (9-04-2006 21:50)

quickiem?

h4nsu (9-04-2006 21:50)

medianek nie sortujemy

h4nsu (9-04-2006 21:50)

dla medianek odpalamy rekurencyjnie select

h4nsu (9-04-2006 21:50)

z k rownym n div 2

h4nsu (9-04-2006 21:51)

gdzie n to liczb tych medianek

Ja (9-04-2006 21:51)

mhm

h4nsu (9-04-2006 21:51)

i zakladamy ze on nam wybierze to co chcemy

Ja (9-04-2006 21:51)

ok

h4nsu (9-04-2006 21:51)

(to jest wlasnie ta czarna skrzynka - nie zastanawiamy sie co ten select z tymi mediankami robi - zakladamy ze dziala )

h4nsu (9-04-2006 21:52)

on se je tam znowu podzieli na piatki i porobi inne brzydkie rzecy

h4nsu (9-04-2006 21:52)

ale my to mamy w dupie

Ja (9-04-2006 21:52)

ale tego selecta skad wziac

h4nsu (9-04-2006 21:52)

wazne ze nam zwroci ta mediane median

Ja (9-04-2006 21:52)

z cormena? :P

h4nsu (9-04-2006 21:52)

no wlasnie go piszesz

h4nsu (9-04-2006 21:52)

rekurencyjnie

Ja (9-04-2006 21:52)

czyli to cale o czym mowimy to jeden wielki select?

Ja (9-04-2006 21:53)

ok

h4nsu (9-04-2006 21:53)

dokladnie

Ja (9-04-2006 21:53)

to tego nikt nie napisal nigdzie

h4nsu (9-04-2006 21:53)

i teraz ten element x ktory zwroci ten select

h4nsu (9-04-2006 21:53)

to jest walsnie mediana median

h4nsu (9-04-2006 21:53)

i co nam to daje

h4nsu (9-04-2006 21:53)

otoz:

h4nsu (9-04-2006 21:53)

wiemy ze polowa medianek jest d niego wieksza

h4nsu (9-04-2006 21:53)

i polowa mniejsza

h4nsu (9-04-2006 21:54)

(w przyblizeniu)

h4nsu (9-04-2006 21:54)

dodatkowo

Ja (9-04-2006 21:54)

mhm

h4nsu (9-04-2006 21:54)

od kazdej wiekszej od x medianki sa jeszcze 2 elementy od niej wieksze

h4nsu (9-04-2006 21:54)

w tablicy

h4nsu (9-04-2006 21:54)

(no bo ona jest mediana jakies piatki)

h4nsu (9-04-2006 21:54)

czaisz

Ja (9-04-2006 21:54)

no ale nie wiemy w jakiej one sa relacji z mediana median

h4nsu (9-04-2006 21:54)

to jest ten taki rysunek

h4nsu (9-04-2006 21:55)

wiemy ze sa wieksze

Ja (9-04-2006 21:55)

mhm

Ja (9-04-2006 21:55)

no tak

h4nsu (9-04-2006 21:55)

skoro mediany polowy piatek sa wieksze

h4nsu (9-04-2006 21:55)

to w kazdej w tych piatek 3 elementy sa wieksze od tego x

h4nsu (9-04-2006 21:55)

mediana i dwa wieksze od mediany

h4nsu (9-04-2006 21:55)

jasne?

Ja (9-04-2006 21:55)

tak

Ja (9-04-2006 21:55)

calkiem calkiem :-)

h4nsu (9-04-2006 21:56)

czyli jest co najmniej n/2 * 3/5 wiekszych

h4nsu (9-04-2006 21:56)

czyli 3/10 n

Ja (9-04-2006 21:56)

mhm

h4nsu (9-04-2006 21:56)

i tyle samo jest mniejszych

h4nsu (9-04-2006 21:56)

na pewno!!!!

Ja (9-04-2006 21:56)

ano ;]

h4nsu (9-04-2006 21:56)

zostaje jeszcze 0,4 n o ktorych nie wiemy

h4nsu (9-04-2006 21:56)

ale to jest hooy

h4nsu (9-04-2006 21:56)

nie potrzeba nam wiecej

h4nsu (9-04-2006 21:57)

bo wiemy ze wybralismy element odlegly o co najmniej 0.3n od "krancow'

h4nsu (9-04-2006 21:57)

wiec on bedzie dobrym pivotem

Ja (9-04-2006 21:57)

zgadzam sie

h4nsu (9-04-2006 21:57)

i w momencie jak mamy tego x

h4nsu (9-04-2006 21:57)

to juz nas nie obchodzi caly podzial na piatki

h4nsu (9-04-2006 21:58)

podzial nam byl potrzebny zeby x znalezc

h4nsu (9-04-2006 21:58)

jak mamy to se podzial mozemy popsuc

h4nsu (9-04-2006 21:58)

i wlasnie to robimy

h4nsu (9-04-2006 21:58)

odpalajac partition dla calej tablicy

h4nsu (9-04-2006 21:58)

(tzn dla tego fragmentu w ktorym jestesmy)

h4nsu (9-04-2006 21:59)

exe, zyjesz? ;)

Ja (9-04-2006 21:59)

ledwo ledwo, troche sie boje :P

Ja (9-04-2006 22:00)

wydaje mi sie, ze malo dzis pospie :D

Ja (9-04-2006 22:00)

ale w miare rozumiem

h4nsu (9-04-2006 22:00)

jakies pytania?

Ja (9-04-2006 22:00)

no i to jest juz wszystko? :D

h4nsu (9-04-2006 22:00)

no jak zrobisz partition

h4nsu (9-04-2006 22:01)

to wywolujesz rekurencyjnie

Ja (9-04-2006 22:01)

hm

h4nsu (9-04-2006 22:01)

selecta

Ja (9-04-2006 22:01)

a w tej prezentacji co podawales linka na forum jest potem jakis bajer ze jesli n>k to costam costam i takie tam

h4nsu (9-04-2006 22:02)

tak jak w tym pseudo qsorcie

Ja (9-04-2006 22:02)

If k=r, then return m
If k<r, then return k th smallest of the set L
If k>r, then return k-r th smallest of the set R.

Ja (9-04-2006 22:02)

a ok ok :D

Ja (9-04-2006 22:02)

nie bylo pytania

h4nsu (9-04-2006 22:02)

:D:D

Ja (9-04-2006 22:02)

dzieki wielkie za wytlumaczenie

Ja (9-04-2006 22:02)

juz sens rozumiem

Ja (9-04-2006 22:02)

ale implementacja to bedzie kosmos!

Ja (9-04-2006 22:02)

:D

h4nsu (9-04-2006 22:02)

nie jest tak zle

h4nsu (9-04-2006 22:03)

najgorsze sa te pietki

Ja (9-04-2006 22:03)

zapodam sobie elektronika supersonika i do rana bede jechal

Ja (9-04-2006 22:03)

dlaczego najgorsze?

h4nsu (9-04-2006 22:03)

zeby to chujozum przerzucic

h4nsu (9-04-2006 22:03)

bo tam jest w pizdu ifow

h4nsu (9-04-2006 22:03)

bo ostatnia piatka

h4nsu (9-04-2006 22:03)

moze miec 1,2,3,4,5 elementow

h4nsu (9-04-2006 22:03)

i to trzeba wyifowac

Ja (9-04-2006 22:04)

to jakby dopelnic calosc zerami dla wielokrotnosci 5, a potem od wyniku odpowiednio odjąć ?

Ja (9-04-2006 22:04)

to czy to by nie ulatwialo?

h4nsu (9-04-2006 22:04)

to by poslulo

Ja (9-04-2006 22:04)

dlaczego

Ja (9-04-2006 22:04)

a racja

Ja (9-04-2006 22:04)

bo za kazdym razem by trza dopelniac

h4nsu (9-04-2006 22:05)

nom

Ja (9-04-2006 22:05)

chociaz

Ja (9-04-2006 22:05)

ale to by chyba wiecej roboty bylo :P

h4nsu (9-04-2006 22:05)

dokladnie

Ja (9-04-2006 22:05)

oka, dzieki hansu wielkie

h4nsu (9-04-2006 22:05)

spoko

Ja (9-04-2006 22:05)

masz u mnie wino :P

h4nsu (9-04-2006 22:05)

dobram wracam do pizdy algebry

Ja (9-04-2006 22:05)

powodzenia

h4nsu (9-04-2006 22:06)

kurwa jebane macierze :P

Ja (9-04-2006 22:06)

a ja wracam do paszczaka

Ja (9-04-2006 22:06)

macierze, nie denerwuj mnie ;]

Ja (9-04-2006 22:06)

3m sie, have fun with algebra :D

h4nsu (9-04-2006 22:06)

zdupcaj

h4nsu (9-04-2006 22:07)

nara

h4nsu (9-04-2006 22:07)

3m sie

Skrobocik

Ale Wy jesteście słodcy ;)