Login lub e-mail Hasło   

Algorytmy wyszukujące - wyszukiwanie max

Odnośnik do oryginalnej publikacji: http://www.i-lo.tarnow.pl/edu/inf/alg/al(...)ex.html
Zadanie jest następujące: W n elementowym zbiorze znaleźć element o największej wartości Problem wyszukania maksymalnego elementu w zbio...
Wyświetlenia: 5.772 Zamieszczono 02/11/2006

Zadanie jest następujące:

W n elementowym zbiorze znaleźć element o największej wartości

Problem wyszukania maksymalnego elementu w zbiorze dotyczy zbiorów nieuporządkowanych (w zbiorach uporządkowanych np. rosnąco wystarczy przyjąć ostatni element za maksymalny) i polega na znalezieniu elementu, którego wartość jest największa ze wszystkich elementów w tym zbiorze. Algorytm może zwracać pozycję tego elementu, lub częściej tylko wartość (albo jedno i drugie).

Zadanie rozwiązujemy w czasie liniowym. Bierzemy pierwszy element zbioru jako tymczasowy element maksymalny zapamiętując jego wartość oraz pozycję w zbiorze. Następnie porównujemy go kolejno z pozostałymi elementami. Jeśli porównywany element zbioru jest większy od tymczasowego, to za nowy tymczasowy element maksymalny przyjmujemy element ze zbioru. Zapamiętujemy również pozycję tego elementu. Gdy porównamy wszystkie elementy zbioru, element tymczasowy stanie się rzeczywistym elementem maksymalnym.

Dane wejściowe

n - liczba elementów w zbiorze;  n N,   n > 0
d[ ] - zbiór, w którym poszukujemy elementu maksymalnego. Indeksy elementów rozpoczynają się od 1.

Dane wyjściowe

wmax - wartość wyznaczonego elementu maksymalnego;
pmax - pozycja elementu maksymalnego;   pmax N,   1 pmax n

Zmienne pomocnicze

i - przechowuje indeksy porównywanych elementów;  i N
krok 1: wmax d[1];  pmax 1
krok 2: Dla i = 2,3,...,n:  jeśli wmax < d[i], to wmax d[i];   pmax i
krok 3: Zakończ algorytm

Zmienna wmax przechowuje tymczasową wartość maksymalną elementów zbioru d[ ], a zmienna pmax przechowuje pozycję elementu maksymalnego w zbiorze. Na początku algorytmu za tymczasowy element maksymalny przyjmujemy pierwszy element zbioru. Pozycja tego elementu jest równa 1.

Rozpoczynamy pętlę przeglądającą pozostałe elementy zbioru od elementu na pozycji 2. W pętli sprawdzamy, czy tymczasowa wartość maksymalna wmax jest mniejsza od wartości i-tego elementu. Jeśli tak, to i-ty element staje się tymczasowym elementem maksymalnym - do wmax przepisujemy jego wartość, a w pmax zapamiętujemy jego pozycję w zbiorze.

Po zakończeniu pętli wmax zawiera największą wartość elementów ze zbioru d[ ], a pmax zawiera pozycję największego elementu. Kończymy algorytm. Zwróć uwagę, iż algorytm da prawidłowy wynik nawet dla zbioru jedno elementowego.

Jeśli za operacje dominujące przyjmiemy ilość wykonanych porównań elementów zbioru, to złożoność obliczeniowa algorytmu wyszukiwania elementu maksymalnego jest równa:

T(n) = n - 1

Algorytm posiada liniową klasę czasowej złożoności obliczeniowej O(n).


   
   
   

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 generuje 20-to elementową tablicę losowych liczb całkowitych z przedziału od 0 do 99, wyszukuje wśród nich element maksymalny i podaje jego wartość oraz pozycję w tablicy.

Efekt uruchomienia programu
Wyszukiwanie elementu maksymalnego
----------------------------------
(C)2006 mgr Jerzy Wałaszek
I LO w Tarnowie

70 24 27 66 77 57 94 93 37 75 76 73 50 9 80 63 >95< 51 40 47

wmax = 95 na pozycji nr 17

KONIEC. Naciśnij dowolny klawisz...

// Wyszukiwanie elementu maksymalnego
//-------------------------------------------
// (C)2006 mgr Jerzy Wałaszek I LO w Tarnowie
//-------------------------------------------

program searchmax;

{$APPTYPE CONSOLE}

const

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

// Deklaracja zmiennych


var
d : array[1..N] of cardinal;
i,wmax,pmax : cardinal;

begin
writeln('Wyszukiwanie elementu maksymalnego');
writeln('----------------------------------');
writeln(' (C)2006 mgr Jerzy Walaszek ');
writeln(' I LO w Tarnowie ');
writeln;

// Generujemy zbiór danych, w którym będzie wykonywane poszukiwanie
// elementu maksymalnego

randomize;
for i := 1 to N do d[i] := random(M + 1);

// Inicjujemy tymczasową wartość maksymalną wmax oraz pozycję
// tymczasowego elementu maksymalnego pmax

wmax := d[1]; pmax := 1;

// W pętli szukamy wartości większych od wmax

for i := 2 to N do
if
wmax < d[i] then
begin

wmax := d[i]; pmax := i
end;

// Prezentujemy wyniki

for i := 1 to N do
if
i = pmax then write('>',d[i]:2,'<') else write(d[i]:3,' ');
writeln;
writeln('wmax = ',wmax,' na pozycji nr ',pmax);
writeln;

// Gotowe

write('KONIEC. Nacisnij klawisz Enter...'); readln;
end.
// Wyszukiwanie elementu maksymalnego
//-------------------------------------------
// (C)2006 mgr Jerzy Wałaszek I LO w Tarnowie
//-------------------------------------------

