Algorytmy wyszukujące - wyszukiwanie max

ada434859fa0e5e71ae978eb189fc667.gif

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.

1955d3aec10841340d9d6780088039a6.gif

Dane wejściowe

n - liczba elementów w zbiorze;  n db9e7d6608c8f418d8b7f5e53207604d.gif 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 db9e7d6608c8f418d8b7f5e53207604d.gif N,   1 340f81b1bfa21210273650ec540cde0e.gif pmax 340f81b1bfa21210273650ec540cde0e.gif n

Zmienne pomocnicze

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

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).


8bd5cfd35d5b72561d268dcc92700de3.gif
e58cc94fe86f021251b99e36c9d147bf.gif    
   
   

0b932844f3246f040811a539a8de3bf4.gif

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...

c9873b6a0308ae4cf690e1ebe9e76bfa.gif
// 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.
97d4946ebcb20f2f48bf4dfed393af97.gif
// 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;
}
fe95272615d944b3d3b2a151adfd4118.gif
' 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
add899b6c2009d69f0a59de979ae29d2.gif
# -*- 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...")
e0db5abbebbe665f9921e08873050587.gif
<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.

 

Źródło: mgr Jerzy Wałaszek