martes, 18 de octubre de 2011

Recursividad:
Es aquella propiedad que provee metodo por la capacidad que puede llamarse a si mismo.
Un metodo que tiene sentencia entre las que se encuentrn al menos una que se llama al propio metodo

No recursividad:
metodo1(...)
{
...
}
metodo(...)
{
...
metodo1()//llamada al metodo2
...
}
Recursividad
Metodo1(...)
{
...
Metodo1
...
}

Aplicaciones de Recursividad
-La suma de los primeros numeros positivos:
-S(6)=S(6)+S(5)+S(4)+S(3)+S(2)+S(1)
-long SumaNenteros(int n)
{
if(n==1)
return 1;
else
return n + SumaNenteros(n-1);
}
-Serie Fibonacci 0,1,2,3,4,8,13,21
-Esta serie inicia con 8 y 1 y tiene la propiedad de que cada elemento es la suma de los 2 elementos.
Suma de los 2 elementos:
ejemplo
0+1=1
1+1=2
2+1=3
3+2=5
5+3=8

 Entonces se puede establecer que:
Fibonacci(0)=0
Fibonacci(1)=1

Fibonacci
Publicado por en No hay comentarios:

viernes, 7 de octubre de 2011

Una pila (stack en inglés) es una lista ordinal o estructura de datos en la que el modo de acceso a sus elementos es de tipo LIFO (del inglés Last In First Out, último en entrar, primero en salir) que permite almacenar y recuperar datos. Esta estructura se aplica en multitud de ocasiones en el área de informática debido a su simplicidad y ordenación implícita de la propia estructura.



Para el manejo de los datos se cuenta con dos operaciones básicas: apilar (push), que coloca un objeto en la pila, y su operación inversa, retirar (o desapilar, pop), que retira el último elemento apilado.
En cada momento sólo se tiene acceso a la parte superior de la pila, es decir, al último objeto apilado (denominado TOS, Top of Stack en inglés). La operación retirar permite la obtención de este elemento, que es retirado de la pila permitiendo el acceso al siguiente (apilado con anterioridad), que pasa a ser el nuevo TOS.

Por analogía con objetos cotidianos, una operación apilar equivaldría a colocar un plato sobre una pila de platos, y una operación retirar a retirarlo.

Las pilas suelen emplearse en los siguientes contextos:

  • Evaluación de expresiones en notación postfija (notación polaca inversa).
  • Reconocedores sintácticos de lenguajes independientes del contexto
  • Implementación de recursividad.



Operaciones

Una pila cuenta con 2 operaciones imprescindibles: apilar y desapilar, a las que en las implementaciones modernas de las pilas se suelen añadir más de uso habitual.
  • Crear: se crea la pila vacía.
  • Apilar: se añade un elemento a la pila.(push)
  • Desapilar: se elimina el elemento frontal de la pila.(pop)
  • Cima: devuelve el elemento que esta en la cima de la pila. (top o peek)
  • Vacía: devuelve cierto si la pila está vacía o falso en caso contrario.


ejemplos de pilas
Estatica

import java.util.Scanner;



/**

 *
 * @author Pollo
 */
public class Pila Estatica {
    public static void main(String[] args) {
        int dato=-1;
        int opcion;
        int num=5;
        int pila[]= new int[num];
        Scanner op = new Scanner(System.in);

        System.out.println("Opciones de Pila");
        System.out.println("1.Insertar");
        System.out.println("2.Eliminar");
        System.out.println("3.Mostrar");
        System.out.println("4.Salir");
        System.out.println("\nElija la operacion que desee:");
        opcion = op.nextInt();
        switch(opcion){
            case 1:
                System.out.println("Inserte el numero:");
                for (int tope = 0; tope < 5; tope++) {
                    Scanner scaner= new Scanner(System.in);
                    dato=scaner.nextInt();
                    pila[tope]=dato;
                }
                break;
            case 2:
                if(dato== -1){
                    System.out.println("No se puede eliminar, pila vacia!!");
                }
                else{
                    
                }
                break;
            case 3:
                System.out.println("La pila tiene los siguientes datos: ");
                for (int tope = 4; tope >= 0; tope--) {
                    System.out.println(pila[tope]);
                }
                break;
            case 4:
                System.exit(1);
                break;
                 default:break;
        }
    }
}
Pila dinamica

2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
#include <stdio.h>
#include <stdlib.h>
 
