Wyszukiwanie max lub min


Tematy pokrewne
Tablice – wektory
Podstawowe operacje na tablicach
Wyszukiwanie liniowe
Wyszukiwanie liniowe z wartownikiem
Zliczanie wg kryterium
Wyszukiwanie max lub min
Jednoczesne wyszukiwanie max i min
Zastosowania wyszukiwania – sortowanie przez wybór
Wyszukiwanie najczęstszej wartości w zbiorze – dominanta
Wyszukiwanie lidera
Wyszukiwanie binarne
Wyszukiwanie interpolacyjne
Wyszukiwanie k-tego największego elementu
Wyszukiwanie szybkie k-tego największego elementu
Wyszukiwanie mediany zbioru
Zbiory rozłączne – implementacja w tablicy
Sumy prefiksowe
Wbudowane generatory liczb pseudolosowych

 

Problem

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

 

 

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: maxZZ[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] > maxZ, to maxZZ[i] ; jeśli natrafimy na większy od maxZ, to zapamiętujemy go w maxZ
K04: Zakończ z wynikiem maxZ  

 

Program

Ważne:

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.

 

Lazarus
// Wyszukiwanie max i min
// Data:   28.04.2008
// (C)2012 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.
Code::Blocks
// Wyszukiwanie max i min
// Data:   28.04.2008
// (C)2012 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;
}
Free Basic
' Wyszukiwanie max i min
' Data:   28.04.2008
' (C)2012 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)2012 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 wykonuj K04...K06 ; przeglądamy następne elementy zbioru
K04:     Jeśli Z[i] maxZ, to następny obieg pętli K03 ; sprawdzamy, czy trafiliśmy 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ę

 

Program

Ważne:

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

 

Lazarus
// Wyszukiwanie pozycji max i min 
// Data:   29.04.2008
// (C)2012 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.
Code::Blocks
// Wyszukiwanie pozycji max i min 
// Data:   29.04.2008
// (C)2012 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;
}
Free Basic
' Wyszukiwanie pozycji max i min 
' Data:   29.04.2008
' (C)2012 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

 



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.