Algorytmy i Struktury Danych - Jednoczesne Max i Min

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.
max_Z	–	tymczasowy element maksymalny.
min_Z	–	tymczasowy element minimalny.

Krok	Operacja	Liczba wykonań
1	min_Z ← Z [ 0 ]	1
2	max_Z ← Z [ 0 ]	1
3	i ← 1	1
4	Jeśli i = n, to idź do kroku 9	n
5	Jeśli Z [ i ] < min_Z, to min_Z ← Z [ i ]	n - 1
6	Jeśli Z [ i ] > max_Z, to max_Z ← Z [ i ]	n - 1
7	i ← i + 1	n - 1
8	Idź do 4	n - 1
9	Pisz min_Z, max_Z	1
10	Zakończ	1

Zastanówmy się, czy można uzyskać lepszy wynik. Algorytm porównuje każdy element zbioru z min_Z oraz z max_Z. 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 min_Z. Wystarczy porównanie z max_Z. To samo dotyczy elementu mniejszego – porównujemy go tylko z min_Z. Otrzymujemy zysk – poprzednio dwa elementy wymagały wykonania 4 porównań (każdy z min_Z i max_Z ). 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 min_Z.
Element większy porównujemy z max_Z.

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.
max_Z	–	tymczasowy element maksymalny.
max_p	–	pozycja tymczasowego elementu maksymalnego.

Lista kroków:

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

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

Pascal

// Jednoczesne min i max
// Data:   30.04.2008
// (C)2020 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.

C++

// Jednoczesne min i max
// Data:   30.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 + 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;
}

Basic

' Jednoczesne min i max
' Data:   30.04.2008
' (C)2020 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

Na początek: podrozdziału 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.

Jednoczesne wyszukiwanie max i min

Problem

Rozwiązanie

Wejście:

Wyjście:

Zmienne pomocnicze:

Algorytm jednoczesnego wyszukiwania max i min w zbiorze

Wejście:

Wyjście:

Zmienne pomocnicze:

Lista kroków:

Przykładowe programy