Rekurencja cpp

Question

Mam problem z pewnym zadaniem w cpp:

Oblicz n-ty wyraz następującego ciągu:
a[0] = 2
a[2*n] = a[n]*a[n]
a[2*n+1] = a[2*n]

nie wiem jak to przedstawić i rozwiązać w rekurencji. Ktoś podpowie?

Comments

Jaki jest zakres n ?

---

 @Bondrusiek wartość n nie przekracza typu int

---

Coś mi tu nie gra:

a[2*n] = a[n]*a[n]
a[2*n+1] = a[2*n]

co daje

a[2*n] = a[n]*a[n]
a[2*n+1] = a[n]*a[n]

Masz gdzieś wypisane pierwsze elementy tego ciągu ?

 

---

właśnie nie mam. Mam tylko w przykładzie podany 14 element ciągu, tj. 256

---

@Bondrusiek,
przecież to jest poprawnie, wyrazy będą parami równe:
0. a[0] = 2
1. a[2*0 + 1] = a[0] = 2
2. a[2*1] = a[1] * a[1] = 4
3. a[2*1 + 1] = a[2*1] = 4
4. a[2*2] = a[2] * a[2] = 16
5. a[2*2 + 1] = a[2*2] = 16
itd
dla wyrazów parzystych korzystasz ze wzoru:
a[2*n] = a[n]*a[n]
dla nieparzystych:
a[2*n+1] = a[2*n]
 

---

. a[2*1 + 1] = a[2*1] = 4

od kiedy to jest prawdą :) bo a[3] != a[2]  w tym co napisałeś :) 

---

no to wynika z powyżej podanych wzorów
a[2*n] = a[n]*a[n]
a[2*n+1] = a[2*n]

dla n=1
a[2] = a[1] * a[1]
a[3] = a[2],
czyli:
a[3] = a[2] = a[1] * a[1]      oraz a[1] = a[0]
czyli:
a[3] = a[2] = a[1] * a[1] = a[0] * a[0],
czyli:
a[3] = a[0] * a[0] = 2 * 2 = 4

---

@Bondrusiek, ma tutaj policzyc n-ty wyraz ciągu jemu nie sa potrzebne wartości tak naprwdę, bo ma to być wzór w postaci a[n] = .... wzór 
Więc autor teraz korzystając z tego co napisałeś, powinien przekształcić wyrażenie, tak aby ten wzór na a[n] wyznaczyc. 

---

@Wiciorny

Ok, dzięki za zaangażowanie.

---

@Wiciorny, 

nie każdy wzór rekurencyjny można zamienić na prosty wzór, tutaj akurat się da, ale na początku padł argument, że wzór rekurencyjny jest źle podany.
Tutaj trzeba policzyć a[n/2] wyraz, a[n/4], a[n/8] itd. bo do tego sprowadza się ta rekurencja, czyli prostą drogą dedukcji można dojść do tego, że te wyrazy będą parami takie same i będą kolejnymi potęgami dwójki