W algorytmie przedstawionym w poprzednim rozdziale znajduje się pętla wyszukująca. W pętli sprawdzane są dwa warunki. Pierwszy z nich (zaznaczony czarną linią na sąsiednim rysunku) jest potrzebny tylko wtedy, gdy zbiór d[ ] nie zawiera poszukiwanego elementu o wartości x. W takim przypadku wymieniony warunek gwarantuje zakończenie pętli przeszukującej po przeglądnięciu wszystkich elementów zbioru. Indeks p przyjmuje wartość n + 1.
Warunek jest sprawdzany dla każdego elementu zbioru. Jeśli moglibyśmy zagwarantować, iż poszukiwany element zawsze zostanie znaleziony, to wtedy warunek ten stałby się zbędny.
Możemy doprowadzić do takiej sytuacji dodając na końcu zbioru poszukiwany element. Wtedy pętla przeszukująca zakończy się albo na elemencie x leżącym wewnątrz zbioru, albo na elemencie x, który został dodany do zbioru. W pierwszym przypadku zmienna p będzie wskazywała pozycję znalezionego elementu i pozycja ta będzie mniejsza lub równa n, a w drugim przypadku (gdy element x w zbiorze nie występuje) zmienna p wskaże pozycję dodanego przez nas elementu, czyli n + 1. Ponieważ pętla ta zawsze zakończy się, to możemy pominąć pierwszy warunek pozostawiając jedynie test na różność od x. Uproszczenie da w wyniku wzrost prędkości wyszukiwania.
Dodany przez nas element na końcu zbioru nosi nazwę wartownika (ang. guard lub sentinel), a stąd pochodzi nazwa algorytmu - przeszukiwanie z wartownikiem. Klasa złożoności obliczeniowej wynosi O(n).
Dane wejściowe
n - liczba elementów w zbiorze wejściowym, i N
d[ ] - zbiór wejściowy, w którym dokonujemy poszukiwań. Indeksy elementów rozpoczynają się od 1. Zbiór musi posiadać miejsce na dodatkowy element, który zostanie dopisany na końcu. x - wartość poszukiwana Dane wyjściowe
p - pozycja elementu x w zbiorze d[ ]. Jeśli p = 0, to element x w zbiorze nie występuje. p
krok 1: d[n + 1] x
krok 2: p krok 3: Dopóki x d[p]: wykonuj p
krok 4: Jeśli p > n, to p krok 5: Zakończ algorytm
Na samym początku algorytmu dopisujemy do zbioru wartownika. Przeszukiwanie rozpoczynamy od pierwszego elementu, dlatego p przyjmuje wartość 1.
Pętla przeszukująca porównuje kolejne elementy zbioru z wartością poszukiwaną. Jeśli są różne, to przesuwa się do następnej pozycji. Wartownik gwarantuje nam, iż przeszukiwanie zawsze się zakończy.
Gdy pętla przeszukująca zostanie zakończona, zmienna p przechowuje pozycję elementu zbioru równego x. Jeśli p wskazuje wartownika, to zbiór nie zawiera poszukiwanego elementu - w takim przypadku zerujemy pozycję p, aby zgłosić porażkę. Kończymy algorytm.
Poniższe, przykładowe programy są praktyczną realizacją omawianego w tym rozdziale algorytmu. Zapewne można je napisać bardziej efektywnie. To już twoje zadanie. Dokładny opis stosowanych środowisk programowania znajdziesz we wstępie. Programy przed opublikowaniem w serwisie edukacyjnym zostały dokładnie przetestowane. Jeśli jednak znajdziesz jakąś usterkę (co zawsze może się zdarzyć), to prześlij o niej informację do autora. Pozwoli to ulepszyć nasze artykuły. Będziemy Ci za to wdzięczni.
Program tworzy zbiór 100 liczb pseudolosowych z zakresu od 0 do 99. Następnie generuje wartość pseudolosową z zakresu od 0 do 99 i szuka jej w zbiorze. Jeśli znajdzie, zaznacza element zbioru i podaje jego pozycję. Jeśli nie znajdzie, wypisuje odpowiedni komunikat.
| Efekt uruchomienia programu |
|---|
Przeszukiwanie z wartownikiem |
// Przeszukiwanie z wartownikiem
//-------------------------------------------
// (C)2006 mgr Jerzy Wałaszek I LO w Tarnowie
//-------------------------------------------
program sentinelsearch;
{$APPTYPE CONSOLE}
const
N = 100; // liczba elementów w zbiorze
M = 99; // maksymalna wartość elementów
// Deklaracja zmiennych
var
d : array[1..N + 1] of cardinal;
i,p,x : cardinal;
begin
writeln('Przeszukiwanie z wartownikiem');
writeln('-----------------------------');
writeln(' (C)2006 mgr Jerzy Walaszek ');
writeln(' I LO w Tarnowie ');
writeln;
// Generujemy zbiór danych, w którym będzie wykonywane poszukiwanie
randomize;
for i := 1 to N do d[i] := random(M + 1);
// Generujemy poszukiwaną wartość
x := random(M + 1);
// Wstawiamy wartownika do zbioru d[ ]
d[N + 1] := x;
// Szukamy x w d[ ]
p := 1;
while x <> d[p] do inc(p);
if p > N then p := 0;
// Prezentujemy wyniki
for i := 1 to N do
if i = p then write('>',d[i]:2,'<') else write(d[i]:3,' ');
writeln;
write('x = ',x);
if p > 0 then
writeln(' wystepuje na pozycji nr ',p)
else
writeln(' nie wystepuje w zbiorze.');
writeln;
// Gotowe
write('KONIEC. Nacisnij klawisz Enter...'); readln;
end.
// Przeszukiwanie z wartownikiem
//-------------------------------------------
// (C)2006 mgr Jerzy Wałaszek I LO w Tarnowie
//-------------------------------------------
#include <iostream>
#include <iomanip>
using namespace std;
int main(void)
{
const int N = 100; // liczba elementów w zbiorze
const int M = 99; // maksymalna wartość elementów
// Deklaracja zmiennych
unsigned d[N + 2],i,p,x;
cout << "Przeszukiwanie z wartownikiem\n"
"-----------------------------\n"
" (C)2006 mgr Jerzy Walaszek \n"
" I LO w Tarnowie \n\n";
// Generujemy zbiór danych, w którym będzie wykonywane poszukiwanie
srand((unsigned)time(NULL));
for(i = 1; i <= N; i++) d[i] = rand() % (M + 1);
// Generujemy poszukiwaną wartość
x = rand() % (M + 1);
// Wstawiamy wartownika do zbioru d[ ]
d[N + 1] = x;
// Szukamy x w d[ ]
p = 1;
while(x != d[p]) p++;
if(p > N) p = 0;
// Prezentujemy wyniki
for(i = 1; i <= N; i++)
if(i == p)
cout << ">" << setw(2) << d[i] << "<";
else
cout << setw(3) << d[i] << " ";
cout << "\nx = " << x;
if(p)
cout << " wystepuje na pozycji nr " << p << endl << endl;
else
cout << " nie wystepuje w zbiorze.\n\n";
// Gotowe
system("pause"); return 0;
}
' Przeszukiwanie z wartownikiem
'-------------------------------------------
' (C)2006 mgr Jerzy Wałaszek I LO w Tarnowie
'-------------------------------------------
Module Module1
Sub Main()
Const N = 100 ' liczba elementów w zbiorze
Const M = 99 ' maksymalna wartość elementów
' Deklaracja zmiennych
Dim d(N + 1), i, p, x As UInteger
Console.WriteLine("Przeszukiwanie z wartownikiem")
Console.WriteLine("-----------------------------")
Console.WriteLine(" (C)2006 mgr Jerzy Wałaszek ")
Console.WriteLine(" I LO w Tarnowie ")
Console.WriteLine()
' Generujemy zbiór danych, w którym będzie wykonywane poszukiwanie
Randomize()
For i = 1 To N : d(i) = Int(Rnd(1) * (M + 1)) : Next
' Generujemy poszukiwaną wartość
x = Int(Rnd(1) * (M + 1))
' Wstawiamy wartownika do zbioru d[ ]
d(N + 1) = x
' Szukamy x w d[ ]
p = 1
While x <> d(p) : p += 1 : End While
If p > N Then p = 0
' Prezentujemy wyniki
For i = 1 To N
If i = p Then
Console.Write(">{0,2}<", d(i))
Else
Console.Write(" {0,2} ", d(i))
End If
Next
Console.WriteLine()
Console.Write("x = {0}", x)
If p > 0 Then
Console.WriteLine(" występuje na pozycji nr {0}", p)
Else
Console.WriteLine(" nie występuje w zbiorze.")
End If
Console.WriteLine()
' Gotowe
Console.WriteLine("KONIEC. Naciśnij dowolny klawisz...")
Console.ReadLine()
End Sub
End Module
# -*- coding: cp1250 -*-
# Przeszukiwanie z wartownikiem
#-------------------------------------------
# (C)2006 mgr Jerzy Wałaszek I LO w Tarnowie
#-------------------------------------------
import random
N = 100 # liczba elementów w zbiorze
M = 99 # maksymalna wartość elementów
d = []
print "Przeszukiwanie z wartownikiem"
print "-----------------------------"
print " (C)2006 mgr Jerzy Walaszek "
print " I LO w Tarnowie "
# Generujemy zbiór danych, w którym będzie wykonywane poszukiwanie
for i in range(N): d.append(random.randint(0, M))
# Generujemy poszukiwaną wartość
x = random.randint(0, M)
# Wstawiamy wartownika do zbioru d[ ]
d.append(x)
# Szukamy x w d[ ]
p = 0;
while x != d[p]: p += 1
if p == N: p = -1
# Prezentujemy wyniki
for i in range(N):
if i == p:
print ">%2d<" % d[i],
else:
print " %2d " % d[i],
print "x =", x,
if p >= 0:
print "występuje na pozycji nr", p + 1
else:
print "nie występuje w zbiorze."
# Gotowe
raw_input("KONIEC. Naciśnij klawisz Enter...")
<html>
<head>
</head>
<body>
<div align="center">
<form style="BORDER-RIGHT: #ff9933 1px outset; PADDING-RIGHT: 4px;
BORDER-TOP: #ff9933 1px outset; PADDING-LEFT: 4px;
PADDING-BOTTOM: 1px; BORDER-LEFT: #ff9933 1px outset;
PADDING-TOP: 1px; BORDER-BOTTOM: #ff9933 1px outset;
BACKGROUND-COLOR: #ffcc66" name="frmsentinelsearch">
<h4 style="TEXT-ALIGN: center">Przeszukiwanie z wartownikiem</h4>
<p style="TEXT-ALIGN: center">
(C)2006 mgr Jerzy Wałaszek<br>
I LO w Tarnowie
</p>
<hr>
<p style="TEXT-ALIGN: center">
<input type="button" value="Szukaj" name="B1" onclick="main();">
</p>
<p style="TEXT-ALIGN: center" id="t_out">...</p>
</form>
<script language=javascript>
// Przeszukiwanie sekwencyjne
//-------------------------------------------
// (C)2006 mgr Jerzy Wałaszek I LO w Tarnowie
//-------------------------------------------
function main()
{
var N = 100; // liczba elementów w zbiorze
var M = 99; // maksymalna wartość elementów
// Deklaracja zmiennych
var d = new Array(N + 2);
var i,p,x,t;
// Generujemy zbiór danych, w którym będzie wykonywane poszukiwanie
for(i = 1; i <= N; i++) d[i] = Math.floor(Math.random() * (M + 1));
// Generujemy poszukiwaną wartość
x = Math.floor(Math.random() * (M + 1));
// Wstawiamy wartownika do zbioru d[ ]
d[N + 1] = x;
// Szukamy x w d[ ]
p = 1;
while(x != d[p]) p++;
if(p > N) p = 0;
// Prezentujemy wyniki
t = "";
for(i = 1; i <= N; i++)
if(i == p)
t += "<nobr><font color=red><b>>" + d[i] + "<</b></font></nobr>";
else
t += " " + d[i] + " ";
t += "<BR><BR>x = " + x + " ";
if(p)
t += "występuje na pozycji nr " + p;
else
t += "nie występuje w zbiorze.";
// Gotowe
document.getElementById("t_out").innerHTML = t;
}
</script>
</div>
</body>
</html>
GNU Free Documentation License.
document.frmadminemail.adminemail_tytul.value = parent.document.title + " : " + document.title;
Źródło: mgr Jerzy Wałaszek