Zakresy

Cel

Zapisywanie wielu liczb pod rząd jest monotonnym zadaniem, więc bardzo często zapisujemy w skrócie np. 1-10 co można przetłumaczyć jako zbiór liczb od 1 do 10. Napisz program, który zamieni tablicę liczb na zakresy. Przykładowo dla liczb 1, 2, 3 poprawny zakres to 1-3, ale dla liczby 5 powinno zostać wypisane tylko 5. Zakładamy, że elementy na liście są unikalne.

Analiza

Opis

Przed przystąpieniem do pisania kodu przeanalizujmy treść zadania. Otóż wiadomo, że liczby na liście będą unikalne, ale czy będą posortowane? Poniższa propozycja rozwiązania zadania wymaga, aby tak było, więc posortowanie powinno zostać wykonane na samym początku algorytmu. Następnie pobieramy pierwszą liczbę z nieprzejrzanej części tablicy i zwiększamy indeks tak długo, aż kolejna liczba jest o jeden większa od poprzedniej. W przypadku, gdy okaże się, że następna liczba jest większa o więcej niż jeden to należy aktualny zakres zapisać na tablicę. Kroki te powtarzamy tak długo, aż w tablicy wszystko elementy zostaną sprawdzone.

Przykład

Dana jest tablica [2, 1, 5, 3]. Na początku sortujemy elementy otrzymując w ten sposób [1, 2, 3, 5]. Następnie rozpoczynamy przeglądanie od elementu 1, wykrywamy, że kolejne 2 i 3 są kolejnymi liczbami, ale 5 już nie, więc zapisujemy na listę 1-3. W tablicy zostaje tylko [5]. Kończymy algorytm stwierdzając, że nie ma więcej elementów, więc zapisujemy aktualnie znaleziony zakres. Ostatecznie skróciliśmy tablicę do zapisu "1-3 5".

Złożoność

Sortowanie tablicy zależy od implementacji algorytmu, ale możemy przyjąć O(nlogn), a druga część kodu jest liniowa, więc ostatecznie algorytm działa w czasie liniowo-logarytmicznym O(nlogn).

Implementacja

Do przechowywania zakresu warto skorzystać z struktury pary liczb, aby zapisać początek i koniec pewnego zakresu. W przypadku, gdy zakres składa się z jednej wartości to obie liczby będą sobie równe.

1. struct zakres
2. {
3.   int poczatek;
4.   int koniec;
5. };

Poniżej znajduje się przykładowa implementacja funkcji konwertujNaZakresy(). Jako argument należy podać tablicę liczb do zamiany na zakresy.

1. vector<zakres> konwertujNaZakresy(int * dane, int n)
2. {
3.   sort(dane, dane + n);
4.   vector<zakres> lista;
5.   for (int i = 0; i < n; i++)
6.   {
7.     int teraz = dane[i];
8.     while (i < n && dane[i + 1] == dane[i] + 1)
9.     {
10.       i++;
11.     }
12.     lista.push_back(utworzZakres(teraz, dane[i]));
13.   }
14.   return lista;
15. }

Testowanie funkcji

Poniższy fragment kodu wczyta dane od użytkownika i wypisze wynik na ekran:

1. int main() {
2.   int n;
3.   cout << "Ile tablica ma liczb?\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.   vector<zakres> lista = konwertujNaZakresy(tab, n);
10.   for (int i = 0; i < lista.size(); i++)
11.     wypiszZakres(lista[i]);
12.   system("pause");
13.   return 0;
14. }

• Kod źródłowy Implementacja