obrazek

Prezentowane materiały są przeznaczone dla uczniów szkół ponadgimnazjalnych.
Autor artykułu: mgr Jerzy Wałaszek, wersja1.0

obrazek

Wyszukiwanie

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

Program wyszukiwania liniowego

// Wyszukiwanie liniowe
// (C)2010 I LO w Tarnowie
//------------------------

#include <iostream>

using namespace std;

int main()
{
    int * T,v,n,i,j;

    // odczytujemy poszukiwaną wartość

    cin >> v;

    // odczytujemy liczbę elementów

    cin >> n;

    // tworzymy tablicę dynamiczną o n elementach

    T = new int[n];

    // wczytujemy elementy do tablicy

    for(i = 0; i < n; i++) cin >> T[i];

    // szukamy elementu o wartości v

    for(i = 0; i < n; i++)
    {
        if(T[i] == v) break;
    }

    // wyświetlamy wyniki

    cout << endl;

    for(j = 0; j < n; j++)
        if(j == i) cout << "*" << T[j] << "* ";
        else       cout << T[j] << " ";

    cout << endl << endl;

    if(i < n) cout << "Element " << v << " na pozycji " << i << endl;
    else      cout << "Elementu " << v << " nie ma w zbiorze\n";

    // usuwamy tablicę dynamiczną

    delete [] T;

    return 0;
}

Zmodyfikuj algorytm, tak aby przeszukiwanie zbioru rozpoczynał od pozycji p a nie od 0.

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

Program wyszukiwania liniowego z wartownikiem

// Wyszukiwanie liniowe z wartownikiem
// (C)2010 I LO w Tarnowie
//------------------------

#include <iostream>

using namespace std;

int main()
{
    int * T,v,n,i,j;

    // odczytujemy poszukiwaną wartość

    cin >> v;

    // odczytujemy liczbę elementów

    cin >> n;

    // tworzymy tablicę dynamiczną o n elementach

    T = new int[n+1];

    // wczytujemy elementy do tablicy

    for(i = 0; i < n; i++) cin >> T[i];

    // w tablicy umieszczamy wartownika

    T[n] = v;

    // szukamy elementu o wartości v

    for(i = 0; T[i] != v; i++);

    // wyświetlamy wyniki

    cout << endl;

    for(j = 0; j < n; j++)
        if(j == i) cout << "*" << T[j] << "* ";
        else       cout << T[j] << " ";

    cout << endl << endl;

    if(i < n) cout << "Element " << v << " na pozycji " << i << endl;
    else      cout << "Elementu " << v << " nie ma w zbiorze\n";

    // usuwamy tablicę dynamiczną

    delete [] T;

    return 0;
}

Zmodyfikuj algorytm, tak aby rozpoczynał przeszukiwanie od pozycji p a nie od 0.

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

W artykułach serwisu są używane cookies. Jeśli nie chcesz ich otrzymywać,
zablokuj je w swojej przeglądarce.
Informacje dodatkowe