31
edits
Changes
Técnicas Avançadas de Contagem (view source)
Revision as of 08:38, 30 November 2015
, 08:38, 30 November 2015no edit summary
k := RecSolver2(-1, -1, lambda, mu);
i := 'i': seq(simplify(k(i)),i=1..10);
'''2.2. Relações de recorrência heterogêneas'''
Nós temos, até agora, discutido relações de recorrência lineares homogêneas com coeficientes constantes. No entanto, as técnicas utilizadas para resolvê-los podem ser extendidas para fornecer soluções para as recorrências heterogêneas deste tipo. Estas são relações de recorrência da forma
math>\ alpha_ {n} r_ {n} + \ alpha_ {n-1} r_ {n-1} + \ cdots + \ alpha_ {nk} {r_ nk} = c_ {n} </math>
onde <math>\ alpha_ {n}, \ alpha_ {n-1}, \ ldots, \ alpha_ {nk} e c_ {n} </math> são constantes. A única nova problemática é que, aqui, o <math>c_ {n}<math> não precisa ser zero. Dito de outra forma, uma equação desta forma, na qual cada <math>c_ {n}</math> é zero é homogênea, por isso as relações homogêneas são apenas um caso especial deste tipo mais geral. Para resolver a recorrência mais geral, precisamos fazer duas coisas:
1) Encontrar uma solução específica para a recorrência heterogênea
2) Resolver a recorrência homogênea correspondente.
A recorrência homogênea correspondente é apenas a obtida substituindo a sequência <math>\ c_ {{n} \} </math> pela seqüência zero:
<math>\ alpha_ {n} r_ {n} + \ alpha_ {n-1} r_ {n-1} + \ cdots + \ alpha_ {nk} {r_ nk} = 0 </math>
Então, nós já sabemos como fazer o segundo passo.
O primeiro passo é mais difícil, mas com a ajuda do Maple, ele manejável.
rSolve (R (0) = 0, r (n) = 3 * r (n-1) + 3 ^ N, r (n));
normal (%, expanded);
Isso nos diz que <math>r_ {n} = n3 ^ n </math> é uma solução para a relação de recorrência <math>r_ {n} = 3r_ {n-1} + 3 ^ n</math>. Agora, todas as soluções são obtidos por adição de uma solução para este conjunto de soluções da recorrência homogênea correspondente.
rSolve (r (n) = 3 * r (n-1), r (n));
% + * 3 N ^ N;
Se temos um valor inicial para <math>r_ {0}</math>, então nós temos uma solução completa.
Agora vamos resolver a Torre de Hanói
<math>H_} {n = 2H_ {N-1} + 1</math>
o que dá o número de movimentos necessários para resolver o enigma da Torres de Hanói com n discos. Lembre-se que <math>H_ {1} = 1.</math> A relação de recorrência homogênea associada é
<math>h_ {n} = 2 h_ {n - 1}</math>
com polinômio característico
<math>x - 2</math>
A única raiz disso é 2, portanto, todas as soluções da relação de recorrência homogênea têm a forma
<math>h_ {n} = \ alpha 2 ^ {n - 1}</math>
para alguma constante <math>\ alfa </math>. (A potência de 2 é N-1, em vez de N, porque a recorrência começa no 1 em vez de 0.) Soluções para a H são obtidos a partir das soluções para h por adição de uma solução particular para H. Agora, H tem a solução constante <math>H_ N} = {-1</math>, para todo n, então todas as soluções para a H são da forma
<math>H_ {n} = \ alpha 2 ^ {n} - 1</math>
Usando a condição inicial
<math>H_ {1} = 1</math>
podemos resolver para <math>\ alpha</math> como se segue.
solve (alfa * 2 ^ 1 - 1 = 1, alfa);
Assim, a solução para as Torres de Hanói é <math>H_ {n} = 2 ^ {n-1} - 1</math>.