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: Seguir @inductioncode
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.
- 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
Nenhum comentário:
Postar um comentário