Punkt Równowagi

Opis

Punkt równowagi to indeks takiego elementu tablicy, ze wszystkie elementy leżące po lewej stronie mają taką samą jak te które leżą po jego prawej stronie. Nie każda tablica ma taki punkt, ale są takie co mają ich kilka.

Przykład

Weźmy przykładowo tablicę [2, 1, 9, 3]. W tym przypadku punktem równowagi jest wartość 9, ponieważ 2 + 1 = 3. W tablicy mogą występować również wartości ujemne oraz 0. W tablicy [-1, 3, 2, 5, 1, 1, 0, 2]. W tym przypadku podział wyznacza liczba 5, ponieważ rozdzielna na dwie podtablice [-1, 3, 2] oraz [1, 1, 0, 2], których suma elementów jest taka sama.

Analiza zadania

Możliwych wyborów punktu równowagi jest dokładnie tyle ile tablica ma elementów. Proste rozwiązanie polega na sprawdzeniu każdego z nich. Nie będzie to rozwiązanie najbardziej efektywne, ponieważ wymaga zsumowania odpowiednio n elementów n razy. To daje w rezultacie O(n²).

Optymalne rozwiązanie zadania polega na zsumowaniu wszystkich elementów, a następnie przeglądanie kolejnych kandydatów na punkt równowagi na bieżąco aktualizując sumę po jego lewej i prawej stronie. Najgorszy przypadek wymaga przejrzenia elementów w celu ich zsumowania, a następnie przejrzenia tablicy jeszcze raz. Oznacza to, że złożoność czasowa optymalnego rozwiązanie wyniesie O(n).

Implementacja

Rozwiązanie proste

Poniższa funkcja punktRownowagi() szuka w podanej tablicy tab punktu równowagi w prosty sposób.

1. int punktRownowagi(int* tab, int n) {
2.   for (int i = 0; i < n; i++) {
3.     int suma = 0;
4.    
5.     for (int j = 0; j < i; j++)
6.       suma += tab[j];
7.    
8.     for (int j = i + 1; j < n; j++)
9.       suma -= tab[j];
11.     if (suma == 0)
12.       return i;
13.   }
14.   return -1;
15. }

Dla każdego możliwego indeksu, który może być punktem równowagi liczymy sumę elementów na lewo od niego i odejmujemy każdy element, który znajduje się na prawo od aktualnie wybranego. Jeśli na koniec iteracji wynik to 0 oznacza to, że i-ty element jest punktem równowagi. Należy wtedy zwrócić numer indeksu. Jeśli jednak indeks nie zostanie znaleziony to należy zwrócić -1.

Rozwiązanie optymalne

Poniższa funkcja punktRownowagi() znajduje punkt równowagi w czasie liniowym:

1. int punktRownowagi(int* tab, int n) {
2.   int suma = 0;
3.   for (int i = 0; i < n; i++) {
4.     suma += tab[i];
5.   }
7.   int poprzednie = 0;
8.   for (int i = 0; i < n; i++) {
9.     suma -= tab[i];
10.     if (suma == poprzednie)
11.       return i;
12.     poprzednie += tab[i];
13.   }
14.   return -1;
15. }

Na początku obliczamy sumę wszystkich elementów. Następnie przechodzimy po kolejnych elementach odpowiednio aktualizując odpowiednio wcześniej obliczoną sumę. Otóż od sumy należy odjąć aktualnie wybrany element, ponieważ nie należy on już do prawej strony. Jeśli suma dotychczas odrzuconych elementów oraz zaktualizowanej sumy jest równa to punkt równowagi został znaleziony. W przeciwnym razie należy dołączyć odrzucony element do sumy odrzuconych. To gwarantuje, że zawsze tablica jest podzielona na dwie sumy lewej i prawej strony.

Testowanie funkcji

Poniższy fragment kodu wczytuje tablicę, a następnie wypisuje na ekran indeks pod którym znajduje się punkt równowagi, albo komunikat, że nie istnieje.

1. int main () {
2.   int n;
3.   cout << "Ile elementow ma tablica ?\n n = ";
4.   cin >> n;
5.   cout << "Podaj elementy:\n";
6.   int* tab = new int[n];
7.   for (int i = 0; i < n; i++)
8.     cin >> tab[i];
9.   int wynik = punktRownowagi(tab, n);
10.   if (wynik == -1) {
11.     cout << "Nie ma punktu rownowagi";
12.   } else {
13.     cout << "Punkt rownowagi pod indeksem " << wynik;
14.   }
15.   system("pause");
16.   return 0;
17. }

• Kod źródłowy Implementacja