Programowanie i algorytmy

KONKURS FRAKTAL

fraktal

VI edycja konkursu programistycznego

FRAKTAL

19-20 listopad 2016

czytaj więcej

Znajdowanie jednocześnie min i max

powrót

Omawiamy algorytm optymalnie wyszukuje  ze zbioru liczb jednocześnie wartość najmniejszą i największą wykonując minimalną liczbę porównań. Metoda ta zaliczana jest do technik programistycznych typu "dziel i zwyciężaj". 

Zasada algorytmu jest bardzo prosta. Do badania bierzemy jednorazowo po dwie liczby, porównujemy je ze sobą i większą z nich przydzielamy do zbioru potencjalnych maksimów, a mniejszą lub równą do potencjalnych minimów. W ten sposób otrzymaliśmy dwa zbioru, gdzie w pierwszym występuje wartość, która jest maksymalna oraz w drugim wartość, która jest minimalna. Aby znaleźć teraz maksimum i minimum wykorzystujemy klasyczne przeszukiwanie liniowe dla tych dwóch podzbiorów. Szukanie to można wykonywać już podczas wczytywania danych nie wykorzystując tablic.

A gdzie tu optymalizacja?

Oczywiście będziemy wykonywać znaczniej mniej porównań, niż w klasycznym przeszukiwaniu liniowym. A dokładnie dla {tex}n{/tex} wyrazów zbioru wykonamy:

dla {tex}n{/tex} parzystego

  • {tex}\frac{n}{2}{/tex} porównań dla rozdzielenia zbiorów
  • {tex}\frac{n}{2}-1{/tex} porównań dla znalezienia minimum z podzbioru przechowującego potencjalne minima i tyle samo dla znalezienia maksimum

Reasumując mamy:

{tex}\frac{n}{2}+2\cdot (\frac{n}{2}-1)=\frac{3\cdot n-4}{2}{/tex} porównań

oraz dla {tex}n{/tex} nieparzystego mamy  

  •  {tex}\frac{n-1}{2}{/tex} porównań dla rozdzielenia zbiorów
  • {tex}\frac{n-1}{2}-1{/tex} porównań dla znalezienia minimum z podzbioru przechowującego potencjalne minima i tyle samo dla znalezienia maksimum
  • oraz {tex}2{/tex} porównania dla elementu, który nie został przydzielony do żadnego zbioru,

W sumie mamy:

{tex}\frac{n-1}{2}+2\cdot (\frac{n-1}{2}-1) + 2 = \frac{3\cdot n-3}{2}{/tex} porównań.

W klasycznym wyszukiwaniu wykonalibyśmy {tex}2\cdot (n-1){/tex} porównań.

Przeanalizujmy następujący zbiór liczb:

{tex}2,\ 4,\ 1,\ 6,\ 0,\ 3,\ 7,\ 5{/tex}

Porównujemy liczby parami i przydzielamy do odpowiednich zbiorów:

  • 2 i 4 -> 2 do zbioru minimum, 4 do zbioru maksimum
  • 1 i 6 -> 1 do zbioru minimum, 6 do zbioru maksimum
  • 0 i 3 -> 0 do zbioru minimum, 3 do zbioru maksimum
  • 7 i 5 -> 5 do zbioru minimum, 7 do zbioru maksimum

 (cztery porównania)

 Teraz mamy dwa zbiory:

Zbiór, w którym jest reprezentant minimum:

2, 1, 0, 5


oraz zbiór, w którym jest reprezentant maksimum:

4, 6, 3, 7

Następnie liniowo przeszukujemy każdy ze zbiorów i otrzymujemy z pierwszego MIN = i z drugiego MAX = 7.

Poniżej przedstawiono dwa rozwiązania.

Bez wykorzystania tablic:

#include<iostream>
#include<cstdlib>
using namespace std;
 
int main()
{
  int a, b, MIN, MAX, i = 4;
  unsigned int n;
 
  cout<<"Podaj liczbę elementów w zbiorze: ";
  cin>>n;
 
  if(n==0)
    cout<<"Podałes nieprawidłową liczbę!\n";
  else
  {  
    if(n>=2) //jesli są co najmnniej dwa elementy
    {
      //podaję pierwsze dwie liczby
      cin>>a>>b;
      if(a>b)
      {
        MIN = b;
        MAX = a;
      }
      else
      {
        MIN = a;
        MAX = b;
      }
 
      //wczytuję resztę liczb
      while(i<=n)
      {
        cin>>a>>b;
        if(a>b)
        {
          //a - należy do zbioru potencjalnych maksimów
          //b - należy do zbioru potencjalnych minimów
          if(a>MAX) 
            MAX = a; 
          if(b<MIN)
            MIN = b;
        }
        else
        {
          //b - należy do zbioru potencjalnych maksimów
          //a - należy do zbioru potencjalnych minimów
          if(b>MAX) 
            MAX = b; 
          if(a<MIN)
            MIN = a;
        }
 
        i+=2;
      }
      if(n%2==1) //jesli liczba elementów jest nieparzysta
      {
        cin>>a; //należy wczytać ostatni element
        if(a > MAX) MAX = a;
        if(a < MIN) MIN = a;
      }
    }
    else
    {
      cin>>a;
      MIN = MAX = a;
    }
 
    cout<<"MAX: "<<MAX<<endl<<"MIN: "<<MIN<<endl;    
  }
 
  system("pause");
  return 0;
}
 

 

Z wykorzystaniem tablicy:

#include<iostream>
#include<cstdlib>
using namespace std;
 
void szukaj(int tab[], int n, int &MIN, int &MAX)
{
  int i = 2;
  if(n>=2) //jesli są co najmnniej dwa elementy
  {
    if(tab[0]>tab[1]) //rozpatrujemy dwa pierwsze elementy
    {
      MIN = tab[1];
      MAX = tab[0];
    }
    else
    {
      MIN = tab[0];
      MAX = tab[1];
    }  
    //rozpatruję resztę liczb
    while(i+2<=n)
    {
      if(tab[i]>tab[i+1])
      {
        //tab[i] - należy do zbioru potencjalnych maksimów
        //tab[i+1 - należy do zbioru potencjalnych minimów
        if(tab[i]>MAX) 
          MAX = tab[i]; 
        if(tab[i+1]<MIN)
          MIN = tab[i+1];
      }
      else
      {
        //tab[i+1] - należy do zbioru potencjalnych maksimów
        //tab[i] - należy do zbioru potencjalnych minimów
        if(tab[i+1]>MAX) 
          MAX = tab[i+1]; 
        if(tab[i]<MIN)
          MIN = tab[i];
      }
      i+=2;
    }
    if(n%2==1) //jesli liczba elementów jest nieparzysta
    {
      if(tab[i] > MAX) MAX = tab[i];
      if(tab[i] < MIN) MIN = tab[i];
    }
  }
  else
  {
    MIN = MAX = tab[0];
  }  
}
 
int main()
{
  int MIN, MAX, tab[100]; 
  unsigned int n;
 
  cout<<"Podaj liczbę elementów w zbiorze: ";
  cin>>n;
 
  if(n == 0 || n > 100)
    cout<<"Podałes nieprawidłową liczbę!\n";
  else
    for(int i=0;i<n;i++)
      cin>>tab[i];
 
  szukaj(tab, n, MIN, MAX);
 
  cout<<"MIN: "<<MIN<<"\nMAX: "<<MAX<<endl;
 
  system("pause");
  return 0;
}