OI....

[bRave 0]

...sprawdzić wszystkie klocki już zrzucone to by było jakieś 4*N! porównań...

 

Rojmarek:

 

A jednak się pomyliłem, nie wiem skąd mi się ta N! wzięła jak to powinna być suma ciągu arytmetycznego czyli w najgorszym wypadku złożoność by była rzędu 4*((N/2)*N) czyli 2*N^2 (co by się zgadzało z Twoimi obliczeniami..więc chyba zgadłem

 

Dodatkowo można wprowadzić parę optymalizacji które przyspieszą ten algorytm w pewnych sytuacjach.

[januzi 24]

kosztem zuzycia pamieci mozna np. do 1/4 zmniejszyc liczbe porownan (ale to tak na wielkie oko), w najgorszym wypadku liczba porownan pozostanie taka sama

[bRave 0]

kosztem zuzycia pamieci mozna np. do 1/4 zmniejszyc liczbe porownan (ale to tak na wielkie oko), w najgorszym wypadku liczba porownan pozostanie taka sama

 

Można też użyć listy uporządkowanej i to na dwa różne sposoby, jedna polepsza złożoność w najgorszym przypadku, druga lepiej się sprawdzi w przeciętnych sytuacjach.

 

Można też w pewnych sytuacjach zmniejszyć ilość klocków z jakimi porównujemy.

 

A co Ty masz na myśli to szczerze powiedziawszy nie wiem Jakie dane tam można buforować?

[mr262560 0]

Można też użyć listy uporządkowanej i to na dwa różne sposoby, jedna polepsza złożoność w najgorszym przypadku, druga lepiej się sprawdzi w przeciętnych sytuacjach.

 

Można też w pewnych sytuacjach zmniejszyć ilość klocków z jakimi porównujemy.

 

A co Ty masz na myśli to szczerze powiedziawszy nie wiem Jakie dane tam można buforować?

jak już zgadnąłeś to: mam listę dwukierunkową, posortowaną wg wysokości klocka, idzie po liście od największego w w dół, jak znajdzie klocek z którym sie pokrywa to w_nowego+=w_znalezione; potem idę po liście w górę i szukam miejsca gdzie wstawić nowego.

zmiejszenie ilości klocków wiąże się z tym, ze za każdym razem musisz przejść całą tablicę i wykonać jeszcze 2 porównania, wiec marne chyba przyspieszenie, jak dadzą hamski test...

[jareqq 0]

hmmm a moze ktos powiedziec mi dlaczego nie dziala test na stronie SIO? podaje kod zrodlowy kra.pas (poprawnie dzialajacy program), w plik wyjsciowy podaje kra.exe i wyskakuje mi w tescie error 106 bład wykonania...

[mr262560 0]

hmmm a moze ktos powiedziec mi dlaczego nie dziala test na stronie SIO? podaje kod zrodlowy kra.pas (poprawnie dzialajacy program), w plik wyjsciowy podaje kra.exe i wyskakuje mi w tescie error 106 bład wykonania...

bo tam jest napisane "plik wEjściowy" i tam wrzucasz Twoj zestaw danych dla ktorych chciałbys sprawdzic Twoje rozwiązanie - Twoj program...

[mr262560 0]

zmienili limity czasowe na TET ;] 40 sekund w najgorszym wypadku ;]

[januzi 24]

a ile wczesniej bylo ?

 

klocki w tetrisie mozna podzielic na 5 grup (wieksza liczba chyba bedzie jedynie przerostem mozliwosci i niewiele da), jesli nowy klocek leci w lewy gorny cwiartek, to po co porownywac go z klockami z prawego dolnego cwiartka ?

[mr262560 0]

a ile wczesniej bylo ?

 

klocki w tetrisie mozna podzielic na 5 grup (wieksza liczba chyba bedzie jedynie przerostem mozliwosci i niewiele da), jesli nowy klocek leci w lewy gorny cwiartek, to po co porownywac go z klockami z prawego dolnego cwiartka ?

było 10s. Złożność pesymistyczna dalej ta sama, a nawet wieksza... chociaz średnia na pewno lepsza

[_Misiek_ 0]

a ile wczesniej bylo ?

 

klocki w tetrisie mozna podzielic na 5 grup (wieksza liczba chyba bedzie jedynie przerostem mozliwosci i niewiele da), jesli nowy klocek leci w lewy gorny cwiartek, to po co porownywac go z klockami z prawego dolnego cwiartka ?

 

hmmm... ale jezeli klocek spada centralnie w lewy gorny rog ale jest tak duzy ze zaczepi o jakis z prawej dolnej cwiartki to juz nie wychwycisz tego?

 

Mam jeszcze pytanko takie... Ucze sie pascala moze od tygodnia wiec wybaczcie moja niewiedze... Co jest wydajniejsze? Przeszukac tablice dwuwymiarowa w poszukiwaniu najwyzszej wartosci petlami czy funkcja rekurencyjna? Nie wiem jak tego tetrisa uproscic.... narazie mam wszystko na petlach porobione i na duzych testach w ogole dupa zbita.

[januzi 24]

wychwyce, bo klocki beda podzielone na 5 grup: cwiartki + mieszane, jesli bedzie lecial klocek cwiartkowy, to sprawdzam z odpowiednia cwiartka oraz mieszanym, jesli bedzie lecial mieszany, to albo z kazda lista (albo okreslic na jakie cwiartki sie ten klocek rozklada)

 

petle: costam[a] zamieniane jest na odpowiednie miejsce w pamieci zapisane jako [c] (pamiec jest liniowa), jesli masz for for if to masz bardzo fajny spowalniacz

 

rekurencja: na stos wrzucany jest adres powrotu i wykonywana jest znowu funkcja, to wrzucenie na stos i zdjecie ze stosu troche zajmuje (jakby mi sie chcialo zajrzec do ksiazki, to bym podal mniej wiecej ile cykli w czystym asemblerze), no i nalezy pamietac o ograniczeniu na wielkosc stosu (o ile pamietam, to w pascalu {$M} sluzylo do ustawienia wielkosci stosu)

 

najlepsze rozwiazanie: napisac obydwie metody i sprawdzic w praktyce ktora bedzie szybsza

[m_frankie 0]

Ciągle mam problemy z zadaniem KRA, przecież ono jest banalne a moje rozwiązania mają beznadziejne czasy. Czytałem cały ten temat i też nic mi się nie rozjaśniło. Proszę o wyrozumiałość i kolejne hinty.

[mr262560 0]

Ciągle mam problemy z zadaniem KRA, przecież ono jest banalne a moje rozwiązania mają beznadziejne czasy. Czytałem cały ten temat i też nic mi się nie rozjaśniło. Proszę o wyrozumiałość i kolejne hinty.

w sumie to juz to co napisaliśmy jest wbrew regulaminowi OI...

[januzi 24]

1. zauwaz, ze rure mozna zapisac inaczej niz zbior roznych srednic

2. licz polozenie klockow od miejsca w ktorym zatrzymaly sie poprzednie

 

edit: raczej chodzilo o kod, bo wymyslec jak ma cos dzialac, to kazdy potrafi, ale z wykonaniem jest roznie (jak np. taki Windows, wymyslony jest jako system operacyjny spelniajacy szereg wymagan, a w praktyce roznie z tym jest, glownie dzieki IE )

[kostek13_88 0]

januzi, mistrzu... w życiu chyba nie pojmę o co Ci chodziło... prawie zrobiłem już tetrisa...z taaaaaaaaaakim if'em i nie wróże dobrego czasu... jedynym moim problemem jest to że gdzieś sie wkradł błąd... i narazie nie chce mi się nad tym myśleć

[_Misiek_ 0]

Tez nie do konca czaje o co Ci chodzilo, ale "to dlatego Ty jestes szefem a nie odwrotnie... "

 

W zadaniu z krazkami moim zdaniem warto zwrocic uwage na to ze jezeli pierwszy walczyk na gorze ma srednice 5 to wszystkie wieksze srednice nizej nie powinny nas interesowac. czyli klocek w rurce 5cm, 6cm, 4cm, 3cm, 6cm, 2cm i 3cm. Powinien byc sprawdzany przy 5cm, 4cm, 3cm,2cm. To narazie luzny pomysl, bo dopiero teraz odkladam tetrisa na bok i biore sie za inne zadania.

