Algorytmy i Struktury Danych

Zadanie znajdowania elementu maksymalnego lub minimalnego jest typowym zadaniem wyszukiwania, które rozwiązujemy przy pomocy algorytmu wyszukiwania liniowego. Za tymczasowy maksymalny (minimalny) element przyjmujemy pierwszy element zbioru. Następnie element tymczasowy porównujemy z kolejnymi elementami. Jeśli któryś z porównywanych elementów jest większy (mniejszy) od elementu tymczasowego, to za nowy tymczasowy element maksymalny (minimalny) przyjmujemy porównywany element zbioru. Gdy cały zbiór zostanie przeglądnięty, w elemencie tymczasowym otrzymamy element maksymalny (minimalny) w zbiorze.

Poniżej podajemy algorytm wyszukiwania max. Wyszukiwanie min wykonuje się identycznie, zmianie ulega tylko warunek porównujący element tymczasowy z elementem zbioru w kroku K03.

Algorytm wyszukiwania elementu maksymalnego w zbiorze

Wejście:

n	–	liczba elementów w tablicy Z, n ∈ N.
Z	–	tablica zawierająca elementy do zliczania. Indeksy elementów rozpoczynają się od 0, a kończą na n - 1.

Wyjście:

Wartość największego elementu zbioru.

Zmienne pomocnicze:

i	–	przebiega przez kolejne indeksy elementów Z. i ∈ C.
max_Z	–	tymczasowy element maksymalny.

Lista kroków:

K01:	max_Z ← Z [ 0 ]	za tymczasowy element maksymalny bierzemy pierwszy element
K02:	Dla i = 1, 2, ..., n - 1: wykonuj K03	przeglądamy następne elementy zbioru
K03:	Jeśli Z [ i ] > max_Z, to max_Z ← Z [ i ]	jeśli natrafimy na większy od max_Z, to zapamiętujemy go w max_Z
K04:	Zakończ z wynikiem max_Z

Przykładowe programy

Uwaga:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

Program generuje 15 liczb pseudolosowych z zakresu od 0 do 9999. Wygenerowane liczby zapisuje w tablicy Z. Następnie wyszukuje liczbę najmniejszą i największą. Jako wynik jest jest wypisywana zawartość całej tablicy w 15 kolejnych wierszach, a w wierszu 17 liczba najmniejsza i największa.

Pascal

// Wyszukiwanie max i min
// Data:   28.04.2008
// (C)2020 mgr Jerzy Wałaszek
//---------------------------

program prg;

const N = 15;

var
  Z : array [ 0..N - 1 ] of integer;
  i, maxZ, minZ: integer;

begin
  randomize;
  for i := 0 to N - 1 do Z [ i ] := random ( 10000 );
  maxZ := Z [ 0 ]; minZ := Z [ 0 ];
  for i := 1 to N - 1 do
  begin
    if Z [ i ] > maxZ then maxZ := Z [ i ];
    if Z [ i ] < minZ then minZ := Z [ i ];
  end;
  for i := 0 to N - 1 do writeln ( Z [ i ] :5 );
  writeln;
  writeln ( minZ:5, maxZ:5 );
  writeln; 
end.

C++

// Wyszukiwanie max i min
// Data:   28.04.2008
// (C)2020 mgr Jerzy Wałaszek
//---------------------------

#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <time.h>

using namespace std;

const int N = 15;

int main( )
{
  int Z [ N ], i, maxZ, minZ;

  srand ( ( unsigned )time ( NULL ) );
  for( i = 0; i < N; i++ ) Z [ i ] = rand( ) % 10000;
  maxZ = minZ + Z [ 0 ];
  for( i = 1; i < N; i++ )
  {
    if( Z [ i ] > maxZ ) maxZ = Z [ i ];
    if( Z [ i ] < minZ ) minZ = Z [ i ];
  }
  for( i = 0; i < N; i++ )
    cout << setw ( 5 ) << Z [ i ] << endl;
  cout << endl << setw ( 5 ) << minZ << setw ( 5 ) << maxZ << endl << endl;
  return 0;
}

Basic

' Wyszukiwanie max i min
' Data:   28.04.2008
' (C)2020 mgr Jerzy Wałaszek
'---------------------------

Const N = 15

Dim As Integer Z ( N - 1 ), i, maxZ, minZ

Randomize

For i = 0 To N - 1
  Z ( i ) = Cint ( Rnd * 9999 )
Next

maxZ = Z ( 0 ): minZ = Z ( 0 )

For i = 1 To N - 1
  If Z ( i ) > maxZ Then maxZ = Z ( i )
  If Z ( i ) < minZ Then minZ = Z ( i )
Next

For i = 0 To N - 1
  Print Using "#####";Z ( i )
Next

Print
Print Using "##### ####";minZ;maxZ
Print

End

Wynik:

89
282
5838
8656
6423
5088
4859
2017
8291
8524
127
621
3826
4914
1733

89 8656

Czasami zależy nam nie na wartości elementu maksymalnego (minimalnego ), lecz na jego pozycji w zbiorze. W tym przypadku musimy, oprócz wartości samego elementu maksymalnego ( minimalnego ), zapamiętywać jego pozycję, którą na końcu zwracamy jako wynik pracy algorytmu.

