Programowanie i algorytmy

KONKURS FRAKTAL

fraktal

VI edycja konkursu programistycznego

FRAKTAL

19-20 listopad 2016

czytaj więcej

Przeszukiwanie liniowe z wartownikiem

powrót

Przeszukiwanie liniowe polega na wyszukaniu pozycji, na której wystąpi pierwszy raz szukana liczba. Może zdarzyć się sytuacja, że ta liczba nie znajduje się w zbiorze.

"Wartownik", to taka wartość, którą ustawiamy na końcu zbioru. Cechuje się ona tym, że nie występuje w badanym ciągu. Jeśli na nią natrafimy to mamy pewność, że przeszukaliśmy już cały zbiór i szukana wartość nie istnieje.

W naszym przykładzie zakładamy, że zbiór składa się z liczb naturalnych. Ilość liczb jest mniejsza od {tex}1000{/tex} Jako wartownik posłuży nam liczba {tex}-1{/tex} (nie jest to liczba naturalna i nie wystąpi wcześniej).

Prześledźmy przykład:

{tex}9,\ 0,\ 8,\ 2,\ 11,\ 6,\ -1{/tex}

Załóżmy, że chcemy wyszukać liczbę {tex}2{/tex}. Jak widać znajduje się ona na pozycji {tex}4{/tex} i ta liczba powinna znaleźć się na wyjściu.

Gdy spróbujemy wyszukać liczbę {tex}7{/tex}, algorytm zatrzyma się na wartości wartownika. Na wyjściu powinien pojawić się stosowny komunikat.

Algorytm można testować na stronie z automatyczną sprawdzarką tutaj.

Rozwiązanie w C++:

 

#include<iostream>
#include<cstdlib>
using namespace std;
 
int main()
{
    int tab[1001], i = 0, szukana;
 
    //wczytanie elementów tablicy, ostatnim elementem jaki wczytamy jest wartownik = -1
    do{
        cin>>tab[i];
    }while(tab[i++]!=-1);
 
    //podanie liczby do wyszukania
    cin>>szukana;
 
    i = 0;
    //przeszukanie tablicy
    while(tab[i]!=szukana && tab[i]!=-1) ++i;
    //koniec wyszukiwania
 
    //jeśli zatrzymaliśmy się na wartowniku, to oznacza, 
   //że szukana liczba nie występuje w zbiorze    
    if(tab[i] == -1) 
       cout<<"Szukany element nie występuje w tablicy"<<endl;
    else
       cout<<"Liczba "<<szukana<<" znajduje się na pozycji "<<i+1<<endl;
 
    system("pause");
    return 0;
}
 
 

 

Złożoność algorytmu jest rzędu O(n). Żeby odnaleźć szukany element w tablicy, w pesymistycznej sytuacji musimy zbadać n elementów.