Seguem alguns comentarios rapidos sobre esse
problema.. Eh provavel que eu tenha errado as contas (nao conferi e fiz meio
rapido), mas desse jeito foi bom que a resposta ficou simpatica..
Chame de x(n) as palavras de n letras sem dois A's
adjacentes.
Quantas palavras x(n+2) existem?
Se a primeira letra for A, há
duas opções para a segunda letra (B ou C) e a partir daí temos x(n)
opções.
Caso contrário, há duas opções
para a primeira letra (B ou C) e a partir daí temos x(n+1) opções.
Logo, x(n+2) = 2x(n+1) + 2x(n) (*)
Usar funções geratrizes em geral
não é uma boa técnica para resolver equações lineares de coeficientes
constantes pq nesse caso tem uma teoria mais prática, muito parecida com a que
voce usa para resolver EDOs..
Sem maiores explicacoes sobre a
teoria (qq coisa, de uma lida na Eureka ou mande um email que eu dou mais
detalhes):
Solucoes da
forma t^n: t^2 - 2t - 2 = 0 => t = 1 +- sqrt(3), logo x(n) =
a(1+sqrt(3))^n + b(1-sqrt(3))^n eh solucao de (*) qq que sejam a,b.
No nosso caso porém, x(1)=3,
x(2)=8 (donde a recorrencia da x(0) = 1) e portanto a+b=1, (a+b) + (a-b)sqrt(3)
= 3 e então
a = (2+sqrt(3))/2sqrt(3) = (1+sqrt(3))^2/8sqrt(3),
b = (-2+sqrt(3))/2sqrt(3) = -(1-sqrt(3))^2/8sqrt(3)
Logo, x(n) = [(1+sqrt(3))^(n+2)
- (1-sqrt(3))^(n+2)]/8sqrt(3)
Mais legal ainda é que, como
(1-sqrt(3))^(n+2) / 8sqrt(3) eh quase sempre muito pequeno, e x(n) eh inteiro,
voce pode concluir que:
n par: x(n) = Piso
{(1+sqrt(3))^(n+2)/8sqrt(3)}
n impar: x(n) = Teto
{(1+sqrt(3))^(n+2)/8sqrt(3)}
|
- [obm-l] Contagem Korshinoi
- RE: [obm-l] Contagem Leandro Lacorte Recôva
- RE: [obm-l] Contagem Johann Peter Gustav Lejeune Dirichlet
- RE: [obm-l] Contagem Leandro Lacorte Recôva
- Re: [obm-l] Contage... Domingos Jr.
- RES: [obm-l] Contagem Rodrigo Maranhão
- [obm-l] Probleminha ciceroth
- Re: [obm-l] Probleminha Domingos Jr.
- Re: [obm-l] Probleminha Johann Peter Gustav Lejeune Dirichlet
- Re: [obm-l] Contagem Domingos Jr.
- Re: [obm-l] Contagem Marcio Afonso A. Cohen
- Re: [obm-l] Contagem Domingos Jr.
- Re: [obm-l] Contage... Johann Peter Gustav Lejeune Dirichlet
- Re: [obm-l] Contagem Johann Peter Gustav Lejeune Dirichlet
- Re: [obm-l] Contagem Johann Peter Gustav Lejeune Dirichlet
- Re: [obm-l] Contagem Leandro Recova
- [obm-l] Contagem andré luiz rodrigues chaves
- Re: [obm-l] Contagem Johann Peter Gustav Lejeune Dirichlet
- Re: [obm-l] Contagem Claudio Buffara
- [obm-l] Contagem Eduardo da Silva