31
edits
Changes
Técnicas Avançadas de Contagem (view source)
Revision as of 11:57, 25 November 2015
, 11:57, 25 November 2015no edit summary
No capítulo 3 descobrimos como representar de forma eficiente a seqüência de Fibonacci pelo procedimento:
Fibonacci := proc(n::posint) option remember;
if n = 1 or n = 2 then RETURN( 1 ); fi;
Fibonacci2(n-1) + Fibonacci2(n-2);
end:
Lembre-se que a primeira linha deste procedimento instrui a Maple de lembrar que quaisquer sejam os valores do processo já foram calculado na sessão atual.
Às vezes, apesar de nossos melhores esforços, uma aplicação recursiva de um algoritmo pode ser muito caro, simplesmente devido à sua própria natureza. A aplicação recursiva pode ser evitado se podemos encontrar uma fórmula explícita para o termo geral da recorrência. O processo de encontrar uma fórmula explícita é referido como resolver a recorrência. Na próxima seção, veremos como usar Maple para fazer isso por certos tipos de relações de recorrência.
'''== 1.1 Torre de Hanoi =='''
O famoso enigma conhecido como Torre de Hanoi é discutido no texto, onde a relação de recorrência
H_{n} = 2H_{n - 1} + 1, \hspace{3ex} H_{1} = 1
é derivada, em que H_ {n} indica o número de movimentos necessários para resolver o enigma para n discos. Como discutido no texto, este tem a solução
H_} {n = 2 ^ {n} - 1
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.