Algorytmy wyszukujące - wyszukiwanie max

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 w_max przechowuje tymczasową wartość maksymalną elementów zbioru d[ ], a zmienna p_max 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 w_max jest mniejsza od wartości i-tego elementu. Jeśli tak, to i-ty element staje się tymczasowym elementem maksymalnym - do w_max przepisujemy jego wartość, a w p_max zapamiętujemy jego pozycję w zbiorze.

Po zakończeniu pętli w_max zawiera największą wartość elementów ze zbioru d[ ], a p_max 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.

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>

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