Programación 3

Ejercicios resueltos de programación 3
Prácticas de la asignatura.
Alumna: Alicia Sánchez
Centro: UNED-Las Rozas (Madrid)
Hemos creado un documento aparte donde iremos guardando los ejercicios de las distintas
prácticas hasta el momento propuestas por el equipo docente. Al ser un documento
aparentemente sencillo, ya que en ocasiones dependerá de la solución lo que el alumno hayaimplementado en su práctica (es bastante subjetivo), no en todas las preguntas se pondrá la
solución. La idea de hacer este documento es ver la tónica general a la hora de preguntar y
además completar los ejercicios que faltan.
No tendremos un índice como tal, ya que estas cuestiones forman un conjunto, por tanto,
empezaremos a ver estas preguntas.
Ejercicios de prácticas
Curso 2007-08
Página 2 de 8Febrero 2000-1a (ejercicio 2)
Enunciado: Comenta las condiciones de poda que has utilizado en la realización de la práctica
del Nim
Respuesta: Este ejercicio es totalmente subjetivo como hemos comentado antes, pero
podremos decir basándonos en el libro de Brassard, que las condiciones de poda podrán ser
aquellas que no lleguen a ganar el juego o bien en tablas. Por ello, se tendría que hacerel árbol
de expansión hasta llegar a solución. De todas maneras, para ello en el citado libro vendría
más expandido, incluso más que en nuestro resumen de la asignatura.
Febrero 2006-1a (ejercicio 2)
Enunciado: Declara en Java o en Modula-2 las clases y/o estructuras de datos que utilizarías en
el problema del Su-doku (práctica de este año) para comprobar en un tiempo de ejecución
constanterespecto a la dimensión n del tablero (n x n) que una casilla contiene un valor
factible.
Respuesta: Este tipo de problemas creo que es preferible implementarlos en Java, antes que
en Modula-2, ya que será el lenguaje que posteriormente se use. Este año fue especial, ya que
al ser de transición se dejaron ambos lenguajes.
Existen varias alternativas, pero de nada sirve que verificar unacasilla se realice en tiempo
constante si luego utilizar su valor se realiza en tiempo lineal. En la siguiente solución se
declaran tres tablas de booleanos que indican si ya hay o no un determinado valor en una
determinada fila, columna o región (cuadrante), respectivamente. Si no es así, entonces es
factible poner el valor en la casilla. Tanto la función de verificación como las de actualizacióntienen un coste computacional constante.
public class Tablero {
int N = 9;
int subN = (int)Math.sqrt (N);
boolean val_en_fil [][] = new boolean [ ] [ ];
boolean val_en_col [][] = new boolean [ ] [ ];
boolean val_en_reg [][] = new boolean [ ] [ ];
boolean valorFactible (int fil, int col, int val) {
int reg = region (fil, col);
return (!val_en_fil [ ][ ] &&
!val_en_col [ ][ ] &&!val_en_reg [
][ ]);
}
void poner (int fil, int col, int val) {
int reg = region (fil, col);
val_en_fil [ ][ ] = true;
val_en_col [ ][ ] = true;
val_en_reg [
][ ]= true;
}
Ejercicios de prácticas
Curso 2007-08
Página 3 de 8
void quitar (int fil, int col, int val) {
int reg = region (fil, col);
val_en_fil [ ][ ] = false;
val_en_col [ ][ ] = false;
val_en_reg [
][ ]= false;
}
int región(int fil, int col) {
)∗
return ( /
}
+
/
;
Febrero 2006-2a (ejercicio 1)
Enunciado: En la práctica obligatoria del presente curso 2005/2006 se ha tenido que diseñar y
desarrollar un algoritmo para resolver el juego del Su-doku. Codifique en Java o en Modula-2
un algoritmo iterativo que recorra el cuadrado de 3 x 3 casillas que corresponda a una casilla
que ocupa las posiciones i, j deltablero.
Respuesta: Se trataba de encontrar la relación entre las posiciones i, j del tablero y las
posiciones de comienzo del cuadrado de 3 x 3 que les corresponde en el tablero del Su-doku.
Supongamos que el tablero tiene como índices 0. .8, 0. .8 y que i y j son de tipo entero, la
relación se puede establecer de la siguiente manera:
int coordFilaInicioCuadrado = ( /3) ∗ 3;
int...