Klasa III - Wyszukiwanie informacji

Wyszukiwanie informacji należy do podstawowych problemów algorytmicznych, z którymi spotkamy się często w programowaniu. A oto kilka przykładów, gdzie wyszukiwanie jest niezbędne:

Bankowość - wyszukiwanie dłużników, którzy nie spłacają kredytów. Również wyszukiwanie wzorowych klientów. Wyszukanie klienta o podanym numerze konta lub znalezienie numeru konta na podstawie danych osobowych klienta.

Sport - na podstawie osiągniętych wyników wyznaczenie trzech kolejnych zwycięzców na pierwsze, drugie i trzecie miejsce.

Hotelarstwo - wyszukiwanie wolnych pokoi w danym terminie oraz pokoi zarezerwowanych.

Fizyka - wyszukanie w danych pomiarowych wartości spełniających określone wymagania.

Chemia - wyszukiwanie związków chemicznych na podstawie ich własności.

Kryminalistyka - wyszukiwanie osób o podanych cechach (np. wzrost, waga, rozmiar obuwia, odciski palców, kolor włosów, itp.).

Samochody - wyszukiwanie właściciela pojazdu na podstawie numeru rejestracyjnego lub określonych cech samochodu (marka, kolor, rok produkcji, numer silnika lub nadwozia, itp.).

Gry komputerowe - wyszukiwanie odpowiedniej strategii, która zapewni zwycięstwo dla komputera.

Algorytm wyszukujący

W informatyce algorytm wyszukujący (ang. searching algorithm) otrzymuje na wejściu pewien problem i daje na wyjściu jego rozwiązanie po przetestowaniu pewnej ilości możliwych wariantów. Większość algorytmów rozwiązujących problemy (np. algorytmy gry w szachy, warcaby, karty itp.) to pewnego rodzaju wyspecjalizowane algorytmy wyszukujące. Zbiór wszystkich możliwych rozwiązań danego problemu nosi nazwę przestrzeni poszukiwań (ang. search space). Najprostszymi algorytmami wyszukującymi są algorytmy naiwne, które stosują najbardziej intuicyjną metodę wyszukiwania w przestrzeni poszukiwań. Wymyślono jednakże bardziej zaawansowane metody, wykorzystujące wiedzę na temat samej struktury przestrzeni poszukiwań, co owocuje zmniejszeniem ilości czasu potrzebnego na przetworzenie danych.

Wyszukiwanie liniowe

Wyszukiwanie liniowe (ang. linear search) polega na przeglądnięciu zbioru element po elemencie i znalezieniu w nim pozycji elementu, który spełnia pewien pożądany warunek (np. jest równy pewnej wartości). Jeśli element nie zostanie znaleziony, to algorytm zwraca pozycję, która w zbiorze nie może wystąpić, np. -1 lub n.

Dane wejściowe:

n - liczba elementów
T[] - tablica n elementowa zawierająca elementy do posortowania. Elementy są numerowane od 0 do n-1.
v - poszukiwana w zbiorze wartość

Dane wyjściowe:

i - pozycja elementu o wartości v. Jeśli element nie został znaleziony, to i przyjmuje wartość n.

Lista kroków:

Krok 1: i ← 0
Krok 2: Jeśli i ≥ n, to zakończ
Krok 3: Jeśli T[i] = v, to zakończ
Krok 4: i ← i + 1
Krok 5: Idź do kroku 2

Przykładowe dane dla programu:

Pierwsza liczba v określa poszukiwaną wartość. Druga liczba n określa ilość elementów w zbiorze. Następne n liczb definiuje n kolejnych elementów. Liczby zbioru są całkowite.
37
20
8 25 38 82 70 63 91 102 37 52
61 18 15 12 14 26 37 41 69 134

Wyszukiwanie liniowe z wartownikiem

Zastanówmy się, czy opisanego powyżej algorytmu nie można uprościć. W każdym obiegu pętli wykonywane są dwa testy w krokach 2 i 3:

Krok 2: Jeśli i ≥ n, to zakończ
Krok 3: Jeśli T[i] = v, to zakończ

Test w kroku 3 jest konieczny dla algorytmu, ponieważ wykrywa on poszukiwany element. Natomiast test w kroku 2 spełniony jest tylko wtedy, gdy algorytm przeszedł przez wszystkie elementy zbioru i nie znalazł w nim poszukiwanej wartości. Czyli praktycznie działa na samym końcu algorytmu, lecz jest wykonywany w każdym obiegu pętli. Jeśli element jest znajdowany w zbiorze w kroku 3, to test z kroku 2 staje się zbędny. Aby zatem pozbyć się tego testu, musimy zapewnić, że poszukiwany element znajduje się w przeszukiwanym zbiorze. Wymóg ten można bardzo prosto spełnić, dopisując na końcu zbioru element o poszukiwanych własnościach. Element ten znajdzie się na pozycji n. Jeśli więc algorytm go znajdzie, to zwróci wartość n, co zinterpretujemy jako brak poszukiwanego elementu w zbiorze. Jeśli znaleziona pozycja jest mniejsza od n, to wskazuje na rzeczywisty element zbioru. Dodany element nazywamy strażnikiem lub wartownikiem (ang. guard lub sentinel) - pilnuje on, aby algorytm nie wyszedł poza elementy zbioru. Ten sposób wyszukiwania nazywamy wyszukiwaniem liniowym z wartownikiem (ang. sentinel linear search). Działa on około dwukrotnie szybciej od zwykłego wyszukiwania liniowego.

