Algoritmos recursivos¶
En este documento vamos a plantear una serie de problemas cuya solución se basa en un planteamiento recursivo. Puede que sea para resolver un proceso matemático más o menos complejo, o para explorar todos los posibles caminos en un determinado problema.
1. Recursividad aplicada a problemas numéricos: la prueba de las cajas y las bolas¶
En este reto de Acepta el Reto nos plantean un supuesto concurso de televisión, donde hay N cajas numeradas de 1 a N. En cada caja caben el mismo número de bolas que el número que tiene (es decir, en la caja 1 cabe 1 bola, en la caja 2 caben 2 bolas... y en la caja N caben N bolas).
Los concursantes disponen de un tanque lleno de bolas con el que llenar las cajas, pero deben cumplir ciertos requisitos: en cada paseo, el concursante puede meter bolas en todas las cajas que elija, pero el número de bolas que meta en cada caja debe ser el mismo. Por ejemplo, si elige meter 2 bolas en la caja 2, en el resto de cajas que elija en ese viaje deberá meter 2 bolas también.
Debemos indicar, dado el número de cajas que hay presentes, cuál es el número mínimo de viajes que deberá hacer el concursante para llenarlas.
Vamos a plantear algunos casos iniciales para comprender mejor el problema:
- Si N = 1 caja es muy sencillo: el concursante hace un viaje con una bola y la llena. Este será nuestro caso base:
if(n == 1)
return 1;
- Si N = 2 cajas, el concursante puede hacer un viaje para poner 2 bolas en la caja 2, y luego otro para poner 1 bola en la caja 1 (total: 2 viajes)
- Si N = 3 cajas, el concursante puede poner en un viaje 2 bolas en las cajas 2 y 3, y luego en otro viaje poner 1 bola en las cajas 1 y 3 (total: 2 viajes)
- Si N = 4 viajes, el concursante puede poner 2 bolas en las cajas 2, 3, y 4, luego 1 bola en las cajas 1, 3 y 4 y luego otra bola en la caja 4 (total: 3 viajes)
- Analicemos más en profundidad el caso N = 5, para entender lo que vamos a hacer. En este caso, el concursante podría poner 3 bolas en las cajas 3, 4 y 5. Con esto la caja 3 queda llena, y las cajas 4 y 5 se quedan como las cajas 1 y 2 (a la espera de 1 y 2 bolas, respectivamente). Hemos convertido un problema de 5 cajas en dos problemas de 2 cajas. ¿Cuánto tardamos en llenar 2 cajas? Antes hemos calculado que 2 viajes. Entonces, en total haremos el viaje inicial para dividir el problema en dos más los dos viajes que necesitaremos para los problemas de 2 cajas = 3 viajes.
Esta estrategia de resolución se llama divide y vencerás, y consiste en descomponer un problema complejo en uno o varios problemas más sencillos. En este caso descomponemos un problema de N cajas en dos problemas de N/2 cajas, y así sucesivamente hasta llegar al caso base.
Nuestra función recursiva quedaría de este modo:
static int viajes(int n)
{
// Caso base: n = 1 cajas, 1 viaje
if (n == 1)
return 1;
// Caso recursivo: descomponemos el problema en dos de n/2 y sumamos 1 viaje
else
return 1 + viajes(n/2);
}
Aplicado al reto en cuestión, nos quedará así:
import java.util.Scanner;
public class CajasBolas
{
static int viajes(int n)
{
// Caso base: n = 1 cajas, 1 viaje
if (n == 1)
return 1;
// Caso recursivo: descomponemos el problema en dos de n/2 y sumamos 1 viaje
else
return 1 + viajes(n/2);
}
public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
int cajas;
// Leemos de la entrada hasta que ya no haya más que leer
while (sc.hasNext())
{
cajas = sc.nextInt();
System.out.println(viajes(cajas));
}
}
}
1.1. Tres dedos en cada mano¶
En este reto de Acepta el Reto tenemos que ponernos en la piel de una persona o robot de 3 dedos en cada mano. Una persona con 10 dedos en las manos está acostumbrada a contar en base 10, pero una con 3 dedos debería contar en base 6. Así que nuestra tarea consiste en indicar a qué equivale en base 6 cada uno de los números que nos digan en base 10.
Por ejemplo, el 3 equivale a 3, el 5 equivale a 5, pero el 6 ya equivaldría a un 10. La idea es hacer una función recursiva que convierta un número a base 6. Para ello podemos tener en cuenta que:
- El caso base serán los números menores que 6, que se traducen al mismo número
- Para convertir un número a base X (la que sea, se va dividiendo el número por X y se van acumulando los restos). Por ejemplo, para convertir 14 a base 3 haríamos lo siguiente:
- 14 / 3 = 4 y sobran 2
- 4 / 3 = 1 y sobra 1
- El resultado final se calcula encadenando el último cociente (1) y los restos en orden inverso (112, en este caso, sería el equivalente en base 3 al 14 en base 10)
Ejercicio 1
Plantea una solución recursiva a este problema y resuélvelo en Java en la plataforma.
2. Recursividad aplicada a búsqueda en mapas: invirtiendo en Jaén¶
En este reto de Acepta el Reto tenemos que explorar un mapa para averiguar cuántas parcelas tiene la plantación más grande. Cada mapa es un caso de prueba distinto donde, en la primera línea, nos dirán cuántas filas y columnas tenemos que leer, y después leeremos un mapa de caracteres con esas filas y columnas. Por ejemplo:
8 8
# # #
### #
####
#
# #
### ##
### ##
#
En este caso tenemos un mapa de 8 filas y 8 columnas. Las casillas marcadas con # corresponden a parcelas de una plantación. Todas las parcelas que estén conectadas vertical u horizontalmente forman una plantación independiente. Así, en el ejemplo anterior, la plantación más grande es la inferior izquierda, con un total de 9 parcelas.
Una de las dificultades de este reto es leer los mapas de entrada. Tendremos que irlos leyendo hasta que ya no haya más datos que leer. Para cada uno identificaremos las filas y las columnas, y crearemos un mapa de caracteres (char) de ese tamaño. Después iremos leyendo línea a línea, y guardando cada carácter en su posición. El bucle podría quedarnos así:
Scanner sc = new Scanner(System.in);
int filas, columnas;
String linea;
while (sc.hasNext())
{
filas = sc.nextInt();
columnas = sc.nextInt();
// Pasamos a la siguiente línea
sc.nextLine();
char[][] mapa = new char[filas][columnas];
for (int i = 0; i < filas; i++)
{
// Leemos una línea del mapa
linea = sc.nextLine();
for (int j = 0; j < columnas; j++)
{
// Vamos guardando cada letra en su columna
mapa[i][j] = linea.charAt(j);
}
}
}
Ahora que ya tenemos el mapa guardado llega el momento de procesarlo. Aquí la recursividad nos va a ayudar mucho a contar cuántas parcelas hay juntas. Lo que haremos será recorrer cada casilla del mapa y, cuando encontremos un #, activaremos una función recursiva que nos diga cuántas parcelas hay contiguas a la que hemos encontrado. Nos guardaremos ese valor en una variable, y nos quedaremos con el máximo que encontremos.
int valor, max = 0;
for (int i = 0; i < filas; i++)
{
for (int j = 0; j < columnas; j++)
{
if (mapa[i][j] == '#')
{
valor = calcularArea(mapa, i, j);
if (valor > max)
max = valor;
}
}
}
System.out.println(max);
Nos queda ahora definir el código de esa función calcularArea. Le indicamos como punto de partida las coordenadas donde hemos encontrado un símbolo # en el mapa. Internamente lo que hará será explorar en los cuatro posibles caminos (arriba, abajo, izquierda y derecha), viendo si hay más símbolos así. Si los encuentra, los quitará (para que no se repitan en otra búsqueda) y seguirá buscando desde esa casilla. Por cada símbolo que encuentre sumaremos uno al conteo:
static int calcularArea(char[][] mapa, int fila, int columna)
{
if (fila < 0 || fila >= mapa.length ||
columna < 0 || columna >= mapa[0].length ||
mapa[fila][columna] == ' ')
// Caso base: hemos llegado a una casilla donde no hay más,
// o nos hemos salido del mapa en esa dirección
return 0;
else
{
// Marcamos la casilla como vacía para no contarla en otro proceso
mapa[fila][columna] = ' ';
// Sumamos 1 al conteo y seguimos buscando en 4 direcciones
return 1 + calcularArea(mapa, fila-1, columna)
+ calcularArea(mapa, fila+1, columna)
+ calcularArea(mapa, fila, columna-1)
+ calcularArea(mapa, fila, columna+1);
}
}
Ejercicio 2
Une las piezas del reto anterior y comprueba la solución en la plataforma.
2.1. Los jardines de la Alhambra¶
En este reto de Acepta el Reto tenemos un planteamiento similar al anterior, pero en este caso tenemos que indicar cuántos jardines distintos hay (independientes), ya que en cada uno de ellos se quiere instalar un cortacésped automático (en realidad, nos piden que indiquemos cuántos cortacéspedes hacen falta, que es lo mismo).
Como diferencia, aparte de lo que tenemos que calcular, los espacios en blanco en el mapa anterior ahora se representan con puntos ., pero significan lo mismo: zonas donde no hay parcela o jardín.
Ejercicio 3
Trata de resolver este reto en Java usando una estrategia similar a la anterior.