Torres de Hanói – solução iterativa em Java

Você precisa estar logado para dar um feedback. Clique aqui para efetuar o login
Para efetuar o download você precisa estar logado. Clique aqui para efetuar o login
Confirmar voto
0
 (1)  (0)

Neste último artigo da série sobre as “Torres de Hanói”, apresenta-se uma abordagem iterativa para a resolução do problema e a sua codificação em Java.

1. Introdução

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.

2. 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 idéia 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 idéia 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”

Listagem 1: Classe HanoiIterativo
import java.util.Stack;
import java.util.Scanner;

public class HanoiIterativo {

	// pilha de comandos que substitui as chamadas recursivas
	private static Stack pilha = new Stack();

	// 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);

	}

}

Com isto chegamos ao fim de nossa série.
 
Você precisa estar logado para dar um feedback. Clique aqui para efetuar o login
Receba nossas novidades
Ficou com alguma dúvida?