Strona główna » Algorytmy » Artykuły » Policz Pary
 

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. static int PoliczPary(int[] dane)
  2. {
  3. int ile = 0;
  4. for (int i = 0; i < dane.Length; i++)
  5. {
  6. for (int j = 0; j < dane.Length; j++)
  7. {
  8. if (dane[i] < dane[j])
  9. {
  10. ile++;
  11. }
  12. }
  13. }
  14. return ile;
  15. }

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(n2).

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. static int PoliczPary(int[] dane)
  2. {
  3. return dane.Length * (dane.Length - 1) / 2;
  4. }

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. static void Main(string[] args)
  2. {
  3. Console.WriteLine("Podaj liczby:");
  4. string[] tab = Console.ReadLine().Split();
  5. int[] dane = new int[tab.Length];
  6. for(int i = 0; i < tab.Length; i++)
  7. {
  8. dane[i] = Convert.ToInt32(tab[i]);
  9. }
  10. int wynik = PoliczPary(dane);
  11. Console.WriteLine("Znalezionych par: {0}", wynik);
  12. Console.ReadLine();
  13. }