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 ?
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
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 :/
zazwyczaj - rekurencja jest łatwiejsza do zaimplementowania ale bardziej złożona obliczeniowo
Dzięki ;)
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
a jeszcze mam jedna prośbę mógłby mi ktoś pomóc z tym zdaniem http://www.fotosik.pl/pokaz_obrazek/80d14f8304f62f58.html ?
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*/ //];
}
a czy to zadanie jest poprawne ? chodzi mi o to ,że używamy tam zmiennej "t" która nie została zdefiniowana ..
już poprawiłem
Ile jest równe b(n)?
- b n = a n - b n - 1
czy
- 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)
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.
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