Tengo un algoritmo escrito de manera recursiva no final en java , y me piden que también que ese algoritmo lo pase a manera iterativa con la técnica bottom-up . ¿Alguien me podría documentar sobre esa técnica? He buscado en otros sitios pero no me queda lo bastante claro
2 respuestas
Un ejemplo de uso de esta tecnica es algo sencillo de implementar: El factorial de un numero.
Por ejemplo, podemos usar la definicion recursiva para implementar este evento:
int fact(int n) {
if(n == 0) return 1;
return n * fact(n-1);
}
Ese es un ejemplo de empleo de Top-Down porque vas de casos mas grandes a casos mas pequeños, sin embargo, este mismo problema puede ser resuelto utilizando el Bottom-Up de la siguiente forma:
int f = 1;
for(int i=1;i<=n;i++) f *= i;
// En f queda el factorial
Otro ejemplo que es un poco mas viable dada su estructura es el de la sucesion de Fibonnacci (1 1 2 3 5 8 13 21 34 55 89)
Cada numero es la suma de los dos anteriores, excepto por su puesto, los dos primeros.
La definicion recursiva (Top-Down) viene dada asi:
int fib(int n) {
if(n < 2) return 1;
return fib(n-1) + fib(n-2);
}
Si corremos esta funcion, veremos que tarda demasiado para valores pequeños como 45. Sin embargo, podemos usar la otra técnica haciendo de las siguientes dos formas:
1-
int F[100];
F[1] = F[2] = 1;
for(int i=3;i<=n;i++)
F[i] = F[i-1] + F[i-2];
La construccion es ascendente (de abajo hacia arriba).
Otra via sería:
int a, b=1, c=1;
for(int i=3;i<=n;i++) {
a = b;
b = c;
c = a + b;
}
El resultado queda en c. Espero que te sirva la idea.
Vos tenés Bottom-up y Top-Down, La idea es que Top Down, es primero hacer desde lo más grande a los más chico, es decir, primero creas el método, luego las funciones más generales, y luego te vas metiendo mas para adentro, implementando cada vez funciones más específicas.
Con Bottom-up es lo contrario, desde lo más chico a lo más grande, primero creas los métodos mas específicos y particulares, y luego vas creciendo.
Por ejemplo en Bottom-up, querés crear un Reloj con alarma, entonces creas un método especifico llamado sonarAlarma() que haga esa funcionalidad, luego vas más para arriba, y te pones a pensar el método esTiempoDeSonarAlarma() que seguramente llame internamente a sonarAlamar() y así, seguís hasta llegar a tener todo terminado.