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

©2024 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, 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.
maxZ : tymczasowy element maksymalny.

Lista kroków:

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

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

using namespace std;

const int N = 15;

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

  srand (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
Python (dodatek)
# Wyszukiwanie max i min
# Data:   28.04.2008
# (C)2020 mgr Jerzy Wałaszek
#---------------------------

import random

N = 15  # Stała
z = []  # Tablica

for i in range(N):
    z.append(random.randrange(10000))

maxZ = z[0]
minZ = z[0]

for i in range(1, N):
    if z[i] > maxZ: maxZ = z[i]
    if z[i] < minZ: minZ = z[i]

for i in range(N):
  print("%5d" % z[i])

print()
print("%5d %5d" % (minZ, maxZ))
print()
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, 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 maxZ jest wartość elementu maksymalnego.

Zmienne pomocnicze:

i : przebiega przez kolejne indeksy elementów Z. i ∈  C.
maxZ : tymczasowy element maksymalny.
maxp : pozycja tymczasowego elementu maksymalnego.

Lista kroków:

K01: maxZZ[0]                   ; za tymczasowy element maksymalny
                                   ; bierzemy pierwszy element
K02: maxp ← 0                      ; zapamiętujemy jego pozycję
K03: Dla i = 1, 2, …, n - 1:       ; przeglądamy następne elementy zbioru
     wykonuj K04…K06
K04:   Jeśli Z[i] ≤ maxZ,          ; sprawdzamy, czy trafiliśmy 
       to następny obieg pętli K03 ; na element większy od maxZ
K05:   maxZZ[i]                 ; jeśli tak, to zapamiętujemy
                                   ; wartość elementu w maxZ
K06:   maxpi                    ; oraz jego pozycję w maxp
K07: Zakończ z wynikiem maxp       ; 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 <ctime>

using namespace std;

const int N = 15;

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

  srand(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
Python (dodatek)
# Wyszukiwanie pozycji max i min
# Data:   29.04.2008
# (C)2020 mgr Jerzy Wałaszek
#---------------------------

import random

N = 15  # Ilość liczb
z = []  # tablica
for i in range(N):
    z.append(random.randrange(10000))
maxZ = z[0]
minZ = maxZ
maxp = 0
minp = 0
for i in range(N):
    if z[i] < minZ:
        minZ, minp = z[i], i
    if z[i] > maxZ:
        maxZ, maxp = z[i], i
for i in range(N):
    print("%2d : %4d" % (i, z[i]))
print()
print(minp,":",maxp)
print()
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
©2024 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.