PDF de programación - Laboratorio 2: Recursividad

ALED
 -­‐
 Laboratorio
 2
  1
 

LABORATORIO 2: RECURSIVIDAD
 

Objetivos
 

Entender
 el
 comportamiento
 de
 los
 algoritmos
 recursivos
 
Implementación
 y
 modificación
 de
 algoritmos
 recursivos
 
Probar
 el
 consumo
 de
 recursos
 de
 los
 algoritmos
 recursivos
 
Entender
 los
 problemas
 de
 consumo
 de
 memoria
 en
 los
 algoritmos
 recursivos
 

Herramientas
 proporcionadas
 

código.
  Estas
  herramientas
 

En
 el
 moodle
 de
 la
 asignatura
 dispone
 de
 herramientas
 para
 la
 corrección
 automática
 
de
  entregas
  de
 
sensibles
  al
  uso
  de
 
mayúsculas/minúsculas,
  por
 
las
 
instrucciones
  dadas
  en
  este
  guión
  respecto
  al
  nombre
  de
  clases
  y
  métodos.
  Si
  tiene
 
dudas
  sobre
  cómo
  usar
  esta
  herramienta
  puede
  consultar
  alguno
  de
  los
  vídeo-­‐
tutoriales
 (screencast)
 disponibles:
 
 
http://www.lab.dit.upm.es/~prog/screencast/SubirProyectosEclipseAMoodle.flv
 
 

son
 

lo
  que
  deberá
 

respetar
  escrupulosamente
 

Introducción
 

El
 software
 de
 juegos,
 así
 como
 el
 de
 optimización
 o
 el
 de
 búsqueda
 en
 grafos
 suele
 
emplear
 algoritmos
 recursivos.
 

En
  esta
  práctica
  vamos
  a
  trabajar
  con
  algoritmos
  que
  permiten
  crear
  y
  resolver
 
juegos
  de
  laberintos.
  Un
  ejemplo
  de
  este
  tipo
  de
  juegos
  es
  el
  que
  se
  emplean
  en
 
http://algs4.cs.princeton.edu/41undirected/maze.swf
 

Un
 juego
 de
 laberinto
 tiene
 dos
 actividades
 fundamentales:
 construir
 el
 laberinto
 a
 
seguir
 y
 resolver
 el
 laberinto.
 Las
 clases
 con
 las
 que
 trabajaremos
 incluyen
 métodos
 
para
 las
 dos
 actividades.
 Además
 incluyen
 métodos
 para
 dibujar
 los
 laberintos.
 En
 la
 
siguiente
  figura
  tenemos
  un
  ejemplo
  de
  laberinto
  con
  el
  que
  vamos
  a
  trabajar.
 
Algunos
 detalles
 específicos
 de
 los
 laberintos
 con
 los
 que
 trabajaremos
 son:
 

1. La
  posición
  de
  salida
  que
  vamos
  a
  emplea
  es
 

gráficamente
 abajo
 a
 la
 izquierda.
 

la
  1,1.
  Representada
 

2. El
 laberinto
 siempre
 es
 cuadrado
 y
 tiene
 NxN
 posiciones.
 En
 el
 ejemplo
 N=20.
 
3. La
 posición
 que
 buscamos
 es
 la
 posición
 central
 del
 
 laberinto.
 Si
 N
 es
 impar
 

esa
 posición
 será
 (N+1)/2,(N+1)/2,
 y
 si
 es
 par
 N/2,N/2.
 

4. Los
  algoritmos
  de
  construcción
  de
  laberintos
  con
  los
  que
  trabajaremos
 

permiten
 llegar
 a
 cualquier
 posición
 del
 laberinto
 desde
 cualquier
 posición.
 



ALED
 -­‐
 Laboratorio
 2
  2
 

5. En
  las
  implementaciones
  con
  las
  que
  trabajaremos,
  el
  camino
  de
  llegada
  al
 
