martes, 18 de octubre de 2011

La Recursividad...

Definición

Recursión es una técnica de programación en el cual un método puede llamarse a sí mismo. Esto seguramente suena como algo raro de hacer o un grave error del que escribió esto. Sin embargo, la recursión una de las más interesantes y una de las técnicas sorprendentemente efectivas en programación.

Algo es recursivo si se define en términos de sí mismo (cuando para definirse hace mención a sí mismo). Para que una definición recursiva sea válida, la referencia a sí misma debe ser relativamente más sencilla que el caso considerado.


En un algoritmo recursivo distinguimos como mínimo 2 partes:

* Caso trivial, base o de fin de recursión: Es la respuesta más sencila a un problema. Es un caso donde el problema puede resolverse sin tener que hacer uso de una nueva llamada a sí mismo. Evita la continuación indefinida de las partes recursivas.


* Parte puramente recursiva: Relaciona el resultado del problema con resultados de casos más simples. Se hacen nuevas llamadas a la función, pero están más próximas al caso base.


EJEMPLO:


package Recursividad;
import java.util.Scanner;
/**
*
* @author pc132-25
*/
public class Fibonacci {
public int fibonnaci ( int n, int fibinf, int fibsup)
{
Scanner teclado = new Scanner (System.in);
System.out.println("Ingrese el numero");
n = teclado.nextInt();
System.out.println("--------------------");
if ((n==0) (n==1))
{
System.out.println("La suma es" +n);
return n;
}
fibinf = 0;
fibsup = 1;
for (int i =2; iint x;
x = fibinf;
fibinf = fibsup;
fibsup = x + fibinf;
System.out.println("" +fibsup);
}
return (fibsup);
}
public static void main(String[] args) {
Fibonacci fb = new Fibonacci();
int n = 0,fibinf = 0,fibsup = 1;
fb.fibonnaci(n, fibinf, fibsup);
}
 
long fibonacci (long n) {
if ( n== 0 n==1)
return n;
else
return fibonacci (n-1) + fibonacci (n-2);
}
}

*-*-*-*-**--*-*-*-*-*-*-*-*-*-*-*-*-*-**--*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*

Utilidad

Cuando la solución de un problema se puede expresar en términos de la resolución de un problema de la misma naturaleza, aunque de menor complejidad.

Sólo tenemos que conocer la solución no recursiva para algún caso sencillo (denominado caso base) y hacer que la división de nuestro problema acabe recurriendo a los casos base que hayamos definido. Como en las demostraciones por inducción, podemos considerar que “tenemos resuelto” el problema más simple para resolver el problema más complejo (sin tener que definir la secuencia exacta de pasos necesarios para resolver el problema).


Funcionamiento

- Se descompone el problema en problemas de menor complejidad (algunos de ellos de la misma naturaleza que el problema original).
- Se resuelve el problema para, al menos, un caso base.
- Se compone la solución final a partir de las soluciones parciales que se van obteniendo.


Diseño de algoritmos recursivos

1. Resolución de problema para los casos base:



  • Sin emplear recursividad.

  • Siempre debe existir algún caso base.

2. Solución para el caso general:



  • Expresión de forma recursiva.


  • Pueden incluirse pasos adicionales (para combinar las soluciones parciales).


Siempre se debe avanzar hacia un caso base: Las llamadas recursivas simplifican el problema y, en última instancia, los casos base nos sirven para obtener la solución.


int factorial (int n)
{

int resultado;

if (n==0) // Caso base
resultado = 1;

else // Caso general
resultado = n*factorial(n-1);
return (resultado);
}

int potencia (int base, int exp)
{

if (exp==0) // Caso base
return 1;

else // Caso general
return base * potencia(base,exp-1);
}


Recursividad vs. iteración

Aspectos que hay que considerar al decidir cómo implementar la solución a un problema (de forma iterativa o de forma recursiva):

- La carga computacional (tiempo de CPU y espacio en memoria) asociada a las llamadas recursivas.

- La redundancia (algunas soluciones recursivas resuelven un problema en repetidas ocasiones).

- La complejidad de la solución (en ocasiones, la solución iterativa es muy difícil de encontrar).

- La concisión, legibilidad y elegancia del código resultante de la solución recursiva del problema.


Ejemplo: Sucesión de Fibonacci


Fib (0) = Fib(1) = 1
Fib (n) = Fib(n - 1) + Fib (n - 2)

Solución recursiva
int fibonacci (int n)
{

if ((n == 0) (n == 1))
return 1;

else
return fibonacci(n-1) + fibonacci(n-2);
}



Ejemplo: Las torres de Hanoi



Mover n discos del poste 1 al poste 3 (utilizando el poste 2 como auxiliar):
hanoi (n, 1, 2, 3);

Solución recursiva:


void hanoi (int n, int inic, int tmp, int final)
{
if (n > 0) {


// Mover n-1 discos de "inic" a "tmp".
// El temporal es "final".

hanoi (n-1, inic, final, tmp);
// Mover el que queda en "inic" a "final"

printf (“Del poste %d al %d.\n”, inic, final);

// Mover n-1 discos de "tmp" a "final".
// El temporal es "inic".

hanoi (n-1, tmp, inic, final);
}
}








Según la leyenda, los monjes de un templo tenían que mover una pila de 64 discos sagrados de un sitio a otro. Sólo podían mover un disco al día y, en el templo, sólo había otro sitio en el que podían dejarlos, siempre ordenados de forma que los mayores quedasen en la base.
El día en que los monjes realizasen el último movimiento, el final del mundo habría llegado…


lunes, 17 de octubre de 2011