Dane wejściowe:

n - liczba elementów
T[] - tablica n+1 elementowa zawierająca elementy do posortowania. Elementy są numerowane od 0 do n-1.
v - poszukiwana w zbiorze wartość

Dane wyjściowe:

i - pozycja elementu o wartości v. Jeśli element nie został znaleziony, to i przyjmuje wartość n.

Lista kroków:

Krok 1: T[n] ← v ; wstawiamy wartownika do zbioru
Krok 2: i ← 0
Krok 3: Jeśli T[i] = v, to zakończ
Krok 4: i ← i + 1
Krok 5: Idź do kroku 3

Przykładowe dane dla programu:

Pierwsza liczba v określa poszukiwaną wartość. Druga liczba n określa ilość elementów w zbiorze. Następne n liczb definiuje n kolejnych elementów. Liczby zbioru są całkowite.
69
40
38 25 38 82 70 63 91 70 37 52
61 18 15 12 14 26 37 41 69 12
71 33 92 72 21 82 79 63 28 14
68 28 65 81 34 76 39 81 31 19

Zadania

Dany jest zbiór:

500
463 926 603 901 826 879 376 264 189 472 582 447 664 547 702
453 401 398 930 907 177 256 105 429 63 995 437 638 190 16
16 320 40 141 523 284 138 405 17 318 257 543 651 378 278
9 27 805 962 204 390 387 382 210 32 64 128 100 150 200
4 12 32 530 35 125 450 41 316 301 15 246 849 844 165
27 959 14 21 8 876 539 948 662 5 13 32 254 577 888
452 715 691 81 725 359 361 381 263 793 144 412 137 119 476
496 189 467 149 377 714 273 443 490 81 976 255 180 71 703
620 161 978 849 678 964 935 188 602 63 659 111 182 245 712
31 9 8 603 178 832 743 916 341 87 65 646 707 830 612
63 877 495 149 290 2 698 166 227 400 476 941 786 129 71
919 820 502 828 481 943 815 70 415 413 484 1 329 250 78
915 466 401 641 802 543 331 766 934 487 786 868 951 768 886
231 762 74 269 508 985 134 24 18 60 531 756 470 464 488
926 25 502 261 339 115 67 962 399 68 882 863 996 791 924
742 13 370 448 183 531 147 41 546 768 318 120 522 466 628
756 968 58 358 592 421 638 978 980 988 444 85 118 831 48
858 754 281 344 210 703 84 885 844 685 148 389 927 84 956
103 310 782 175 614 523 496 897 562 399 924 896 539 328 995
685 336 548 961 15 175 982 120 300 100 583 228 588 672 950
68 232 659 587 909 967 218 608 838 779 343 873 980 478 572
950 944 395 754 598 994 26 689 399 342 3 4 5 982 730
985 780 160 816 933 628 433 414 845 600 336 18 716 849 619
669 855 278 173 687 471 304 460 377 424 10 7 20 130 721
883 654 47 145 224 771 927 320 579 38 361 773 661 662 155
335 9 159 283 49 971 963 318 913 431 811 266 374 861 284
232 672 564 888 932 484 973 226 143 344 962 110 444 532 646
16 3 29 14 83 874 871 401 381 473 538 908 58 760 20
969 120 160 40 584 176 598 110 358 443 822 403 198 46 199
643 614 574 5 8 13 4 8 3 143 703 7 242 50 61
34 487 526 290 818 219 968 710 894 510 180 447 708 226 296
782 314 932 211 169 67 824 127 90 508 138 350 824 799 882
713 212 335 223 990 735 502 743 363 434 484 509 782 166 512
565 654 934 364 397

Pierwsza liczba określa ilość elementów w zbiorze. Za nią następują kolejne elementy.

Napisz program, który wyliczy średnią arytmetyczną wszystkich liczb, a następnie poda ile jest liczb większych od tej średniej i ile jest liczb mniejszych od tej średniej.
Napisz program, który wypisze wszystkie trójki kolejnych liczb, które są podzielne przez 6.
Napisz program, który znajdzie trójkę kolejnych liczb dających najmniejszą sumę.