Jednoczesne wyszukiwanie max i 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 maksymalny i minimalny.

 

 

Jeśli do wyszukiwania elementu max i min zastosujemy standardowy algorytm, to otrzymamy:

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ść najmniejszego i największego elementu w tablicy Z.

Zmienne pomocnicze
i  –  przebiega przez kolejne indeksy elementów Z. i   C
maxZ  – tymczasowy element maksymalny
minZ  – tymczasowy element minimalny

 

Numer Operacja Liczba wykonań
1 minZZ[0] 1
2 maxZZ[0] 1
3 i ← 1 1
4 Jeśli i = n, to idź do 9 n
5 Jeśli Z[i] < minZ, to minZZ[i] n - 1
6 Jeśli Z[i] > maxZ, to maxZZ[i] n - 1
7 ii + 1 n - 1
8 Idź do 4 n - 1
9 Pisz minZ, maxZ 1
10 Zakończ 1

 

Zastanówmy się, czy można uzyskać lepszy wynik. Algorytm porównuje każdy element zbioru z minZ oraz z maxZ. Tutaj tkwi nieefektywność. Obie operacje nr 5 i 6 są wykonywane po n - 1 razy, co daje w sumie 2n - 2 porównania w całym zbiorze.

Wyobraźmy sobie, iż ze zbioru bierzemy parę 2 elementów i porównujemy je ze sobą. Element większy nie może być minimalnym, zatem nie musimy go już porównywać z minZ. Wystarczy porównanie z maxZ. To samo dotyczy elementu mniejszego – porównujemy go tylko z minZ. Otrzymujemy zysk – poprzednio dwa elementy wymagały wykonania 4 porównań (każdy z minZ i maxZ). Teraz mamy:

 

Jedno porównanie dwóch elementów, które rozdzieli je na element mniejszy i element większy.
Element mniejszy porównujemy z minZ.
Element większy porównujemy z maxZ.

 

Daje to 3 porównania zamiast 4. Ponieważ ze zbioru pobieramy po dwa kolejne elementy, to ich liczba musi być parzysta. Jeśli zbiór ma nieparzystą liczbę elementów, to po prostu dublujemy ostatni element i dostaniemy parzystą liczbę elementów.

Porównanie pary elementów dzieli zbiór na dwa podzbiory – zbiór elementów większych i mniejszych. W podzbiorze elementów większych szukamy elementu maksymalnego, a w podzbiorze elementów mniejszych szukamy minimalnego. Ponieważ ich liczebność jest o połowę mniejsza od liczebności zbioru wejściowego, to wykonamy mniej operacji porównań.

Metoda rozwiązywania problemów przez podział na mniejsze części w informatyce nosi nazwę Dziel i Zwyciężaj (ang. Divide and Conquer). Dzięki niej często udaje się zmniejszyć złożoność obliczeniową wielu algorytmów.

 

Algorytm jednoczesnego wyszukiwania max i min 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. Tablica musi umożliwiać dodanie elementu, jeśli n jest nieparzyste.
Wyjście:

Element minimalny i maksymalny w tablicy Z

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: Jeśli n mod 2 = 1, Z[n] ← Z[n-1] ; jeśli nieparzysta liczba elementów, dublujemy ostatni
K02: minZ ← największa liczba całkowita ; inicjujemy minZ i maxZ
K03: maxZ ← najmniejsza liczba całkowita  
K04: i ← 0  
K05: Dopóki i < n wykonuj K06...K12 ; wybieramy pary kolejnych elementów
K06:     Jeśli Z[i] > Z[i+1], to idź do K10 ; rozdzielamy je na element mniejszy i większy
K07:     Jeśli Z[i] < minZ, to minZZ[i] ; Z[i] - mniejszy, Z[i+1] - większy
K08:     Jeśli Z[i+1] > maxZ, to maxZZ[i+1]  
K09:     Idź do K12  
K10:     Jeśli Z[i] > maxZ, to maxZZ[i] ; Z[i] - większy, Z[i+1] - mniejszy
K11:     Jeśli Z[i+1] < minZ, to minZZ[i+1]  
K12:     ii + 2 ; przechodzimy do następnej pary elementów
K13: Pisz minZ, maxZ ; wyprowadzamy wyniki
K14: Zakończ  

 

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 podane zostają element minimalny i maksymalny.

 

Lazarus
// Jednoczesne min i max
// Data:   30.04.2008
// (C)2012 mgr Jerzy Wałaszek
//---------------------------

program prg;

const N = 15;

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

begin
  randomize;
  for i := 0 to N-1 do Z[i] := random(10000);
  if N mod 2 = 1 then Z[N] := Z[N-1];
  minZ := 10000; maxZ := -1;
  i := 0;
  while i < N do
  begin
    if Z[i] > Z[i+1] then
    begin
      if Z[i]   > maxZ then maxZ := Z[i];
      if Z[i+1] < minZ then minZ := Z[i+1];
    end
    else
    begin
      if Z[i]   < minZ then minZ := Z[i];
      if Z[i+1] > maxZ then maxZ := Z[i+1];
    end;
    inc(i,2);
  end;
  for i := 0 to N-1 do writeln(Z[i]:4);
  writeln;
  writeln(minZ,' : ',maxZ);
  writeln;
end.
Code::Blocks
// Jednoczesne min i max
// Data:   30.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+1],minZ,maxZ,i;

  srand((unsigned)time(NULL));
  for(i = 0; i < N; i++) Z[i] = rand() % 10000;
  if(N % 2) Z[N] = Z[N-1];
  minZ = 10000; maxZ = -1;
  for(i = 0; i < N; i += 2)
    if(Z[i] > Z[i+1])
    {
      if(Z[i]   > maxZ) maxZ = Z[i];
      if(Z[i+1] < minZ) minZ = Z[i+1];
    }
    else
    {
      if(Z[i]   < minZ) minZ = Z[i];
      if(Z[i+1] > maxZ) maxZ = Z[i+1];
    }
  for(i = 0; i < N; i++) cout << setw(4) << Z[i] << endl;
  cout << endl <<  minZ << " : " << maxZ << endl << endl;
  return 0;
}
Free Basic
' Jednoczesne min i max
' Data:   30.04.2008
' (C)2012 mgr Jerzy Wałaszek
'---------------------------

Const N = 15

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

Randomize
For i = 0 To N-1
  Z(i) = Cint(Rnd * 9999)
Next    
If N Mod 2 = 1 Then Z(N) = Z(N-1)
minZ = 10000: maxZ = -1
i = 0
While i < N
  If Z(i) > Z(i+1) Then
    If Z(i)   > maxZ Then maxZ = Z(i)
    If Z(i+1) < minZ Then minZ = Z(i+1)
  Else
    If Z(i)   < minZ Then minZ = Z(i)
    If Z(i+1) > maxZ Then maxZ = Z(i+1)
  End If
  i += 2
Wend
For i = 0 To N-1
  Print Using "####";Z(i)
Next
Print
Print minZ;" : ";maxZ
Print
End
Wynik
4850
3151
2213
 272
7933
2490
1267
4923
 713
 987
3253
5533
1759
8103
9414

272 : 9414

 



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.