Login lub e-mail Hasło   

Algorytmy wyszukujące - wyszukiwanie z wartownikiem

Odnośnik do oryginalnej publikacji: http://www.i-lo.tarnow.pl/edu/inf/alg/al(...)ex.html
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 rys...
Wyświetlenia: 5.329 Zamieszczono 02/11/2006

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 C
krok 1: d[n + 1] x
krok 2: p 1
krok 3: Dopóki x d[p]: wykonuj p p + 1
krok 4: Jeśli p > n,  to p 0
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
-----------------------------
(C)2006 mgr Jerzy Wałaszek
I LO w Tarnowie

77 34 9 87 13 54 89 49 44 33 61 34 13 73 25 21 45 32 8 10
88 95 69 6 89 54 33 14 84 29 49 71 24 3 72 93 14 89 70 55
88 17 59 88 3 49 61 14 57 18 84 87 40 90 31 77 97 58 35 70
30 50 13 93 12 74 53 66 40 76 18 81 96 35 81 98 51 72 82 78
81 94 12 32 12 51 20 96 90 34 43 33 >80< 82 70 63 82 24 20 10

x = 80 występuje na pozycji nr 93

KONIEC. Naciśnij dowolny klawisz...

// 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 "
print

# 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
print
print
"x =", x,
if p >= 0:
print "występuje na pozycji nr", p + 1
else:
print "nie występuje w zbiorze."
print

# 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>&gt;" + d[i] + "&lt;</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>
 
Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.
   document.frmadminemail.adminemail_tytul.value = parent.document.title + " : " + document.title;   

Podobne artykuły


7
komentarze: 1 | wyświetlenia: 6261
16
komentarze: 5 | wyświetlenia: 9002
9
komentarze: 0 | wyświetlenia: 2782
49
komentarze: 18 | wyświetlenia: 64970
12
komentarze: 3 | wyświetlenia: 29777
37
komentarze: 9 | wyświetlenia: 28511
11
komentarze: 2 | wyświetlenia: 33147
18
komentarze: 11 | wyświetlenia: 9266
7
komentarze: 1 | wyświetlenia: 34646
17
komentarze: 4 | wyświetlenia: 14160
15
komentarze: 5 | wyświetlenia: 32754
13
komentarze: 2 | wyświetlenia: 22958
12
komentarze: 2 | wyświetlenia: 18504
11
komentarze: 1 | wyświetlenia: 86393
 
Autor
Artykuł




Brak wiadomości


Dodaj swoją opinię
W trosce o jakość komentarzy wymagamy od użytkowników, aby zalogowali się przed dodaniem komentarza. Jeżeli nie posiadasz jeszcze swojego konta, zarejestruj się. To tylko chwila, a uzyskasz dostęp do dodatkowych możliwości!
 

© 2005-2018 grupa EIOBA. Wrocław, Polska