Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Como resolver uma relação recorrência usando o método de expansão?

0 votos
18 visitas
perguntada Set 18 em Ciência da Computação por Fabio Fujita (36 pontos)  

Resolva a seguinte relação de recorrência usando o método de expansão:

\( \begin{equation}
T(n) = \begin{cases}
1 & \text{se n=0} \\
1+\sum\limits_{j=0}^{n-1} T(j) & \text{se n>0}
\end{cases}
\end{equation}
\)

Exercício 3.12 apresentado no livro "Introduction to Recursive Programming" de Manuel Rubio-Sanchez, no capítulo 3, página 102.

Compartilhe

1 Resposta

0 votos
respondida Set 18 por Fabio Fujita (36 pontos)  
editado Set 20 por Fabio Fujita

O exercício é um bom exemplo de como podemos simplificar um problema usando o método de expansão em relações de recorrência.

Note que a solução direta da recorrência do enunciado exige a implementação de duas funções recorrentes: uma para T(n) e outra para o somatório \( \sum\limits_{j=0}^{n-1} T(j) \), conforme apresentado a seguir:

def soma(n):
    if n==0 :
        return T(0)
    else:
        return T(n)+soma(n-1)

def T(n):
    if n == 0 :
        return 1 
    else:
        return 1+soma(n-1)

if __name__ == '__main__': 
    n=int(input('Digite o valor de n: '))
    if n<0 :
        print('O valor de n deve ser não negativo')
    else:
        print('O resultado da recursão é: %g' %(T(n)))

Realizando uma expansão parcial, nota-se que:

\( T(0)=1\)
\(T(1)=1+T(0)\)
\(T(2)=1+T(0)+T(1)=T(1)+T(1)=2*T(1) \)
\(T(3)=1+T(0)+T(1)+T(2)=T(2)+T(2)=2*T(2)\)
\(...\)
\(T(n)=2*T(n-1)\)

A solução do problema pode ser simplificada, de forma a não ser mais necessário definir o somatório, conforme a seguir:

def T(n):
    if n == 0 :
        return 1 
    else:
        return 2*T(n-1)

if __name__ == '__main__': 
    n=int(input('Digite o valor de n: '))
    if n<0 :
        print('O valor de n deve ser não negativo')
    else:
        print('O resultado da recursão é: %g' %(T(n)))

No entanto, observando a expansão mais cuidadosamente, nota-se que:

\( T(0)=1\)
\(T(1)=1+T(0) = 2\)
\(T(2)=1+T(0)+T(1)=T(1)+T(1)=2^2 \)
\(T(3)=1+T(0)+T(1)+T(2)=T(2)+T(2)=2*T(2)=2^3\)
.\(..\)
\(T(n)=2*T(n-1)=2^n\)

Portanto, usando o método da expansão, percebe-se que sequer precisamos implementar uma recursão para encontrarmos T(n). Podemos utilizar a implementação da exponenciação já otimizada em Python, simplificando o cálculo e reduzindo o tempo de execução (ou implementar manualmente a operação de exponenciação utilizando algum algoritmo otimizado).

...