Policz Pary

Zadanie

Dana jest tablica unikalnych liczb naturalnych. Policz ile par można znaleźć w tablicy takich, że pierwszy element pary jest mniejszy od drugiego elementu pary. Kolejność wyboru elementów z tablicy jest dowolna.

Przykład

Przykładowo dane jest tablica liczb [1, 3, 2]. W takiej tablicy znajdują się 3 pary spełniające warunki zadania:

1. (1, 2)
2. (1, 3)
3. (2, 3)

Implementacja

Rozwiązanie Siłowe

Rozwiązanie siłowe polega na przejrzeniu wszystkich możliwych par. Poniższa funkcja PoliczPary() realizuje to zadanie.

1. int PoliczPary(vector<int> dane) {
2.   int ile = 0;
3.   for (int i = 0; i < dane.size(); i++) {
4.     for (int j = 0; j < dane.size(); j++) {
5.       if (dane[i] < dane[j]) {
6.         ile++;
7.       }
8.     }
9.   }
10.   return ile;
11. }

Algorytm działa w dwóch pętlach dzięki temu wybierane są wszystkie możliwe pary. Następnie porównywana jest para wybranych liczb i jeśli spełniają warunki to są zliczane. Tego typu rozwiązanie daje poprawne wyniki za każdym razem, ale jego złożoność jest kwadratowa O(n²).

Rozwiązanie Optymalne

Rozwiązanie siłowe można uprościć do zaledwie jednego wzoru. Jak wiadomo wszystkie liczby na liście są unikalne, a więc elementy się nie powtarzają. Jeśli lista składa się z n elementów to jest n-1 elementów większych od najmniejszego, n-2 większych od drugiego najmniejszego itd. Ostatecznie okazuje się, że łączna ilość par to n-1 + n-2 + .. + 2 + 1 = n(n - 1) / 2.

1. int PoliczPary(vector<int> dane) {
2.   return dane.size() * (dane.size() - 1) / 2;
3. }

Obliczenie wyniku na podstawie wzoru ma stałą złożoność O(1), która jest nieporównywalnie lepsza od rozwiązania siłowego.

Testowanie funkcji

W celu przetestowania napisanych funkcji można skorzystać z poniższego fragmentu programu.

1. int main () {
2.   int n, tmp;
3.   cout << "Ile tablica ma liczb?\n n = ";
4.   cin >> n;
5.   vector<int> dane;
6.   while (n--) {
7.     cin >> tmp;
8.     dane.push_back(tmp);
9.   }
10.   int wynik = PoliczPary(dane);
11.   cout << "Znalezionych par: " << wynik;
12.   system("pause");
13.   return 0;
14. }

• Kod źródłowy Implementacja