/* estructura auto-referenciada */
struct nodoPila {      int dato;                  /* define un dato como int */
   struct nodoPila *ptrSiguiente; /* apuntador a nodoPila */
}; /* fin de la estructura nodoPila */
 
typedef struct nodoPila NodoPila; /* sinónimo de la estructura nodoPila */typedef NodoPila *ptrNodoPila; /* sinónimo para NodoPila* */
 
/* prototipos */
void empujar( ptrNodoPila *ptrCima, int info );
int sacar( ptrNodoPila *ptrCima );int estaVacia( ptrNodoPila ptrCima );
void imprimePila( ptrNodoPila ptrActual );
void instrucciones( void );
 
/* la función main comienza la ejecución del programa */int main()
{ 
   ptrNodoPila ptrPila = NULL; /* apunta al tope de la pila */
   int eleccion; /* elección de menú del usuario */
   int valor;  /* entrada int del usuario */ 
   instrucciones(); /* despliega el menú */
   printf( "? " );
   scanf( "%d", &eleccion );
    /* mientras el usuario no introduzca 3 */
   while ( eleccion != 3 ) { 
 
      switch ( eleccion ) { 
          /* empuja el valor dentro de la pila */
         case 1:      
            printf( "Introduzca un entero: " );
            scanf( "%d", &valor );
            empujar( &ptrPila, valor );            imprimePila( ptrPila );
            break;
 
         /* saca el valor de la pila */
         case 2:       
            /* si la pila no esta vacía */
            if ( !estaVacia( ptrPila ) ) {
               printf( "El valor sacsdo es %d.n", sacar( &ptrPila ) );
            } /* fin de if */ 
            imprimePila( ptrPila );
            break;
 
         default:            printf( "Eleccion no valida.nn" );
            instrucciones();
            break;
 
      } /* fin de switch */ 
      printf( "? " );
      scanf( "%d", &eleccion );
   } /* fin de while */
    printf( "Fin del programa.n" );
 
   return 0; /* indica terminación exitosa */
 
} /* fin de main */ 
/* despliega las instrucciones del programa para el usuario */
void instrucciones( void )
{ 
   printf( "Introduzca su eleccion:n"      "1 para empujar un valor dentro de la pilan"
      "2 para sacar un valor dwe la pilan"
      "3 para terminar el programan" );
} /* fin de la función instrucciones */
 /* Inserta un nodo en la cima de la pila */
void empujar( ptrNodoPila *ptrCima, int info )
{ 
   ptrNodoPila ptrNuevo; /* apuntador al nuevo nodo */
    ptrNuevo = malloc( sizeof( NodoPila ) );
 
   /* inserta el nodo en la cima de la pila */
   if ( ptrNuevo != NULL ) {   
      ptrNuevo->dato = info;      ptrNuevo->ptrSiguiente = *ptrCima;
      *ptrCima = ptrNuevo;
   } /* fin de if */
   else { /* no queda espacio disponible */
      printf( "%d no se inserto. Memoria insuficiente.n", info );   } /* fin de else */
 
} /* fin de la función empujar */
 
/* Elimina un nodo de la cima de la pila */int sacar( ptrNodoPila *ptrCima )
{ 
   ptrNodoPila ptrTemp; /* apuntador a un nodo temporal */
   int valorElim; /* valor del nodo */
    ptrTemp = *ptrCima;
   valorElim = ( *ptrCima )->dato;
   *ptrCima = ( *ptrCima )->ptrSiguiente;
   free( ptrTemp );
    return valorElim;
 
} /* fin de la función sacar */
 
/* Imprime la pila */void imprimePila( ptrNodoPila ptrActual )
{ 
 
   /* si la pila esta vacía */
   if ( ptrActual == NULL ) {      printf( "La pila esta vacia.nn" );
   } /* fin de if */
   else { 
      printf( "La pila es:n" );
       /* mientras no sea el final de la pila */
      while ( ptrActual != NULL ) { 
         printf( "%d --> ", ptrActual->dato );
         ptrActual = ptrActual->ptrSiguiente;
      } /* fin de while */ 
      printf( "NULLnn" );
   } /* fin de else */
 
} /* fin de la función imprimePila */ 
/* Devuelve 1 si la pila está vacía, de lo contrario 0 */
int estaVacia( ptrNodoPila ptrCima )
{ 
   return ptrCima == NULL;




Publicado por en No hay comentarios:
Suscribirse a: Entradas (Atom)