Descarga la aplicación para disfrutar aún más
Lea materiales sin conexión, sin usar Internet. Además de muchas otras características!
ALED_LAB2
Materiales Generales
Esta es una vista previa del archivo. Inicie sesión para ver el archivo original
ALED-lab2 (1).zip
ALED-lab2/.classpath
ALED-lab2/.project
ALED-lab2
org.eclipse.jdt.core.javabuilder
org.eclipse.jdt.core.javanature
ALED-lab2/.settings/org.eclipse.jdt.core.prefs
eclipse.preferences.version=1
org.eclipse.jdt.core.compiler.codegen.inlineJsrBytecode=enabled
org.eclipse.jdt.core.compiler.codegen.targetPlatform=1.8
org.eclipse.jdt.core.compiler.codegen.unusedLocal=preserve
org.eclipse.jdt.core.compiler.compliance=1.8
org.eclipse.jdt.core.compiler.debug.lineNumber=generate
org.eclipse.jdt.core.compiler.debug.localVariable=generate
org.eclipse.jdt.core.compiler.debug.sourceFile=generate
org.eclipse.jdt.core.compiler.problem.assertIdentifier=error
org.eclipse.jdt.core.compiler.problem.enumIdentifier=error
org.eclipse.jdt.core.compiler.source=1.8
ALED-lab2/src/es/upm/dit/aled/lab2/Laberinto.java
ALED-lab2/src/es/upm/dit/aled/lab2/Laberinto.java
package es.upm.dit.aled.lab2;
import java.awt.Font;
public class Laberinto {
protected int N; // Tamano alto y ancho del laberinto
// norte, sur este y oeste nos dicen cuando hay paredes o no alrededor de una posicion
protected boolean[][] norte;
protected boolean[][] este;
protected boolean[][] sur;
protected boolean[][] oeste;
// visitado nos dice cuando hemos pasado por una posicion
protected boolean[][] visitado;
// encontrado: hemos llegado al punto central
protected boolean encontrado = false;
protected double radio=StdDraw.getPenRadius();
/**
* Crea un nuevo laberinto
*
* @param N tamano del laberinto
*/
public Laberinto(int N) {
this.N = N;
StdDraw.setCanvasSize(700,700);
StdDraw.setXscale(0, N+2);
StdDraw.setYscale(0, N+2);
init();
generar();
}
private void init() {
// todas las posiciones del marco exterior marcadas como visitadas
visitado = new boolean[N+2][N+2];
for (int x = 0; x < N+2; x++) visitado[x][0] = visitado[x][N+1] = true;
for (int y = 0; y < N+2; y++) visitado[0][y] = visitado[N+1][y] = true;
// todas las paredes levantadas
norte = new boolean[N+2][N+2];
este = new boolean[N+2][N+2];
sur = new boolean[N+2][N+2];
oeste = new boolean[N+2][N+2];
for (int x = 0; x < N+2; x++)
for (int y = 0; y < N+2; y++)
norte[x][y] = este[x][y] = sur[x][y] = oeste[x][y] = true;
}
// generar el laberinto
private void generar(int x, int y) {
visitado[x][y] = true;
// mientras tengamos una posicion junto a esta que no este visitada
while (!visitado[x][y+1] || !visitado[x+1][y] || !visitado[x][y-1] || !visitado[x-1][y]) {
// elegimos una posicion cualquiera
while (true) {
double r = Math.random();
if (r < 0.25 && !visitado[x][y+1]) {
norte[x][y] = sur[x][y+1] = false;
generar(x, y + 1);
break;
}
else if (r >= 0.25 && r < 0.50 && !visitado[x+1][y]) {
este[x][y] = oeste[x+1][y] = false;
generar(x+1, y);
break;
}
else if (r >= 0.5 && r < 0.75 && !visitado[x][y-1]) {
sur[x][y] = norte[x][y-1] = false;
generar(x, y-1);
break;
}
else if (r >= 0.75 && r < 1.00 && !visitado[x-1][y]) {
oeste[x][y] = este[x-1][y] = false;
generar(x-1, y);
break;
}
}
}
}
/**
* Generamos un laberinto, empezamos a generar por la posicion izquierda y abajo
*/
protected void generar() {
generar(1, 1);
}
// resolvemos buscado la primera solucion que encontremos
private int resolver(int x, int y, int pasos) {
// TODO
return 0;
}
/**
* Resolver el laberinto empezando en la primera posicion: abajo a la izquierda
* @return numero de pasos dados
*/
public int resolver() {
for (int x = 1; x <= N; x++)
for (int y = 1; y <= N; y++)
visitado[x][y] = false;
encontrado = false;
return resolver(1, 1, 1);
// StdDraw.show(0);
}
/**
* Dibuja el laberinto
*/
public void dibuja() {
StdDraw.clear();
StdDraw.setPenRadius(radio);
StdDraw.setPenColor(StdDraw.RED);
StdDraw.filledCircle(Math.round(N/2.0) + 0.5, Math.round(N/2.0) + 0.5, 0.375);
StdDraw.filledCircle(1.5, 1.5, 0.375);
StdDraw.setPenColor(StdDraw.BLACK);
Font f = StdDraw.getFont();
int size=300/N;
StdDraw.setFont(new Font(null,0, size > 12 ? 16 : size));
for (int x = 1; x <= N; x++)
StdDraw.text(x+0.5, 0, new Integer(x).toString());
for (int y = 1; y <= N; y++)
StdDraw.text(0, y+0.5, new Integer(y).toString());
StdDraw.setFont(f);
for (int x = 1; x <= N; x++) {
for (int y = 1; y <= N; y++) {
if (sur[x][y]) StdDraw.line(x, y, x + 1, y);
if (norte[x][y]) StdDraw.line(x, y + 1, x + 1, y + 1);
if (oeste[x][y]) StdDraw.line(x, y, x, y + 1);
if (este[x][y]) StdDraw.line(x + 1, y, x + 1, y + 1);
}
}
StdDraw.show(0);
}
/**
* Punto de entrada al programa. Incluye una prueba
* @param args debe incluir un argumento con el tamano del laberinto
*/
public static void main(String[] args) {
int N = Integer.parseInt(args[0]);
Laberinto laberinto = new Laberinto(N);
StdDraw.show(0);
laberinto.dibuja();
System.out.println("Pasos hasta solucion: "+laberinto.resolver());
}
}
ALED-lab2/src/es/upm/dit/aled/lab2/LaberintoTodoAccesible.java
ALED-lab2/src/es/upm/dit/aled/lab2/LaberintoTodoAccesible.java
package es.upm.dit.aled.lab2;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
/**
* Clase para mejorar la generacion de laberintos que se resuelven en Laberinto
*
* @author Miguel A. de Miguel
*
* es.upm.dit.aled.lab2.Laberinto
*/
public class LaberintoTodoAccesible extends Laberinto {
/**
* Constructor para crear un nuevo laberinto. Este constructor inicializa el laberinto y lo genera
*
* @param n numero de filas y columnas del laberinto cuadrado
*/
public LaberintoTodoAccesible(int n) {
super(n);
}
public boolean compruebaAccesibilidad() {
// TODO
return false;
}
protected void aisla(int x, int y) {
// TODO
}
/**
* Prueba de ejecucion controlando la acesibilidad de todo el laberinto
*
* @param numFilasColumnas tamano del laberinto
* @return falso si todo el labrinto no es accesible
*/
public static boolean ejecutaConControlAccesibilidad(int numFilasColumnas) {
LaberintoTodoAccesible laberinto = new LaberintoTodoAccesible(numFilasColumnas);
StdDraw.show(0);
laberinto.dibuja();
if (!laberinto.compruebaAccesibilidad())
return false;
laberinto.resolver();
return true;
}
/**
* Prueba de ejecucion controlando la acesibilidad de todo el laberinto, y aislando
* el punto central
*
* @param numFilasColumnas tamano del labrinto
* @return
falso si todo el labrinto no es accesible
*/
public static boolean ejecutaConControlAccesibilidadYAislado(int numFilasColumnas) {
LaberintoTodoAccesible laberinto = new LaberintoTodoAccesible(numFilasColumnas);
laberinto.aisla(numFilasColumnas/2,numFilasColumnas/2);
StdDraw.show(0);
laberinto.dibuja();
if (!laberinto.compruebaAccesibilidad())
return false;
laberinto.resolver();
return true;
}
/**
* Punto de entrada al programa
*
* @param args argumentos de la linea de comandos
*/
public static void main(String[] args) {
int N = Integer.parseInt(args[0]);
if (LaberintoTodoAccesible.ejecutaConControlAccesibilidad(N))
System.out.println("Todas las posiciones son accesibles");
else System.out.println("Hay posiciones no accesibles");
/*
if (LaberintoTodoAccesible.ejecutaConControlAccesibilidadYAislado(N))
System.out.println("Todas las posiciones son accesibles");
else System.out.println("Hay posiciones no accesibles");
*/
}
}
ALED-lab2/src/es/upm/dit/aled/lab2/StdDraw.java
ALED-lab2/src/es/upm/dit/aled/lab2/StdDraw.java
package es.upm.dit.aled.lab2;
/*************************************************************************
* Compilation: javac StdDraw.java
* Execution: java StdDraw
*
* Standard drawing library. This class provides a basic capability for
* creating drawings with your programs. It uses a simple graphics model that
* allows you to create drawings consisting of points, lines, and curves
* in a window on your computer and to save the drawings to a file.
*
* Todo
* ----
* - Add support for gradient fill, etc.
*
* Remarks
* -------
* - don't use AffineTransform for rescaling since it inverts
* images and strings
* - careful using setFont in inner loop within an animation -
* it can cause flicker
*
*************************************************************************/
import java.awt.*;
import java.awt.event.*;
import java.awt.geom.*;
import java.awt.image.*;
import java.io.*;
import java.net.*;
import java.util.LinkedList;
import java.util.TreeSet;
import javax.imageio.ImageIO;
import javax.swing.*;
/**
* <i>Standard draw</i>. This class provides a basic capability for
* creating drawings with your programs. It uses a simple graphics model that
* allows you to create drawings consisting of points, lines, and curves
* in a window on your computer and to save the drawings to a file.
* <p>
* For additional documentation, see <a href="http://introcs.cs.princeton.edu/15inout">Section 1.5</a> of
* <i>Introduction to Programming in Java: An Interdisciplinary Approach</i> by Robert Sedgewick and Kevin Wayne.
*/
public final class StdDraw implements ActionListener, MouseListener, MouseMotionListener, KeyListener {
// pre-defined colors
public static final Color BLACK = Color.BLACK;
public static final Color BLUE = Color.BLUE;
public static final Color CYAN = Color.CYAN;
public static final Color DARK_GRAY = Color.DARK_GRAY;
public static final Color GRAY = Color.GRAY;
public static final Color GREEN = Color.GREEN;
public static final Color LIGHT_GRAY = Color.LIGHT_GRAY;
public static final Color MAGENTA = Color.MAGENTA;
public static final Color ORANGE = Color.ORANGE;
public static final Color PINK = Color.PINK;
public static final Color RED = Color.RED;
public static final Color WHITE = Color.WHITE;
public static final Color YELLOW = Color.YELLOW;
/**
* Shade of blue used in Introduction to Programming in Java.
* It is Pantone 300U. The RGB values are approximately (9, 90, 166).
*/
public static final Color BOOK_BLUE = new Color( 9, 90, 166);
public static final Color BOOK_LIGHT_BLUE = new Color(103, 198, 243);
/**
* Shade of red used in Algorithms 4th edition.
* It is Pantone 1805U. The RGB values are approximately (150, 35, 31).
*/
public static final Color BOOK_RED = new Color(150, 35, 31);
// default colors
private static final Color DEFAULT_PEN_COLOR = BLACK;
private static final Color DEFAULT_CLEAR_COLOR = WHITE;
// current pen color
private static Color penColor;
// default canvas size is DEFAULT_SIZE-by-DEFAULT_SIZE
private static final int DEFAULT_SIZE = 512;
private static int width = DEFAULT_SIZE;
private static int height = DEFAULT_SIZE;
// default pen radius
private static final double DEFAULT_PEN_RADIUS = 0.002;
// current pen radius
private static double penRadius;
// show we draw immediately or wait until next show?
private static boolean defer = false;
// boundary of drawing canvas, 5% border
private static final double BORDER = 0.05;
private static final double DEFAULT_XMIN = 0.0;
private static final double DEFAULT_XMAX = 1.0;
private static final double DEFAULT_YMIN = 0.0;
private static final double DEFAULT_YMAX = 1.0;
private static double xmin, ymin, xmax, ymax;
// for synchronization
private static Object mouseLock = new Object();
private static Object keyLock = new Object();
// default font
private static final Font DEFAULT_FONT = new Font("SansSerif", Font.PLAIN, 16);
// current font
private static Font font;
// double buffered graphics
private static BufferedImage offscreenImage, onscreenImage;
private static Graphics2D offscreen, onscreen;
// singleton for callbacks: avoids generation of extra .class files
private static StdDraw std = new StdDraw();
// the frame for drawing to the screen
private static JFrame frame;
// mouse state
private static boolean mousePressed = false;
private static double mouseX = 0;
private static double mouseY = 0;
// queue of typed key characters
private static LinkedList<Character> keysTyped = new LinkedList<Character>();
// set of key codes currently pressed down
private static TreeSet<Integer> keysDown = new TreeSet<Integer>();
// singleton pattern: client can't instantiate
private StdDraw() { }
// static initializer
static { init(); }
/**
* Set the window size to the default size 512-by-512 pixels.
*/
public static void setCanvasSize() {
setCanvasSize(DEFAULT_SIZE, DEFAULT_SIZE);
}
/**
* Set the window size to w-by-h pixels.
*
* @param w the width as a number of pixels
* @param h the height as a number of pixels
* @throws a IllegalArgumentException if the width or height is 0 or negative
*/
public static void setCanvasSize(int w, int h) {
if (w < 1 || h < 1) throw new IllegalArgumentException("width and height must be positive");
width = w;
height = h;
init();
}
// init
private static void init() {
if (frame != null) frame.setVisible(false);
try {
frame = new JFrame();
} catch (Exception e) {
defer=true;
}
offscreenImage = new BufferedImage(width, height, BufferedImage.TYPE_INT_ARGB);
onscreenImage = new BufferedImage(width, height, BufferedImage.TYPE_INT_ARGB);
offscreen = offscreenImage.createGraphics();
onscreen = onscreenImage.createGraphics();
setXscale();
setYscale();
offscreen.setColor(DEFAULT_CLEAR_COLOR);
offscreen.fillRect(0,
0, width, height);
setPenColor();
setPenRadius();
setFont();
clear();
// add antialiasing
RenderingHints hints = new RenderingHints(RenderingHints.KEY_ANTIALIASING,
RenderingHints.VALUE_ANTIALIAS_ON);
hints.put(RenderingHints.KEY_RENDERING, RenderingHints.VALUE_RENDER_QUALITY);
offscreen.addRenderingHints(hints);
// frame stuff
ImageIcon icon = new ImageIcon(onscreenImage);
JLabel draw = new JLabel(icon);
draw.addMouseListener(std);
draw.addMouseMotionListener(std);
if (frame != null) {
frame.setContentPane(draw);
frame.addKeyListener(std); // JLabel cannot get keyboard focus
frame.setResizable(false);
frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE); // closes all windows
// frame.setDefaultCloseOperation(JFrame.DISPOSE_ON_CLOSE); // closes only current window
frame.setTitle("Standard Draw");
frame.setJMenuBar(createMenuBar());
frame.pack();
frame.requestFocusInWindow();
frame.setVisible(true);
}
}
// create the menu bar (changed to private)
private static JMenuBar createMenuBar() {
JMenuBar menuBar = new JMenuBar();
JMenu menu = new JMenu("File");
menuBar.add(menu);
JMenuItem menuItem1 = new JMenuItem(" Save... ");
menuItem1.addActionListener(std);
menuItem1.setAccelerator(KeyStroke.getKeyStroke(KeyEvent.VK_S,
Toolkit.getDefaultToolkit().getMenuShortcutKeyMask()));
menu.add(menuItem1);
return menuBar;
}
/*************************************************************************
* User and screen coordinate systems
*************************************************************************/
/**
* Set the x-scale to be the default (between 0.0 and 1.0).
*/
public static void setXscale() { setXscale(DEFAULT_XMIN, DEFAULT_XMAX); }
/**
* Set the y-scale to be the default (between 0.0 and 1.0).
*/
public static void setYscale() { setYscale(DEFAULT_YMIN, DEFAULT_YMAX); }
/**
* Set the x-scale (a 10% border is added to the values)
* @param min the minimum value of the x-scale
* @param max the maximum value of the x-scale
*/
public static void setXscale(double min, double max) {
double size = max - min;
synchronized (mouseLock) {
xmin = min - BORDER * size;
xmax = max + BORDER * size;
}
}
/**
* Set the y-scale (a 10% border is added to the values).
* @param min the minimum value of the y-scale
* @param max the maximum value of the y-scale
*/
public static void setYscale(double min, double max) {
double size = max - min;
synchronized (mouseLock) {
ymin = min - BORDER * size;
ymax = max + BORDER * size;
}
}
/**
* Set the x-scale and y-scale (a 10% border is added to the values)
* @param min the minimum value of the x- and y-scales
* @param max the maximum value of the x- and y-scales
*/
public static void setScale(double min, double max) {
double size = max - min;
synchronized (mouseLock) {
xmin = min - BORDER * size;
xmax = max + BORDER * size;
ymin = min - BORDER * size;
ymax = max + BORDER * size;
}
}
// helper functions that scale from user coordinates to screen coordinates and back
private static double scaleX(double x) { return width * (x - xmin) / (xmax - xmin); }
private static double scaleY(double y) { return height * (ymax - y) / (ymax - ymin); }
private static double factorX(double w) { return w * width / Math.abs(xmax - xmin); }
private static double factorY(double h) { return h * height / Math.abs(ymax - ymin); }
private static double userX(double x) { return xmin + x * (xmax - xmin) / width; }
private static double userY(double y) { return ymax - y * (ymax - ymin) / height; }
/**
* Clear the screen to the default color (white).
*/
public static void clear() { clear(DEFAULT_CLEAR_COLOR); }
/**
* Clear the screen to the given color.
* @param color the Color to make the background
*/
public static void clear(Color color) {
offscreen.setColor(color);
offscreen.fillRect(0, 0, width, height);
offscreen.setColor(penColor);
draw();
}
/**
* Get the current pen radius.
*/
public static double getPenRadius() { return penRadius; }
/**
* Set the pen size to the default (.002).
*/
public static void setPenRadius() { setPenRadius(DEFAULT_PEN_RADIUS); }
/**
* Set the radius of the pen to the given size.
* @param r the radius of the pen
* @throws IllegalArgumentException if r is negative
*/
public static void setPenRadius(double r) {
if (r < 0) throw new IllegalArgumentException("pen radius must be nonnegative");
penRadius = r;
float scaledPenRadius = (float) (r * DEFAULT_SIZE);
BasicStroke stroke = new BasicStroke(scaledPenRadius, BasicStroke.CAP_ROUND, BasicStroke.JOIN_ROUND);
// BasicStroke stroke = new BasicStroke(scaledPenRadius);
offscreen.setStroke(stroke);
}
/**
* Get the current pen color.
*/
public static Color getPenColor() { return penColor; }
/**
* Set the pen color to the default color (black).
*/
public static void setPenColor() { setPenColor(DEFAULT_PEN_COLOR); }
/**
* Set the pen color to the given color. The available pen colors are
* BLACK, BLUE, CYAN, DARK_GRAY, GRAY, GREEN, LIGHT_GRAY, MAGENTA,
* ORANGE, PINK, RED, WHITE, and YELLOW.
* @param color the Color to make the pen
*/
public static void setPenColor(Color color) {
penColor = color;
offscreen.setColor(penColor);
}
/**
* Set the pen color to the given RGB color.
* @param red the amount of red (between 0 and 255)
* @param green the amount of green (between 0 and 255)
* @param blue the amount of blue (between 0 and 255)
* @throws IllegalArgumentException if the amount of red, green, or blue are outside prescribed range
*/
public static void setPenColor(int red, int green, int blue) {
if (red < 0 || red >= 256) throw new IllegalArgumentException("amount of red must be between 0 and 255");
if (green < 0 || green >= 256) throw new IllegalArgumentException("amount of red must be between 0 and 255");
if (blue < 0 || blue >= 256) throw new IllegalArgumentException("amount of red must be between 0 and 255");
setPenColor(new Color(red, green, blue));
}
/**
* Get the current font.
*/
public static Font getFont() { return font; }
/**
* Set the font to the default font (sans serif, 16 point).
*/
public static void setFont() { setFont(DEFAULT_FONT); }
/**
* Set the font to the given value.
* @param f the font to make text
*/
public static void setFont(Font f) { font = f; }
/*************************************************************************
* Drawing geometric shapes.
*************************************************************************/
/**
* Draw a line from (x0, y0) to (x1, y1).
* @param x0 the x-coordinate
of the starting point
* @param y0 the y-coordinate of the starting point
* @param x1 the x-coordinate of the destination point
* @param y1 the y-coordinate of the destination point
*/
public static void line(double x0, double y0, double x1, double y1) {
offscreen.draw(new Line2D.Double(scaleX(x0), scaleY(y0), scaleX(x1), scaleY(y1)));
draw();
}
/**
* Draw one pixel at (x, y).
* @param x the x-coordinate of the pixel
* @param y the y-coordinate of the pixel
*/
private static void pixel(double x, double y) {
offscreen.fillRect((int) Math.round(scaleX(x)), (int) Math.round(scaleY(y)), 1, 1);
}
/**
* Draw a point at (x, y).
* @param x the x-coordinate of the point
* @param y the y-coordinate of the point
*/
public static void point(double x, double y) {
double xs = scaleX(x);
double ys = scaleY(y);
double r = penRadius;
float scaledPenRadius = (float) (r * DEFAULT_SIZE);
// double ws = factorX(2*r);
// double hs = factorY(2*r);
// if (ws <= 1 && hs <= 1) pixel(x, y);
if (scaledPenRadius <= 1) pixel(x, y);
else offscreen.fill(new Ellipse2D.Double(xs - scaledPenRadius/2, ys - scaledPenRadius/2,
scaledPenRadius, scaledPenRadius));
draw();
}
/**
* Draw a circle of radius r, centered on (x, y).
* @param x the x-coordinate of the center of the circle
* @param y the y-coordinate of the center of the circle
* @param r the radius of the circle
* @throws IllegalArgumentException if the radius of the circle is negative
*/
public static void circle(double x, double y, double r) {
if (r < 0) throw new IllegalArgumentException("circle radius must be nonnegative");
double xs = scaleX(x);
double ys = scaleY(y);
double ws = factorX(2*r);
double hs = factorY(2*r);
if (ws <= 1 && hs <= 1) pixel(x, y);
else offscreen.draw(new Ellipse2D.Double(xs - ws/2, ys - hs/2, ws, hs));
draw();
}
/**
* Draw filled circle of radius r, centered on (x, y).
* @param x the x-coordinate of the center of the circle
* @param y the y-coordinate of the center of the circle
* @param r the radius of the circle
* @throws IllegalArgumentException if the radius of the circle is negative
*/
public static void filledCircle(double x, double y, double r) {
if (r < 0) throw new IllegalArgumentException("circle radius must be nonnegative");
double xs = scaleX(x);
double ys = scaleY(y);
double ws = factorX(2*r);
double hs = factorY(2*r);
if (ws <= 1 && hs <= 1) pixel(x, y);
else offscreen.fill(new Ellipse2D.Double(xs - ws/2, ys - hs/2, ws, hs));
draw();
}
/**
* Draw an ellipse with given semimajor and semiminor axes, centered on (x, y).
* @param x the x-coordinate of the center of the ellipse
* @param y the y-coordinate of the center of the ellipse
* @param semiMajorAxis is the semimajor axis of the ellipse
* @param semiMinorAxis is the semiminor axis of the ellipse
* @throws IllegalArgumentException if either of the axes are negative
*/
public static void ellipse(double x, double y, double semiMajorAxis, double semiMinorAxis) {
if (semiMajorAxis < 0) throw new IllegalArgumentException("ellipse semimajor axis must be nonnegative");
if (semiMinorAxis < 0) throw new IllegalArgumentException("ellipse semiminor axis must be nonnegative");
double xs = scaleX(x);
double ys = scaleY(y);
double ws = factorX(2*semiMajorAxis);
double hs = factorY(2*semiMinorAxis);
if (ws <= 1 && hs <= 1) pixel(x, y);
else offscreen.draw(new Ellipse2D.Double(xs - ws/2, ys - hs/2, ws, hs));
draw();
}
/**
* Draw an ellipse with given semimajor and semiminor axes, centered on (x, y).
* @param x the x-coordinate of the center of the ellipse
* @param y the y-coordinate of the center of the ellipse
* @param semiMajorAxis is the semimajor axis of the ellipse
* @param semiMinorAxis is the semiminor axis of the ellipse
* @throws IllegalArgumentException if either of the axes are negative
*/
public static void filledEllipse(double x, double y, double semiMajorAxis, double semiMinorAxis) {
if (semiMajorAxis < 0) throw new IllegalArgumentException("ellipse semimajor axis must be nonnegative");
if (semiMinorAxis < 0) throw new IllegalArgumentException("ellipse semiminor axis must be nonnegative");
double xs = scaleX(x);
double ys = scaleY(y);
double ws = factorX(2*semiMajorAxis);
double hs = factorY(2*semiMinorAxis);
if (ws <= 1 && hs <= 1) pixel(x, y);
else offscreen.fill(new Ellipse2D.Double(xs - ws/2, ys - hs/2, ws, hs));
draw();
}
/**
* Draw an arc of radius r, centered on (x, y), from angle1 to angle2 (in degrees).
* @param x the x-coordinate of the center of the circle
* @param y the y-coordinate of the center of the circle
* @param r the radius of the circle
* @param angle1 the starting angle. 0 would mean an arc beginning at 3 o'clock.
* @param angle2 the angle at the end of the arc. For example, if
* you want a 90 degree arc, then angle2 should be angle1 + 90.
* @throws IllegalArgumentException if the radius of the circle is negative
*/
public static void arc(double x, double y, double r, double angle1, double angle2) {
if (r < 0) throw new IllegalArgumentException("arc radius must be nonnegative");
while (angle2 < angle1) angle2 += 360;
double xs = scaleX(x);
double ys = scaleY(y);
double ws = factorX(2*r);
double hs = factorY(2*r);
if (ws <= 1 && hs <= 1) pixel(x, y);
else offscreen.draw(new Arc2D.Double(xs - ws/2, ys - hs/2, ws, hs, angle1, angle2 - angle1, Arc2D.OPEN));
draw();
}
/**
* Draw a square of side length 2r, centered on (x, y).
* @param x the x-coordinate of the center of the square
* @param y the y-coordinate of the center of the square
* @param r radius is half the length of any side of the square
* @throws IllegalArgumentException if r is negative
*/
public static void square(double x, double y, double r) {
if (r < 0) throw new IllegalArgumentException("square side length must be nonnegative");
double xs = scaleX(x);
double ys = scaleY(y);
double ws = factorX(2*r);
double hs = factorY(2*r);
if (ws <= 1 && hs <= 1) pixel(x, y);
else offscreen.draw(new Rectangle2D.Double(xs - ws/2, ys - hs/2, ws, hs));
draw();
}
/**
* Draw a filled square of side length 2r, centered on (x, y).
* @param x the x-coordinate of the center of the square
* @param y the y-coordinate of the center of the square
* @param r radius is half the length of any side of the square
* @throws IllegalArgumentException if r is negative
*/
public static void filledSquare(double x, double y, double r) {
if (r < 0) throw new IllegalArgumentException("square side length must be nonnegative");
double xs = scaleX(x);
double ys = scaleY(y);
double ws = factorX(2*r);
double hs = factorY(2*r);
if (ws <= 1 && hs <= 1) pixel(x, y);
else offscreen.fill(new Rectangle2D.Double(xs - ws/2, ys - hs/2, ws, hs));
draw();
}
/**
* Draw
a rectangle of given half width and half height, centered on (x, y).
* @param x the x-coordinate of the center of the rectangle
* @param y the y-coordinate of the center of the rectangle
* @param halfWidth is half the width of the rectangle
* @param halfHeight is half the height of the rectangle
* @throws IllegalArgumentException if halfWidth or halfHeight is negative
*/
public static void rectangle(double x, double y, double halfWidth, double halfHeight) {
if (halfWidth < 0) throw new IllegalArgumentException("half width must be nonnegative");
if (halfHeight < 0) throw new IllegalArgumentException("half height must be nonnegative");
double xs = scaleX(x);
double ys = scaleY(y);
double ws = factorX(2*halfWidth);
double hs = factorY(2*halfHeight);
if (ws <= 1 && hs <= 1) pixel(x, y);
else offscreen.draw(new Rectangle2D.Double(xs - ws/2, ys - hs/2, ws, hs));
draw();
}
/**
* Draw a filled rectangle of given half width and half height, centered on (x, y).
* @param x the x-coordinate of the center of the rectangle
* @param y the y-coordinate of the center of the rectangle
* @param halfWidth is half the width of the rectangle
* @param halfHeight is half the height of the rectangle
* @throws IllegalArgumentException if halfWidth or halfHeight is negative
*/
public static void filledRectangle(double x, double y, double halfWidth, double halfHeight) {
if (halfWidth < 0) throw new IllegalArgumentException("half width must be nonnegative");
if (halfHeight < 0) throw new IllegalArgumentException("half height must be nonnegative");
double xs = scaleX(x);
double ys = scaleY(y);
double ws = factorX(2*halfWidth);
double hs = factorY(2*halfHeight);
if (ws <= 1 && hs <= 1) pixel(x, y);
else offscreen.fill(new Rectangle2D.Double(xs - ws/2, ys - hs/2, ws, hs));
draw();
}
/**
* Draw a polygon with the given (x[i], y[i]) coordinates.
* @param x an array of all the x-coordindates of the polygon
* @param y an array of all the y-coordindates of the polygon
*/
public static void polygon(double[] x, double[] y) {
int N = x.length;
GeneralPath path = new GeneralPath();
path.moveTo((float) scaleX(x[0]), (float) scaleY(y[0]));
for (int i = 0; i < N; i++)
path.lineTo((float) scaleX(x[i]), (float) scaleY(y[i]));
path.closePath();
offscreen.draw(path);
draw();
}
/**
* Draw a filled polygon with the given (x[i], y[i]) coordinates.
* @param x an array of all the x-coordindates of the polygon
* @param y an array of all the y-coordindates of the polygon
*/
public static void filledPolygon(double[] x, double[] y) {
int N = x.length;
GeneralPath path = new GeneralPath();
path.moveTo((float) scaleX(x[0]), (float) scaleY(y[0]));
for (int i = 0; i < N; i++)
path.lineTo((float) scaleX(x[i]), (float) scaleY(y[i]));
path.closePath();
offscreen.fill(path);
draw();
}
/*************************************************************************
* Drawing images.
*************************************************************************/
// get an image from the given filename
private static Image getImage(String filename) {
// to read from file
ImageIcon icon = new ImageIcon(filename);
// try to read from URL
if ((icon == null) || (icon.getImageLoadStatus() != MediaTracker.COMPLETE)) {
try {
URL url = new URL(filename);
icon = new ImageIcon(url);
} catch (Exception e) { /* not a url */ }
}
// in case file is inside a .jar
if ((icon == null) || (icon.getImageLoadStatus() != MediaTracker.COMPLETE)) {
URL url = StdDraw.class.getResource(filename);
if (url == null) throw new IllegalArgumentException("image " + filename + " not found");
icon = new ImageIcon(url);
}
return icon.getImage();
}
/**
* Draw picture (gif, jpg, or png) centered on (x, y).
* @param x the center x-coordinate of the image
* @param y the center y-coordinate of the image
* @param s the name of the image/picture, e.g., "ball.gif"
* @throws IllegalArgumentException if the image is corrupt
*/
public static void picture(double x, double y, String s) {
Image image = getImage(s);
double xs = scaleX(x);
double ys = scaleY(y);
int ws = image.getWidth(null);
int hs = image.getHeight(null);
if (ws < 0 || hs < 0) throw new IllegalArgumentException("image " + s + " is corrupt");
offscreen.drawImage(image, (int) Math.round(xs - ws/2.0), (int) Math.round(ys - hs/2.0), null);
draw();
}
/**
* Draw picture (gif, jpg, or png) centered on (x, y),
* rotated given number of degrees
* @param x the center x-coordinate of the image
* @param y the center y-coordinate of the image
* @param s the name of the image/picture, e.g., "ball.gif"
* @param degrees is the number of degrees to rotate counterclockwise
* @throws IllegalArgumentException if the image is corrupt
*/
public static void picture(double x, double y, String s, double degrees) {
Image image = getImage(s);
double xs = scaleX(x);
double ys = scaleY(y);
int ws = image.getWidth(null);
int hs = image.getHeight(null);
if (ws < 0 || hs < 0) throw new IllegalArgumentException("image " + s + " is corrupt");
offscreen.rotate(Math.toRadians(-degrees), xs, ys);
offscreen.drawImage(image, (int) Math.round(xs - ws/2.0), (int) Math.round(ys - hs/2.0), null);
offscreen.rotate(Math.toRadians(+degrees), xs, ys);
draw();
}
/**
* Draw picture (gif, jpg, or png) centered on (x, y), rescaled to w-by-h.
* @param x the center x coordinate of the image
* @param y the center y coordinate of the image
* @param s the name of the image/picture, e.g., "ball.gif"
* @param w the width of the image
* @param h the height of the image
* @throws IllegalArgumentException if the width height are negative
* @throws IllegalArgumentException if the image is corrupt
*/
public static void picture(double x, double y, String s, double w, double h) {
Image image = getImage(s);
double xs = scaleX(x);
double ys = scaleY(y);
if (w < 0) throw new IllegalArgumentException("width is negative: " + w);
if (h < 0) throw new IllegalArgumentException("height is negative: " + h);
double ws = factorX(w);
double hs = factorY(h);
if (ws < 0 || hs < 0) throw new IllegalArgumentException("image " + s + " is corrupt");
if (ws <= 1 && hs <= 1) pixel(x, y);
else {
offscreen.drawImage(image, (int) Math.round(xs - ws/2.0),
(int) Math.round(ys - hs/2.0),
(int) Math.round(ws),
(int) Math.round(hs), null);
}
draw();
}
/**
* Draw picture (gif, jpg, or png) centered on (x, y), rotated
* given number of degrees, rescaled to w-by-h.
* @param x the center x-coordinate of the image
* @param y the center y-coordinate of the image
* @param s the name of the image/picture, e.g., "ball.gif"
* @param
w the width of the image
* @param h the height of the image
* @param degrees is the number of degrees to rotate counterclockwise
* @throws IllegalArgumentException if the image is corrupt
*/
public static void picture(double x, double y, String s, double w, double h, double degrees) {
Image image = getImage(s);
double xs = scaleX(x);
double ys = scaleY(y);
double ws = factorX(w);
double hs = factorY(h);
if (ws < 0 || hs < 0) throw new IllegalArgumentException("image " + s + " is corrupt");
if (ws <= 1 && hs <= 1) pixel(x, y);
offscreen.rotate(Math.toRadians(-degrees), xs, ys);
offscreen.drawImage(image, (int) Math.round(xs - ws/2.0),
(int) Math.round(ys - hs/2.0),
(int) Math.round(ws),
(int) Math.round(hs), null);
offscreen.rotate(Math.toRadians(+degrees), xs, ys);
draw();
}
/*************************************************************************
* Drawing text.
*************************************************************************/
/**
* Write the given text string in the current font, centered on (x, y).
* @param x the center x-coordinate of the text
* @param y the center y-coordinate of the text
* @param s the text
*/
public static void text(double x, double y, String s) {
offscreen.setFont(font);
FontMetrics metrics = offscreen.getFontMetrics();
double xs = scaleX(x);
double ys = scaleY(y);
int ws = metrics.stringWidth(s);
int hs = metrics.getDescent();
offscreen.drawString(s, (float) (xs - ws/2.0), (float) (ys + hs));
draw();
}
/**
* Write the given text string in the current font, centered on (x, y) and
* rotated by the specified number of degrees
* @param x the center x-coordinate of the text
* @param y the center y-coordinate of the text
* @param s the text
* @param degrees is the number of degrees to rotate counterclockwise
*/
public static void text(double x, double y, String s, double degrees) {
double xs = scaleX(x);
double ys = scaleY(y);
offscreen.rotate(Math.toRadians(-degrees), xs, ys);
text(x, y, s);
offscreen.rotate(Math.toRadians(+degrees), xs, ys);
}
/**
* Write the given text string in the current font, left-aligned at (x, y).
* @param x the x-coordinate of the text
* @param y the y-coordinate of the text
* @param s the text
*/
public static void textLeft(double x, double y, String s) {
offscreen.setFont(font);
FontMetrics metrics = offscreen.getFontMetrics();
double xs = scaleX(x);
double ys = scaleY(y);
int hs = metrics.getDescent();
offscreen.drawString(s, (float) (xs), (float) (ys + hs));
draw();
}
/**
* Write the given text string in the current font, right-aligned at (x, y).
* @param x the x-coordinate of the text
* @param y the y-coordinate of the text
* @param s the text
*/
public static void textRight(double x, double y, String s) {
offscreen.setFont(font);
FontMetrics metrics = offscreen.getFontMetrics();
double xs = scaleX(x);
double ys = scaleY(y);
int ws = metrics.stringWidth(s);
int hs = metrics.getDescent();
offscreen.drawString(s, (float) (xs - ws), (float) (ys + hs));
draw();
}
/**
* Display on screen, pause for t milliseconds, and turn on
* <em>animation mode</em>: subsequent calls to
* drawing methods such as <tt>line()</tt>, <tt>circle()</tt>, and <tt>square()</tt>
* will not be displayed on screen until the next call to <tt>show()</tt>.
* This is useful for producing animations (clear the screen, draw a bunch of shapes,
* display on screen for a fixed amount of time, and repeat). It also speeds up
* drawing a huge number of shapes (call <tt>show(0)</tt> to defer drawing
* on screen, draw the shapes, and call <tt>show(0)</tt> to display them all
* on screen at once).
* @param t number of milliseconds
*/
public static void show(int t) {
if (frame != null) defer = false;
draw();
try { Thread.sleep(t); }
catch (InterruptedException e) { System.out.println("Error sleeping"); }
defer = true;
}
/**
* Display on-screen and turn off animation mode:
* subsequent calls to
* drawing methods such as <tt>line()</tt>, <tt>circle()</tt>, and <tt>square()</tt>
* will be displayed on screen when called. This is the default.
*/
public static void show() {
if (frame != null) defer = false;
draw();
}
// draw onscreen if defer is false
private static void draw() {
if (defer) return;
onscreen.drawImage(offscreenImage, 0, 0, null);
frame.repaint();
}
/*************************************************************************
* Save drawing to a file.
*************************************************************************/
/**
* Save onscreen image to file - suffix must be png, jpg, or gif.
* @param filename the name of the file with one of the required suffixes
*/
public static void save(String filename) {
File file = new File(filename);
String suffix = filename.substring(filename.lastIndexOf('.') + 1);
// png files
if (suffix.toLowerCase().equals("png")) {
try { ImageIO.write(onscreenImage, suffix, file); }
catch (IOException e) { e.printStackTrace(); }
}
// need to change from ARGB to RGB for jpeg
// reference: http://archives.java.sun.com/cgi-bin/wa?A2=ind0404&L=java2d-interest&D=0&P=2727
else if (suffix.toLowerCase().equals("jpg")) {
WritableRaster raster = onscreenImage.getRaster();
WritableRaster newRaster;
newRaster = raster.createWritableChild(0, 0, width, height, 0, 0, new int[] {0, 1, 2});
DirectColorModel cm = (DirectColorModel) onscreenImage.getColorModel();
DirectColorModel newCM = new DirectColorModel(cm.getPixelSize(),
cm.getRedMask(),
cm.getGreenMask(),
cm.getBlueMask());
BufferedImage rgbBuffer = new BufferedImage(newCM, newRaster, false, null);
try { ImageIO.write(rgbBuffer, suffix, file); }
catch (IOException e) { e.printStackTrace(); }
}
else {
System.out.println("Invalid image file type: " + suffix);
}
}
/**
* This method cannot be called directly.
*/
public void actionPerformed(ActionEvent e) {
FileDialog chooser = new FileDialog(StdDraw.frame, "Use a .png or .jpg extension", FileDialog.SAVE);
chooser.setVisible(true);
String filename = chooser.getFile();
if (filename != null) {
StdDraw.save(chooser.getDirectory() + File.separator + chooser.getFile());
}
}
/*************************************************************************
* Mouse interactions.
*************************************************************************/
/**
* Is the mouse being pressed?
* @return true or false
*/
public static boolean
mousePressed() {
synchronized (mouseLock) {
return mousePressed;
}
}
/**
* What is the x-coordinate of the mouse?
* @return the value of the x-coordinate of the mouse
*/
public static double mouseX() {
synchronized (mouseLock) {
return mouseX;
}
}
/**
* What is the y-coordinate of the mouse?
* @return the value of the y-coordinate of the mouse
*/
public static double mouseY() {
synchronized (mouseLock) {
return mouseY;
}
}
/**
* This method cannot be called directly.
*/
public void mouseClicked(MouseEvent e) { }
/**
* This method cannot be called directly.
*/
public void mouseEntered(MouseEvent e) { }
/**
* This method cannot be called directly.
*/
public void mouseExited(MouseEvent e) { }
/**
* This method cannot be called directly.
*/
public void mousePressed(MouseEvent e) {
synchronized (mouseLock) {
mouseX = StdDraw.userX(e.getX());
mouseY = StdDraw.userY(e.getY());
mousePressed = true;
}
}
/**
* This method cannot be called directly.
*/
public void mouseReleased(MouseEvent e) {
synchronized (mouseLock) {
mousePressed = false;
}
}
/**
* This method cannot be called directly.
*/
public void mouseDragged(MouseEvent e) {
synchronized (mouseLock) {
mouseX = StdDraw.userX(e.getX());
mouseY = StdDraw.userY(e.getY());
}
}
/**
* This method cannot be called directly.
*/
public void mouseMoved(MouseEvent e) {
synchronized (mouseLock) {
mouseX = StdDraw.userX(e.getX());
mouseY = StdDraw.userY(e.getY());
}
}
/*************************************************************************
* Keyboard interactions.
*************************************************************************/
/**
* Has the user typed a key?
* @return true if the user has typed a key, false otherwise
*/
public static boolean hasNextKeyTyped() {
synchronized (keyLock) {
return !keysTyped.isEmpty();
}
}
/**
* What is the next key that was typed by the user? This method returns
* a Unicode character corresponding to the key typed (such as 'a' or 'A').
* It cannot identify action keys (such as F1
* and arrow keys) or modifier keys (such as control).
* @return the next Unicode key typed
*/
public static char nextKeyTyped() {
synchronized (keyLock) {
return keysTyped.removeLast();
}
}
/**
* Is the keycode currently being pressed? This method takes as an argument
* the keycode (corresponding to a physical key). It can handle action keys
* (such as F1 and arrow keys) and modifier keys (such as shift and control).
* See <a href = "http://download.oracle.com/javase/6/docs/api/java/awt/event/KeyEvent.html">KeyEvent.java</a>
* for a description of key codes.
* @return true if keycode is currently being pressed, false otherwise
*/
public static boolean isKeyPressed(int keycode) {
synchronized (keyLock) {
return keysDown.contains(keycode);
}
}
/**
* This method cannot be called directly.
*/
public void keyTyped(KeyEvent e) {
synchronized (keyLock) {
keysTyped.addFirst(e.getKeyChar());
}
}
/**
* This method cannot be called directly.
*/
public void keyPressed(KeyEvent e) {
synchronized (keyLock) {
keysDown.add(e.getKeyCode());
}
}
/**
* This method cannot be called directly.
*/
public void keyReleased(KeyEvent e) {
synchronized (keyLock) {
keysDown.remove(e.getKeyCode());
}
}
/**
* Test client.
*/
public static void main(String[] args) {
StdDraw.square(.2, .8, .1);
StdDraw.filledSquare(.8, .8, .2);
StdDraw.circle(.8, .2, .2);
StdDraw.setPenColor(StdDraw.BOOK_RED);
StdDraw.setPenRadius(.02);
StdDraw.arc(.8, .2, .1, 200, 45);
// draw a blue diamond
StdDraw.setPenRadius();
StdDraw.setPenColor(StdDraw.BOOK_BLUE);
double[] x = { .1, .2, .3, .2 };
double[] y = { .2, .3, .2, .1 };
StdDraw.filledPolygon(x, y);
// text
StdDraw.setPenColor(StdDraw.BLACK);
StdDraw.text(0.2, 0.5, "black text");
StdDraw.setPenColor(StdDraw.WHITE);
StdDraw.text(0.8, 0.8, "white text");
}
}
__MACOSX/._ALED-lab2 (1).zip
Lab2_2017.pdf
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 diferencias entre algoritmos con una solución y con múltiples soluciones
Herramientas proporcionadas
En el moodle de la asignatura dispone de herramientas para la corrección automática
de entregas de código. Estas herramientas son sensibles al uso de
mayúsculas/minúsculas, por lo que deberá respetar escrupulosamente las
instrucciones dadas en este guion 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
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://www.gamesolo.com/flash-game/maze.html
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 emplear es la 1,1. Representada
gráficamente abajo a la izquierda.
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.
ALED - Laboratorio 2 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.
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 izquierda, que es como suelen trabajar las bibliotecas Java).
Esto no es más 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 Moodle (Trabajo previo)
La estructura del proyecto a desarrollar, así como algunas de las clases necesarias se
encuentran disponibles en moodle junto a esta guía de laboratorio:
Antes del inicio de la sesión de laboratorio, deberá:
1. Descargar ALED-lab2.zip
2. Crear el proyecto java ALED-lab2 en Eclipse.
ALED - Laboratorio 2 3
3. Importar la carpeta fuente src de ALED-lab2 en ALED-lab2.zip.
4. Explorar las clases Laberinto y StdDraw.
5. Contestar a las preguntas 1-3.
Implementar el método resolver (Trabajo en laboratorio)
Vamos a implementar el método que permite encontrar el camino desde la
posición origen a la posición destino. El método de la clase Laberinto que
construye el laberinto, genera un laberinto con una única solución. La búsqueda
del camino se implementa en dos métodos sobrecargados resolver() y resolver(int
x,int y, int pasos). 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:
protected boolean[][] norte;
protected boolean[][] este;
protected boolean[][] sur;
protected boolean[][] oeste;
protected boolean[][] visitado;
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, en general, no debemos modificarlos. Son variables algo redundantes.
Están así implementadas para hacer más sencillos los algoritmos de resolver, pero
debemos saber qué 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).
Oeste x Este
0 1 … N N+1
Norte
y
Sur
N+1
N
…
1
0
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 implementando el método resolver(int x, int y, int pasos) 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), con pasos igual a p. 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 central. Si no es ninguno de esos casos marcamos la
posición como visitada, la pintamos de azul e intentamos resolver, de forma
recursiva, moviéndonos en dirección norte, si no hay pared en esa dirección,
después en dirección este, después sur y después oeste, siempre y cuando no haya
paredes, debemos explorar suponiendo que damos un paso (y por tanto
incrementamos en uno la variable pasos de la llamada). Hemos elegido como orden
las agujas del reloj. Si por ninguno de esos caminos hemos llegado a la posición
central, pintamos la posición de gris, y retornamos diciendo que hemos llegado a
punto muerto o visitado. El método devuelve el número de pasos necesarios para
llegar a la solución. Si esa llamada no encuentra solución puede devolver 0.
El pseudo código del algoritmo nos queda:
int resolver(int x, int y, int pasos)
Si encontrado o visitado[x][y] return 0 o pasos;
visitado[x][y] = true;
// marcamos la posicion de azul
StdDraw.setPenColor(StdDraw.BLUE);
StdDraw.filledCircle(x + 0.5, y + 0.5, 0.25);
StdDraw.show(0);
Si hemos llegado el punto central
encontrado = true;
return pasos
Si no hay pared en norte[x][y] resolver(x, y + 1, pasos+1);
Si no hay pared en este[x][y] resolver(x + 1, y, pasos+1;
Si no hay pared en sur[x][y] resolver(x, y – 1, pasos+1);
Si no hay pared en oeste[x][y] resolver(x - 1, y, pasos+1);
Si encontrado return pasos devueltos por resolver que ha llegado al centro;
ALED - Laboratorio 2 5
// marcamos la posicion de gris
StdDraw.setPenColor(StdDraw.GRAY);
StdDraw.filledCircle(x + 0.5, y + 0.5, 0.25);
StdDraw.show(0);
return 0;
Implementar el algoritmo y compilarlo.
Para probar el algoritmo tenemos que configurar una ejecución que pase como
argumento el valor N. Creamos una configuración de ejecución con Run->Run
Configurations…; seleccionamos Java Applications (entre los tipos de ejecuciones
de la ventana a la izquierda) y creamos una nueva configuración de ejecución,
presionando el botón de nueva configuración (arriba a la izquierda).
En la carpeta principal de la configuración de ejecución seleccionamos el proyecto,
y la clase Laberinto, y en la carpeta de argumento ponemos 10 como argumento de
programa.
ALED - Laboratorio 2 6
1. Pruebe la ejecución del algoritmo con números entre 5 y 100 (números mayores
pueden crearnos problemas de memoria y tiempos de ejecución).
2. Responda a las preguntas 4-6 al final de este documento.
3. Documente la clase y genere la documentación javadoc correspondiente.
ALED - Laboratorio 2 7
Algoritmo con exploración aleatoria y tiempos de
ejecución (Trabajo en laboratorio)
Realizar las siguientes pruebas:
1. En el ejemplo anterior la exploración de caminos la hacemos dando prioridad
al norte frente al resto, al este frente al sur y oeste, y al sur frente al oeste.
Podemos cambiar el algoritmo para explorar de forma aleatoria. Podemos
utilizar Math.random() para elegir de forma aleatoria el camino que
seguiremos (dentro de los posibles). Debemos modificar el algoritmo para
que tengan la misma probabilidad la exploración de cualquiera de los
caminos.
2. Modificaremos el método público resolver() para sacar por salida estándar
cuanto tiempo se ha tardado en resolver el camino. Podemos incluir como
primera sentencia de este método
long t=System.currentTimeMillis();
y como última:
System.out.println("Tiempo total "+(System.currentTimeMillis()-t));
3. Podemos ver que buena parte del tiempo se va en
la representación gráfica.
Si comentamos las sentencias
StdDraw.show(0);
del método resolver(int x, int y, int pasos) y la introducimos al final del
método resolver(), solamente se hacen las actualizaciones gráficas cuando la
exploración está terminada. Compara los tiempos de ejecución de esta forma
y la anterior (cuando se actualiza la representación gráfica por cada paso).
4. Responda a las preguntas 7-10 al final de este documento.
5. Podemos generar errores en el programa si ejecutamos con una N=1000.
ALED - Laboratorio 2 8
Búsqueda del camino comprobando que todas las
posiciones son accesibles (Trabajo después de
laboratorio)
Las implementaciones que hemos hecho tienen sentido si el laberinto tiene solución.
Hay varios algoritmos para generar el laberinto; la solución que empleamos en la
clase Laberinto genera laberintos con solución, y con todas las posiciones del
laberinto accesibles.
Vamos a implementar la clase LaberintoTodoAccesible que extenderá la clase
Laberinto, y añadirá métodos que permitan comprobar que todas las posiciones del
laberinto son accesibles antes de resolverlo. LaberintoTodoAccesible incluirá el
método:
public boolean compruebaAccesibilidad()
Que devuelve true cuando todas las posiciones del laberinto son accesibles, y false
cuando alguna posición no es accesible partiendo desde la posición 1,1.
Realizar los siguientes pasos:
1. Implementar el método compruebaAccesibilidad.
2. Documente el método y los posibles métodos añadidos.
3. La clase incluye la implementación de:
public boolean ejecutaConControlAccesibilidad(int numFilasColumnas)
con una implementación similar al método main de Laberinto, que construye un
laberinto, comprueba que todas las posiciones son accesibles, y si es así, resuelve
el laberinto.
4. Ejecutar la clase LaberintoTodoAccesible y su método main que hace llamadas a
ejecutaConControlAccesibilidad pasando como parámetro el número de filas
del laberinto.
5. Hacer pruebas con diferentes tamaños (5-100).
Como la clase Laberinto siempre genera laberintos con todas las posiciones accesibles,
vamos a crear un método en la clase LaberintoTodoAccesible que nos permita aislar
posiciones del laberinto, al que podemos llamar después de haber construido el
laberinto, pero antes de comprobar la accesibilidad y de resolver el laberinto. La
cabecera puede ser:
protected void aisla(int x, int y)
Este método debe levantar las 4 paredes de la posición que fijan los parámetros x,y
(teniendo en cuenta que esas paredes deben ser consistentes con las de sus posiciones
vecinas). Tenemos implementado el método:
public boolean ejecutaConControlAccesibilidadYAislado(int numFilasColumnas)
ALED - Laboratorio 2 9
Con la misma implementación que ejecutaConControlAccesibilidad pero ejecutando
aisla para una cierta posición del laberinto, después de haber construido el laberinto y
antes de comprobar la accesibilidad. El método main puede hacer llamadas a
ejecutaConControlAccesibilidad o a ejecutaConControlAccesibilidadYAislado para
hacer ejecuciones con posiciones aisladas o no aisladas.
6. Implementar los métodos aisla.
7. Documente estos los métodos.
8. Hacer pruebas con diferentes tamaños (5-100).
Entregas
Instrucciones para la entrega durante la sesión de laboratorio:
• Las preguntas planteadas deben entregarse en papel al final de la sesión. Las
preguntas 1-3 estarán resueltas antes del laboratorio, y el resto podrán resolverse
en el laboratorio.
• El código fuente y la documentación de la clase Laberinto. Deberá entregarse
en el moodle de la asignatura antes del final de la sesión de laboratorio.
• El nombre del fichero que incluya los ficheros requeridos no debe contener
tildes ni espacios.
• En el contenido del fichero comprimido de la entrega, el código fuente debe
estar en el directorio relativo: “ALED-lab2/src/es/upm/dit/aled/lab2/”.
Instrucciones para la entrega a realizar después del laboratorio:
• El código fuente y la documentación de las clases
LaberintoMultiplesSoluciones y Laberinto deberán entregarse en el Moodle
de la asignatura antes de las 23:59 del 19 de octubre, siguiendo las mismas
instrucciones que la entrega de laboratorio respecto al nombre y ruta de los
ficheros.
• Al realizar la entrega se le informará, que estará sujeta a revisión por parte del
profesor, así como información sobre algunos fallos detectados. La evaluación
de práctica se hará con el siguiente criterio:
o 7 puntos máximo por la corrección del código de la clase Laberinto y
LaberintoTodoAccesible;
o 3 puntos máximo por la corrección de la documentación;
• Para la evaluación de la entrega sólo se considerará el último envío realizado.
• No se aceptarán entregas fuera de plazo bajo ningún concepto.
AVISO MUY IMPORTANTE
ALED - Laboratorio 2 10
Se recuerda a los alumnos que el trabajo es individual, y que la copia de entregas
supondrá ́el suspenso en la asignatura de forma automática, tanto para quien copia
como para quien se deja copiar.
No está permitido:
• Realizar este trabajo en grupo.
• Copiar el trabajo de otro alumno, ni permitir la copia del propio trabajo, ni
siquiera parcialmente.
• Usar código publicado sin citar el origen.
ALED - Laboratorio 2 11
Responda a las siguientes preguntas según se le indica en el enunciado del
laboratorio. Entregue al profesor esta hoja con sus respuestas antes de la sesión.
Nombre:_______________________________ DNI/NIE:____________________
1. Enumera los métodos que tiene la clase Laberinto. ¿Cual es el método que está sin
implementar?
2. ¿Qué argumentos presupone que tendrá el método main?
3. ¿Desde dónde se llama al método generar? ¿Que hace ese método?
4. ¿Cuales son las sentencias de Ejecución Base de la implementación del algoritmo?
5. ¿Cuales son las sentencias de Ejecución Recursiva de la implementación del
algoritmo?
6. ¿Cuales son las sentencias de Cálculos Generales de la implementación del
algoritmo?
7. ¿Cómo modificas el algoritmo para seleccionar de forma aleatoria un camino,
teniendo en cuenta que no todos los caminos se pueden explorar?
ALED - Laboratorio 2 12
8. ¿Cuánto es el tiempo de ejecución para un laberinto de tamaño 10? (cuando la
actualización gráfica solo se hace al final de la resolución)
9. ¿Cuánto es el tiempo de ejecución para un laberinto de tamaño 50? (cuando la
actualización gráfica solo se hace al final de la resolución). Si los métodos de
generación de laberintos fallan comenta que esto ha pasado y reduce el tamaño
del laberinto para que esto no suceda.
10. ¿Cuánto es el tiempo de ejecución para un laberinto de tamaño 100? (cuando la
actualización gráfica solo se hace al final de la resolución). Si los métodos de
generación de laberintos fallan, comenta que esto ha pasado y reduce el tamaño
del laberinto para que esto no suceda.
__MACOSX/._Lab2_2017.pdfCompartir
Compartir