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.

Elementy 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: ; przeglądamy następne elementy zbioru
     wykonuj K03
K03:   Jeśli Z[i] > max_Z, ; jeśli natrafimy na większy od max_Z, 
       to max_Z ← Z[i]     ; to zapamiętujemy go w max_ZK04: 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 <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 = [random.randrange(10000) for i in range(N)]

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

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.

Elementy 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: ; przeglądamy następne elementy zbioru
     wykonuj K04…K06
K04:   Jeśli Z[i] ≤ max_Z, ; sprawdzamy, czy trafiliśmy 
       to następny obieg pętli K03 ; na element większy od max_Z
K05:   max_Z ← Z[i] ; jeśli tak, to zapamiętujemy; wartość elementu w max_ZK06:   max_p ← i    ; oraz jego pozycję w max_pK07: 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 <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 = [random.randrange(10000) for i in range(N)]
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:

do podrozdziału do 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:

Elementy pomocnicze:

Lista kroków:

Przykładowe programy

Algorytm wyszukiwania pozycji elementu maksymalnego w zbiorze

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Przykładowe programy