Informatyka UJ forum

ostoj

o wielki robsonie z avatarem oinopiona, Bog ci zaplaci, w dzieciach wynagrodzi, moze nawet na stosie nie spali :)

Robson

Mam taka nadzieję... ale z dzieciami moze być trudno... w koncu przez pączkowanie to trudno sie rozmnazac.... uppsss... chyba sie z offtopicu przeslizgują teksty... sorry ;)

urban

DObra moje rozwiazanie bylo takie:

Hasza licze tak:
1 . Najpierw zamieniam duza litere na mala
2. dopelniam do 10 znakow znakiem #96
3. odejmuje od kazdego znaku 96, i teraz mam liczby z zakresu od 0 do 26 czyli caly alfabet z pustym znakiem
4. sumuje to w taki spoob

suma := 0; pow := 7;

for i := 1 to 10
suma := suma + ord( slowo[ i ] ) * pow;
pow := pow * 7;

w sumie mam wartosc hash'a

czyli licze to w takim jakby systemie7 ale mocno porytym.

a nastepnie to mod wielkosc tablicy.

Jak wiemy wielkosc tablicy przy modzie musi byc pierwsze i dalekie od poteg 2 dlatego wzialem 175003 jest pierwsza i lezy miedzy 131072 i 262144 prawie pomiedzy. Pozatym mieszcza sie wszyscy pilakrze i daje zapas miejsca.

To jest tablica wskaznikow do rekordu pilkarza.
Jeden pilkarz to:
jego nazwisko o dlugosci 10 znakow - 11 bajtow
jego gole tablica byte'ow - 101 bajtow
jego nastepnik longint - 4 byty

adresowanie urbana( losowo- kolejkowe )

dodawanie

objasnienie zmiennych
pos pozycja aktualnego elementu
prev pozycja wczesniejszego elemtn, musimy sobie ja zachowac

1. pos := h( klucz ) mod PRIME // prime wielkosc tablicy

2. jezeli pod pos w tablicy jest nil to stworz nowy elemnt !!!wyzeruj!!!( wazne za to bombka wpadla ) tablice goli i wpisz jego bramki. wskaznik do nastepnego ustaw na -1

3. jezeli zajete to sprawdzamy po kolei kazdy element.

jezeli natrafimy na nasz element to zmieniamy tylko troche tablice jego goli

jezeli nie natrafimy to szukamy mu miejsca
pos := random( PRIME );
while Table <> nil pos := ( pos + 1 ) mod PRime;

jak znajdziemy to ustwiamy mu nastepny na -1 a elementowi o numerze prev ( czyli pop rzednikowi ) nastepny na wartosc pos.

W taki sposob tworzy nam sie 'lista' wszystkich elementow o tym samym hashu:

Head : element o pozycji rownej h( key ) mod PRime
Kolejne elemnty do ktorych trafiamy po nastepnikach
Tail element ktory jako nastepnik ma -1

Zalety:
Nie tworza sie skupiska bo uzywamy randoma, rownomierne zapelnienie tablicy
Przy podpowiednio duzej tablicy wskaznikow prawie nie wystepuja kolizje przy randomie, dlatego moja tablicy jest o 3/4 wieksza niz powinna, ale to i tak tylko wskazniki:

jeden wskazni 4 bajty
jeden rekord 116 bajtow

Czyli sie oplaca.

Wady:

najgorsza zlozonosc przy elementach o takim samym hashu to O( n ) ale kto wymysli wszystkie elementy o tym samym hashu.
narzut na tworzenie i disposowanie obiektow

pobieranie wartosci

przechodzimy przez 'liste' elementow o tym samym hashu szukajac naszego

zalety

szybkosc

wady

zlozonosc pesymistyczna

Mam nadzieje za ten blyskotliwy co by nie bylo sposob realizacji hashowania dostane magistra, bo co by nie bylo sam go wymyslilem. I mam nadzieje ze dosyc ladnie wyjasnile, jezeli nie to przepraszam pozna godzina i sklonnosc do skrotow myslowych.

ps. Pamietajcie! uzywac randomize!!!! sprawdzac czy nie korzystacie z nila!!! inicjalizowac zerami tablice goli!!! za to wszystko dostalem bombek pare, ale nie zauje pomysl naprawde dobry.

ps2. wiem smieszne.

urban

ups spozniony

Spectro

NARESZCIE!!!!!! :)

Jakąś godzinę temu udało mi się przepchnąć to nieszczęsne U.

