53
edits
Changes
Técnicas Avançadas de Contagem (view source)
Revision as of 14:00, 25 November 2015
, 14:00, 25 November 2015no edit summary
==='''1. Relações de recorrência'''===
Uma relação de recorrência descreve uma relação que um membro de uma sequência {<math>{a_n}</math>} de valores tem de outro membro da seqüência que o precedem. Por exemplo, a famosa seqüência de Fibonacci {<math>F_n</math>} satisfaz a relação de recorrência <math>F_{(n)} = F_{(n-1)} + F_{(n-2)}</math>. Juntamente com as condições iniciais <math>F_1 = 1 </math> e <math>F_2 = 1 </math>, esta relação é suficiente para definir toda a seqüência <math>F_n</math>.
Em geral, podemos pensar em uma relação de recorrência como uma relação do formulário
<math>r_{n} = f(r_{n-1}, r_{n-2}, \ldots , r_{n-k})</math>, em que cada termo <math>r_{n}</math> da sequência depende de um número k dos termos que o precedem na seqüência. Por exemplo, para a sequência de Fibonacci, a função F é <math>f(x, y) = y + x</math>.
Para entender como podemos trabalhar com relações de recorrência em Maple, temos de parar por um momento e perceber que uma sequência <math>r_{n}</math> de valores (números, matrizes, círculos, funções, etc.) é apenas uma função cujo domínio passa a ser o conjunto de inteiros (geralmente positivos). Se queremos levar este ponto de vista (e nós queremos!), então o <math>r</math> enésimo termo <math>r_{n}</math> de uma sequência de {<math>r_{n}</math>} seria convencionalmente escrito como <math>r_(n)</math>, e gostaríamos de referir à função r. Desta forma, podemos pensar na seqüência {<math>r_ {n}</math>} como uma forma de representar uma função <math>r</math> cujo domínio é o conjunto de números inteiros positivos, e cujo valor no número <math>n</math> é apenas <math>r_{n} = r(n)</math>. Isto apenas equivale a uma mudança na notação; não há nada mais do que isso.
No capítulo 3 descobrimos como representar de forma eficiente a seqüência de Fibonacci pelo procedimento:
if n = 1 or n = 2 then RETURN( 1 ); fi;
Fibonacci2(n-1) + Fibonacci2(n-2);</pre> 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.
''' 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 <math>H_{n} {</math> indica o número de movimentos necessários para resolver o enigma para n discos. Como discutido no texto, este tem a solução <math>H_n = 2 ^ {n} - 1</math>
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.