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
Sin resumen de edición |
Sin resumen de edición |
||
Línea 1:
== Clase patrón ==
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;
}
|