Informatyka UJ forum

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

Mam problem.Chodzi o zadanie F.Testuje to zadanie na gronostaju i na athinie i daje rd8(na gronostaju na kilku testach daje rd8)
sciagnałem sobie te pliki F.in z gronostaja gdzie dostawałem rd8
U mnie o dziwo działaja normalnie.
czy mógłby mi ktos powiedzieć co to jest to rd8 i jak to naprawić

jagm

a kompilasz z opcjami kompilacji? zreszta wyslij na athine, moze akurat przejdzie ;]

Yoter

mi ostatnio pascal bez problemu skompilowal cos w stylu cos.innycos mimo ze cos byl wskaznikiem do rekordu.....

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

na athinie nie przeszło (tez rd8)

Spectro

Może rekurencja jest za głęboka? Na Athine są niekiedy dość restrykcyjne limity pamięciowe. Radzę przejść na wersję iteracyjną, akurat w medianie median jest to dość proste (rekurencja ogonowa) ;) .

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

wersja iteracyjna?
a gdzie mozna cos takiego podpatrzyc jak wyglada bo w ksiazkach i wykładach chyba tylko rekurencyjne były

Kwiatek

A jesli mam ANS na Gronostaju w zadaniu F, a jak zapuszczę test u siebie, to mam wszystkie wyniki prawidłowo?

Gorfin

Testerka mateo rozwiazuje wiele problemow...

Spectro

@AMD:
Rzuć okiem na ostatni wykład dr Ślusarka z ASD1. Tam jest przedstawiona metoda usuwania rekurencji. Ogonowa jest na samym poczatku, jako szczególny przypadek.

@Kwiatek:
Jakiś gronostajowy błąd ;) .

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

czy komus udało sie ostatnio przephnąc zadanie F bo ja już 3 rozwiazania które podobno na athinie przeszły dałem na gronostaja i wszedzie były błedy i to sporo
----------------------
wysłałem algorytm hoar'e na athine (przepisany czysto z ksiazki)
i dało ans cos tu jest chyba nie tak

Kwiatek

Zwracam honor Gronostajowi, integer mi się gdzieś zaplątał zamiast longinta :P

Yoter

ja ostatnio przepchnąłem F....

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

Mam prosbe do wszystkich którzy zrobili F.
wiem że powinienem dojs do tego sam ale już straciłem kilka dni przez to zadanie.
Czy mógł by mi ktoś powiedziec co robie żle w moim programie.
psuje sie napewno główna funkcja select
//to jej kod
//i-poczatek przedzialu j-koniec k-szukana
//sortowanie działa dobrze
function select(i,j,k:longint):longint;
var m,n,t,i1,lx,pivot:longint;
Begin
n:=j-i+1;t:=0;
if n<10 then begin
for i1:=i to j do begin
t:=t+1;a[first_med+t]:=a[i1];end;
sortuj(first_med+1,t,1);
end{if n<?}
else
begin
{golwna czesc programu}
sortuj(1,5,n div 5);
if(n mod 5 <> 0) then sortuj(5*(n div 5)+1,n-(5*(n div 5)),1);
if(n-(5*(n div 5))<3) then lx:=n div 5
else lx:=n div 5 +1;
for m:=0 to lx-1 do a[first_med+1+m]:=a[m*5+3];{tworzenie tablicy median na koncu danej tablicy}
pivot:=select(first_med+1,first_med+lx,(n+7) div 10);
m:=partition(i,j,pivot);
piv:=pivot;
if k<=m-i then begin ;select:=select(i,m-1,k); end
else
begin
select:=select(m,j,k-(m-i)); end

end;
end;
//###############################
a to kod partition
function partition(i,j,pivot:longint):longint;
var l,r:longint;
Begin
l:=i;r:=j;p:=0;
repeat
swap(l,r);
while a[l]<pivot do begin
l:=l+1;end;
while a[r]>=pivot do begin
if(a[r]=pivot)then p:=p+1;r:=r-1;end;
until l>r;
partition:=l;
End;
procedure wyzeruj;
var i:longint;
Begin
for i:=first_med+1 to max_tab do
a[i]:=0;
End;
//////////////////////////////////////////
wczesniej uwzgledniałem powtórzenia tak jak z wykładu dr slusarka ale było jescze wiecej błedów wiec chciałem zrobic sprawnie działajacą chociaż tą funkcje

Yoter

no nie wiem.... czy Twoje partition dzieli tablice na 3 cześci? bo z tego co widze chyba nie.... i od czego jest to p? uzywasz tego gdzieś? w każdym bądź razie ja bym zmienił partition na hansową wariację Lomuto (topic do zadania G) i potem uruchamiał selecta tylko dla odpowiednich przedziałów.....

Skrobocik