Dany jest ciąg A liczb naturalnych. Ma on taką własność,że jest posortowany nierosnaca ze wzgledu na resztę z dzielenia przez 3. Zaproponuj ,oparty na metodzie "dziel i zwyciężaj" algorytm wyznaczania wyrazów ciagu A podzilenych przez 3.Zapisz algorytm w wersji rekurencyjnej.Wyznacz funcję kosztu pesymistycznego algorytmu T(n).Zapisz tę funkcję w postacji jawnej i rekurencyjnej.Zakładamy że rozmiarem zadania jest długośc ciagu,która oznaczamy przez n,operacją elementarna są porównania reszt z dzielenia przez 3 liczb ciągu .
Przykład
WP: A:5 2 11 8 7 4 1 6 9
WK:liczba wyrazów w ciągu A podzielnych przez 3 wynosi 2
Wiem jak napisać algorytm naiwny
,ale nie mam pomysłu jak w tym przypadku użyć metody dziel i zwycieżaj,liczę na jakieś wskazówki
Z góry dzięki