Bienvenidos señoras y señores a la octava práctica de OCA J. Esta vez se trataba de que aprendiésemos sobre la tabla Hash y la recursión. Comenzamos la clase con explicaciones sobre ambas, pero la que trataba de la primera nos pareció muy constructiva. Básicamente entendimos la tabla Hash como una tabla compuesta por listas enlazadas que hará más fácil las búsquedas. Hay distintas formas con las que podemos buscar datos e insertar otros nuevos, por eso siempre debemos usar el más adecuado para cada situación, hay que utilizar la más rápida, así no se desperdiciará tiempo ni memoria. Ejemplos de ello son el array, las listas enlazadas, una pila, una cola, un vector y la tabla Hash. Ahora comparemos entre ellos lo que tardan en insertar y el tiempo de búsqueda.
Respecto al array, hay que tener siempre en cuenta, antes de nada, que es estático, por tanto tiene un tamaño fijo y se desperdicia memoria. Pero para explicar lo que queremos, supongamos que su tamaño es mayor que el del último valor ocupado. En un array el tiempo que se tarde en insertar un elemento será constante, da igual que sea en la posición 0 o en la 10.000. Para buscar un elemento tiene más miga, ya que hay que recorrer el array hasta que hallemos lo que buscamos. Si tenemos n elementos en el array, entonces el tiempo será de n/2.
Las listas enlazadas también tardan un tiempo constante en insertar, y n/2 en buscar. Por ejemplo, la agenda del móvil está implementada con una lista enlazada.
El contenedor de tipo pila, tarda en insertar un tiempo constante y es el peor a la hora de buscar un elemento, siendo mayor de n (>n).
El contenedor de tipo cola, como todos, tarda en insertar un elemento un tiempo constante, y en buscar un elemento un tiempo n.
Y por último, miramos la tabla Hash, la cual tarda en insertar un tiempo constante, y en buscar un elemento, un tiempo constante también.
Tras esto, y la explicación de la recursión, poniendo como ejemplo el famoso y típico Fibonacci, para la cual existe otra forma de resolverla que de la forma recursiva de siempre, se puede iterativamente con la fórmula: .Nos quedamos anonadados, la verdad.
Empezamos a leer la práctica. “Ala que guay, haremos la lista de trucos de un videojuego!!!”, y…….chan-chaaaaaaaaaaaaaan, volvió a salir la vena friki que llevamos dentro. No tuvimos ningún tipo de problema para resolver este ejercicio. Apoyándonos en los apuntes, la tabla salió fácilmente. Para pensar en los trucos rápidamente salieron de nuestras bocas las palabras que nos identifican como raritos: “PONGAMOS BOMBAS, ..Y FLECHAS…Y UN ESCUDO…Y UNA PRINCESA PARA QUE NO SE QUEDE SOLO AL FINAL, JAJA ”, nos venían muchísimas ideas pero como se trataba de poner mínimo 10, decidimos poner sólo ese número porque sino no todavía seguiríamos escribiendo. La verdad que en ese momento nos lo pasamos muy bien. J Como estábamos tan animados, también queríamos que al comprobar si estaba bien hecha nuestra tabla Hash, nos fuese ameno. Para ello, hicimos que el usuario introdujese el nombre de una fruta (de ahí el import.io.*), si está en la lista, se imprimirá por pantalla lo correspondiente a ella. Cada fruta tiene una correspondencia gracias al método put. El método put(clave,valor), inserta en la lista el objeto valor asociado al objeto clave. Antes de esto creamos un objeto Hashtable inicializado en 10 elementos, las 10 ricas frutitas.
Como disponíamos del get(clave), el cual obtiene el objeto asociado al objeto clave, llamamos al objeto Hashtable con él, pasándole por parámetro el String que introdujese por teclado el usuario. Tuvimos un error cuando al realizar esta operación no colocamos el casting a String, nos dimos cuenta al compilar. Al principio colocamos String temp2=trucos.get(temp); y nos quedamos tan anchos 
, cuando trucos.get(temp) nos devuelve un Object, ya que get devuelve un Object.
Después rematamos la faena colocando un mensaje por pantalla por si el usuario no introduce nada.
|
import java.io.*; ;
public class Tabla
{ public static void main(String[] args) { Hashtable trucos=new Hashtable(10); trucos.put(“PERA”,“Vidas Infinitas”); trucos.put(“MANZANA”,“Recuperas Una vida”); trucos.put(“MELON”,“Consigues El Arco”); trucos.put(“SANDIA”,“Consigues Las Flechas”); trucos.put(“PEPINO”,“BAZOCAAAAAAA!!!”); trucos.put(“PLATANO”,“Invencible Durante 20 segundos”); trucos.put(“NARANJA”,“Invisible”); trucos.put(“MANGO”,“Escudo”); trucos.put(“PAPAYA”,“Bombas”); trucos.put(“PINA”,“SIGUIENTE NIVEL!!!”); trucos.put(“UVA”,“Te Acompana La Princesa yujuuu!!!”); try { BufferedReader datos=new BufferedReader(new InputStreamReader(System.in)); System.out.print(“Introduzca palabra clave: “); String temp=(datos.readLine()).toUpperCase(); String temp2=(String) trucos.get(temp); if(temp2==null) System.out.println(“No hay truco para esa clave lo siento  “);else System.out.println(temp2); } catch(IOException e) { System.err.println(e); } } }
|
A continuación compilamos y nos saltaba algo muy extraño. Se puede observa en el primer mensaje de la ventana siguiente. No entendíamos que era eso. Rodrigo, que entiende de MS2, pulso a la sentencia ya escrita –Xlint. Se podían ver entonces unos warnings. Los warnings no son errores como nosotros al principio pudimos llegar a pensar, esto ocurre porque si en Java 1.6 no le ponemos información a la pila saltan warning, ya que antes tan sólo se podían hacer una pila de objetos (Stack), ahora la pila se puede formar de lo que se quiera (Stack<E>). Resultó que no era un problema nuestro, sino que debía saltar.
Comprobamos entonces que todo iba según lo esperado. Menos mal porque los warnings nos dieron un buen susto jeje.
Lo esencial de esta clase era entender la recursividad. Creo que el objetivo era que nos diésemos cuenta de que siempre, en un método recursivo, tiene que haber una condición de parada o caso base, sino sería un bucle infinito. Cuando dudemos entre escoger un caso base u otro, nosotros optamos por quedarnos por el que más casos englobe. Es lo primero que hay que poner, y seguidamente la llamada recursiva, la cual vuelve a llamar al método pero produciendo un cambio en los parámetros, ya que, de lo contrario, volveríamos a encontrarnos con que es un método infinito. Llegaría un momento en el que pararía, sería cuando la pila de Java se llenará de tanto repetir la operación, saltando la excepción StackOverflow (Pila desbordada). Por lo anteriormente explicado, la llamada recursiva debe tender al caso base obligatoriamente, se corre sino el riesgo de quedarse igual o alejarse, entonces no acabaría hasta que saltase la excepción.
Algo que también observamos es que no se usan variables locales dentro de un método recursivo ni de caso base, ya que cada vez que se llamase al método, esa variable siempre tiene el mismo valor.
En fin, no tuvimos ningún problema para entender el funcionamiento de los métodos de la clase Recursividad. El que más nos llamó la atención fue el inverso, porque tiene el caso base y el recursivo en la misma sentencia ¡¡AMAZING!!
|
/**
public class Recursividad
{ // Factorial de un numero. public long factorial(long num) { if (num==1) return 1; else return num * factorial(num-1); } // Qué hace el siguiente algoritmo public void p1(int a) { if (a>0) { System.out.println(a); p1(a-1); } else System.out.println(“FIN”); } // qué hace el siguiente programa public void p2(int a, int b) { if (a>0) { p2(a-1,b+a); } else System.out.println(b); } // Método recursivo que suma los elementos de un array de enteros. public long suma(long [] tabla, int posActual, int tamano) { // Condición de salida en el último elemento if (posActual == tamano -1 ) return tabla[posActual]; else return tabla[posActual] + suma(tabla, posActual+1, tamano); } // Obtener el inverso de un número dado: // El inverso de 254 es 452 // 254 mod 10 = 4 (lo saco) // 254 div 10 = 25 // 25 mod 10 = 5 (lo saco) // 25 div 10 = 2 // 2 mod 10 = 2 (lo saco) public void inverso(int n) { System.out.print(n % 10); if (n>=10) inverso(n/10); } // Función de Fibonacci // Fib(1) = 1 // Fib(2) = 1 // Fib(3) = Fib(2) + Fib (1) // Fib(4) = Fib(3) + Fib (2) public long fibonacci(long num) { if ((num == 1) || (num == 2)) return 1; else return fibonacci(num-2) + fibonacci(num-1); } // Probando recursividad public static void main(String []args) { Recursividad r = new Recursividad(); System.out.println(“El factorial de 10 es: “ + r.factorial(10)); // Qué hace el método p1: 4,3,2,1 FIN r.p1(4); // ¿Cuál es el resultado de llamar a p2 así? r.p2(3,0); // Suma recursiva en un array long [] tabla = {1,2,3,4,5,6,7,8,9,10}; System.out.println(“La suma de los elementos del array es: “ + r.suma(tabla, 0, tabla.length)); // Fibonacci System.out.println(“Fibonacci de 10: “ + r.fibonacci(5)); // Inverso System.out.print(“El inverso de 254 es: “ ); r.inverso(254); System.out.println(); } // main } // Recursividad.
|
Si compilamos y ejecutamos aparece lo siguiente:
Hasta aquí llegamos en la sesión de laboratorio.
Lo que sigue corresponde al ejercicio 3 pero se acabó en casa. Lo que nos pedían era que mediante recursividad busquemos en el “tétris” si hay alguna línea, es decir que si hay en una fila un conjunto de piezas sin tener espacios vacíos lo detectemos, nosotros hemos llegado un poco más lejos no solo lo hemos detectado si no que si encontramos una linea completa la eliminamos como lo haría el tétris de verdad, lo suyo seria volver a recolocar las piezas pero esa parte os la dejamos a vosotros, si alguien lo consigue que ponga un post con el enlace a su blog. La rutina anterior tenemos que hacer con la matriz entera, asiesq ahi esta el código.
En caso de alguna duda, referirse con un comentario. Gracias y hasta pronto.
|
class Pieza |
|
public class Matriz |
|
|