#include <iostream>
#include <iomanip>

using namespace std;

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

int main(void)
{
unsigned d[N + 1],i,wmax,pmax;

cout << "Wyszukiwanie elementu maksymalnego\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
// elementu maksymalnego

srand((unsigned)time(NULL));
for(i = 1; i <= N; i++) d[i] = rand() % (M + 1);

// Inicjujemy tymczasową wartość maksymalną wmax oraz pozycję
// tymczasowego elementu maksymalnego pmax

wmax = d[1]; pmax = 1;

// W pętli szukamy wartości większych od wmax

for(i = 2; i <= N; i++)
if(wmax < d[i])
{
wmax = d[i]; pmax = i;
}

// Prezentujemy wyniki

for(i = 1; i <= N; i++)
if(i == pmax)
cout << ">" << setw(2) << d[i] << "<";
else
cout << setw(3) << d[i] << " ";
cout << "\nwmax = " << wmax << " na pozycji nr " << pmax << "\n\n";

// Gotowe

system("pause"); return 0;
}
' Wyszukiwanie elementu maksymalnego
'-------------------------------------------
' (C)2006 mgr Jerzy Wałaszek I LO w Tarnowie
'-------------------------------------------

Module Module1

Sub Main()
Const N = 20 ' liczba elementów w zbiorze
Const M = 99 ' maksymalna wartość elementów

' Deklaracja zmiennych


Dim d(N), i, wmax, pmax As UInteger

Console.WriteLine("Wyszukiwanie elementu maksymalnego")
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
' elementu maksymalnego

Randomize()
For i = 1 To N : d(i) = Int(Rnd(1) * (M + 1)) : Next

' Inicjujemy tymczasową wartość maksymalną wmax oraz pozycję
' tymczasowego elementu maksymalnego pmax

wmax = d(1) : pmax = 1

' W pętli szukamy wartości większych od wmax

For i = 2 To N
If wmax < d(i) Then
wmax = d(i) : pmax = i
End If
Next

' Prezentujemy wyniki

For i = 1 To N
If i = pmax Then
Console.Write(">{0,2}<", d(i))
Else
Console.Write(" {0,2} ", d(i))
End If
Next

Console.WriteLine()
Console.WriteLine("wmax = {0} na pozycji nr {1}", wmax, pmax)
Console.WriteLine()

' Gotowe

Console.WriteLine("KONIEC. Naciśnij dowolny klawisz...")
Console.ReadLine()

End Sub

End Module
# -*- coding: cp1250 -*-
# Wyszukiwanie elementu maksymalnego
#-------------------------------------------
# (C)2006 mgr Jerzy Wałaszek I LO w Tarnowie
#-------------------------------------------

import random

N = 20 # liczba elementów w zbiorze
M = 99 # maksymalna wartość elementów

d = []

print "Wyszukiwanie elementu maksymalnego"
print "----------------------------------"
print " (C)2006 mgr Jerzy Walaszek "
print " I LO w Tarnowie "
print

# Generujemy zbiór danych, w którym będzie wykonywane poszukiwanie
# elementu maksymalnego

for i in range(N): d.append(random.randint(0, M))

# Inicjujemy tymczasową wartość maksymalną wmax oraz pozycję
# tymczasowego elementu maksymalnego pmax

wmax = d[0]; pmax = 0

# W pętli szukamy wartości większych od wmax

for i in range(1, N):
if wmax < d[i]:
wmax, pmax = d[i], i

# Prezentujemy wyniki

for i in range(N):
if i == pmax:
print ">%2d<" % d[i],
else:
print " %2d " % d[i],
print
print "wmax =", wmax, "na pozycji nr", pmax + 1
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="frmmaxsearch">
<h4 style=
"text-align: center">Wyszukiwanie elementu maksymalnego</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>

// Wyszukiwanie elementu maksymalnego
//-------------------------------------------
// (C)2006 mgr Jerzy Wałaszek I LO w Tarnowie
//-------------------------------------------

var N = 20; // liczba elementów w zbiorze
var M = 99; // maksymalna wartość elementów

function main()
{
var d = new Array(N + 1);
var i,wmax,pmax,t;

// Generujemy zbiór danych, w którym będzie wykonywane poszukiwanie
// elementu maksymalnego

for(i = 1; i <= N; i++) d[i] = Math.floor(Math.random() * (M + 1));

// Inicjujemy tymczasową wartość maksymalną wmax oraz pozycję
// tymczasowego elementu maksymalnego pmax

wmax = d[1]; pmax = 1;

// W pętli szukamy wartości większych od wmax

for(i = 2; i <= N; i++)
if(wmax < d[i])
{
wmax = d[i]; pmax = i;
}

// Prezentujemy wyniki

t = "";
for(i = 1; i <= N; i++)
if(i == pmax)
t += "<b><font color=red>&gt;" + d[i] + "&lt;</b></font> ";
else
t += d[i] + " ";
t += "<BR><BR>wmax = " + wmax + " na pozycji nr " + pmax;

// 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: 6262
16
komentarze: 5 | wyświetlenia: 9006
9
komentarze: 0 | wyświetlenia: 2784
49
komentarze: 18 | wyświetlenia: 64981
12
komentarze: 3 | wyświetlenia: 29780
37
komentarze: 9 | wyświetlenia: 28522
11
komentarze: 2 | wyświetlenia: 33154
18
komentarze: 11 | wyświetlenia: 9268
7
komentarze: 1 | wyświetlenia: 34650
17
komentarze: 4 | wyświetlenia: 14190
15
komentarze: 5 | wyświetlenia: 32763
13
komentarze: 2 | wyświetlenia: 22961
12
komentarze: 2 | wyświetlenia: 18506
11
komentarze: 1 | wyświetlenia: 86408
 
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