efektywny algorytm

Odpowiedz Nowy wątek
2015-01-31 23:21
Wielki Pomidor
0

Mam takie zadanie : podaj implementacje w jezyku c/c++ efektywnego algorytmu obliczania n-tego wyrazu ciągu (an) zadanego rekurencyjnie :a n=a n-1+2b n-1+3
b n=a n-bn -1
a 0=b0 =0
i mam pytanie czy najefektywniejszym będzie to zapisanie w rekurencji czy próbować to zapisać w pętli ?

Pozostało 580 znaków

2015-01-31 23:40
0

Najefektywniej będzie to zapisać jako mnożenie macierzy.

Jeśli zalozysz ze aktualna iteracja to macierz mn:
|a_n b_n 1|

I jeśli założysz, że macierz m0 to:
|0 0 1|

to kolejna iteracja to mn

       |1  1 0|
       |2 -1 0|
m_(n-1)|3 -1 1|

to efektywnie n-ta iteracja to:

       |1  1 0|^n
       |2 -1 0|
[0 0 1]|3 -1 1|

Nazwijmy tą macierz 3x3: C. Podnoszenie macierzy można wykonać w czasie logarytmicznym licząc kolejne potęgi C:
C1, C2, C4, C8, C16...
C2 = C1 C1
C4 = C2
C2
...

Cn to efektywnie = C1 b0 + C2 b1 + C4 b2 + C8 b3....
gdzie b0.. bn to kolejne bity liczby n


░█░█░█░█░█░█░█░█░█░█░█░
edytowany 2x, ostatnio: krwq, 2015-01-31 23:41

Pozostało 580 znaków

2015-01-31 23:50
Wielki Pomidor
0

Dzięki za odpowiedz ale sama bym nie wpadła na taki pomysł ;)..a jeśli miałabym możliwość wyboru kombinowania między rekurencja a szukaniem zapisu tego ciągu w jakiejś pętli ? Jaka jest złożoność rekurencji bo średnio to ogarniam :/

Pozostało 580 znaków

2015-01-31 23:53
0

zazwyczaj - rekurencja jest łatwiejsza do zaimplementowania ale bardziej złożona obliczeniowo

Pozostało 580 znaków

2015-01-31 23:54
Wielki Pomidor
0

Dzięki ;)

Pozostało 580 znaków

2015-01-31 23:59
0

Złożoność rekurencji zależy od tego jak to zaimplementujesz. W tym przypadku wydaje mi się, że najłatwiej będzie napisać iteracyjnie:
http://ideone.com/aXwmQW

Zauważ, że jak robisz więcej zapytań to tą samą wartość będziesz liczyć więcej niż raz i dałoby się to prosto zoptymalizować. Jeśli masz więcej zapytań to najlepiej użyć macierzy, jako że będziesz mieć złożoność praktycznie stałą (logarytmiczną binarnie do maksymalnej wartości n), a dokładniej:
O(q * ln nmax) gdzie q to liczba zapytań a nmax maksymalna wartość n


░█░█░█░█░█░█░█░█░█░█░█░
edytowany 5x, ostatnio: krwq, 2015-02-01 00:19

Pozostało 580 znaków

2015-02-01 00:03
Wielki Pomidor
0

a jeszcze mam jedna prośbę mógłby mi ktoś pomóc z tym zdaniem http://www.fotosik.pl/pokaz_obrazek/80d14f8304f62f58.html ?

Pozostało 580 znaków

2015-02-01 00:12
0

trollsko, ale zgodnie z treścią:

int tab[10];
int j=2;
int p;
int *w;
for (int i=1;i<0;)
{
    p=i;}int* t = &i;
    *(t);p=1;int i=-1;while(i<9){p*=2;t[i+2]=p+1;i++;w=tab+1;/*++j)=p-1;
    w=ssdftab[j*/ //];
}

░█░█░█░█░█░█░█░█░█░█░█░
edytowany 6x, ostatnio: krwq, 2015-02-01 03:11
to jest O(2n) a miało być O(n) - zadroozyn 2015-02-01 00:15
po pierwsze stałych się w złożonościach nie liczy w ogóle, po drugie w treści nic nie ma o złożoności - na oko nie pod tym postem skomentowałeś - krwq 2015-02-01 00:17
sformatuj kod jeszcze raz bo może źle zrozumiałem :) - zadroozyn 2015-02-01 00:22
przeczytaj post wyżej :D - krwq 2015-02-01 00:22

Pozostało 580 znaków

2015-02-01 01:23
Wielki Pomidor
0

a czy to zadanie jest poprawne ? chodzi mi o to ,że używamy tam zmiennej "t" która nie została zdefiniowana ..

Pozostało 580 znaków

2015-02-01 03:11
0

już poprawiłem


░█░█░█░█░█░█░█░█░█░█░█░

Pozostało 580 znaków

2015-02-01 12:58
0

Ile jest równe b(n)?

1) b n = a n - b n - 1

czy

2) b n = a n - b n - 1

Jeśli wersja nr 1 to:

b(n) = a(n) - b(n) - 1
b(n) = (a(n) - 1)/2

a(n) = a(n-1) + 2*(a(n-1) - 1)/2) + 3
a(n) = a(n-1) + a(n-1) - 1 + 3
a(n) = a(n-1) + a(n-1) + 2

a(n) = 2*a(n-1) + 2
a(n) = 2*(a(n-1) + 1)

Kod:
http://ideone.com/iUjkVe


Szacuje się, że w Polsce brakuje 50 tys. programistów

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