Diferencia entre revisiones de «Manual del estudiante de Ingeniería en Sistemas de UTN/Diseño e Implementación de Estructuras de Datos/Guías prácticas/Recursividad/Solución al ejercicio 3 de recursividad»

Contenido eliminado Contenido añadido
Rgfernan (discusión | contribs.)
Sin resumen de edición
Sin resumen de edición
 
Línea 1:
== Clase patrón ==
Calculando la complejidad del algoritmo recursivo.
public class Patron {
int x;
int y;
int L;
public int solucionRecursiva(int lado,int xCentro,int yCentro);
public int solucionIterativa(int lado,int xCentro,int yCentro);
public Patron(int x,int y,int L)
{
this.x=x;
this.y=y;
this.L=L;
}
}
 
== El método recursivo ==
 
public int solucionRecursiva(int lado,int xCentro,int yCentro)
{
int dentro=0;
if (x<=xCentro+lado/2&&x>=xCentro-lado/2&&
y<=yCentro+lado/2&&y>=yCentro-lado/2)
dentro=1;
if (lado<=2) //caso base
return dentro;
//caso recursivo
return dentro+
solucionRecursiva(lado/2,xCentro+lado/2,yCentro+lado/2)+
solucionRecursiva(lado/2,xCentro+lado/2,yCentro-lado/2)+
solucionRecursiva(lado/2,xCentro-lado/2,yCentro+lado/2)+
solucionRecursiva(lado/2,xCentro-lado/2,yCentro-lado/2);
}
 
== La complejidad del método ==
En este caso, el algoritmo abre 4 hijos, pero y la complejidad general para un algoritmo que abra n hijos es:
 
Línea 31 ⟶ 66:
 
El orden de la complejidad del algoritmo queda entonces en función del ancho del cuadrado de entrada, y resulta de <math>O(a^2)</math>.
 
== Transformación del método recursivo en iterativo ==
 
public int solucionIterativa(int lado,int xCentro,int yCentro)
{
int cuenta=0;
Stack cuadradosAProcesar;
cuadradosAProcesar=new Stack();
cuadrado primero=new cuadrado(lado,xCentro,yCentro);
cuadrado actual;
cuadradosAProcesar.push(primero);
while (!cuadradosAProcesar.isEmpty())
{
actual=(cuadrado)cuadradosAProcesar.pop();
if(x<=actual.getX()+actual.getLado()/2&&
x>=actual.getX()-actual.lado/2&&
y<=actual.getY()+actual.getLado()/2&&
y>=actual.getY()-actual.getLado()/2)
cuenta++;
if(actual.getLado()>2)
{
cuadradosAProcesar.push(
new cuadrado(actual.getLado()/2,
actual.getX()+actual.getLado()/2,
actual.getY()+actual.getLado()/2));
cuadradosAProcesar.push(
new cuadrado(actual.getLado()/2,
actual.getX()+actual.getLado()/2,
actual.getY()-actual.getLado()/2));
cuadradosAProcesar.push(
new cuadrado(actual.getLado()/2,
actual.getX()-actual.getLado()/2,
actual.getY()+actual.getLado()/2));
cuadradosAProcesar.push(
new cuadrado(actual.getLado()/2,
actual.getX()-actual.getLado()/2,
actual.getY()-actual.getLado()/2));
}
}
return cuenta;
}