[bRave 0]

najlepsze rozwiazanie: napisac obydwie metody i sprawdzic w praktyce ktora bedzie szybsza

 

Zwykle zakłada się, że interacja jest lepszym rozwiązaniem niż rekurencja (zwykle też komplikuje algorytm

[januzi 24]

dlatego niech napisze obydwa sposoby bedzie mial trening i na wlasne oczy sie przekona co i jak

 

apropo rekurencji, to czasami jest latwiejsza w uzyciu, bo przy iteracji trzeba by okreslic zakres, a przy rekurencji wystarczy podac punkt poczatkowy i dalej leci samo

[_Misiek_ 0]

dlatego niech napisze obydwa sposoby bedzie mial trening i na wlasne oczy sie przekona co i jak

 

apropo rekurencji, to czasami jest latwiejsza w uzyciu, bo przy iteracji trzeba by okreslic zakres, a przy rekurencji wystarczy podac punkt poczatkowy i dalej leci samo

 

Wyczułem tą zachętę do treningu. Probowalem ta rekurencje napisac, ale nie dalem rady. Odstawilem na bok tetrisa i sie wzialem za krazki. W sumie juz zrobilem, lecz nie moze podolac na najbardziej wrednym tescie.

 

BTW. Trenuje non-stop.

[januzi 24]

pamietaj, ze im mniej porownan w petli tym lepiej

nic tak nie zabija programu jak if then else w srodku petli

[_Misiek_ 0]

pamietaj, ze im mniej porownan w petli tym lepiej

nic tak nie zabija programu jak if then else w srodku petli

 

Ok. Dzieki za cenna rade. Rzeczywiscie troszke mam tych porownan w petlach. Bede musial sie tego w jakis sposob pozbyc.

 

W standardowych testach dla krazkow mam podobne czasy co Kostek i Rojmarek. Tylko z jednym testem sobie nie moge poradzic. http://btk.net.pl/~bikol1/bicom/test_max3.zip Mozecie zobaczyc jak Wam smiga? Moze moj komp nie daje rady (tylko 400mhz). Albo sa zle dane wejsciowe. Jezeli u Was dobrze by chodzilo tzn ze musze cos z kodem pokombinowac. A na SiO tego nie idzie wyslac... za duzo zajmuje po spakowaniu.

[mr262560 0]

Ok. Dzieki za cenna rade. Rzeczywiscie troszke mam tych porownan w petlach. Bede musial sie tego w jakis sposob pozbyc.

 

W standardowych testach dla krazkow mam podobne czasy co Kostek i Rojmarek. Tylko z jednym testem sobie nie moge poradzic. http://btk.net.pl/~bikol1/bicom/test_max3.zip Mozecie zobaczyc jak Wam smiga? Moze moj komp nie daje rady (tylko 400mhz). Albo sa zle dane wejsciowe. Jezeli u Was dobrze by chodzilo tzn ze musze cos z kodem pokombinowac. A na SiO tego nie idzie wyslac... za duzo zajmuje po spakowaniu.

mi wyrzucił odpowiedź 11 po jakiejś pół sekundy... (procesor 800MHz)

[_Misiek_ 0]

ech... siedze nad tymi krazkami od wczoraj.... Najprostrzy algorytm do ktorego doszedlem polega na porownaniu kazdego klocka kolejno z segmentami rury od gory... :? Od czego wyjsc zeby zrobic linowy algorytm?

[koko_bongo 0]

Hej, a jak zrobić żabki? Robić tablicę Wx na Wy?

[mr262560 0]

ech... siedze nad tymi krazkami od wczoraj.... Najprostrzy algorytm do ktorego doszedlem polega na porownaniu kazdego klocka kolejno z segmentami rury od gory... :? Od czego wyjsc zeby zrobic linowy algorytm?

od tego ze informatyka to zboczona nauka i wszystko chciałaby robić "od tyłu"