"Que Son Las Colas..."

Una cola es simplemente un lugar para almacenar cosas, donde esas cosas se insertan una detrás de otra y para extraer siempre se lo hace por adelante de la cola donde se encuentra el primer elemento. Una cola funciona como una fila o cola de personas, que esperan su turno para ser atendidas, la primera persona atendida es siempre la primera de la fila y cuando llega una persona y queremos incorporarla a cola o adicionarla debemos hacerlo por detrás de la ultima persona en la cola.







Con fines educativos una cola se la puede representar gráficamente así:






Una cola puede almacenar lo que nosotros queramos, números, personas, documentos, cualquier cosa. Esta estructura de datos tiene muchas aplicaciones en la informática al igual que la pila, por ejemplo cuando mandan a imprimir varios documentos a una impresora, existe una cola de impresión que sigue la filosofía, se imprimen los primeros documentos y si quiero imprimir un nuevo documento se adiciona al final de todos los documentos que están esperando a imprimirse.




Existen dos formas de implementar para que la cola sea o bien estática (reservamos un espacio fijo en memoria) o bien dinámica (el tamaño en memoria va creciendo según se requiere), se implementa con arrays o con listas enlazadas respectivamente.



Para manipular elementos en el vector de la cola son necesarias variables que me digan en donde empiezan los elementos y otra en donde terminan,usamos dos variables enteras que llamaremos inicio y fin, estas variables funcionan de la siguiente manera:





Consideremos que nuestro array bidimensional o vector lo creamos con 10 posiciones enumeradas del 0 al 9, la variable inicio guarda una posición antes en la cual se encuentra el primer elemento y la variable fin guarda la posición en donde se encuentra justamente el ultimo elemento.




Entonces los atributos que tendrá nuestra clase Cola de números enteros serán:

1.- private final int MAXIMO = 101;
2.- private int[] V;
3.- private int inicio;
4.- private int fin;




Ahora una vez teniendo esta estructura hay que definir los métodos principales para manejar una cola, estos métodos son:






  • esVacia() : boolean **** retorna verdad si la cola esta vacía es decir no tiene ningún elemento, para esto solo se pregunta si inicio es igual a fin.


  • esLlena() : boolean **** retorna verdad si es que la cola esta llena, pasa cuando se ha llenado todo el vector, la cantidad de elemento que permite la cola lo determina la variable MAXIMO.


  • adicionar(int a) **** adiciona un nuevo elemento a la cola, para esto solo se incrementa la variable fin y se coloca el elemento en esa posición.


  • eliminar() : int **** extrae el primer elemento de la cola, para esto se retorna la posición inicio + 1 del vector y se incrementa inicio en 1.


  • tamaño() : int **** retorna la cantidad de elementos que tiene la cola, para realizar esto se realiza la resta fin - inicio.



  • copiar(Cola B) **** copia tal cual la cola B a la cola destino, al finalizar cola B queda totalmente vacía. Este método es muy útil al momento de hacer operaciones con colas.



Con todos estos métodos básicos se puede realizar cualquier operación que necesitemos.




















miércoles, 12 de octubre de 2011

"Que Es Una Pila..."

Una Pila en palabras sencillas es un lugar donde se almacenan datos, al igual que en un Array, pero una Pila tiene una filosofía de entrada y salida de datos, esta filosofía es la LIFO (Last In First Out, en español, ultimo en entrar, primero en salir). Esta estructura de datos tiene muchas aplicaciones debido a su simplicidad.

Ahora vamos a implementar esta estructura en lenguaje de programación Java, aunque debemos tomar en cuenta que esta clase Pila ya existe en el API de Java, con el nombre Stack (Pila en ingles) en el paquete java.util pero de esta clase hablamos en otro Post. Ahora implementemos desde cero, que nos ayudara a entender su funcionamiento y además porque nos lo piden en materias de estructura de datos. La versión que veremos esta muy bien estructurada y con tipo de datos primitivos, por eso utilizaremos un Array para almacenar los datos asiéndolo así no dinámica (porque no la dimensión de un vector la declaramos en cuando se la crea, es de dimisión fija).
Gráficamente a una pila la representamos así:




Esta pila tiene 4 elementos, para la implementación de la clase haremos uso una variable entera tope que se encargara de decirnos en que posición del Array esta el elemento de la cima, en este caso tope=3 porque en el Array donde ingresamos los datos desde la posición 0, entonces los atributos son:




1.- private final int MAXIMO = 100;
2.- private int[] V;
3.- private int tope;

El atributo MAXIMO podemos poner un numero grande considerando la cantidad aproximada que deseemos almacenar.Los métodos principales de una Pila son:





  • esVacia() --------- retorna verdad o falso si la Pila esta vacía, es decir que no tiene ningún elemento, retorna un boolean.


  • apilar(int a)------ adiciona el elemento a en la Pila.


  • desapilar() ------- elimina el elemento de la cima de la pila.


  • vaciar(Pila B) ---- vacía todo el contenido de la Pila B en la Pila, dejando a B vacía.


  • tamaño() ---------- retorna cuantos elementos tenemos en la Pila.


  • cima() ------------ retorna el elemento de la cima sin eliminarlo de la Pila.


  • mostrar() --------- muestra todos los elementos de la Pila en modo Consola.


Siguiendo la filosofía de adicionar elementos apilando uno debajo de otro.



Para eliminar un elemento, se extrae o desapila un elemento por la cima.




Otro método que necesita explicación es el método vaciar, un método muy útil que también utilizamos para mostrar la Pila es el vaciar.




Luego la Pila principal queda vacía y la pila B queda así: