Recursividad - Ejercicios resueltos 100

Si fuéramos menos impacientes no tendríamos problema con el backtracking.

Aquellos que son usuarios (y sólo usuarios), están tan acostumbrados a que sus amados computadores les resuelvan todo que no están ni cerca de experimentar un trabajo repetitivo de ensayo y error.

El problema de las ocho reinas es un clásico del ingenio y cual más cual menos, debe utilizar el backtracking para solucionarlo.

El algoritmo general del problema de las ocho reinas se resuelve así:

1. Se coloca una reina en alguna de las filas.
2. Se siguen intentando colocar la siguiente reina en la siguiente fila preguntando en cada posición si está amenazada por otra reina existente.
3. Si no quedan más posiciones, se vuelve a la pieza anterior y se sigue intentando por las siguientes columnas de su fila

¿Nada más?

Nada más. Eso es el algoritmo general. Cuanto más general mayores posibilidades de hacerlo recursivo.

5.- Confeccione una función recursiva que llene un tablero de ajedrez con 8 reinas sin que estas se amenacen entre sí:


La implementación en Java es la siguiente:

public void reinas(int i, int j, int dama)
{
 
 //  Mientras no haya recorrido todo el tablero...
 if ( estaDentro(i,j) )
 {
 
  //  ...y si la posición en la que voy a poner la 
  //  reina no está amenazada...                   
  if (noAmenazada(i,j))
  {
   //Ponemos la reina
   T[i][j]=dama;

   //BORDE: Si logramos colocar la última reina
   //Imprimimos el tablero con la solución
   if (dama == N) imprimir();

   //Y si no es la última recurrimos por la
   //siguiente fila
   reinas(i+1, 0, dama + 1);

   //Si lo anterior falla sacamos la reina
   T[i][j]=0;
  }
  // Si la posición está amenazada recurrimos por la
  // siguiente columna.
  reinas(i, j+1, dama);

  //Si lo anterior falló, quitamos la reina
  T[i][j]=0;
 }
}

Recursividad - Ejercicios resueltos 11

No existe una única forma de implementar una función recursiva. Cuando una solución es de tipo procedural puede que la primera acción no sea el "borde", si no una acción concreta, para luego a través de la validación hacer el llamado recursivo.

4.- Confeccione una función recursiva que llene un tablero n-goro. Un tablero n-goro es una matriz de n x n+1 que se llena consecutivamente en diagonal y cada vez que se desborda la continuidad se sigue por la fila o columna desocupada contigua según corresponda:

1	17	13	9	5
6	2	18	14	10
11	7	3	19	15
16	12	8	4	20

Empezamos inmediatamente a llenar la matriz empezando por la primera posición y continuamos por la diagonal (posiciones 0,0 1,1 2,2 3,3 ... etc).

Borde: Si i=n y j=n+1, quiere decir que llegamos a la última posición de la matriz y podemos imprimir.

Si no es así, debemos revisar si la i (filas) excedió la última posición y debemos mantener el número que queríamos colocar y la posición de la columna pero cambiar la fila por la 0 (empezar de arriba de nuevo).

También debemos validar que la j no exceda n+1, lo que significará que se habrá pasado de la última columna y en ese caso, mantenemos la fila y el número para cambiar la j por 0 (primera columna).

La implementación en Java es la siguiente:

public void nGoro(int i, int j, int paso){
 /*************************************
  * Si se mantiene dentro del tablero,*
  * llenar la posición con el valor   *
  * en la recursión y continuar por la*
  * posición en diagonal.             *
  *************************************/
 
 if( estaDentro(i,j) ){
  T[i][j] = paso;
  nGoro(i+1, j+1, paso + 1);
 }
 /****************************************
  * BORDE:                               *
  * Si se ha llegado a la última posición*
  * se imprime y no hace nada más        *
  ****************************************/
 else if( (i==N) && (j==N+1))
   imprimir( );
 
 /****************************************
  * Si    se ha pasado de la última fila *
  * conservar número y columna y recurrir*
  * por la primera fila                  *
  ****************************************/
 else if ( i == N )
  nGoro(0, j, paso);
  
 /****************************************
  * Si se excede la última columna se    *
  * conserva el número y la fila y se    *
  * recurre por la primera columna.      *
  ****************************************/
 else if ( j == N+1 )
  nGoro(i, 0, paso);
}

Recursividad - Ejercicios resueltos 10

Otro algoritmo interesante es el que descompone un número cualquiera en sus factores primos. Lo más entretenido de este ejercicio es que nos prepara para para  recorrer datos en una estructura de árbol (como en el ejercicio de a elevado a n).

3.- Confeccione una función recursiva que permita determinar o presentar los factores primos de un número n.
Ejemplo: 90 = 9 * 10 = (3 * 3) * (2 * 5).

