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(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. 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. }

• Kod źródłowy Implementacja