sexta-feira, 9 de agosto de 2013

Análise da Torre de Hanói

O matemático Frances Édouar Lucas criou em 1883 um desafio elegante conhecido como Torre de Hanói. Nele temos oito discos, inicialmente empilhados em ordem decrescente em um de seus três pinos. O objetivo é transferir toda a torre para outro pino, movendo um disco de cada vez e nunca movendo um disco maior sobre o menor.





































































































































































































































































































































































































                Lucas agregou ao seu brinquedo a lenda de que uma torre ainda maior conhecida como Torre de Brahma, que supostamente teria 64 discos de ouro, cujos pinos em que eram colocados, teriam a forma de agulhas feitas de diamante. No inicio, Deus teria colocado estes disco de ouro na primeira agulha e ordenado que um grupo de sacerdotes inicia-se a transferência para a terceira agulha seguindo as regras descritas acima. Os sacerdotes trabalham dia e noite nesta tarefa, quando a terminarem, a torre desabara e junto dela o mundo irá acabar.


                Para solucionar o desafio, precisa-se entender como funciona a solução, que consiste em utilizar os 2 pinos vazios trocar de posição, agora surge o questionamento: Quantos movimentos são suficientes para completar a tarefa?

                Utilizando a generalização nós podemos redimensionar o problema para menos, com as Torres de Brahma tendo 64 discos e as de Hanói tendo 8, procura-se a resposta para n discos.  Utilizando pequenas quantidades fica fácil ver como se transfere uma torre contendo um ou dois discos e com uma pequena quantidade de experimentos descobre-se como transferir uma torre de três.

                Incluindo uma notação T para a quantidade de trocas, teremos T(n) para indicar o numero de trocas necessárias através dos pinos seguindo as regras de Lucas, tem-se inicialmente T(0) = 0, T(1) = 1 e T(2) = 3.

                Mudar a perspectiva e tentar um caso maior experimentando com três discos:
























































































































































1. Pela experimentação a melhor opção é mover os dois discos superiores para o pino do meio.
























































































































































2. Espalha-se os dois pinos superiores  com o maior no meio.
























































































































































3. Volta a empilhar no meio para liberar o terceiro pino.
























































































































































NOTA: Aqui se te a primeira pista para se transferir n discos, sabemos que para movimentar dois discos temos 3 movimentos, como visto até agora se confirma que T(2) = 3.

4. O único deslocamento do maior disco para o terceiro pino
























































































































































NOTA: Agora vem a segunda pista para a generalização, aonde o maior disco se movimenta uma única vez, somando no total dos três movimentos já realizados ou T(2) + 1.

5. Volta a espalhar os discos superiores.
























































































































































6. Liberando assim a movimentação do disco do intermediário.
























































































































































7. Terminada a transferência, repare que os passos 7, 6, e 5 são respectivamente os passos 3, 2 e 1 utilizando um pino diferente.
























































































































































NOTA: Tem-se a pista final aonde foram realizados mais três movimentos para os dois discos superiores, repetindo que T(2) = 3, com o total final sendo T(2) + 1 + T(2) = 7.

Buscando um padrão generalizado, para n = 3, temos os (n – 1) discos menores para mudar com T(n-1) movimentos, 1 deslocamento do disco maior e novamente (n – 1) discos menores de volta sobre o maior com mais T(n – 1) movimentos. Aonde se obtém o numero de trocas de discos com no mínimo 2 * T(n - 1) + 1.



Tendo descoberto a formula geral em cima um conjunto de igualdades como o mostrado acima é um caso de recorrência ou relação recursiva, aonde temos o valor limite e a equação de uso geral em termos de valores que o precedem.

Em termos de solução, o ideal seria obter uma resposta direta, analisando os resultados obtidos com a equação recorrente teríamos T(3) = 2*3+1 = 7; T(4) = 2*7+1 = 15; T(5) = 2*15+1 = 31; T(6) = 2*31+1 = 63. A sequencia 0, 1, 3, 7, 15, 31, 63 resulta na dedução de uma nova formula:


Através da indução matemática prova-se a afirmação acima usando o teste para o menor valor de n como base, neste caso T(0) e a partir dele provamos os valores restantes para n > 0, aonde se substitui a chamada recorrente pela nova formula:






Concluída prova, pode-se calcular através da expressão de forma fechada o numero de movimentos necessários facilmente, retornando ao ponto em que os sacerdotes estão movendo os discos da torre de Brahma, sabemos os mesmos terão de realizar 2 elevado a 64 menos 1 movimentos, algo em torno de 18 quintilhões, o que provavelmente explica o motivo nenhum apocalipse Hindu ter ocorrido. E o desafio da torre de Hanói requer 255 movimentos para completar a tarefa.

Encontrar a função matemática para o desafio ajuda na compreensão do problema e como solucionar o mesmo, o assunto será finalizado na próxima postagem com as rotinas que calculam o total de movimentos e um programa que irá descrever passo a passo os movimentos dos discos entre os pinos.

sábado, 27 de julho de 2013

Números de Fibonacci

A sequência:     0, 1, 1, 2, 3, 5, 8, 13, 21, 34,...,

