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

Rekurencja, problem ze zrozumieniem algorytmu

VPS Starter Arubacloud
+1 głos
493 wizyt
pytanie zadane 6 stycznia 2016 w C i C++ przez kacperoo7 Nowicjusz (200 p.)
Witam. Mam taki oto algorytm:

C(n)= 2*C(n-1) - C(n-2)

C(1)=2. C(2)=5

Mam napisać do tego algorytm w rekurencji i iteracji. Problem jest taki, że nie wiem jak to napisać a co najważniejsze nie rozumiem tego schematu. Znalazłem program, który oblicza rekurencyjnie te liczby i np. dla 3 wychodzi 8, dla 4-11... Nie wiem skąd to się bierze i jak to wytłumaczyć.

Chętnego proszę o pomoc :)

4 odpowiedzi

+2 głosów
odpowiedź 6 stycznia 2016 przez Mariusz O Mądrala (5,290 p.)
wybrane 6 stycznia 2016 przez kacperoo7
 
Najlepsza
Jest to zwyczajny ciąg zapisany rekurencyjnie. W którym pierwsze dwa to 2 i 5... a każdy kolejny to [2*(poprzedni) - (dwa poprzednie)].

Czyli 2, 5, (2*5 - 2 = 8 // trzeci wyraz, który Ci wyszedł), (2 * 8 - 5 = 11), (2 * 11 - 8 = 14), (2 * 14 - 11 = 17), ... = 2, 5, 8, 11, 14, 17 i tak dalej.

Można to rozwiązać tak jak ciąg fibonacciego.

Funkcja A z parametrem x
Dla x = 1, daj 2,
Dla x = 2, daj 5,
Dla x > 2 daj A( 2 * A( x-1 ) - A( x-2 ) )
+3 głosów
odpowiedź 6 stycznia 2016 przez Szykem2 Nałogowiec (29,510 p.)
Naucz się czytać wzory to dużo daje. Wytłumaczę dla c(3). Więc jak mówi wzór c(3) = 2*c(2) - c(1) = 2*5 - 2 = 10 - 2 = 8. Analogicznie dla c(4) = 2*c(3) - c(2) = 2*8 - 5 = 16 - 5 = 11. Czyli żeby obliczyć wartość dla dowolnej liczby naturalnej n musisz znaleźć wartość funkcji dla n-1 i n-2 a mając te wartości podstawiasz do wzoru i wychodzi. Równanie rekurencyjne jest bardzo proste do  zaimplementowania właściwie tylko przepisujesz równanie. Trzeba trochę pokombinować z rozwiązaniem iteracyjnym.
+1 głos
odpowiedź 6 stycznia 2016 przez Dorion300 Szeryf (90,250 p.)
edycja 6 stycznia 2016 przez Dorion300

Mam nadzieję że za pomocą tego kodu zrozumiesz o co mniej więcej chodzi, że to łatwe jest jak się spojrzy z innej strony.
 

#include <iostream>
#include <conio.h>

using namespace std;

int C(int x)
{
    if(x == 1) return 2;
    if(x == 2) return 5;
    return 2*C(x-1) - C(x-2);
}

int main()
{
    cout << C(10) << endl;
    cout << C(5);
    getch();
    return 0;
}

 

0 głosów
odpowiedź 6 stycznia 2016 przez kacperoo7 Nowicjusz (200 p.)
Bardzo dziękuję za pomoc i jasne wytłumaczenie problemu.

Podobne pytania

0 głosów
2 odpowiedzi 274 wizyt
pytanie zadane 12 października 2016 w Algorytmy przez j0nasz Nowicjusz (190 p.)
0 głosów
7 odpowiedzi 2,022 wizyt
pytanie zadane 16 września 2015 w Algorytmy przez emSon Stary wyjadacz (10,480 p.)
0 głosów
1 odpowiedź 286 wizyt
pytanie zadane 10 października 2021 w C i C++ przez yato_ Początkujący (350 p.)

92,452 zapytań

141,262 odpowiedzi

319,079 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!

...