53
edits
Changes
Jump to navigation
Jump to search
Técnicas Avançadas de Contagem (view source)
Revision as of 16:59, 3 December 2015
, 16:59, 3 December 2015no edit summary
sujeito às condições iniciais
<math> r_{1} = u \hspace{3em}\mbox{and}\hspace{3em} r_{2} = v </math>
e, em seguida, retorna um procedimento que pode ser utilizado para calcular termos da sequência.
Antes de olharmos para a nova versão do RecSol2, vamos olhar para um exemplo envolvendo uma relação de recorrência com um valor double próprio (raiz de seu polinômio característico). A relação de recorrência
<math> r_} r_n = 4r_{(n = 4 r_ {N-1)} - 4 r_ 4r_{N(n-2)} </math>
tem a equação característica
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 estendidas para fornecer soluções para as recorrências heterogêneas deste tipo. Estas são relações de recorrência da forma
<math>\ alpha_ alpha{n} r_ {n} + \ alpha_ alpha{n-1} r_ {n-1} + \ cdots + \ alpha_ alpha{nkn-k} r_{r_ nkn-k} = 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;
A recorrência homogênea correspondente é apenas a obtida substituindo a sequência <math> c_ {{n}} </math> pela sequência zero:
<math>/alpha_ \alpha{n} r_ {n} + /alpha_ \alpha{n-1} r_ {n-1} + \ cdots + /alpha_ \alpha{nkn-k} r_{r_ nkn-k} = 0 </math>
Então, nós já sabemos como fazer o segundo passo.
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 Hanoi
