Programowanie i algorytmy

KONKURS FRAKTAL

fraktal

VII edycja konkursu programistycznego

FRAKTAL

8-9 kwietnia 2017

czytaj więcej

Jednoczesne wyszukiwanie min i max

powrót

Algorytm, który wyszukuje minimum i maksimum w optymalny sposób znajduje się w tym miejscu. Omawiany algorytm będzie oparty na zasadzie klasycznego wyszukiwania tych elementów i jest opisany tutaj.

Zastosowany algorytm wykonuje {tex}2\cdot n-2{/tex} porównań elementów zbioru.

Prześledźmy ciąg:

{tex}4,\ 6,\ 3,\ 1,\ 8,\ 4{/tex}

 Postępujemy według schematu:

  • do zmiennych MIN i MAX przypisujemy pierwszą liczbę: MIN = MAX = 4
  • następny element zbioru sprawdzamy, czy jest większy niż MAX (if(6 > 4))
    • jeśli tak, to zmienną MAX nadpisujemy tą wartością (MAX = 6)
  • teraz sprawdzamy, czy ten element jest mniejszy od MIN (if(6 < 4))
    • jeśli tak, to zmienną MIN zastępujemy tą wartością (w tym przypadku warunek nie jest spełniony)
  • czynność tą postarzymy do wyczerpania liczb w zbiorze

Ostatecznie otrzymujemy:

  • MIN = 1
  • MAX = 8

 

Algorytm ten można wykorzystywać przy wyszukiwaniu rozstępu zbioru. Rozstęp zbioru to różnica między wartością maksymalną i minimalną.

 

Rozwiązanie w C++:

#include<iostream>
#include<cstdlib>
using namespace std;
 
int main()
{
  int tab[] = {1, 3, 4, 5, 2, 0, 6, 9, 8}, MIN, MAX;
 
  MIN = MAX = tab[0];
 
  for(int i=1; i < 9; i++)
  {
    if(tab[i] > MAX)
      MAX = tab[i];
 
    if(tab[i] < MIN)
      MIN = tab[i];
  }
 
  cout<<"MAX: "<<MAX<<"\nMIN: "<<MIN<<endl;
 
  system("pause");
  return 0;
}
 

 

Out: 

  • MAX: 9
  • MIN: 0