Nos dois primeiros artigos da série, o problema das “Torres de Hanói” foi introduzido, e uma solução recursiva para o mesmo foi apresentada, implementada na linguagem Java (classe TorresDeHanoi), tendo ainda o seu funcionamento explicado. O objetivo deste artigo final é apresentar uma abordagem menos convencional para a resolução do problema, que consiste no uso de um algoritmo iterativo.
Solução Iterativa em Java
Muitas vezes, resolver de forma iterativa um problema cuja solução “mais natural” consiste em uma técnica recursiva exige trabalho ou criatividade, ou mesmo as duas coisas! No caso das “Torres de Hanói” é possível utilizar diversas idéias diferentes para realizar a conversão (faça uma busca na Internet e comprove!). Neste artigo mostraremos a maneira mais convencional, que consiste em empregar uma pilha (isto mesmo, a velha e boa estrutura de dados) para empilharmos e desempilharmos o que seriam as chamadas recursivas.
A solução iterativa implementada em Java é apresentada na Listagem 1, na definição da classe HanoiIterativo. Veja que o código fica muito maior do que o necessário para a implementação da solução recursiva. Basicamente, a ideia geral do programa é esta:
- Os comandos são representados em Strings do tipo “n,O,D,T” (n = número de discos, O = pino origem atual, D = pino destino atual, T = pino de trabalho atual).
- Logo no primeiro passo, empilhamos o comando “n, 1, 3, 2” (em nosso jogo, o “pino origem” é o 1, o “pino destino” é o 3 e o “pino de trabalho” é o 2).
- A cada rodada, ao invés de realizarmos uma chamada recursiva, fazemos o seguinte: os parâmetros do que seria a chamada recursiva são concatenados em uma String e esta é empilhada (com o valor de “n” decrementado).
- Sempre que “n” atingir o valor 1, torna-se necessário retirar (desempilhar) um comando da pilha e executar o movimento correspondente.
- O algoritmo encerra a execução quando a pilha estiver vazia.
Observações:
- O código do programa contém diversos comentários para facilitar o entendimento da ideia geral que apresentamos.
- Embora a forma de representar cada comando em uma String não seja a mais “bela”, preferimos esta abordagem a criar um novo tipo para representar um comando. Esta opção - assim como outras escolhas como, por exemplo, o uso dos comandos split e parseInt - foi feita apenas para simplificar o código e dar maior destaque para o que é realmente importante: a técnica iterativa para resolver o problema das “Torres de Hanói”
import java.util.Stack;
import java.util.Scanner;
public class HanoiIterativo {
// pilha de comandos que substitui as chamadas recursivas
private static Stack<String> pilha = new Stack<String>();
// armazena o número no movimento atual
private static long numMov;
// Método que realiza (imprime) o movimento
// de um disco entre dois pinos
private static void mover(int O, int D) {
numMov++;
System.out.println("[" + numMov + "]:" + O + " -> " + D);
}
// método que implementa o algoritmo hanoi iterativo
public static void hanoi(int n) {
int O = 1; // pino origem
int D = 3; // pino destino
int T = 2; // pino trabalho
// monta e empilha o primeiro comando
String comandoAtual = n + "," + O + "," + D + "," + T;
pilha.push(comandoAtual);
// o jogo chega ao fim quando a pilha de comandos estiver vazia!
while (!pilha.empty()) {
// quando n > 1, devemos empilhar um novo comando
if (n > 1) {
// monta o novo comando a ser empilhado
n--;
String[] vetAux = comandoAtual.split(",");
O = Integer.parseInt(vetAux[1]);
D = Integer.parseInt(vetAux[2]);
T = Integer.parseInt(vetAux[3]);
// isto seria uma chamada recursiva...
comandoAtual = n + "," + O + "," + T + "," + D;
// empilha o novo comando
pilha.push(comandoAtual);
// caso contrário, devemos desempilhar
// e executar um movimento
} else {
//desempilha um comando
comandoAtual = pilha.pop();
// separa n, origem, destino e trabalho
String[] vetAux = comandoAtual.split(",");
n = Integer.parseInt(vetAux[0]);
O = Integer.parseInt(vetAux[1]);
D = Integer.parseInt(vetAux[2]);
T = Integer.parseInt(vetAux[3]);
// executa movimento
mover(O, D);
// quando n > 1, é preciso empilhar
// um comando depois do movimento
if (n > 1) {
n--;
// isto seria uma chamada recursiva...
comandoAtual=n + "," + T + "," + D + "," + O;
pilha.push(comandoAtual);
}
}
}
}
// método main para restar o programa!
public static void main(String[] args) {
int n; // número de discos
// recebe o nú mero de discos digitado pelo usuário
Scanner entrada = new Scanner(System.in);
System.out.println("Digite o número de discos: ");
n = entrada.nextInt();
// executa o algoritmo iterativo das Torres de Hanói
HanoiIterativo.hanoi(n);
}
}