Serwis Edukacyjny
w I-LO w Tarnowie
obrazek

Materiały dla uczniów liceum

  Wyjście       Spis treści       Wstecz       Dalej  

Autor artykułu: mgr Jerzy Wałaszek

©2020 mgr Jerzy Wałaszek
I LO w Tarnowie

Wyszukiwanie max lub min

SPIS TREŚCI
Tematy pomocnicze

Problem

W n-elementowym zbiorze Z  należy znaleźć element o maksymalnej ( minimalnej ) wartości.

Rozwiązanie

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, nN.
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. iC.
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
Wyszukiwanie max i min
(C)2020 mgr Jerzy Wałaszek


...


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, nN.
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. iC.
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.

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 podana zostaje pozycja elementu najmniejszego i największego.
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 

Zespół Przedmiotowy
Chemii-Fizyki-Informatyki

w I Liceum Ogólnokształcącym
im. Kazimierza Brodzińskiego
w Tarnowie
ul. Piłsudskiego 4
©2020 mgr Jerzy Wałaszek

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.