punto
  destino
  está
  representado
  en
  azul,
  y
  en
  gris
  están
  representados
 
puntos
  por
  los
  que
  hemos
  pasado,
  y
  nos
  han
  llevado
  a
  puntos
  muertos
  o
  a
 
puntos
 por
 los
 que
 ya
 hemos
 pasado
 (debemos
 evitar
 meternos
 en
 ciclos
 de
 
donde
 no
 salimos).
 En
 rojo
 están
 marcados
 el
 punto
 origen
 y
 destino.
 


 

La
  práctica
  emplea
  la
  clase
  StdDraw.
  Es
  una
  clase
  que
  permite
  dibujar
  de
  forma
 
sencilla
 elementos
 gráficos
 como
 líneas,
 círculos,
 puntos,
 ….
 Pero
 a
 diferencia
 de
 las
 
bibliotecas
  estándar
  de
  Java,
  esta
  clase
  localiza
  las
  posiciones
  y
  tamaños
  de
  los
 
objetos
 mediante
 parámetros
 double
 y
 permite
 escalar
 las
 figuras
 de
 forma
 sencilla
 
(frente
  a
  los
  valores
  enteros
  absolutos
  de
  las
  bibliotecas
  estándar).
  Este
  escalado
 
permite
  ver
  en
  el
  mismo
  espacio
  gráfico
  laberintos
  de
  diferente
  tamaño,
  sin
  tener
 
que
  cambiar
  apenas
  nuestro
  programa.
  Otra
  diferencia
  importante
  es
  que
  la
 
coordenada
  de
  origen
  del
  espacio
  gráfico
  está
  abajo
  a
  la
  izquierda
  (frente
  a
  la
 
posición
  de
  arriba
  a
  la
  derecha,
  que
  es
  como
  suelen
  trabajar
  las
  bibliotecas
  Java).
 
Esto
 no
 es
 mas
 que
 un
 simple
 resumen,
 porque
 la
 representación
 gráfica
 no
 es
 un
 
objetivo
 fundamental
 de
 la
 práctica.
 

Actividades
 a
 desarrollar
 

Descarga
 del
 proyecto
 desde
 GitHub
 (Trabajo
 previo)
 
La
 estructura
 del
 proyecto
 a
 desarrollar,
 así
 como
 algunas
 de
 las
 clases
 necesarias
 se
 
encuentran
  disponibles
  en
  el
 
la
  asignatura
  en
  GitHub:
 
https://github.com/ALED-­‐UPM/Tema2
 
 

repositorio
  de
 

Antes
 del
 inicio
 de
 la
 sesión
 de
 laboratorio,
 deberá:
 

1. Configurar
 EGit
 para
 acceder
 al
 repositorio
 Tema2
 de
 la
 asignatura.
 
 
2. Clonar
 el
 repositorio
 Tema2.
 
3. Importar
 el
 proyecto
 ALED-­‐lab2
 a
 su
 Eclipse.
 



ALED
 -­‐
 Laboratorio
 2
  3
 

4. Explorar
 la
 clases
 Laberinto
 y
 StdDraw.
 
5. Contestar
 a
 las
 preguntas
 1-­‐3.
 


 



Implementar
 el
 método
 resolver
 (Trabajo
 en
 laboratorio)
 

protected boolean[][] norte;
protected boolean[][] este;
protected boolean[][] sur;
protected boolean[][] oeste;
protected boolean[][] visitado;

Vamos
 a
 implementar
 el
 método
 que
 permite
 encontrar
 el
 camino
 desde
 la
 
posición
 origen
 a
 la
 posición
 destino.
 La
 búsqueda
 del
 camino
 se
 implementa
 en
 
dos
 métodos
 sobrecargados
 resolver()
 y
 resolver(int
 x,int
 y).
 El
 primero
 es
 público,
 
 
es
 un
 método
 fachada;
 hace
 inicializaciones
 antes
 de
 empezar
 la
 búsqueda,
 y
 llama
 
