sábado, 14 de julio de 2012

Práctica. Las Torres de Hanoi



Introducción:

Codigo fuente
soltorresframe.zip

Cuenta la leyenda que los monjes budistas del monasterio de Hanoi (en Corea), tenían tres postes de plata, como en el dibujo. Los monjes tenían sesenta y cuatro discos de oro que originalmente se encontraban apilados en el poste izquierdo, de mayor a menor diámetro. Cada día, los monjes movían un disco de un poste a otro, siguiendo estas reglas:
  1. Sólo se puede tomar el disco de arriba de la pila,
  2. sólo se puede tomar un disco a la vez, y
  3. un disco sólo puede ser colocado arriba de la plataforma o de un disco de mayor diámetro.

El objetivo de los monjes era que, eventualmente, todos los discos quedaran en el poste derecho. La leyenda indica que el día que eso ocurra, el universo cesará de existir.

Instrucciones:
  1. Utilizando monedas u otra versión física de las torres, resuelve de modo manual el problema para diferente número de discos. Asegúrate de encontrar el menor número de movimientos posibles para cada cantidad de discos.

  1. Corre el ejemplo que se te proporciona de SolTorresFrame.zip, este archivo incluye los archivos con extensión .class para ejecutar la solución como java TorresFrame

  1. Encuentra una solución recursiva para resolver el problema de las torres dado un número determinado de discos. En este mismo documento se incluye el código de las diferentes clases que necesitas, o puedes bajarlos de FuenteTorresFrame.zip dentro del material de este curso.

  1. Escribe un programa de consola que lea del teclado el número de discos y muestre en pantalla los movimientos necesarios para resolver el problema, como se muestra en este ejemplo:

Dime el numero de discos: 3
Los movimientos son:
Mover un disco de Izquierda a Centro
Mover un disco de Izquierda a Derecha
Mover un disco de Centro a Derecha.

Recuerda documentar tu programa con JavaDoc y seguir las convenciones de estilo.

  1. Reto: El archivo FuenteTorresFrame.zip contiene clases para la implementación de una versión gráfica de las torres de Hanoi. Con base en tu solución de consola, completa la clase Hanoi.java para resolver el problema de las torres de Hanoi. Los códigos que se encuentran en el zip, se incluyen en este documento para mayor facilidad.
Para ver como se debe comportar este programa, descomprime el archivo SolTorresFrame.zip dentro de un directorio y ejecuta el siguiente java TorresFrame:

TorresFrame.java

