Monotoniczność ciągu liczbowego

Ciąg monotoniczny

Przypuśćmy, że mamy ciąg liczbowy (a_n), którego kolejnym elementami są a₁, a₂, .. a_n. Ciąg możemy powiedzieć, że jest monotoniczny jeśli każda para kolejnych elementów spełnia określony warunek. W tabelce zostały wyróżnione typy ciągu liczbowego:

Jeśli dany ciąg liczbowy nie można przyporządkować do żadnego z wymienionych typów to mówimy, że jest niemonotoniczny.

Implementacja

Sprawdzanie wybranego warunku będzie się różnić tylko wykonywanym porównaniem. Szkielet funkcji, która będzie przyjmowała listę liczb, a następnie sprawdzi ją pod określoną cechą będzie miała następujący szablon:

1. bool czy_monotoniczny (int* data, int n) {
2.   for(int i = 0; i < n - 1; i++){
3.     if (! ([warunek]))
4.       return false;
5.   }
6.   return true;
7. }

(1.) Funkcja przyjmuje dwa argumenty: data - lista zawierająca kolejne wyrazy ciągu liczbowego, n - określa ile jest elementów w data. Zwrócona wartość ma typ logiczny, która będzie oznaczała czy cały ciąg spełnia określony warunek. (2.) Dla każdej pary elementów: (3.) sprawdzany jest określony [warunek]. Jeśli nie jest spełniony to (4.) funkcja zwróci fałsz. (6.) W przypadku, gdy pętla się zakończy i nie została przerwana to znaczy, że jest to określony ciąg monotoniczny.

Podany szablon należy uzupełnić odpowiednim warunkiem. Istnieje szansa, aby uniknąć negacji (co zmniejszy ilość wykonywanych operacji przez procesor) wystarczy sprawdzić warunek przeciwny. Jego spełnienie będzie oznaczało, że sprawdzany warunek nie jest spełniony.

Dla sprawdzenia jednego ciągu istnieje potrzeba porównania n - 1 par liczb. Oznacza to, że złożoność podanego algorytmu wynosi Θ(n). Nie istnieje algorytm o lepszej złożoności wykonujący podane rozwiązanie.

Sprawdzanie ciągu rosnącego

Warunkiem, że ciąg jest monotoniczny rosnący spełniony musi być warunek a_i < a_{i + 1}. Na podstawie szablonu funkcja czy_rosnacy() będzie wyglądać następująco:

1. bool czy_rosnacy (int* data, int n) {
2.   for(int i = 0; i < n - 1; i++){
3.     if (! (data[i] < data[i+1]))
4.       return false;
5.   }
6.   return true;
7. }

W celu usunięcia negacji warunek należy zamienić na przeciwny:

3.   if (data[i] >= data[i+1])

Testowanie funkcji

Poniższy kod wczytuje najpierw liczbę n, a następnie n liczb i wywołuje funkcję czy_rosnacy(), aby sprawdzić określony warunek monotoniczności:

1. int main () {
2.   int n;
3.   cin >> n;
4.   int* data = new int [n];
5.   for(int i = 0; i < n - 1; i++)
6.     cin >> data[i];
7.   cout << czy_rosnacy(data, n);
8.   delete[] data;
9.   system("pause");
10.   return 0;
11. }

• Kod źródłowy Implementacja

Zadania

Zadanie 1

Napisz funkcję czy_malejacy(), czy_nierosnacy(), czy_niemalejacy(), które sprawdzą monotoniczność ciągu (kolejno typ malejący, nierosnący i niemalejący).

Zadanie 2

Usuń negację z funkcji napisanych w zadaniu 1.

Zadanie 3

Napisz funkcję main(), która wczyta ciąg liczbowy i określi jego typ. Należy pamiętać, że ciąg (1, 1, 1, 1, ..) jest zarówno nierosnący, niemalejący i stały!

• Kod źródłowy Zadanie 1
• Kod źródłowy Zadanie 2
• Kod źródłowy Zadanie 3