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

Rekurencja cpp

VPS Starter Arubacloud
0 głosów
240 wizyt
pytanie zadane 26 kwietnia 2021 w C i C++ przez anteq69 Początkujący (260 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 (61,370 p.)
Jaki jest zakres n ?
komentarz 26 kwietnia 2021 przez anteq69 Początkujący (260 p.)

 @Bondrusiek wartość n nie przekracza typu int

komentarz 26 kwietnia 2021 przez Bondrusiek Maniak (61,370 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 Początkujący (260 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,080 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 (269,120 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,080 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 (269,120 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 (61,370 p.)
@Wiciorny

Ok, dzięki za zaangażowanie.
komentarz 27 kwietnia 2021 przez Michał Muzyka Pasjonat (24,080 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ź 380 wizyt
pytanie zadane 6 stycznia 2021 w C i C++ przez monia79wawa Nowicjusz (190 p.)
0 głosów
1 odpowiedź 1,316 wizyt
0 głosów
4 odpowiedzi 393 wizyt
pytanie zadane 18 stycznia 2016 w C i C++ przez Seamel Nowicjusz (120 p.)

92,453 zapytań

141,262 odpowiedzi

319,088 komentarzy

61,854 pasjonatów

Motyw:

Akcja Pajacyk

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

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Akademia Sekuraka 2024 zapewnia dostęp do minimum 15 szkoleń online z bezpieczeństwa IT oraz dostęp także do materiałów z edycji Sekurak Academy z roku 2023!

Przy zakupie możecie skorzystać z kodu: pasja-akademia - użyjcie go w koszyku, a uzyskacie rabat -30% na bilety w wersji "Standard"! Więcej informacji na temat akademii 2024 znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...