Encontrar los factores "medios" de un número (por así decirlo) pasa por encontrar el factor más cercano a la raíz cuadrada del número. Tomando sólo la parte entera de la raíz cuadrada de n se puede obtener el factor exacto o un número un poco menor. Si es menor lo incrementamos hasta encontrar el factor buscado. El otro factor se obtiene dividiendo n por el factor encontrado. Si los factores no son primos se recurre con estos valores. Por lo tanto la condición de paro (borde) es que n se haya transformado en primo.

La implementación en Java es la siguiente:

public static void factoresPrimos(int n) {

 //Si n es primo se imprime.
 if (esPrimo(n)){
  System.out.print("*"+n+" ");
  return;
 }

 //Si n no es primo calculamos el primer factor... 
 int factor1 = (int) Math.sqrt(n);
 
 while (n % factor1 !=0) factor1++;
 
 //... recurrimos por el primer factor
 factoresPrimos(factor1);

 //... y luego recurrimos por el siguiente factor.
 factoresPrimos(n/factor1);
}

Recursividad - Ejercicios resueltos 1

Anteriormente, habíamos hecho un algoritmo para transformar un número decimal a string binario. Con una pequeña modificación podemos hacer lo mismo pero en base decimal.

2.- Confeccione una función recursiva que reciba un número natural y retorne un string conteniendo su equivalente hexadecimal.

El algoritmo es el mismo del anterior: Se divide consecutivamente el número entero por 16 (la base) y se concatenan los restos de la división. Cabe destacar que como la recolección de los restos debe ser en sentido inverso la recursión debe ser antes de la concatenación con el dígito resultante.


La implementación en Java es la siguiente:

public static String hexadecimal(int n){

 //Si el entero llega a ser cero, quiere decir que terminó la
 //división y como no queda resultado que calcular retornamos
 //un espacio vacío (no en blanco, ojo)
 if (n==0) return "";

 //Pero si aún es mayor que cero debemos calcular el resto de
 //la división por la base y evaluar el caso especial de cada
 //valor. Recordemos que la base 16 o hexadecimal tiene seis
 //dígitos más que representan los números decimales del 10
 //al 15.
 int digHex = n%16; 

 switch (digHex){
  case 10: return hexadecimal(n/16)+"A"; 
  case 11: return hexadecimal(n/16)+"B"; 
  case 12: return hexadecimal(n/16)+"C"; 
  case 13: return hexadecimal(n/16)+"D"; 
  case 14: return hexadecimal(n/16)+"E"; 
  case 15: return hexadecimal(n/16)+"F"; 
  default: return hexadecimal(n/16)+Integer.toString(digHex);
 }
}

Recursividad - Ejercicios resueltos 0

Sin duda, la idea de recursividad es clara pero su implementación es lo más engorroso. Basta con leer "El Principito" de Antoine de Saint-Exupéry para reírnos con el diálogo recursivo del niño con el borracho (Capítulo XII).

Vamos a ir planteando algunos problemas y vamos a pasar por el planteamiento hasta llegar a la implementación.

1.- Confecciones un algoritmo que permita calcular la potencia de a elevado a n, según se aprecia en los siguientes cálculos.
a) exponente par:
$$5^8 = 5^4 \times 5^4 \\ 5^4 = 5^2 \times 5^2 \\ 5^2 = 5 \times 5\\$$

b) exponente impar: $$5^7 = 5^3 \times 5^3 \times 5\\ 5^3 = 5 \times 5 \times 5 \\ $$ Como vemos en la gráfica tenemos la condición de paro (borde) en el fondo de la secuencia: "Si el exponente es 1 retorne la base".
Ahora que tenemos el borde tenemos que fijarnos en el resto del problema.

Si nos fijamos bien, en el caso del exponente par se debe dividir la potencia en la multiplicación de la base elevada a la mitad del exponente original. A su vez, si el exponente es mayor a 1, se debe repetir esta tarea (se crea una especie de árbol).

Para el caso de los exponentes impares, se separa la expreción en las base sola (elevada a 1 en realidad) por la base elevada al exponente menos 1 dividido por la mitad (fácil de intuir, difícil de explicar).

La implementación en Java es la siguiente:

public static int elevado(int a, int n){

 //Si el exponente es 1 retorna la base.
 if (n==1) return a;

 //Si el exponente es par retorna la multiplicación
 //de la base elevado a la mitad del exponente
 //consigo misma.
 if (n%2==0) return (elevado(a,n/2) * elevado(a,n/2));

 //Si el exponenete es impar retorna la base multiplicada
 // por la base elevada a la mitad del exponente -1 por la
 //base elevada al exponenete menos uno.
 else return (elevado(a,(n-1)/2) * elevado(a,(n-1)/2) * a);
}