TORRES DE HANOI
Enviado por victored1982 • 18 de Junio de 2014 • 828 Palabras (4 Páginas) • 418 Visitas
Torres de Hanói
Se trata de un juego de ocho discos de radio creciente que se apilan insertándose en una de las tres estacas de un tablero. El objetivo del juego es crear la pila en otra de las estacas siguiendo unas ciertas reglas.
Mover N discos de origen a destino
• Mover (N-1) discos de origen a auxiliar
• Mover 1 disco origen a destino
• Mover (N-1) disco de auxiliar a destino
El diagrama de Flujo del algoritmo (N,origen,destino)
El pseudocódigo de este algoritmo es el siguiente
Hanoi (N, origen,destino)
Si N >1
Auxiliar ← TorreLibre(origen,destino)
Hanoi (N-1,origen,auxiliar)
Print “mover 1 disco de origen a destino
Hanoi(N-1,auxiliar,destino)
En caso contrario
Print “mover 1 disco de origen a destino”
Para calcular la torre auxiliar, dadas un origen y destino cualquiera sabemos que tenemos las siguientes posibilidades:
TORRES DE HANOI
ORIGEN DESTINO AUXILIAR
A B C
A C B
B A C
B C A
C A B
C B A
El diagrama de flujo para calcular la TorreLibre(origen,destino) es el siguiente:
Lo implementamos en Java con la aplicación eclipse:
package hanoi;
/**Programa para resolver el problema de las torres de Hanoi
* @author Nessy */
public class Hanoi {
/**Este método permite determinar qué torre se puede utilizar como auxiliar
* para los movimientos intermedios dadas unas torres de orígen y destino
* cualquiera
* @param origen Torre de origen de los discos.
* @param destino Torre de destino de los discos
* @param auxiliar Torre auxiliar de los discos
*/
static public char torreDisponible(char origen,char destino){
char auxiliar;
if((origen !='A')&& (destino!='A')){
auxiliar='A';
}else if ((origen !='B')&& (destino!='B')){
auxiliar='B';
}else{
auxiliar='C';
}
return auxiliar;
}
/**Resolución del problema de las Torres de Hanoi para el caso de tener n discos y unas torres de origen y destino arbitrarias
* @param n Número de discos a mover.
* @param origen Torre donde están inicialmente los discos
* @param destino Torre a la que mover los discos*/
static public void resolverHanoi(int n,char origen,char destino){
/**n es el número de discos a resolver*/
if(n>1){
char auxiliar =torreDisponible(origen,destino);
resolverHanoi((n-1),origen,auxiliar);
System.out.println("Mover disco de " + origen + " a "+ destino);
resolverHanoi((n-1),auxiliar,destino);
}else{
System.out.println("Mover disco de " + origen + " a "+ destino);
}
}
public static void main(String[] args) {
/*con esta línea compruebo que el método torreDisponible funciona correctamente
* al enviarle las torres que tengo como origen y destino*/
//System.out.println(torreDisponible('A','B'));
resolverHanoi(4,'A','C');
}
}
Vamos a introducir los cambios necesarios en el programa para que nos indique el número de movimientos realizados.
...