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 

Zadanie J - Ławka
Idź do strony Poprzedni  1, 2, 3  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ść
hansu
Nieomylny Admin



Dołączył: 17 Lis 2005
Posty: 1990
Przeczytał: 0 tematów

Skąd: przychodzimy? Czym jestesmy? Dokad zmierzamy?

PostWysłany: Czw 21:11, 02 Lis 2006    Temat postu:

Polecam nie przeklejac quicksorta z zadania G z asd1 tylko z zadania J (tego o punktach). Otoz okazuje sie ze moj quicksort z G jako ze sluzyl do sortowania pojedynczych liczb a nie rekordow zaniedbywal sytuacje dublujacych sie kluczy (no bo dla pojedynczych liczb to nierozroznialne). Co ciekawe blad ujawnial sie tylko w losowych przypadkach (dlatego ze uzywalem randomizowanego qsorta). Co najciekawsze, IDENTYCZNY blad zrobilem w zeszlym roku przeklejajac tego durnego qsorta do w/w zadania J o punktach... ==* A mowia ze czlowiek uczy sie na bledach... :/
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
smas
Okrutny Admin



Dołączył: 20 Paź 2005
Posty: 1634
Przeczytał: 0 tematów


PostWysłany: Pią 0:31, 03 Lis 2006    Temat postu:

Ja odradzam stosowanie podwójnego indexowania tab[tab2[i]]. To jest koszmarnie wolne. Miałem sortowanie tablicy index[]. Zamiast exch() po 3 tablicach => TLE x2
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 19:31, 04 Lis 2006    Temat postu:

Thx Makros za binarke ;].

Generator testów w cpp, może się komuś przyda:

Kod:
#include <cstdio>
#include <cstdlib>
#include <fstream>

const int maxZest= 100;
const int maxBand= 100;
const int maxCzas= 100;
const int maxFot= 100;

int main() {
   std::srand( std::time( 0 ) );
   int zestawow= std::rand() % maxZest + 1;
   printf( "%d\n", zestawow );
   int bandytow;
   int lewy;
   for( int aktZest= 0; aktZest < zestawow; ++aktZest ) {
      bandytow= std::rand() % maxBand + 1;
      printf( "%d\n", bandytow );
      for( int aktBand= 0; aktBand < bandytow; ++aktBand ) {
         lewy= std::rand() % ( maxCzas - 1 );
         printf( "%d %d %d\n", lewy, std::rand() % ( maxCzas - lewy ) + lewy + 1, std::rand() % maxFot + 1 );
         }
      }
   }
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: Sob 22:07, 04 Lis 2006    Temat postu:

Fidel napisał:
polecam srand wywolywac tylko raz :P

Przechodzi tez bez losowego wybierania elementu dzielacego.
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 22:17, 04 Lis 2006    Temat postu:

Przechodzi też w ogóle bez elementu dzielącego. Jeśli ktoś poza mną nie ufa quicksortowi...
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: Sob 23:45, 04 Lis 2006    Temat postu:

ogolnie: testy nie sa perwersyjne.
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
kg86
zielony żul



Dołączył: 22 Gru 2005
Posty: 1194
Przeczytał: 0 tematów

Skąd: pochodze?

PostWysłany: Nie 0:12, 05 Lis 2006    Temat postu:

ja przekleilem quicksorta z G, posortowalem wszystkie klucze wobec tego jednego i wszystko bylo ok :) srand() wywolywalem tylko raz ;)
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
kafex
zielony żul



Dołączył: 28 Mar 2006
Posty: 1458
Przeczytał: 0 tematów

Skąd: Zawiercie

PostWysłany: Nie 1:25, 05 Lis 2006    Temat postu:

a ja wogóle...dawałem rand()%n + 1 :P
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
smh
[świeżak]



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


PostWysłany: Pon 20:04, 06 Lis 2006    Temat postu:

Czy byłby ktoś na tyle uprzejmy i udostępnił mi zarys algorytmu do tego ćwiczenia? Byłbym wdzięczny za pomoc:-)
:prayer:
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Yoter
zielony żul



Dołączył: 19 Lis 2005
Posty: 1033
Przeczytał: 0 tematów

Skąd: Gościeradów

PostWysłany: Pon 20:54, 06 Lis 2006    Temat postu:

1. Sortujemy wszystkich biorąc za klucz czas odejścia.
2. Robimy pierwszemu tyle zdjęc, ile mamy mu zrobić ( number[i] ) w chwili w której odchodzi z ławki.
3. Bierzemy następnego w kolejności sortu i obliczamy, ile jeszcze mamy mu zrobić zdjęć (być może zrobiliśmy mu już jakieś zdjęcia gdy robiliśmy je poprzednikowi) i robimy mu tyle własnie zdjęć w chwili jego odejścia z ławki.
4. Powtarzaj punkt 3. aż otrzymasz wynik.

Chyba nigdzie się nie pomyliłem, ale jeśli tak, to mnie poprawcie...
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: Pon 21:03, 06 Lis 2006    Temat postu:

Sam wymyśliłem inny algorytm ale zapodam ten, bo bardziej mi się spodobał :D

Będzie potrzebna struktura Zdarzenie w której pamiętamy 3 rzeczy: czas zdarzenia, jakiego agenta ono dotyczy oraz czy jest to przyjście czy opuszczenie ławeczki.

Oprócz tego mamy zmienną N określającą ilość agentów i zmienną Act określającą ile wykonaliśmy zdjęć od początku do danego momentu (na końcu będzie rządany to wynik). Będą też potrzebne 2 tablice: tablica Zdarzeń o liczności 2*N (nazwę ją Events) oraz tablica intów rozmiaru N w której pamiętamy ile zdjęć było zrobionych zanim dany agent pojawił się na ławeczce (nazwę ją PicBef).

Tablicę PicBef inicjujemy na 0, Act też na 0. Dla każdego zczytanego agenta wrzucamy do tablicy Events 2 zdarzenia - opisujące jego przyjście i opuszczenie ławeczki. Tablicę Events sortujemy rosnąco po czasach Zdarzenia. Jeśli czasy 2 Zdarzeń są równe to Zdarzenia określające przyjście agenta mają być w posortowanej tablicy przed tymi określającymi opuszczenie ławeczki. W przypadku równych czasów i typów Zdarzeń kolejność w tablicy nie ma znaczenia.

I teraz iterujemy po wszystkich zdarzeniach od 1 do 2*N. Jeśli dane zdarzenie opisuje przyjście agenta o numerze 'k' na ławeczkę to w tablicy PicBef na pozycji 'k' zapisujemy aktualną wartość zmiennej Act. Jeśli zaś zdarzenie opisuje opuszczenie ławeczki przez tego agenta to liczymy ile wykonaliśmy zdjęć gdy był on na ławeczce (od zmiennej Act odejmujemy wartość z PicBef[k]) i sprawdzamy czy to wystarcza. Jeśli nie to zmienną Act zwiększamy o tyle ile zdjęć wykonaliśmy za mało.

Po przejściu po całej tablicy Events w zmiennej Act mamy szukany wynik. :wink:
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
h
pijak



Dołączył: 15 Lis 2005
Posty: 134
Przeczytał: 0 tematów


PostWysłany: Śro 16:56, 08 Lis 2006    Temat postu:

ten twój tester wrzuca spacje po kazdym wyniku i chwile mi zajelo zanim sie polapalem czemu diff mi wszystko wyrzuca.
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: 1603
Przeczytał: 0 tematów

Skąd: znienacka

PostWysłany: Śro 20:56, 08 Lis 2006    Temat postu:

Ma ktos jakis generator lub testy? Na wszystkich przykladowych i wymyslonych mam OK, natomiast Athina mowi ANS. :/
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Yoter
zielony żul