al
 segundo
 que
 es
 privado
 y
 es
 donde
 realmente
 se
 busca
 el
 camino.
 Nos
 
centraremos
 en
 este
 segundo.
 
La
 clase
 Laberinto
 incluye
 los
 siguientes
 atributos:
 

 El
 constructor
 de
 Laberinto
 nos
 ha
 dejado
 inicializados
 norte,
 sur,
 este
 y
 oeste.
 El
 
método
 resolver()
 (el
 punto
 de
 entrada
 fundamental
 de
 la
 clase)
 deja
 inicializado
 
visitado.
 Todos
 estos
 atributos
 son
 arrays
 de
 tamaño
 N+2,N+2.
  norte,
  sur,
  este,
 y
 
oeste
 nos
 indican
 cuando
 una
 posición
 tiene
 una
 pared
 en
 sentido
 norte,
 sur
 este
 u
 
oeste.
 Los
 fija
 el
 generador
 de
 caminos
 (la
 implementación
 de
 la
 construcción
 del
 
laberinto)
 y
 no
 debemos
 modificarlos.
 Son
 variables
 algo
 redundantes.
 Están
 así
 
implementadas
 para
 hacer
 mas
 sencillos
 los
 algoritmos
 de
 resolver,
 pero
 debemos
 
saber
 que
  norte[x][y]
  ==
  sur[x][y+1]
 (para
  y
  >=
  0
 e
  y
  <=
  N)
 y
  este[x][y]
  ==
 
oeste[x+1][y]
 (para
 x
 >=
 0
 y
 
 x
 <=
 N).
 

 

 

 
N+1
 
N
 
…
 
1
 
0
 

Oeste
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 x
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 Este
 
0
 
N+1
 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


 

 
Norte
 

 
 
 

 y
 
 
Sur
 

1
 


 
…
 


 

 

 

 

 

N
 


 

 

 

 

 

implementando
  el
  método
  resolver(int
  x,
 

ALED
 -­‐
 Laboratorio
 2
  4
 
El
 atributo
  visitado
 nos
 servirá
 para
 controlar
 los
 caminos
 por
 los
 que
 
anteriormente
 hemos
 pasado
 y
 no
 nos
 han
 llevado
 a
 una
 solución.
 
El
 tamaño
 de
 todos
 estos
 arrays
 es
 N+2,N+2
 mientras
 que
 el
 laberinto
 como
 tal
 
está
 representado
 en
 los
 rangos
 1..N,1..N.
 Todos
 los
 arrays
 tienen
 un
 marco
 
exterior
 para
 identificar
 los
 límites
 del
 laberinto.
 Por
 ejemplo,
  visitados[0][y],
 
visitados[N+1][y],
  visitados[x][0]
 y
  visitados[x][N+1]
 están
 inicializados
 a
  true,
 el
 
resto
 a
  false.
 Deben
 estar
 siempre
 a
  true
  norte[x][0],
  sur[x][N+1],
  este[0][y]
 y
 
oeste[N+1][y].
 
Empezaremos
 
int
  y)
  de
  forma
 
determinista
 (intentamos
 buscar
 caminos
 siempre
 en
 el
 mismo
 orden).
 Dos
 
ejecuciones
 con
 el
 mismo
 laberinto,
 encuentran
 siempre
 el
 mismo
 resultado
 de
 la
 
misma
 forma.
 El
 algoritmo
 que
 vamos
 a
 seguir
 parte
 de
 una
 posición
 x,y
 (x
 >
 0,
 x
 <
 
N+1,
 y
 
 >
 0,
 y
 <
 N+1).
 Si
 esa
 posición
 ya
 ha
 sido
 visitada,
 la
 descartamos;
 si
 es
 la
 
posición
 central
 (Math.round(N/2.0),
  Math.round(N/2.0))
 hemos
 encontrado
 el
 
punto
 ce