Login lub e-mail Hasło   

Algorytmy wyszukujące - wyszukiwanie. sekwencyjne

Odnośnik do oryginalnej publikacji: http://www.i-lo.tarnow.pl/edu/inf/alg/al(...)ex.html
Problem jest następujący: W n elementowym zbiorze wyszukać element o zadanych własnościach. Zadanie przeszukiwania sekwencyjnego po...
Wyświetlenia: 7.036 Zamieszczono 02/11/2006

Problem jest następujący:

W n elementowym zbiorze wyszukać element o zadanych własnościach.

Zadanie przeszukiwania sekwencyjnego polega na przeglądaniu kolejnych elementów zbioru. Znaleziony element zostaje zwrócony (zwykle interesuje nas nie sam element, ale jego pozycja w zbiorze) lub algorytm zwraca informację, iż poszukiwanego elementu w zbiorze nie ma.

Ponieważ wymagane jest sprawdzenie kolejnych elementów zbioru, to w przypadku pesymistycznym (brak poszukiwanego elementu, lub jest on na samym końcu zbioru) algorytm musi wykonać n porównań, gdzie n jest liczbą elementów w zbiorze. Pesymistyczna złożoność czasowa jest następująca:

W(n) = n

Jeśli elementy są rozłożone losowo, to prawdopodobieństwo znalezienia poszukiwanego elementu na każdej pozycji w zbiorze jest takie samo i wynosi:

pi =   1   , i = 1,2,...,n
n

Oczekiwana złożoność czasowa algorytmu jest równa:

W obu przypadkach klasa czasowej złożoności obliczeniowej jest liniowa i wynosi O(n). Dokładniejszy opis czasowych złożoności obliczeniowych oraz notacji omikron znajdziesz w artykułach o algorytmach sortujących oraz o liczbach pierwszych.

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.
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: p 1
krok 2: Dopóki (p n) (x d[p]) wykonuj p p + 1
krok 3: Jeśli p > n, to p 0
krok 4: Zakończ algorytm

Przeszukiwanie zbioru rozpoczynamy od pierwszego elementu. Zmienna p przechowuje pozycję sprawdzanego elementu i na początku przyjmuje wartość 1.

W pętli warunkowej najpierw sprawdzamy, czy pozycja p wskazuje element wewnątrz zbioru. Jeśli nie, pętla jest przerywana.

Drugi test w pętli sprawdza, czy element zbioru leżący na pozycji p jest różny od poszukiwanego elementu x. Jeśli tak, to pozycja p jest zwiększana o 1 wskazując kolejny element zbioru i pętla kontynuuje się. Jeśli nie, to element został znaleziony i pętla zostaje przerwana.

Wyjście z pętli przeszukującej zbiór następuje w dwóch przypadkach:

- przeglądnięty został cały zbiór, elementu x nie znaleziono i pozycja p jest większa od n.

- znaleziono element x w zbiorze na pozycji p.

Zatem w przypadku gdy p > n, elementu x nie znaleziono i zerujemy pozycję p, aby zgłosić ten fakt. Inaczej p zawiera pozycję w zbiorze, na której znajduje się poszukiwany przez nas element x.

Ostatni test właściwie nie jest konieczny - program wykorzystujący ten algorytm może przecież sprawdzić, czy p jest większe od n. Jednakże wyzerowanie p jest bardziej czytelne i intuicyjne - w zbiorze nie ma elementu na pozycji zero. Zwracanie zera w przypadku niepowodzenia jest często stosowaną praktyką w programowaniu (jeśli zero jest możliwą wartością, to często zwraca się minus jeden dla zaznaczenia porażki)..

   
   
   

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 sekwencyjne
--------------------------
(C)2006 mgr Jerzy Wałaszek
I LO w Tarnowie

15 82 78 44 53 97 74 59 26 >49< 26 0 29 89 88 95 34 28 33 96
41 98 73 57 47 42 81 34 38 30 56 12 14 96 4 58 30 2 43 97
72 28 39 12 45 86 63 71 98 59 73 81 70 63 24 62 57 41 97 48
10 72 60 17 53 12 50 40 33 59 80 56 81 41 75 79 20 30 23 18
73 80 66 34 18 95 1 13 51 13 19 69 86 25 55 70 75 8 80 91

x = 49 występuje na pozycji nr 10

KONIEC. Naciśnij dowolny klawisz...
Przeszukiwanie sekwencyjne
--------------------------
(C)2006 mgr Jerzy Wałaszek
I LO w Tarnowie

20 43 64 73 99 59 84 41 37 44 61 35 6 8 78 88 63 15 42 58
89 56 95 5 60 29 41 92 45 61 11 11 25 40 42 34 36 87 83 93
44 38 31 75 37 59 89 58 46 91 46 52 89 7 88 85 45 5 27 97
44 20 63 72 95 65 63 87 22 93 74 89 41 90 49 96 53 83 9 24
64 83 27 40 33 50 32 37 38 78 43 34 74 14 31 7 72 94 95 36

x = 47 nie występuje w zbiorze.

KONIEC. Naciśnij dowolny klawisz...

// Przeszukiwanie sekwencyjne
//-------------------------------------------
// (C)2006 mgr Jerzy Wałaszek I LO w Tarnowie
//-------------------------------------------

program seqsearch;

{$APPTYPE CONSOLE}

const
N = 100; // liczba elementów w zbiorze
M = 99; // maksymalna wartość elementów

// Deklaracja zmiennych


var
d : array[1..N] of cardinal;
i,p,x : cardinal;

begin
writeln('Przeszukiwanie sekwencyjne');
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);

// Szukamy x w d[ ]

p := 1;
while (p <= N) and (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 sekwencyjne
//-------------------------------------------
// (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 + 1],i,p,x;

cout << "Przeszukiwanie sekwencyjne\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);

// Szukamy x w d[ ]

p = 1;
while((p <= N) && (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 sekwencyjne
'-------------------------------------------
' (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), i, p, x As Integer

Console.WriteLine("Przeszukiwanie sekwencyjne")
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))

' Szukamy x w d[ ]

p = 1
While (p <= N) AndAlso (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 sekwencyjne
#-------------------------------------------
# (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 sekwencyjne"
print "--------------------------"
print "(C)2006 mgr Jerzy Wałaszek"
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)

# Szukamy x w d[ ]

p = 0
while (p < N) and (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="frmseqsearch">
<h4 style="TEXT-ALIGN: center">
Przeszukiwanie sekwencyjne</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 + 1);
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));

// Szukamy x w d[ ]

p = 1;
while((p <= N) && (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.

Podobne artykuły


7
komentarze: 1 | wyświetlenia: 6261
16
komentarze: 5 | wyświetlenia: 9002
9
komentarze: 0 | wyświetlenia: 2781
49
komentarze: 18 | wyświetlenia: 64970
12
komentarze: 3 | wyświetlenia: 29776
37
komentarze: 9 | wyświetlenia: 28510
11
komentarze: 2 | wyświetlenia: 33147
18
komentarze: 11 | wyświetlenia: 9266
7
komentarze: 1 | wyświetlenia: 34646
17
komentarze: 4 | wyświetlenia: 14156
15
komentarze: 5 | wyświetlenia: 32753
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