Strona główna » Algorytmy » Artykuły » Rozpiętość Wartości
 

Rozpiętość Wartości

https://mattomatti.com/a0214

Wstęp

Dane są zapisy wartości pewnej firmy na przestrzeni kolejnych dni. Znajdź dla każdego dnia rozpiętość jego cen tj. jak długo do danego dnia cena była niższa, albo identyczna. Program powinien wczytać tablicę n liczb, a następnie wypisać dla każdego dnia rozpiętość cen.

Przykład

Przykładowo dany jest zapisa cen z całego tygodnia tj. {20, 30, 60, 40, 50, 70, 50}. Zapis ten można przedstawić również graficznie:

Ilustracja zapisu cen

Pierwszy dzień będzie miał wartość 1, ponieważ w ciągu dnia cena się nie zmienia, więc cena utrzymuje się cały dzień. Drugi dzień ma rozpiętość 2, ponieważ pierwszy dzień ma wartość mniejszą niż drugi. Analogicznie można wyjaśnić dla 3. Z kolei czwarty dzień będzie miał rozpiętość 1, ponieważ poprzedni dzień miał większą wartość niż on.

Dla tego zadania największą rozpiętość ma dzień 6, ponieważ rozciąga się od 1 do 6 włącznie (łącznie 6 dni). Należy oczywiście pamiętać, że dzień po nim ma rozpiętość 1, ponieważ jest mniejszy od poprzednika.

Implementacja

Rozwiązanie Siłowe

Zadanie można rozwiązać poprzez wybranie odpowiedniego dnia, a następnie policzeniu ile dni przed nim jest mniejszych. Jednak takie rowiązanie będzie miało złożoność kwadratową O(n2), a więc im więcej danych tym znacznie dłużej będą trwały obliczenia. Oto przykładowa implementacja:

  1. vector<int> PoliczRozpietosci(vector<int> dane) {
  2.   vector<int> wynik;
  3.   for (int i = 0; i < dane.size(); i++) {
  4.     int ile = 0;
  5.     int j = i;
  6.     while (j >= 0 && dane[j] <= dane[i]) {
  7.       ile++;
  8.       j--;
  9.     }
  10.     wynik.push_back(ile);
  11.   }
  12.   return wynik;
  13. }

Dla każdego kolejnego dnia tworzymy nowy licznik i cofamy się tak długo, aż napotkamy większą wartość, albo dojdziemy na początek listy. Przy każdym cofnięciu należy zwiększyć licznik.

Rozwiązanie Optymalne

Zadanie można rozwiązać w czasie liniowym O(n) korzystając z stosu. Metoda polega na tym, że na stos wrzucane są kolejne indeksy elementów. Jeśli i-ty element jest mniejszy, równy poprzedniemu to należy zdejmować tak długo elementy, aż stos będzie pusty, albo pierwszy element na stosie ma większą wartość niż aktualny. Jeśli po tej operacji stos jest pusty to jako i-ty element zapisujemy aktualny indeks powiększony o 1, a w przeciwnym przypadku przypisujemy różnicę indeksów pierwszego elementu na stosie i aktualnego. Oto przykładowa implementacja:

  1. vector<int> PoliczRozpietosci(vector<int> dane) {
  2.   vector<int> wynik;
  3.   stack<int> st;
  4.   st.push(0);
  5.   wynik.push_back(1);
  6.   for (int i = 1; i < dane.size(); i++) {
  7.     while (!st.empty() && dane[st.top()] <= dane[i]) {
  8.       st.pop();
  9.     }
  10.     if (st.empty()) {
  11.       wynik.push_back(i + 1);
  12.     } else {
  13.       wynik.push_back(i - st.top());
  14.     }
  15.     st.push(i);
  16.   }
  17.   return wynik;
  18. }

Kluczem do zrozumienia powyższego rozwiązania jest zrozumienie, że stos przedstawia wszystkie dotychczas większe elementy od elementu i. Jeśli stos jest pusty to znaczy, że żaden z poprzedników na pewno nie jest większy od aktualnego, a więc jest większy od i elementów i siebie samego.

Testowanie funkcji

Do przetestowania kodu można z korzystać z poniższego fragmentu programu:

  1. int main () {
  2.   int n, tmp;
  3.   cout << "Dla ilu dni dane sa ceny?\n n = ";
  4.   cin >> n;
  5.   cout << "Podaj wartosci w ciagu kolejnych dni:";
  6.   vector<int> lista;
  7.   while (n-- > 0) {
  8.     cin >> tmp;
  9.     lista.push_back(tmp);
  10.   }
  11.   vector<int> wynik = PoliczRozpietosci(lista);
  12.   for (int i = 0; i < wynik.size(); i++) {
  13.     cout << wynik[i] << " ";
  14.   }
  15.   system("pause");
  16.   return 0;
  17. }