Recorrência Linear

Nesse artigo vamos apresentar vários conteúdos produzidos pela comunidade brasileira sobre Recorrência Linear.

Conteúdos em vídeo

Code Marathon

Recorrência Linear - Code Marathon

Com estes vídeos é possível aprender como resolver as seguintes recorrências em O(log(N)).

fib(n) = \begin{Bmatrix} 1 & \text{se} \; n \le 1\\ fib(n-1) + fib(n-2) & \text{se} \; n \gt 1 \end{Bmatrix}

f(n) = \begin{Bmatrix} 1 & \text{se} \; n \le 1\\ 4 \cdot f(n-1) + f(n-2) + 5 & \text{se} \; n \gt 1 \end{Bmatrix}

g(n) = \begin{Bmatrix} 1 & \text{se} \; n = 0\\ 5 \cdot g(n-1) + n^2 +n + 3 & \text{se} \; n \gt 0 \end{Bmatrix}

Código da Exponenciação de Matrizes

const int D = 3;
const int MOD = 1000000007;
struct Matriz{
  int mat[D][D];
  int* operator[](int i){
    return mat[i];
  }
  Matriz operator*(Matriz oth){
    Matriz res;
    for(int i=0; i<D; i++){
      for(int j=0; j<D; j++){
        res[i][j] = 0;
        for(int k=0; k<D; k++)
          res[i][j] = (res[i][j]+(mat[i][k]*1LL*oth[k][j])%MOD)%MOD;
      }
    }
    return res;
  }
  Matriz exp(long long e){
    Matriz res;
    for(int i=0; i<D; i++)
      for(int j=0; j<D; j++)
        res[i][j] = (i==j);    
    Matriz base = *this;  
    while(e > 0){
      if(e & 1LL)
        res = res * base;
      base = base*base;
      e = e>>1;
    }
    return res;
  }
};

MaratonUSP

Exponenciação Rápida e Recorrência Linear

Tópicos da aula:

• Exponenciação Rápida
• Recorrências Lineares

Material Complementar

• Portal OBMEP - Recorrências