Po pierwsze, nie doczytałem treści zadania i myślałem, że 100000 piłkarzy jest w każdym zestawie, a nie pliku, co szczerze mówiąc mi jednak w ogóle nie przeszkodziło, a kodowałem nazwiska z rokiem, nie same nazwiska :P . Aha, mój rozmiar tablicy (liczba pierwsza) wyniósł ponad 1300000 :P .

Po drugie, popełniłem 2 głupie błędy. Pierwszy wyniknął z różnicy priorytetów operatorów mnożenia i przesunięcia bitowego w lewo w C++ (mnożenie ma pierwszeństwo) i Pascalu (tutaj pierwszeństwo ma shl). Drugi to niedoszacowanie maksymalnego możliwego wyniku hashowania - ale tutaj wystarczyło modularnie zmiejszyć wynik.

Po trzecie, zrobiłem sobie generator i komparator (neologizm?) plików na użyek zadania. Generator produkuje plik z testem i plik z odpowiedziami (w oparciu o prosty algorytm, który na pamięci nie oszczędza ;) ). Komparator porównuje znak po znaku plik wyjściowy generatora i podany mu plik z odpowiedziami do danego testu zadania U. Na virgo (czyli pod linuksem) oba programy działały prawidłowo, nie wiem jak będą się zachowywały na Windowsie (szczególnie komparator), ale chyba nie powinno być z nimi większego problemu.

[link widoczny dla zalogowanych]
[link widoczny dla zalogowanych]

smh · [świeżak] Dołączył: 05 Mar 2006 Posty: 21 Przeczytał: 0 tematów

Czy program przechodzi przy założeniu, ze liczba punktów zdobytych przez jednego gracza w całej jego karierze nie przekracza 255 ?
Ponieważ z treści wynika, ze w sumie jeden gracz może zdobyć nawet 1000000 punktów.

Spectro

urban

Ja dla jednego gracza mam tablice od 1906 do 2006 byte'ow. i sie zmiescilo.

Spectro

W takim razie zrobiłem istotnie trudniejsze zadanie :P .

kap00ch

slabe testy dali ;p

Roxel

AVL przechodzi :D
Wystarczy do zadania K dorobic wczytywanie danych (no i pare innych szczegolow) 8)
Szkoda tylko tych 10 gwiazdek nabitych funkcja haszujaca :?

Robson

:shock:
Cóż... zadanie na hashu pisze sie 15 minut po 1 piwie (jejku ale to zabrzmiało :P )... ale jak ktoś lubi AVL... to fajne ;)

Roxel

Wiedzialem ze o czyms zapomnialem, nastepnym razem skocze po piwo :wink:

kap00ch

e co ty robson...15 minut sugerowaloby ze to jakies wybitnie trudne zadanie....2 pifka i 10 minut max;]

Robson

Ejjj no wiesz ja taki master jak Ty nie jestem... ;) musisz mi dac troche fory...

PS. Co to jest Kap00chHelpLine?

kap00ch

@Robson - kap00ch HelpLine - ta pseudo strzaleczka w dol wskazuje moje gg :P wiec jak ktos ma problem to mnie na tym gg meczy ;p a to co jest w sigu to ilosc cudzych problemow ktore dotad rozwiazalem...tak wiesz jak mi sie nudzi to akurat mam na gg x nowych wiadomosci ;p <w tym dostaje prowizje od producenta gg za kazda rozmowe ale ci...>

r4ku

poszlo, 41 gwiazdeczek, malo braklo a pobilbym rekord :D, z tym ze przepisalem na haszowanie otwarte i poszlo za pierwszym razem bez problemu. Rozwiazanie z lancuchowym zwraca identyczne wyniki i zajmuje prawie tyle samo pamieci, lecz athina go nie chciala...

Skrobocik

U mnie też w końcu przeszło, ale pięć bombek złapałem :evil:

Moje błędy zaczynały się od złego sprawdzania czy rekord jest zajęty:

chlebek

Po ciezkim boju udalo sie to z pozoru latwe zadanie przpchnac, gdyby nie to cholerne wczytywanie to juz dawno bylby z tym spokoj, ehh, no coz tak bywa
15145 U Mon, 5 Jun 2006 06:08:28 CEST OK
tylko po co mi to, jak i tak pewnie nie bede mial zaliczenia :(

ostoj

jak to co ci po tym, satysfakcja z kolejnej nieprzespanej nocy :)