Serwis Edukacyjny
w I-LO w Tarnowie
obrazek

Materiały dla uczniów liceum

  Wyjście       Spis treści       Wstecz       Dalej  

Autor artykułu: mgr Jerzy Wałaszek

©2020 mgr Jerzy Wałaszek
I LO w Tarnowie

Jednoczesne wyszukiwanie max i min

SPIS TREŚCI
Tematy pomocnicze

Problem

W n-elementowym zbiorze Z  należy znaleźć element maksymalny i minimalny.

Rozwiązanie

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

Wejście:

n  –    liczba elementów w tablicy Z, nN.
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. iC.
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, nN.
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. iC.
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 

Zespół Przedmiotowy
Chemii-Fizyki-Informatyki

w I Liceum Ogólnokształcącym
im. Kazimierza Brodzińskiego
w Tarnowie
ul. Piłsudskiego 4
©2020 mgr Jerzy Wałaszek

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.