Dołączył: 19 Lis 2005
Posty: 1033
Przeczytał: 0 tematów

Skąd: Gościeradów

PostWysłany: Śro 21:08, 08 Lis 2006    Temat postu:

7
1 3 2
6 7 4
6 7 5
6 7 7
6 7 20
7 7 8
8 9 15

nie wiem spróbuj czegoś takiego...
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: 1603
Przeczytał: 0 tematów

Skąd: znienacka

PostWysłany: Śro 21:36, 08 Lis 2006    Temat postu:

Dzieki Yoter, faktycznie, wykrzacza mi sie :)
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: 1603
Przeczytał: 0 tematów

Skąd: znienacka

PostWysłany: Śro 22:56, 08 Lis 2006    Temat postu:

Jakie macie zlozonosci pesymistyczne?
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: Śro 23:16, 08 Lis 2006    Temat postu:

@exeman:
Nie wiem i nie chcę wiedzieć ;) . Hmmm... myślę, że spokojnie za górne ograniczenie (pewnie z lekkim nadmiarem :P ) w moim algorytmie mogę przyjąć O(n*max{number[i]-number[j]}).
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:27, 08 Lis 2006    Temat postu:

O(n log n)
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: 1603
Przeczytał: 0 tematów

Skąd: znienacka

PostWysłany: Śro 23:30, 08 Lis 2006    Temat postu:

hansu, robiles na kopcu?
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: Śro 23:46, 08 Lis 2006    Temat postu:

nlogn ma qsort + binsearch, albo 2xqsort.
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: 1603
Przeczytał: 0 tematów

Skąd: znienacka

PostWysłany: Śro 23:55, 08 Lis 2006    Temat postu:

jakim cudem quicksort ma pesymistycznie nlogn?
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
nathaniel
pijak



Dołączył: 25 Paź 2005
Posty: 229
Przeczytał: 0 tematów

Skąd: Bielsko-Biała

PostWysłany: Czw 0:06, 09 Lis 2006    Temat postu:

Sam quicksort oczywiscie nie ma zlozonosci pesymistycznej nlogn - przeciez dobrze to wiesz!
Tylko testy nie sa 'perwersyjne' jak to okreslil oinopion :)
Powiedz jak sortujesz to moze ci cos podpowiemy. Ja zlapalem pare bombek na 'usprawnianiu' quicksorta bo wywolywalem rekurencyjnie tylko dla ciagow wiekszych niz 10 a potem wstawianie. Jak zmienilem na pelna rekurencje do samego konca to przeszlo...
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: 1603
Przeczytał: 0 tematów

Skąd: znienacka

PostWysłany: Czw 0:09, 09 Lis 2006    Temat postu:

No to dlatego sie was pytam o pesymistyczna a nie srednia :P
Ja walcze nad pesymistyczna nlogn. Moze do jutra zdaze, dluga noc...
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
kg86
zielony żul



Dołączył: 22 Gru 2005
Posty: 1194
Przeczytał: 0 tematów

Skąd: pochodze?

PostWysłany: Czw 0:13, 09 Lis 2006    Temat postu:

ja mam O(n^2) i poszlo :)
a robilem tak:
- sortuje wszystkie 3 klucze po koncach quicksortem z randomizacja :)
- petla po wszystkich elementach - kazdemu robie tyle zdjec ile mu brakuje, i jesli brakowalo > 0, to w drugiej petli - od nastepnego do ostatniego (o ile sa w odpowiednim przedziale) odejmuje ta ilosc zrobionych zdjec...

@exeman - pesymistycznie ma n^2, ale przeciez bardzo trudno o pesymistyczny przypadek :)
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: Czw 0:27, 09 Lis 2006    Temat postu:

No ok, masz racje, ja robilem heapsortem.
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  Następny
Strona 2 z 3

 
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