import java.awt.*;
import java.awt.event.*;
/**
* Programa autónomo para las torres de Hanoi.
*
* @author Maestros computación II
* @version Primavera 2003
*/
public class TorresFrame extends Frame implements ActionListener,
WindowListener {
private Button b1, b2;
private Label l1;
private TextField t1;
private Hanoi h;
private boolean resolver;
/**
* Método principal: se ejecuta al iniciar el programa
*/
public static void main(String[] args) {
TorresFrame f = new TorresFrame();
f.setSize(500,500);
f.setVisible(true);
}
/**
* Constructor: inicializa el frame
*/
public TorresFrame() {
setTitle("Las torres de Hanoi");
setLayout(new FlowLayout());
this.addWindowListener(this);
b1= new Button("# discos");
b2 = new Button("Resolver");
l1 = new Label("Número de discos");
t1 = new TextField(10);
h = new Hanoi(4); /* cuatro discos en la torre */
add(l1);
add(t1);
add(b1);
add(b2);
b1.addActionListener(this);
b2.addActionListener(this);
resolver = false;
t1.setText("4");
}
/**
* dibujar el contenido del frame
*
* @param g the Graphics object for this frame
*/
public void paint(Graphics g) {

h.dibuja(g);
if(resolver) {
h.resuelve(g);
}
}
/**
* Cazador de eventos
* @param e el evento ocurrido
*/
public void actionPerformed(ActionEvent e) {
int n;
if (e.getSource() == b1) {
n = Integer.parseInt(t1.getText());
if ((n >= 1) && (n <= 10))
h = new Hanoi(n); //crear un juego de n discos
}
if (e.getSource() == b2) {
if(!resolver) {
b2.setLabel("Reiniciar");
b1.setEnabled(false);
else {
h.reinicia();
b2.setLabel("Resolver");
b1.setEnabled(true);
}
resolver = !resolver;
}
repaint();
}
//Eventos de ventana, en este caso solo usamos WindowClosing
/**
* Captura windowClosing cierra la aplicación al capturar este evento.
*
* @param e WindowEvent
*/
public void windowClosing(WindowEvent e){
System.exit(0);
}
public void windowIconified(WindowEvent e){
}

public void windowOpened(WindowEvent e){
}
public void windowClosed(WindowEvent e) {
}

public void windowDeiconified(WindowEvent e) {
}
public void windowActivated(WindowEvent e) {
}
public void windowDeactivated(WindowEvent e) {
}
}

Hanoi.java. Este es el código que debes completar:

import java.awt.*;
/**
* Solución gráfica para el problema de las Torres de Hanoi
* El juego acepta entre 1 y 10 discos
*
* @author Maestros computación II
* @version Primavera 2003
*/
public class Hanoi {

private int n;
private Poste izq, cen, der;

/**
* Constructor
* @param n número de discos en la torre inicial
*/
public Hanoi(int n) {
this.n = n;
izq = new Poste(n, 80);
cen = new Poste(0, 250);
der = new Poste(0, 420);
}

//-------------------------------------------------------------
// INTERFAZ
/**
* Resolver el problema
* Pre: hay discos en poste izquierdo
* @param g el espacio grafico
*/
public void resuelve(Graphics g) {

solucion(n, izq, der, cen, g);
}
/**
* Dibujar el tablero de juego
* @param g el espacio gráfico
*/
public void dibuja(Graphics g) {

izq.dibuja(g);
cen.dibuja(g);
der.dibuja(g);
}
/**
* Regresa los discos al estado inicial
*/
public void reinicia() {

izq.ponDiscos(n);
der.ponDiscos(0);
cen.ponDiscos(0);
}

//-------------------------------------------------------------
// Logica
/**
* Algoritmo para resolver el problema de las torres de Hanoi
* @param n numero de discos a mover
* @param f poste fuente
* @param d poste destino
* @param a poste auxiliar
* @param g ambiente grafico
*/
public void solucion(int n,
Poste f, Poste d, Poste a,
Graphics g) {

//aquí va el código para resolver el problema

}
/**
* Pasar un disco del poste a al poste b
* mostrando el resultado en la pantalla gráfica
* Pre: a tiene al menos un disco
* @param a poste fuente
* @param b poste destino
* @param g ambiente gráfico
*/
public void mover(Poste a, Poste b, Graphics g) {

//esperar para que los movimientos se vean con claridad
try {
Thread.sleep(1000);
catch(InterruptedException e) {
g.drawString("Error en sleep", 100, 100);
}

Disco d;
//toma un disco de a y guárdalo

//pon el disco que guardaste en b

//dibuja los postes a y b
}
}


Disco.java

import java.awt.*;
/**
* Un disco de las torres de Hanoi.
*
* @author Maestros computación II
* @version Primavera 2003
*/
public class Disco {
private int b, h; /*base, altura del disco */

/**
* Constructor
*/
public Disco(int b, int h) {
this.b = b;
this.h = h;
}

/**
* Dibujar el disco en las coordenadas proporcionadas
* @param g espacio gráfico
* @param x posición del centro del disco
* @param y posición de la base del disco
*/
public void dibuja(Graphics g, int x, int y) {
g.setColor(Color.red);
g.fillRoundRect(x-b/2,y-h, b, h,10,10);
g.setColor(Color.black);
g.drawRoundRect(x-b/2,y-h, b, h,10,10);
}
}
Poste.java

import java.awt.*;
/**
* Un poste de las torres de Hanoi.
*
* @author Maestros computación II
* @version Primavera 2003
*/
public class Poste {

private int n;
private int x, y; //coordenadas poste
private int ad, bd; //altura y base del disco más grande
private int ab, ap; //anchos de la base y poste
private Disco disco[]; //discos del poste
/**
* Constructor
* @param n numero inicial de discos
* @param px coordenada x del poste
*/
public Poste(int n, int px) {

this.n = n;
x = px;
y = 500;
ad = 20;
bd = 140;
ab = 150;
ap = 10;
disco = new Disco[10]; //espacio para 10 discos
for(int i= 0; i < n; i++) {
disco[i]= new Disco((int)(bd * (1- 0.1*i)), ad);
}
}
/**
* Reasignar el número total de discos
* @param n nuevo número de discos
*/
public void ponDiscos(int n) {

this.n = n;
disco = new Disco[10];
for(int i= 0; i < n; i++) {
disco[i]= new Disco((int)(bd * (1- 0.1*i)), ad);
}
}
/**
* Agregar un disco al poste
* @param d Disco a agregar
*/
public void agregaDisco(Disco d) {

disco[n] = d;
n++;
}
/**
* Eliminar un disco del poste
* Pre: n>=1;
* @return el disco eliminado
*/
public Disco quitaDisco() {

n--;
Disco d = disco[n];
disco[n] = null;
return d;
}
/**
* Dibujar el poste
* @param g el ambiente gráfico
*/
public void dibuja(Graphics g) {

//borrar fondo
g.setColor(Color.white);
g.fillRect(x-ab/2,500-15*ad, ab, 15*ad);
//dibujar base
g.setColor(Color.black);
g.fillRect(x-ab/2, 500-ad, ab, ad);
//dibujar poste
g.setColor(Color.yellow);
g.fillRect(x-ap/2, 500-15*ad, ap, 14*ad);
//dibujar discos
for(int i = 0; i<n; i++) {
disco[i].dibuja(g, x, 500-ad-i*ad);
}
}
}

No hay comentarios:

Publicar un comentario