ALG6

Rozdział 7. Algorytmy przeszukiwania

^r > dzielenie modulo R_mM: H(v) = v% R_max

Przykład:

^Dla ^, = 37 H(,,KOT")=(01011 01110 10100), % (37) ,₀ = (11732),₀=3.

Zalety:

• funkcja H łatwa do obliczenia.

Wady:

• otrzymana wartość zależy dość paradoksalnie - bardziej od R_mas niż od klucza!

Przykładowo gdy R_max jest parzyste, na pewno wszystkie otrzymane indeksy danych o kluczach parzystych będą również parzyste, ponadto dla pewnych dzielników wiele danych otrzyma ten sam indeks... Można temu częściowo zaradzić poprzez wybór R_imx jako liczby pierwszej, ale tu znowu będziemy mieli do czynienia z akumulacją elementów w pewnym obszarze tablicy - a wcześniej wyraźnie zażyczyliśmy sobie, aby funkcja H rozdzielała indeksy „sprawiedliwie'" po całej tablicy!

• w przypadku dużych liczb binarnych nie mieszczących się w reprezentacji wewnętrznej komputera, obliczenie modulo już nie jest możliwe przez zwykłe dzielenie arytmetyczne.

Co się tyczy ostatniej wady, to prostym rozwiązaniem dla ciągów tekstowych w C++ („wewnętrznie” są to przecież zwykłe ciągi bajtów!) jest następująca funkcja, bazująca na interpretacji tekstu jako szeregu cyfr ^-bitowych:

int H(char *s, int Rmax)

(

for (int lmp=0; *s!=NULL; s++)

Łmp=(64*tmp+(*s))% Rmax; return tmp;

)

Powyższą formułę należy odczytywać następująco: klucz v jest mnożony przez pewną liczbę 6 z przedziału otwartego (OJ). Z wyniku bierzemy część ułam kową. mnożymy przez E_mm i ze wszystkiego liczymy część całkowitą.

Wyszukiwarka

Podobne podstrony:
ALG 0 200 Rozdział 7. Algorytmy przeszukiwania Rekordy E i F zostały zapamiętane w momencie stwierdz
ALG 2 202 Rozdział 7. Algorytmy przeszukiwani! gdzie a jest współczynnikiem zapełnienia tablicy T. A
ALG 4 204 Rozdział 7. Algorytmy przeszukiwania i (gdzie a jest, tak jak poprzednio, współczynnikiem
ALG0 190 Rozdział 7. Algorytmy przeszukiwania Odnalezienie liczby .1 w tablicy tub jest sygnalizowa
ALG2 192 Rozdział 7. Algorytmy przeszukiwani; gdy maksymalna ilość elementów należących do pewnej d
ALG4 194 Rozdział 7. Algorytmy przeszukiwania •    powinna być tatwo obliczalna, tak
ALG8 198 Rozdział 7. Algorytmy przeszukiwania pod indeks ///, stwierdzimy, że już wcześniej ktoś si
ALG9 Rozdział 7Algorytmy przeszukiwania Pojęcie „przeszukiwania” pojawiało się w tej książce już ki
ALG&8 268 Rozdziału. Algorytmy numeryczne11.1.Poszukiwanie miejsc zerowych funkcji Jednym z częstych
ALG 0 270____Rozdziału. Algorytmy numeryczne F(x, y)=0. (funkcję w klasycznej postaci y=f(x) można ł
ALG 2 272 Rozdziału. Algorytmy numei 272 Rozdziału. Algorytmy numei (czyli F(z)) //zwraca wartość fu
ALG 4 274 Rozdział11. Algorytmy numeryczne (1,    7.00), // tablicy: wpisane sa dwie
ALG 6 276__Rozdziału. Algorytmy numeryczne double simpson_f(double i *f) (double),//wskaźnik do f(x)
ALG 8 278 Rozdziału, Algorytmy numeryczne Mając macierz w takiej postaci, można już pokusić się o wy
ALG6 56 Rozdział 3. Analiza sprawności algorytmów jest intuicyjnie bardzo proste, dalej będziemy uż
ALG6 66 Rozdział 3. Analiza sprawności algorytmów return pos; else    //element zost
ALG6 76 Rozdział 3. Analiza sprawności algorytmów Analogicznie dla 2 otrzymamy: Vn > 1, A(n,2) =
ALG6 86 Rozdział 4. Algorytmy sortowania zamiany sąsiadujących ze sobą elementów, a druga będzie wy

więcej podobnych podstron