Algorytm 1 - min
Zadanie: Znajdź najmniejszą liczbę spośród podanego zbioru i podaj jej miejsce w zbiorze.
Specyfikacja:
Dane: Liczba naturalna n i zbiór n liczb
Wynik: Najmniejsza spośród liczb w zbiorze i jej miejsce w zbiorze.
Implementacja w C++
#include <iostream>
using namespace std;
int main()
{
unsigned int n, min, miejsce;
cout << "Podaj ilosc elementow: " << endl;
cin >> n;
unsigned int t[n];
for (unsigned int i = 1; i<=n; i++ )
{
cout << i << ": ";
cin >> t[i-1];
cout << endl;
}
min = t[0];
for (int i = 1; i<n; i++ )
{
if(t[i] < min)
{
min = t[i];
miejsce = i;
}
}
cout << "Najmniejsza: "<< min << endl<< "Jest " << miejsce+1<< " liczba w zbiorze";
return 0;
}
Złożoność algorytmu: T(n) = n - 1
Algorytm 2 - min i max - metodą dziel i zwyciężaj
Zadanie: Znajdź najmniejszą i największą liczbę spośród podanego zbioru.
Specyfikacja:
Dane: Liczba naturalna n i zbiór n liczb
Wynik: Najmniejsza i największa spośród liczb w zbiorze
Implementacja w C++
#include <iostream>
using namespace std;
int main()
{
unsigned int n, min, max;
cout << "Podaj ilosc elementow: " << endl;
cin >> n;
unsigned int t[n];
for (unsigned int i = 1; i<=n; i++ )
{
cout << i << ": ";
cin >> t[i-1];
cout << endl;
}
if (n % 2){ t[n] = t[n-1] }
min = t[0];
max = t[0];
for (unsigned int i = 0; i<n; i=i+2 )
{
if (t[i]<t[i+1])
{
if(t[i] < min)
min = t[i];
if(t[i+1] > max)
max = t[i+1];
}
else //if (t[i] > t[i+1])
{
if(t[i+1] < min)
min = t[i+1];
if(t[i] > max)
max = t[i];
}
}
cout << "Najmniejsza: "<< min << endl;
cout << "Najwieksza: "<< max << endl;
return 0;
}
Złożoność algorytmu: 3/2 * n