Strona główna » Algorytmy » Artykuły » Równe Elementy
 

Równe Elementy

https://mattomatti.com/a0261

Zadanie

Napisz algorytm, który znajdzie minimalną ilość operacji do wykonania, aby wszystkie elementy były równe. Operacja może polegać na dodaniu, odjęciu, pomnożeniu czy podzieleniu przez dowolną wartość. Na wejściu znajduje się tablica liczb całkowitych o określonej długości. Funkcja powinna zwrócić jedną liczbę - minimalną ilość operacji do wykonania.

Przykład

Przykładowo dana jest tablica [1, 2, 3, 4]. Najprostszym sposobem na uzyskanie wszystkich elementów tej samej wartości polega na podzieleniu przez nie same tj. [1/1, 2/2, 3/3, 4/4]. W wyniku tej operacji zostanie zwrócona tablica samych wartości 1. Zatem potrzeba dokładnie trzech operacji. Warto zauważyć, że dla tablicy [1, 1, 2, 3, 4] liczb operacji nie zmienia się i wynosi dokładnie 3.

Implementacja

Interesuje nas jedynie liczba operacji do wykonania, a nie jakie to będą operacje. Najprostszy sposób na rozwiązanie podanego zadania polega na zliczeniu wystąpień poszczególnych elementów i znalezieniu najczęściej występującego. Przyjmijmy, że pewien element x występuje k razy pośród n elementów tablicy. Operacje, które można wykonać na elemencie są dowolne, więc trzeba wykonać dokładnie n - k operacji arytmetycznych.

Tego typu rozwiązania implementuje poniższy kod:

  1. int MinimumOperacji(vector<int> dane) {
  2.   sort(dane.begin(), dane.end());
  3.   dane.push_back(INT32_MAX);
  4.   int maksimum = 0;
  5.   int i = 1;
  6.   int ile = 1;
  7.   while (dane[i - 1] != INT32_MAX) {
  8.     if (dane[i] == dane[i - 1]) {
  9.       ile++;
  10.     }
  11.     else
  12.     {
  13.       if (ile > maksimum) {
  14.         maksimum = ile;
  15.       }
  16.       ile = 1;
  17.     }
  18.     i++;
  19.   }
  20.   return dane.size() - maksimum - 1;
  21. }

Algorytm początkowo sortuje elementy i skanuje raz tablicę, aby znaleźć najczęściej występujący element i zwraca wynik zgodnie z równaniem podanym w opisie algorytmu.

Testowanie funkcji

Do wczytania tablicy danych można skorzystać z poniższego kodu:

  1. int main () {
  2.   int n, tmp;
  3.   cout << "Ile elementow?\n n = ";
  4.   cin >> n;
  5.   vector<int> dane;
  6.   cout << "Podaj elementy:\n";
  7.   for (int i = 0; i < n; i++) {
  8.     cin >> tmp;
  9.     dane.push_back(tmp);
  10.   }
  11.   int wynik = MinimumOperacji(dane);
  12.   cout << "Potrzebnych operacji: " << wynik;
  13.   system("pause");
  14.   return 0;
  15. }