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. def PoliczPary(dane):
2. ile = 0
3. for x in dane:
4. for y in dane:
5. if (x < y):
6. ile += 1
7. return ile

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. def PoliczPary(dane):
2. return len(dane) * (len(dane) - 1) / 2

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. print("Podaj liczby:")
2. dane = [int(x) for x in input().split()]
3. wynik = PoliczPary(dane)
4. print("Znalezionych par:", wynik)

• Kod źródłowy Implementacja