Algorytm wyszukiwania pozycji elementu maksymalnego w zbiorze

Wejście:

n	–	liczba elementów w tablicy Z, n ∈ N.
Z	–	tablica zawierająca elementy do zliczania. Indeksy elementów rozpoczynają się od 0, a kończą na n - 1.

Wyjście:

Pozycja (indeks) elementu maksymalnego. W max_Z jest wartość elementu maksymalnego.

Zmienne pomocnicze:

i	–	przebiega przez kolejne indeksy elementów Z. i ∈ C.
max_Z	–	tymczasowy element maksymalny.
max_p	–	pozycja tymczasowego elementu maksymalnego.

Lista kroków:

K01:	max_Z ← Z [ 0 ]	za tymczasowy element maksymalny bierzemy pierwszy element
K02:	max_p ← 0	zapamiętujemy jego pozycję
K03:	Dla i = 1, 2, ..., n - 1: wykonuj K04...K06	przeglądamy następne elementy zbioru
K04:	Jeśli Z [ i ] ≤ max_Z, to następny obieg pętli K03	sprawdzamy, czy trafiliśmy na element większy od max_Z
K05:	max_Z ← Z [ i ]	jeśli tak, to zapamiętujemy wartość elementu w max_Z
K06:	max_p ← i	oraz jego pozycję w max_p
K07:	Zakończ z wynikiem max_p	zwracamy zapamiętaną pozycję

Przykładowe programy

Uwaga:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

Pascal

// Wyszukiwanie pozycji max i min 
// Data:   29.04.2008
// (C)2020 mgr Jerzy Wałaszek
//---------------------------

program prg;

const N = 15;

var
  Z : array [ 0..N - 1 ] of integer;
  i, maxZ, maxp, minZ, minp : integer;

begin
  randomize;
  for i := 0 to N - 1 do Z [ i ] := random ( 10000 );
  maxZ := Z [ 0 ]; minZ := maxZ;
  maxp := 0; minp := 0;
  for i := 0 to N - 1 do
  begin
    if Z [ i ] < minZ then
    begin
      minZ := Z [ i ]; minp := i;
    end;
    if Z [ i ] > maxZ then
    begin
      maxZ := Z [ i ]; maxp := i;
    end;
  end;
  for i := 0 to N - 1 do writeln ( i:2, ' : ', Z [ i ] :4 );
  writeln;
  writeln ( minp, ':', maxp );
  writeln;
end.

C++

// Wyszukiwanie pozycji max i min 
// Data:   29.04.2008
// (C)2020 mgr Jerzy Wałaszek
//---------------------------

#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <time.h>

using namespace std;

const int N = 15;

int main( )
{
  int Z [ N ], i, maxZ, maxp, minZ, minp;

  srand ( ( unsigned )time ( NULL ) );
  for( i = 0; i < N; i++ ) Z [ i ] = rand( ) % 10000;
  maxZ = minZ + Z [ 0 ];
  maxp = minp = 0;
  for( i = 0; i < N; i++ )
  {
    if( Z [ i ] < minZ )
    {
      minZ = Z [ i ]; minp = i;
    }
    if( Z [ i ] > maxZ )
    {
      maxZ = Z [ i ]; maxp = i;
    }
  }
  for( i = 0; i < N; i++ )
    cout << setw ( 2 ) << i << ": " << setw ( 4 ) << Z [ i ] << endl;
  cout << endl << minp << ":" << maxp << endl << endl;
  return 0;
}

Basic

' Wyszukiwanie pozycji max i min 
' Data:   29.04.2008
' (C)2020 mgr Jerzy Wałaszek
'---------------------------

Const N = 15

Dim As Integer Z ( N - 1 ), i, maxZ, maxp
Dim As Integer minZ, minp

Randomize
For i = 0 To N - 1
  Z ( i ) = Cint ( Rnd * 9999 )
Next
maxZ = Z ( 0 ): minZ = maxZ
maxp = 0: minp = 0
For i = 0 To N - 1
  If Z ( i ) < minZ Then
    minZ = Z ( i ): minp = i
  End If
  If Z ( i ) > maxZ Then
    maxZ = Z ( i ): maxp = i
  End If
Next
For i = 0 To N - 1
  Print Using "## : ####";i;Z ( i )
Next  
Print
Print minp;":";maxp
Print
End

Wynik:

0 : 7223
1 : 2137
2 : 7026
3 : 5658
4 : 5012
5 : 6046
6 : 5609
7 : 6493
8 : 916
9 : 9623
10 : 2385
11 : 122
12 : 4679
13 : 7316
14 : 2069

11:9

Na początek: podrozdziału strony

Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone
pod warunkiem podania źródła oraz niepobierania za to pieniędzy.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.

Informacje dodatkowe.

Wyszukiwanie max lub min

Problem

Rozwiązanie

Algorytm wyszukiwania elementu maksymalnego w zbiorze

Wejście:

Wyjście:

Zmienne pomocnicze:

Lista kroków:

Przykładowe programy

Algorytm wyszukiwania pozycji elementu maksymalnego w zbiorze

Wejście:

Wyjście:

Zmienne pomocnicze:

Lista kroków:

Przykładowe programy