dziel i zwyciezaj

Odpowiedz Nowy wątek
2018-11-25 16:31
0

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

Pozostało 580 znaków

2018-11-25 16:49
1

Użyj wyszukiwania binarnego, wtedy wyzanzcysz liczbę wyrazów podzielnych przez 3 w czasie log n.


It's easy to hate code you didn't write, without an understanding of the context in which it was written.

Pozostało 580 znaków

2018-11-25 17:24
0

pseudokod
wyszukaj(A[],poczatek,koniec)
{
x=0;
if(poczatek>koniec)return brak
else{
srodek=(poczatek+koniec)/2
z=(A[sr]%3)
if(x==z)ile++;
else if(x<z)return wyszukaj(A,0,srodek-1)
else return wyszukaj(A,srodek+1,koniec)

return ile;

}

co o tym sądzicie ?

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0