Mostrando postagens com marcador Torres de Hanói. Mostrar todas as postagens
Mostrando postagens com marcador Torres de Hanói. Mostrar todas as postagens

sábado, 21 de setembro de 2013

Torres de Hanói: Computando o número de movimentações


Em posts anteriores, apresentamos a descrição indutiva para o problema das Torres de Hanói e provamos que o número mínimo de movimentações necessárias para resolver o problema é $2^n - 1$, onde n é o número de discos. Agora, vamos usar a descrição indutiva já discutida para calcular o número de movimentações necessárias, mas com um detalhe, o número de movimentações será calculado no momento em que as movimentações forem feitas. Nosso objetivo é apresentar o significado de "fortalecimento da hipótese de indução".

Fortalecer uma hipótese, significa assumir que ela realiza algo a mais quando comparada à hipótese original. Ou seja, além de assumirmos que a proposição P(n-1) é válida, também assumiremos uma condição C(n-1) e em seguida estenderemos nossa solução para P(n) e C(n).

Para um pleno entendimento do tema tratado aqui, não deixem de ler os posts:
Siga o Inductioncode no Twitter: 

Descrição indutiva:

  • Caso Base: para n = 0, temos que o número de movimentações é 0.
  • Hipótese de Indução: vamos assumir que sabemos como mover n-1 discos, e como condição extra vamos assumir que o número de movimentações está armazenado em uma variável que chamaremos de numMoves.
  • Caso Geral: No passo indutivo, vamos estender a solução para o caso geral. Para isso, após realizar uma movimentação, basta incrementar a variável numMoves.
A implementação que apresentaremos em Java, segue exatamente a ideia apresentada acima.

  • Implementação em Java
public static int numMoves = 0;
static void hanoi(int n, char A, char B, char C) {
  if (n > 0) {
    hanoi(n - 1, A, C, B);
    System.out.println("Mova o disco " + n + " de " + A + " para " + B);
    numMoves++;
    hanoi(n - 1, C, B, A);
  }
}

Em breve, falaremos mais sobre o fortalecimento da hipótese de indução. Aguardem.
@inductioncode

terça-feira, 3 de setembro de 2013

Torres de Hanói: O número mínimo de movimentações é $2^n$-1

Continuando a série de posts sobre torres de Hanói e indução, vamos provar que o número mínimo de movimentações necessárias para resolver o problema é $2^n - 1$.

A prova é por indução em n:

  • Caso Base: Para n = 0, temos $2^0-1 = 0$.
  • Hipótese de Indução: Vamos supor que para mover n-1 discos entre quaisquer 2 pinos sejam necessárias $2^{n-1}-1$ movimentações.
  • Caso Geral: Para compor o caso geral teremos que considerar o custo para mover n-1 discos para um pino auxiliar ($2^{n-1}-1$ movimentações), o custo para mover 1 disco para o pino final (1 movimentação) e o custo para mover os n-1 discos do pino auxiliar para o pino final ($2^{n-1}-1$ movimentações), ou seja
                                                      Nº de movimentações =  $\underbrace{(2^{n-1}-1) + (2^{n-1}-1)}_\text{Hipótese de Indução} + 1$
                                                                                                     
                                                                                    = $2(2^{n-1}-1) + 1$

                                                                                    = $(2^n -2) + 1$

                                                                                    = $2^n -1$     C.Q.D.

segunda-feira, 19 de agosto de 2013

Torres de Hanói em Haskell

Neste post, apresentarei uma implementação em Haskell do jogo conhecido como Torres de Hanói. Uma descrição completa com implementações em java e python já foi apresentada e discutida em outra postagem, para acessá-la clique aqui.

Torre de Hanói
  • Implementação em Haskell

hanoi :: Char -> Char -> Char -> Int -> IO()
hanoi a b c 0 = putStr ""
hanoi a b c n = do (hanoi a c b (n-1))
                   putStrLn ("Mova o disco " ++ (show n) ++ " de " ++ (show a) ++" para " ++ (show b))
                   (hanoi c b a (n-1)) 


Curtam a nossa fanpage no facebook: InductionCode no Facebook

quinta-feira, 28 de junho de 2012

Torres de Hanói

Agora, vamos resolver indutivamente o problema das Torres de Hanói. Muita gente conhece o jogo, mas não sabe como resolvê-lo computacionalmente. As regras são as seguintes:
  1. Devemos mover um disco de cada vez.
  2. Um disco maior não pode ser colocado sobre um disco menor.
Usando indução, a solução computacional para o problema é quase trivial.
Idéia indutiva:
  • Caso Base: para zero disco, o problema já está resolvido.
  • Hipótese de Indução: vamos supor que o problema pode ser resolvido para n - 1 elementos. Esse truque libera o disco da base (maior disco).
  • Caso Geral: basta invocar a hipótese de indução para mover os n- 1 discos e liberar o disco maior, e em seguida, invocamos a H.I. novamente para mover os n - 1 discos para o destino.
Para esclarecer, vamos analisar um exemplo:

Situação inicial: todos os discos estão em A.


Hipótese de indução 1: vamos supor que os n - 1 discos iniciais serão movidos para o pino C.


Caso trivial: agora ficou fácil mover o disco maior para o destino, ou seja, para o pino B.

Hipótese de indução 2: agora vamos supor que os n - 1 discos que estão em C serão movidos para B.


E assim, chegamos a solução do problema!!!

As implementações decorrem da idéia apresentada acima.
  • Implementação em Python
def hanoi(n, A, B, C):
  if n > 0:
    hanoi(n - 1, A, C, B)
    print "Mova o disco " + str(n) + " de " + A + " para " + B
    hanoi(n - 1, C, B, A)
  • Implementação em Java
static void hanoi(int n, char A, char B, char C) {
  if (n > 0) {
    hanoi(n - 1, A, C, B);
    System.out.println("Mova o disco " + n + " de " + A + " para " + B);
    hanoi(n - 1, C, B, A);
  }
}

Complexidade do algoritmo: vamos derivar a relação de recorrência T(n) = 2T(n - 1) + 1.

$T(n) = 2T(n - 1) + 1$
$T(n) = 2(2T(n - 2) + 1) + 1$
$T(n) = 4T(n - 2) + 2 + 1$
$T(n) = 4(2T(n - 3) + 1) + 2 + 1$
$T(n) = 8T(n - 3) + 4 + 2 + 1$
$...$
$T(n) = 2^n + 2^{n - 1} + 2^{n - 2} + ... + 2^2 + 2^1 + 2^0$
$T(n) = 2^n - 1$
$T(n) = O(2^n)$

Podemos concluir que a complexidade do algoritmo é limitada pela função exponencial. Na prática, se o número de discos for muito grande, a obtenção de uma solução torna-se inviável.