Instituto Politécnico Nacional
UNIDAD PROFESIONAL INTERDISCIPLINARIA DE
INGENIERÍA CAMPUS ZACATECAS
INGENIERÍA EN SISTEMAS COMPUTACIONALES
Docente: Mayra Alejandra Torres Hernández
Materia: Estructura de Datos
Luis Alfredo Castañeda Fernández
Grupo: 1CM1
Torres de Hanoi
Las Torres de Hanoi es un rompecabezas matemático donde tenemos tres barras y
“n” discos. El objetivo del rompecabezas es mover toda la pila a la barra final,
obedeciendo las siguientes reglas simples:
1) Solo se puede mover un disco a la vez.
2) Cada movimiento consiste en tomar el disco superior de una de las pilas y
colocarlo encima de otra pila, es decir, un disco solo se puede mover si es el
disco superior de una pila.
3) No se puede colocar ningún disco encima de un disco más pequeño.
Representación grafica
Entradas y Salidas
La entrada es el numero de discos y la salida el orden de los
movimientos.
Entrada: 2
Salida:
Mueva el disco 1 desde A hasta B
Mueva el disco 2 desde A hasta C
Mueva el disco 1 desde B hasta C
Entrada: 3
Salida:
Mueva el disco 1 desde A hasta C
Mueva el disco 2 desde A hasta B
Mueva el disco 1 desde C hasta B
Mueva el disco 3 desde A hasta C
Mueva el disco 1 desde B hasta A
Mueva el disco 2 desde B hasta C
Mueva el disco 1 desde A hasta C
Código
#include <iostream>
using namespace std;
void hanoi(int num, char A, char C, char B){
if(num == 1){
cout << "Mueva el bloque " << num << " desde " << A <<
" hasta " << C << endl;
}
else{
hanoi(num - 1, A, B, C);
cout<<"Mueva el bloque " << num << " desde " << A << "
hasta " << C << endl;
hanoi(num-1, B, C, A);
}
}
int main(){
int n;
cout<<"Las barras son A B C"<<endl;
cout<<"Numero de discos: ";
cin>>n;
hanoi(n,'A','C','B');
return 0;
}
Recorrido del caballero
El recorrido de un caballero o la vuelta del caballo es una secuencia de movimientos
donde el caballero se coloca en el primer bloque de un tablero vacío y, moviéndose
de acuerdo con las reglas del ajedrez, debe visitar cada casilla exactamente una
vez.
Representación grafica
En esta representación de un tablero de ajedrez de 8 x 8 celdas los
números en las celdas indican el número del movimiento del caballero.
Salida
0 59 38 33 30 17 8 63
37 34 31 60 9 62 29 16
58 1 36 39 32 27 18 7
35 48 41 26 61 10 15 28
42 57 2 49 40 23 6 19
47 50 45 54 25 20 11 14
56 43 52 3 22 13 24 5
51 46 55 44 53 4 21 12
Código
#include <iostream>
#include <iomanip>
#define N 8
using namespace std;
int sol[N][N];
bool esValido(int x, int y, int sol[N][N]){
return(x >= 0 && x < N && y >= 0 && y < N && sol[x][y] == -1);
}
void imprimirSolucion(){
for(int x = 0; x < N; x++) {
for(int y = 0; y < N; y++)
cout << setw(3) << sol[x][y] << " ";
cout << endl;
}
}
int vueltaCaballo(int x, int y, int move, int sol[N][N], int
xmov[N], int ymov[N]) {
int xsig, ysig;
if (move == N*N)
return true;
for (int k = 0; k < 8; k++){
xsig = x + xmov[k];
ysig = y + ymov[k];
if (esValido(xsig, ysig, sol)){
sol[xsig][ysig] = move;
if (vueltaCaballo(xsig, ysig, move+1, sol, xmov, ymov) ==
true)
return true;
else
sol[xsig][ysig] = -1;
}
}
return false;
}
bool buscarSolucion(){
for (int x = 0; x < N; x++)
for (int y = 0; y < N; y++)
sol[x][y] = -1;
int xmov[8] = {2, 1, -1, -2, -2, -1, 1, 2};
int ymov[8] = {1, 2, 2, 1, -1, -2, -2, -1};
sol[0][0] = 0;
if (vueltaCaballo(0, 0, 1, sol, xmov, ymov) == false) {
cout << "La solucion no existe" << endl;
return false;
}
else
imprimirSolucion();
return true;
}
int main(){
buscarSolucion();
return 0;
}
Laberinto
Un laberinto se proporciona como una matriz binaria N * N de bloques donde el bloque de
origen es el bloque más a la izquierda superior, es decir, la posición [0] [0] y el bloque de
destino es el bloque inferior derecho, es decir, la posición [N-1] [N-1]. Una rata comienza
desde el origen y tiene que llegar al destino. La rata solo puede moverse en dos direcciones:
hacia adelante y hacia abajo. En la matriz del laberinto, 0 significa que el bloque es un
callejón sin salida y 1 significa que el bloque puede usarse en la ruta desde el origen hasta
el destino. Esta es una versión simple del típico problema de un laberinto. Por ejemplo, una
versión más compleja puede ser que la rata puede moverse en 4 direcciones y una versión
más compleja puede ser con un número limitado de movimientos.
Representación grafica
Los bloques grises son callejones sin salida (valor = 0).
Representación matricial
{1, 0, 0, 0}
{1, 1, 0, 1}
{0, 1, 0, 0}
{1, 1, 1, 1}
Matriz de solución (salida del programa) para la matriz de entrada anterior
{1, 0, 0, 0}
{1, 1, 0, 0}
{0, 1, 0, 0}
{0, 1, 1, 1}
Todas las entradas en la ruta de solución están marcadas como 1.
Código
#include<iostream>
#define N 4
using namespace std;
bool resolverLaberintoFuncion(int maze[N][N], int x, int y, int
sol[N][N]);
void imprimirSolucion(int sol[N][N]){
for (int i = 0; i < N; i++){
for (int j = 0; j < N; j++)
cout<<sol[i][j]<<"";
}
cout<<endl;
}
bool esValido(int maze[N][N], int x, int y){
if(x >= 0 && x < N && y >= 0 && y < N && maze[x][y] == 1){
return true;
}
return false;
}
bool resolverLaberinto(int maze[N][N]){
int sol[N][N] = { {0, 0, 0, 0},
{0, 0, 0, 0},
{0, 0, 0, 0},
{0, 0, 0, 0}};
if(resolverLaberintoFuncion(maze, 0, 0, sol) == false){
cout << "La solucion no existe" << endl;
return false;
}
imprimirSolucion(sol);
return true;
}
bool resolverLaberintoFuncion(int maze[N][N], int x, int y, int
sol[N][N]){
if(x == N-1 && y == N-1){
sol[x][y] = 1;
return true;
}
if(esValido(maze, x, y) == true){
sol[x][y] = 1;
if (resolverLaberintoFuncion(maze, x+1, y, sol) == true)
return true;
if (resolverLaberintoFuncion(maze, x, y+1, sol) == true)
return true;
sol[x][y] = 0;
return false;
}
return false;
}
int main(){
int maze[N][N] = { {1, 0, 0, 0},
{1, 1, 0, 1},
{0, 1, 0, 0},
{1, 1, 1, 1}};
resolverLaberinto(maze);
return 0;
}
