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.

Elementy 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.

Elementy pomocnicze:

i : przebiega przez kolejne indeksy elementów Z. i ∈ C.
max_Z : tymczasowy element maksymalny.
min_Z : tymczasowy element minimalny.

Lista kroków:

K01: Jeśli n mod 2 = 1, ; jeśli nieparzysta liczba elementów, 
     to Z[n] ← Z[n-1]   ; dublujemy ostatni
K02: min_Z ← największa liczba całkowita ; inicjujemy min_Z i max_ZK03: max_Z ← najmniejsza liczba całkowita
K04: i ← 0
K05: Dopóki i < n: ; wybieramy pary kolejnych elementów
     wykonuj kroki K06…K12
K06:   Jeśli Z[i] > Z[i+1], ; rozdzielamy je na element 
       to idź do K10        ; mniejszy i większy
K07:   Jeśli Z[i] < min_Z, ; Z[i] : mniejszy, Z[i+1] : większy
       to min_Z ← Z[i]
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, ; Z[i]-większy, Z[i+1]-mniejszy
       to max_Z ← Z[i]
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 <ctime>

using namespace std;

const int N = 15;

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

  srand(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

Python (dodatek)

# Jednoczesne min i max
# Data:   24.02.2024
# (C)2024 mgr Jerzy Wałaszek
#---------------------------

import random

N = 15 # Liczba elementów
z = [random.randrange(10000) for i in range(N)]
if N % 2:
    z.append(z[N-1])
minz, maxz, i = 10000, -1, 0
while i < N:
    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]
    i += 2
for i in range(N):
    print("%4d" % z[i])
print()
print(minz, ":", maxz)
print()

Wynik:

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:

Elementy pomocnicze:

Algorytm jednoczesnego wyszukiwania max i min w zbiorze

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Przykładowe programy