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 $$n$$ wyrazów zbioru wykonamy:

dla $$n$$ parzystego

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

Reasumując mamy:

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

oraz dla $$n$$ nieparzystego mamy  

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

W sumie mamy:

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

W klasycznym wyszukiwaniu wykonalibyśmy $$2\cdot (n-1)$$ porównań.

Przeanalizujmy następujący zbiór liczb:

$$2,\ 4,\ 1,\ 6,\ 0,\ 3,\ 7,\ 5$$

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 = 0 i z drugiego MAX = 7.

Poniżej przedstawiono dwa rozwiązania.

Bez wykorzystania tablic:

//algorytm.edu.pl
#include<iostream>
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:

//algorytm.edu.pl
#include<iostream>
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;
	
	return 0;
}