31
edits
Changes
Técnicas Avançadas de Contagem (view source)
Revision as of 23:08, 25 November 2015
, 23:08, 25 November 2015no edit summary
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.
TransferDisk := proc(src::string, via::string,
dest::string, ndisks::posint)
if ndisks = 1 then
PrintMove(src, dest);
else
TransferDisk(src, via, dest, ndisks -1);
PrintMove(src, dest);
TransferDisk(via, dest, src, ndisks -1);
fi;
end:
Finalmente, empacotamos em um procedimento de alto nível, Hanoi, proporcionando assim uma interface para o mecanismo recursivo.
Hanoi := proc(ndisks::posint)
if ndisks < 1 then
printf(`What's wrong with this picture?`);
else
TransferDisk(`A`, `B`, `C`, ndisks);
fi;
end:
Nosso programa Hanoi program consegue exibir uma solução específica para o enigma das Tcan exhibit a specific solution to the Torres de Hanoi para qualquer número n de discos.
Hanoi(2);
Hanoi(3);
Tente experimentar com diferentes valores n de discos para ter uma noção do quão grande o problema se torna mesmo para valores moderadamente grandes de n discos.
'''2. Resolução de recorrências com Maple'''
Agora que sabemos como implementar relações de recorrência em Maple, e temos trabalhado com eles um pouco, vamos ver como usar Maple para resolver certos tipos de relações de recorrência.
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 r_ {k}, 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
<math> r_{n} = a_{1}r_{n-1} + a_{2}r_{n-2} + \cdots + a_{k}r_{n-k} </math>
onde <math> a_{1}, a_{2}, \ldots , a_{k} </math> são constantes reais e <math> a_{k} </math> é diferente de zero. Lembre-se que o inteiro k é chamado de grau da relação de recorrrência. Para ter uma núnica solução, pelo menos o k inicial deve sere especificado.