[Algorytmy][C++] Wzór rekurencyjny

[madasu]

Witam,

Mam problem z następującym zadaniem:

Napisać wzór rekurencyjny liczby kroków działania następującego algorytmu, gdzie zakładamy, że
operacją dominującą jest operacja print. Metodą funkcji tworzących znaleźć wzory jawne.

Algorytm w C++:

Kod: Zaznacz cały

void c(int n) {
        if((n == 0) || (n == 1)) 
        {
                print n;
        } 
        else 
        {
                print n;
                c(n-1);
                c(n-1);
                c(n-2);
                c(n-2);
                c(n-2);
        }
}

Z góry dziękuję za pomoc.

[ksisquare]

takie tam zabawy z komputerem

\(\displaystyle{ 1,1,6,\dots}\)

\(\displaystyle{ a_n = 3a_{n-1} +a_{n-2} -3a_{n-3}}\)

\(\displaystyle{ G(a_n)(x)=\frac{2 x^2
- 2 x
+ 1}{3 x^3
- x^2
- 3 x
+ 1}}\)

\(\displaystyle{ a_n=\left[\begin{array}{ccc}1&1&6\end{array}\right] \cdot
\left[\begin{array}{ccc}0&0&-3\\0&1&1\\0&1&3\end{array}\right]^n=
\left[\begin{array}{ccc}a_n&a_{n+1}&a_{n+2}\end{array}\right]}\)

\(\displaystyle{ a_n=\frac{-6-15(-1)^{n+1}+5\cdot 3^{n+1}}{24}}\)