53
edits
Changes
Técnicas Avançadas de Contagem (view source)
Revision as of 10:18, 26 November 2015
, 10:18, 26 November 2015no edit summary
Mais tarde, veremos como usar Maple para obter esse resultado de forma simples.
Além de resolver para o número de movimentos necessários para resolver o enigma das Torres de Hanói para para n discos, podemos ilustrar a solução escrevendo um programa em Maple para calcular os movimentos necessários para resolver o dito problema, e descrevendo-os para nós. Nós vamos escrever um pequeno programa em Maple que consiste em três procedimentos: o principal programa de '''Hanói''', a rotina utilitária '''PrintMove ''', e o mecanismo recursivo do programa '''TransferDisk''', que faz a maioria do trabalho.
A parte mais fácil de escrever é a função '''PrintMove''', que apenas mostra para nós a mudança para fazer em um determinado passo.
PrintMove: = proc (src :: string, dest :: string)
printf (`Mova disco de peg% s para peg% s`, src, dest);
end:
Aqui, nós apenas chamamos o comando '''printf ''' da biblioteca do Maple, que pode ser usado para saída formatada. A função '''printf ''' tem uma sintaxe de chamada complexa; consulte a ajuda online para obter detalhes e informações adicionais. (Nota: Se você estiver familiarizado com a função printf em C, então você vai achar que a versão do Maple do printf é bem semelhante. Neste caso, os símbolos %s acima são substituídos pelos valores de string do segundo e terceiro argumentos, respectivamente.)
Em seguida, o procedimento recursivo '''TransferDisk ''' faz a maior parte do trabalho para nós. Esta função modela a ideia de transferir um disco de um Peg para outro. Mas, porque é recursivo, precisamos fornecer a ele, como um argumento, o número total de discos a serem tratados em cada chamada.
Finalmente, empacotamos em um procedimento uma procedure de alto nível, '''Hanoi''', proporcionando assim uma interface para o mecanismo recursivo.
Hanoi := proc(ndisks::posint)
end:
Nosso programa '''Hanoi program ''' consegue exibir uma solução específica para o enigma Enigma das Tcan exhibit a specific solution to the Torres de '''Hanoi ''' para qualquer número n '''ndisk''' de discos.
Hanoi(2);
Hanoi(3);
Tente experimentar com diferentes valores n de discos '''ndisk''' para ter uma noção do quão grande o problema se torna mesmo para valores moderadamente grandes de n discos'''ndisks'''.
Maple tem um poderoso solucionador de recorrência, rsolver, que discutiremos mais tarde. A sua utilização, no entanto, pode obscurecer algumas das ideias importantes que estão envolvidas. Portanto, devemos primeiro usar algumas das instalações mais rudimentares do Maple para resolver certos tipos de relações de recorrência, um passo de cada vez.
Dada uma seqüência definida recursivamente <math> {r_ {n}} </math>, o que nós gostaríamos é encontrar algum tipo de fórmula, envolvendo apenas o índice n (e, talvez, outras constantes fixas e funções conhecidas) que não dependem do conhecimento da valor de <math>r_ {k}</math>, por qualquer índice k.
Para começar, vamos considerar relações de recorrência que são lineares, homogêneas, e que têm coeficientes constantes; ou seja, eles têm a forma
O método geral para resolver tal relação de recorrência envolve encontrar as raízes de sua seu polinômio característico.l
<math> x^{k} - a_{1}x^{k-1} - a_{2}x^{k-2} - \cdots - a_{k-1}x - a_{k} </math>
sujeitos às condições iniciais
<math> r_{1} = 4 \hspace{3em}\mbox{</math> and}\hspace{3em} <math> r_{2} = 2 </math>
Então sua equação caracerística é Then its characteristic equation is:
<math> x^{2} - 2x - 3 </math>
solve (x ^ 2-2 * x - 3 = 0, x);
A sintaxe diz à função que queremos os valores da variável x que '''satisfazem ''' a equação quadrática.
'''<math> ''x ^ 2-2 * x - 3 = 0.'' </math>'''
Agora que o Maple aponta que as soluções são <math>x = 3 </math> e <math>x = -1</math>, podemos escrever a forma de a solução para a recorrência como
<math> r_ {n} = \ alpha 3 ^ {n} + \ beta (-1) ^ {n} </math>
onde \ alpha e \ beta são constantes que ainda temos de determinar. Podemos usar Maple para determinar as constantes \ alpha e \ beta. Uma vez que as condições iniciais são <math> r_ {1} = 4 e r_ {2} = 2 </math>, sabemos que a nossa relação de recorrência deve satisfazer as seguintes duas equações.
<math> 3 \ alpha - \ beta = 4 </math><math> 3 ^ {2} \ alpha + \ beta = 2 </math>