Aonde cada número é a soma dos dois valores precedentes é um exemplo de sequência facilmente calculada pela recursão, os números da sequência são denotados por F(n), e definimos formalmente como:


Esta famosa sequência foi publicada em 1202 por Leonard Pisano (Leonardo de Pisa), também conhecido como Leonardo Fibonacci (Fillius Bonaccii, filho de Bonaccii). Seu Livro do Ábaco contem o seguinte exercício: “Quantos pares de coelhos podem ser produzidos a partir de um par durante um ano?”. Para resolver este problema, pede-se para assumir que cada par gera um novo par, e cada novo par se torna fértil com um mês, alem disso, os coelhos nunca morrem. Após um mês, serão dois pares de coelhos, após dois meses serão três pares, no mês seguinte o par nascido no primeiro mês ira gerar um novo par junto do par inicial e irá ter um total de cinco, e assim prossegue.

                Considere que cada par de coelhos é simbolizado como uma vogal.


JAN
FEV
MAR
ABR
MAI
JUN
JUL












M











H



A



B



E



L













K







C



G











D



J











F















I


ORIGEM
A

B

C

D

E


Simulando o ano temos a tabela com o total de pares de coelhos de cada mês.

Mês
Pares
Total de pares
Jan
A
1
Fev
A
1
Mar
A B
2
Abr
A B C
3
Mai
A B C D E
5
Jun
A B C D E F G H
8
Jul
A B C D E F G H I J K L M
13
...

Simplificado o modelo, voltamos para uma tabela menor, sem o uso de vogais que se mostrariam insuficientes, para o numero crescente de pares.

Jan
Fev
Mar
Abr
Mai
Jun
Jul
Ago
Set
Out
Nov
Dez
1
1
2
3
5
8
13
21
34
55
89
144

                Fibonacci foi um dos grandes matematicos da idade media, ele estudou a obra de al-Khwārizmī (através do qual o termo algoritmo foi criado) e adicionou varias contribuições originais para aritmética e geometria. Antes de Fibonacci ter redigido seu trabalho, os escolares indianos já haviam discutido sobre o a sequência F(n), devido aos interesses dos mesmos por padrões rítmicos. A primeira utilidade pratica para os números de Fibonacci surgiu quando o matemático E. Léger usou a sequência para estudar a eficiência do algoritmo de Euclides, mais tarde outro matemático É. Lucas obteve resultado para provar a validade de números primos utilizando a sequência F(n) que ele chamou de “números de Fibonacci”, e desde então o termo passou a ser utilizado.

                Ao aplicar a definição de números de Fibonacci em uma rotina para C:

typedef unsigned int    uint;

uint fib(uint uN)
{
      if (uN <= 1)
            return uN;
      else
            return ( fib(uN - 1) + fib(uN - 2) );
}

                Observe como a definição recursiva dos números de Fibonacci difere da definição recursiva para calculo de fatorial, com a rotina recursiva fib chamando a si mesma por duas vezes, por exemplo, fib(5) = fib(4) + fib(3), de modo que ao calcular fib(5), a rotina fib será calculada duas vezes, e dentro de fib(4), requer o calculo de fib(3) e fib(2) e assim sucessivamente gerando uma quantidade grande de redundância computacional, com o caso de fib(2) sendo calculada três vezes até retornar a solução de fib(5), se ao programar uma solução, aumenta-se a eficiência ao lembrar valores já calculados anteriormente, utilizando um método iterativo:

uint ifib(uint uN)
{
      uint uX, uPrev, uAns, uTmp;

      if (uN <= 1)
            return uN;

      uPrev = 0;
      uAns = 1;
      for ( uX = 2; uX <= uN; ++uX) {
            uTmp = uAns + uPrev;
            uPrev = uAns;
            uAns = uTmp;
      }

      return uAns;
}

                Diferente do que ocorre no caso da função fatorial, o mesmo numero de multiplicações ocorre para calcular n! por meio das rotinas iterativas e recursivas, ao comparar o numero de adições (não incluindo o do incremento usado pelo loop) efetuadas para calcular fib(5) da rotina iterativa com a recursiva, o método recursivo consome mais recursos que o iterativo, razão que tende a aumentar junto ao avanço da sequência.

Figura. Em uma sequência até 13 fica visível a grande diferença no desempenho entre o numero de adições realizadas pelas rotinas recursiva e iterativa.
                Como discutido anteriormente, uma versão não recursiva de um programa executara com mais eficiência em termos de tempo e espaço do que uma versão recursiva, isso acontece porque o trabalho extra dispendido para entrar e sair de um bloco é evitado, a versão não recursiva pode identificar um numero considerável de variáveis locais e temporárias que não precisam ser salvas e restauradas pelo uso da pilha, o compilador dificilmente consegue identificar tais fatores para eliminar a atividade de empilhamento desnecessária.

                Uma resposta recursiva é em vários casos uma implementação lógica e simples de uma definição apresentada, o que nos leva ao ponto em que a criação da versão não recursiva deve ser criada ao adaptar a solução recursiva simulando o funcionamento, ao invés de buscar diretamente uma resolução não recursiva do enunciado proposto.