Rekurencja, problem ze zrozumieniem algorytmu

Question

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 :)

Answer 1

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 ) )

Answer 2

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.

Answer 3

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;
}

 

Answer 4

Bardzo dziękuję za pomoc i jasne wytłumaczenie problemu.