efektywny algorytm

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 ?

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

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 :/

0

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

0

Dzięki ;)

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

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 ?

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*/ //];
}
0

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

0

już poprawiłem

0

Ile jest równe b(n)?

  1. b n = a n - b n - 1

czy

  1. 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

0
Wielki Pomidor napisał(a):

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

int tab[10];
int j=2;
int p;
int *w;
for (int i=1; i <= 512; i *= 2)
{
    p = i * 2 + 2;
    *(tab - 3 + ++j) = p - 1;
    w = &tab[j - 3];
}

Fajna krzyżówka.

1

A ja uważam że efektywny algorytm to byloby policzenie tego na kartce i wyznaczenie jednoznacznego wzoru na n-ty wyraz ciągu ;)
http://4programmers.net/Forum/C_i_C++/150919-optymalizacja_rekurencji?p=984625#id984625

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