• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Rekurencja cpp

0 głosów
139 wizyt
pytanie zadane 26 kwietnia 2021 w C i C++ przez anteq69 Nowicjusz (240 p.)
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?
komentarz 26 kwietnia 2021 przez Bondrusiek Maniak (60,730 p.)
Jaki jest zakres n ?
komentarz 26 kwietnia 2021 przez anteq69 Nowicjusz (240 p.)

 @Bondrusiek wartość n nie przekracza typu int

komentarz 26 kwietnia 2021 przez Bondrusiek Maniak (60,730 p.)

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 ?

 

komentarz 26 kwietnia 2021 przez anteq69 Nowicjusz (240 p.)
właśnie nie mam. Mam tylko w przykładzie podany 14 element ciągu, tj. 256
komentarz 26 kwietnia 2021 przez Michał Muzyka Pasjonat (24,140 p.)

@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]
 

komentarz 26 kwietnia 2021 przez Wiciorny Ekspert (218,670 p.)
. a[2*1 + 1] = a[2*1] = 4

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

komentarz 26 kwietnia 2021 przez Michał Muzyka Pasjonat (24,140 p.)
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
komentarz 26 kwietnia 2021 przez Wiciorny Ekspert (218,670 p.)

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

komentarz 26 kwietnia 2021 przez Bondrusiek Maniak (60,730 p.)
@Wiciorny

Ok, dzięki za zaangażowanie.
komentarz 27 kwietnia 2021 przez Michał Muzyka Pasjonat (24,140 p.)

@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

Zaloguj lub zarejestruj się, aby odpowiedzieć na to pytanie.

Podobne pytania

+1 głos
1 odpowiedź 153 wizyt
pytanie zadane 6 stycznia 2021 w C i C++ przez monia79wawa Nowicjusz (190 p.)
0 głosów
1 odpowiedź 743 wizyt
0 głosów
4 odpowiedzi 330 wizyt
pytanie zadane 18 stycznia 2016 w C i C++ przez Seamel Nowicjusz (120 p.)

87,916 zapytań

136,502 odpowiedzi

304,327 komentarzy

58,291 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto dwie polecane książki warte uwagi. Pełną listę znajdziesz tutaj.

...