listas pilas colas recursividad

Listas – Pilas - Colas. Resumen 1

CONTENIDO

1 ESTRUCTURAS DINÁMICAS DE DATOS. ..................................................... 4

1.1 LISTAS SIMPLEMENTE LIGADAS. .......................................................... 4 1.2 LISTAS DOBLEMENTE ENLAZADAS ...................................................... 6

1.3 LISTAS SIMPLEMENTE LIGADAS CIRCULARES ................................... 7 1.4 LISTAS SIMPLEMENTE LIGADAS CON REGISTRO CABEZA ............... 8 1.5 LISTAS SIMPLEMENTE LIGADAS CIRCULARES CON REGISTRO

CABEZA .................................................................................................... 8 1.6 LISTAS DOBLEMENTE LIGADAS CIRCULARES .................................... 9 1.7 LISTAS DOBLEMENTE LIGADAS CON REGISTRO CABEZA ................ 9 1.8 LISTAS DOBLEMENTE LIGADAS CIRCULARES CON REGISTRO

CABEZA .................................................................................................. 10 1.9 PILAS ...................................................................................................... 10 1.10 COLAS (FILAS) ....................................................................................... 11

2 ALGUNOS TIPS ............................................................................................. 12

3 ALGORITMOS ............................................................................................... 13 3.1 LISTAS SIMPLEMENTE LIGADAS ......................................................... 13

3.1.1 Subprograma que recorre una lista simplemente ligada ................... 13

3.1.2 Subprograma que inserta en una lista simplemente ligada ordenada (manteniendo el orden) ..................................................... 13

3.1.3 Subprograma (función) que busca donde insertar en una lista simplemente ligada (ordenada) ......................................................... 14

3.1.4 Subprograma que inserta en una lista simplemente ligada siempre al principio. .......................................................................... 14

3.1.5 Subprograma que inserta en una lista simplemente ligada siempre al final. ................................................................................. 15

3.1.6 Subprograma (función) que busca el último nodo de una lista simplemente ligada ........................................................................... 15

3.1.7 Subprograma que busca un dato en una lista simplemente ligada (no ordenada) .................................................................................... 16

3.1.8 Subprograma que borra un dato de una lista simplemente ligada. ... 16

3.2 LISTAS SIMPLEMENTE LIGADAS CIRCULARES ................................. 17 3.2.1 Subprograma que recorre una lista simplemente ligada circular ....... 17 3.2.2 Subprograma que inserta en una lista simplemente ligada circular

ordenada (manteniendo el orden) ..................................................... 17 3.2.3 Subprograma (función) que busca donde insertar en una lista

simplemente ligada circular (ordenada) ............................................ 18 3.3 LISTAS SIMPLEMENTE LIGADAS CIRCULARES CON REGISTRO

CABEZA .................................................................................................. 19 3.3.1 Subprograma que recorre una lista simplemente ligada circular

con registro cabeza ........................................................................... 19 3.3.2 Subprograma que inserta en una lista simplemente ligada circular

con registro cabeza, ordenada (manteniendo el orden) .................... 19


3.3.3 Subprograma (función) que busca donde insertar en una lista simplemente ligada circular con registro cabeza (ordenada) ............ 20

3.3.4 Subprograma que busca un dato en una lista simplemente ligada (no ordenada) .................................................................................... 20

3.3.5 Subprograma que borra un dato de una lista simplemente ligada circular con registro cabeza .............................................................. 21

3.4 LISTAS DOBLEMENTE LIGADAS .......................................................... 22

3.4.1 Subprograma que recorre una lista doblemente ligada de izquierda a derecha ........................................................................... 22

3.4.2 Subprograma que recorre una lista doblemente ligada de derecha a izquierda ......................................................................................... 22

3.4.3 Subprograma que inserta en una lista doblemente ligada ordenada (manteniendo el orden) ..................................................... 22

3.4.4 Subprograma (función) que busca donde insertar en una lista doblemente ligada (ordenada) .......................................................... 23

3.4.5 Subprograma que inserta en una lista doblemente ligada siempre al principio. ........................................................................................ 24

3.4.6 Subprograma que inserta en una lista doblemente ligada siempre al final. ............................................................................................... 24

3.4.7 Subprograma (función) que busca el último nodo de una lista doblemente ligada ............................................................................. 25

3.4.8 Subprograma que busca un dato en una lista doblemente ligada (no ordenada) .................................................................................... 25

3.4.9 Subprograma que borra un dato de una lista doblemente ligada. ..... 26 3.5 LISTAS DOBLEMENTE LIGADAS CIRCULARES .................................. 27

3.5.1 Subprograma que recorre una lista doblemente ligada circular izquierda a derecha ........................................................................... 27

3.5.2 Subprograma que recorre una lista doblemente ligada circular derecha a izquierda ........................................................................... 27

3.5.3 Subprograma que inserta en una lista doblemente ligada circular ordenada (manteniendo el orden) ..................................................... 27

3.5.4 Subprograma (función) que busca donde insertar en una lista doblemente ligada circular (ordenada) .............................................. 28

3.6 LISTAS DOBLEMENTE LIGADAS CIRCULARES CON REGISTRO CABEZA .................................................................................................. 30

3.6.1 Subprograma que recorre una lista doblemente ligada circular con registro cabeza de izquierda a derecha ............................................ 30

3.6.2 Subprograma que recorre una lista doblemente ligada circular con registro cabeza de derecha a izquierda ............................................ 30

3.6.3 Subprograma que inserta en una lista doblemente ligada circular con registro cabeza, ordenada (manteniendo el orden) .................... 30

3.6.4 Subprograma (función) que busca donde insertar en una lista doblemente ligada circular con registro cabeza (ordenada) .............. 31

3.6.5 Subprograma que busca un dato en una lista doblemente ligada (no ordenada) .................................................................................... 31

3.6.6 Subprograma que borra un dato de una lista doblemente ligada circular con registro cabeza .............................................................. 32


4 NOTAS ........................................................................................................... 33 5 RECURSIVIDAD ............................................................................................ 34

5.1 Números de Fibonacci ............................................................................. 36 5.2 Considere la siguiente ecuación recurrente: ............................................ 37 5.3 Considere las siguientes sucesiones: ...................................................... 38 5.4 Definición recursiva para elevar un número a una potencia: ................... 39 5.5 Número de Combinaciones ..................................................................... 39

5.6 Algoritmo de Euclides .............................................................................. 39 5.7 Técnica de diseño “dividir para vencer” ................................................... 40


1 ESTRUCTURAS DINÁMICAS DE DATOS.

Las estructuras dinámicas de datos son estructuras que crecen a medida que ejecuta un programa. Una estructura dinámica de datos es una colección de elementos – llamadas nodos - que son normalmente registros. Al contrario de un arreglo que contiene espacio para almacenar un número fijo de elementos, una estructura dinámica de datos se amplía y contrae durante la ejecución del programa, basada en los registros de almacenamiento de datos del programa. Las estructuras dinámicas de datos se pueden dividir en dos grandes grupos:

Lineales o Pilas. o Colas. o Listas enlazadas.

No lineales o Árboles. o Grafos.

Las estructuras dinámicas de datos se utilizan para almacenamiento de datos del mundo real, que están cambiando constantemente. Un ejemplo típico, es la lista de pasajeros de una línea aérea. Si esta lista se mantuviera en orden alfabético en un arreglo, sería necesario hacer espacio para insertar un nuevo pasajero por orden alfabético. Esto requiere utilizar un ciclo para copiar los datos del registro de cada pasajero al siguiente elemento del arreglo. Si en su lugar se utilizará una estructura dinámica de datos, los nuevos datos del pasajero se pueden insertar simplemente entre dos registros existentes con un mínimo de esfuerzo.

1.1 LISTAS SIMPLEMENTE LIGADAS.

Una lista enlazada o encadenada es un conjunto de elementos en los que cada uno contiene la posición o dirección de memoria del siguiente elemento de la lista. Cada elemento de la lista encadenada debe tener al menos dos campos: Un campo que tiene el valor del elemento y un campo (enlace o link) que contiene la posición del siguiente elemento, es decir, su conexión, enlace o encadenamiento. Los elementos de una lista son enlazados por medio de los campos enlaces. Las listas encadenadas tienen una terminología propia que se suele utilizar normalmente. Primero, los valores se almacenan en un nodo.


Los componentes de un nodo se llaman campos. Un nodo tiene al menos un campo de dato o valor y un enlace (indicador o puntero) con el siguiente campo. El campo enlace apunta (proporciona la dirección de) al siguiente nodo de la lista. El ultimo nodo de la lista encadenada, por convenio, se suele representar por un enlace con la palabra Null (nulo), una barra inclinada, el número cero (0), y en ocasiones, el símbolo eléctrico de tierra o masa.

Una lista enlazada o encadenada es una lista que se construye empleando apuntadores. Además, no tiene un tamaño fijo, sino que puede crecer y decrecer durante la ejecución del programa. Se constituyen como variables dinámicas. En las listas enlazadas no es necesario que los elementos en la lista sean almacenados en posiciones físicas adyacentes, ya que el apuntador indica dónde se encuentra el siguiente elemento de la lista. Por consiguiente, la inserción y borrado no exigen desplazamiento como en el caso de las listas contiguas o vectores.

Para eliminar un elemento de una lista enlazada, solo es necesario cambiar el puntero del elemento anterior al elemento siguiente del que deseamos eliminar. Para insertar un elemento en determinada posición, solo necesitamos cambiar el apuntador de la posición anterior a donde queremos insertar a nuestro nuevo


elemento y este elemento deberá direccionar el elemento al que anteriormente apuntaba el elemento que quedó antes del nuevo elemento. Una lista enlazada sin ningún elemento se llama lista vacía. Su puntero inicial o de cabecera tiene el valor nulo (nil o Null) o cero. Una lista enlazada se puede definir por:

El tipo de sus elementos: campo de información (datos) y campo enlace (puntero).

Un puntero de cabecera que permite acceder al primer elemento de la lista.

Un medio para detectar el último elemento de la lista: puntero nulo (nil) o cero.

Las operaciones que hay que realizar con una lista enlazada son:

Definir y crear la lista.

Recorrer los nodos de una lista enlazada.

Agregar un nodo a la lista. 1. Al final. 2. Al Principio. 3. En el centro.

Eliminar un nodo de la lista. 1. Al final. 2. Al Principio. 3. En el centro.

1.2 LISTAS DOBLEMENTE ENLAZADAS

Una lista doblemente enlazada o encadenada es un conjunto de elementos en los que cada elemento además de contener la posición o dirección del siguiente elemento de la lista, contiene la dirección del anterior elemento en la lista. Cada elemento de la lista doblemente encadenada debe tener al menos tres campos: Un campo que tiene el valor del elemento y dos campos (enlaces o links) que contiene la posición del anterior y siguiente elemento, es decir, su conexión, enlace o encadenamiento. Los elementos de una lista son enlazados por medio de los campos enlaces.


En este tipo de listas el recorrido se puede hacer en dos direcciones: de izquierda a derecha y de derecha a izquierda. Para poder lograr esto el diseño de los nodos se hace con dos campos de enlace: uno que llamaremos Liga Izquierda (LI) y otro que llamaremos Liga Derecha (LD). Un esquema general de dicho nodo es:

LIGA IZQUIERDA

AREA DE DATOS

LIGA DERECHA

LI(X) X LD(X) LI(X): Apunta hacia el registro anterior a X LD(X): Apunta hacia el registro siguiente a X La propiedad fundamental de las listas doblemente ligadas es:

LD(LI(X)) = X = LI(LD(X))

1.3 LISTAS SIMPLEMENTE LIGADAS CIRCULARES

Una lista simplemente enlazada o encadenada circular es un conjunto de elementos en los que el último nodo en vez de contener un indicador de “fin” tiene la dirección de memoria del primer nodo o cabeza.

ANT INFO SIG

Null

ANT INFO SIG

ANT INFO SIG

ANT INFO SIG

Null

INFO SIG

INFO SIG

INFO SIG

INFO SIG

PRIMERO

PRIMERO


1.4 LISTAS SIMPLEMENTE LIGADAS CON REGISTRO CABEZA

El registro cabeza es un registro (NODO) que, por lo general, no tendrá ningún valor en su(s) campo(s) de información y siempre será el primer nodo de la lista ligada facilitando así las operaciones de inserción, borrado, recorrido y hasta la creación. Para recorrer la lista se inicia en el segundo nodo, es decir, a p se le asigna la Liga(L). La lista está vacía cuando la liga del primer nodo (registro cabeza) es nil (Null, Nulo ó 0) La creación de este tipo de lista varía con respecto a aquellas en las que no existe el registro cabeza, en las cuales basta con asignarle 0, Nil, Null o Nulo a una variable L, en que es necesario crear un nuevo nodo y asignarle Null en el campo de información, así: Struct NODO { Dato Numérico Liga Apuntador } X = New_Nodo( ) L = X Dato(X) = Null Liga(X) = Null

1.5 LISTAS SIMPLEMENTE LIGADAS CIRCULARES CON REGISTRO CABEZA

La diferencia de este tipo de lista con la anterior está en que el último nodo de las circulares apunta a la cabeza (registro cabeza). De igual manera para recorrer la lista se inicia en el segundo nodo, es decir, a p se le asigna la Liga(L) y se termina de recorrer cuando p sea igual a L. Sí la lista está vacía, inicialmente p queda valiendo L, y su creación se hace de la siguiente manera:


Struct NODO { Dato Numérico Liga Apuntador } X = New_Nodo( ) L = X Dato(X) = Null Liga(X) = X

1.6 LISTAS DOBLEMENTE LIGADAS CIRCULARES

En las listas doblemente ligadas circulares el campo de liga derecha del último nodo apunta hacia el primer Nodo de la lista y el campo de la liga izquierda del primer modo apunta hacia el último registro de la lista.

1.7 LISTAS DOBLEMENTE LIGADAS CON REGISTRO CABEZA

En las listas doblemente ligadas NO circulares el campo de datos del primer nodo (registro cabeza) lleva como valor Null y la liga derecha apunta hacia el primer Nodo que contiene información en la lista. En caso de estar la lista vacía la liga derecha tendrá por valor Nil, Null, Nulo ó 0. Para crear la lista se definen las siguientes instrucciones: Struct NODO { Dato Numérico LI Apuntador LD Apuntador } X = New_Nodo( ) L = X Dato(X) = Null LI(X) = Null LD(X) = Null


1.8 LISTAS DOBLEMENTE LIGADAS CIRCULARES CON REGISTRO CABEZA

En las listas doblemente ligadas circulares el campo de datos del primer nodo (registro cabeza) lleva como valor Null, y tanto la liga izquierda como la derecha apuntan hacia si misma cuando la lista está vacía. Para crear la lista se definen las siguientes instrucciones: Struct NODO { Dato Numérico LI Apuntador LD Apuntador } X = New_Nodo( ) L = X Dato(X) = Null LI(X) = X LD(X) = X

1.9 PILAS

Es una estructura de datos especial en donde la inserción y el borrado de los nuevos elementos se realizan sólo por un extremo que se denomina cima o tope. Esta estructura posee numerosas analogías en la vida real, por ejemplo imagine una pila de platos. Dado que las operaciones de insertar y eliminar se realizan por un solo extremo (el superior), los elementos solo pueden eliminarse en orden inverso al que se insertan en la pila. El último elemento que se pone en la pila es el primero en sacar; dado a esto a estas estructuras se les conoce con el nombre de LIFO. Las operaciones que se pueden realizar con una pila son:

PUSH (pila, elemento): Introduce un elemento en la pila. También se le conoce como poner o meter.

POP (pila): Elimina un elemento de la pila. También se le conoce como sacar o quitar.

VACIA(pila): Función booleana que indica si la pila esta vacía o no. Las pilas se pueden implementar por arreglos o bien por punteros siempre y cuando se respete el concepto antes mencionado.


Idealmente, una pila puede contener un número ilimitado de elementos y no producir nunca desbordamiento. En la práctica, sin embargo, el espacio de almacenamiento disponible es finito. La codificación de una pila requiere un cierto equilibrio, ya que si la longitud máxima es demasiado grande, se gasta mucha memoria, mientras que un valor pequeño de longitud máxima producirá desbordamientos frecuentes.

1.10 COLAS (FILAS)

Las colas o filas son otro tipo de estructura lineal de datos, similares a las pilas, diferenciándose de ellas en el modo de insertar ó eliminar elementos. Una cola es una estructura lineal de datos en la que las eliminaciones se realizan al principio de la lista, y las inserciones se realizan por el final de la misma. En las colas el elemento que entró primero también sale primero, por ello se conocen como estructuras FIFO. Así pues la diferencia con las pilas es solamente el modo de entrada y salida de datos. En la vida real se tienen ejemplos numerosos de colas: la cola de un autobús, la cola de un cine, etc. En todas ellas el primer elemento que llega es el primero que sale. En informática existen también numerosas aplicaciones de colas. Por ejemplo, en un sistema de tiempo compartido suele haber un procesador central y una serie de periféricos compartidos: discos, impresoras, etc. Los recursos se comparten por los diferentes usuarios y se utiliza una cola para almacenar los programas o peticiones de los usuarios que esperan su turno de ejecución. Las colas se pueden representar como estructuras dinámicas de datos o como arreglos. Las operaciones que se pueden realizar con una cola son:

Acceder al primer elemento de la cola.

Añadir un elemento al final de la cola.

Eliminar el primer elemento de la cola.

Vaciar la cola.

Verificar el estado de la cola.


2 ALGUNOS TIPS

Recuerde que la cabeza de lista no se puede perder

Si la lista no está creada se deben hacer los siguientes pasos para crearla: o Definir la estructura de cada nodo (Struct NODO) o Crear la Lista

Para Insertar en una lista los pasos son: o Pedir una copia de la estructura (Solicitar el registro) o Guardar en el Nodo la información dada o Ligar el Nodo a la Lista. Depende de lo solicitado en el ejercicio (Al

principio, Al final o manteniendo el orden de la lista)

Para Borrar en una lista es necesario: o Reconstruir las ligas de la lista “soltando” (desligando) el Nodo a

borrar” o Liberar la memoria que ocupaba el Nodo

Definición del NODO para todos los algoritmos de listas simplemente ligadas a utilizar aquí Struct NODO { Dato Numérico Liga Apuntador } Gráficamente sería: Definición del NODO para todos los algoritmos de listas doblemente ligadas a utilizar aquí Struct NODO { Dato Numérico LI Apuntador LD Apuntador } Gráficamente sería:

DATO LIGA

LI DATO LD


3 ALGORITMOS

3.1 LISTAS SIMPLEMENTE LIGADAS

3.1.1 Subprograma que recorre una lista simplemente ligada

RECIBE: L = Cabeza de la lista a recorrer RETORNA: Nada Subprograma Recorre_lista(L) Apuntador P P = L MIENTRAS (P <> Null) haga Escriba dato(p) Ver NOTA_1. P = liga(P) Fin MIENTRAS Fin (recorre_Lista)

3.1.2 Subprograma que inserta en una lista simplemente ligada ordenada (manteniendo el orden)

RECIBE: L = Cabeza de la lista a recorrer d = Dato a Insertar

Y = Dirección del Nodo inmediatamente anterior al que se va a insertar

RETORNA: Nada Subprograma Insertar_Lista(L,d) Apuntador X, Y X = New_Nodo( ) Ver NOTA_2. Dato(X) = d Y = Buscar_donde_Insertar(L,d) Ver NOTA_3. Si (Y = Null) Entonces Liga(X) = L L = X Sino Liga(X) = Liga(Y) Liga(Y) = X Fin si Fin (Insertar_Lista)


3.1.3 Subprograma (función) que busca donde insertar en una lista simplemente ligada (ordenada)

RECIBE:

L = Cabeza de la lista a recorrer d = Dato a Insertar RETORNA:

Y = Dirección del Nodo inmediatamente anterior al que se va a insertar. Si Y = Null, es porque el dato a insertar es el primero, si Y tiene valor esta será la del nodo inmediatamente anterior a la del nodo insertar (inclusive si es el último)

Subprograma Buscar_Insertar_lista(L,d) Apuntador P, Y P = L Y = Null MIENTRAS (P <> Null and Dato(P) < d) Haga Y = P P = Liga(P) Fin MIENTRAS Retorne (Y) Fin (Buscar_Insertar_lista)

3.1.4 Subprograma que inserta en una lista simplemente ligada siempre al principio.

RECIBE: L = Cabeza de la lista a recorrer d = Dato a Insertar RETORNA: Nada Subprograma Insertar_Lista_Inicio(L,d) Apuntador X X = New_Nodo( ) Ver NOTA_2. Dato(X) = d Si (L = Null) Entonces Liga(X) = Null Sino Liga(X) = L Fin si L = X Fin (Insertar_Lista_Inicio)


3.1.5 Subprograma que inserta en una lista simplemente ligada siempre al final.

RECIBE: L = Cabeza de la lista a recorrer d = Dato a Insertar RETORNA: Nada Subprograma Insertar_Lista_Final(L,d) Ver NOTA_8. Apuntador X, Ultimo X = New_Nodo( ) Ver NOTA_2. Dato(X) = d Liga(X) = Null Si (L = Null) Entonces L = X SiNO

Ultimo = Buscar_Ultimo(L) Ver NOTA_7. Liga(Ultimo) = X Fin si Fin (Insertar_Lista_Final)

3.1.6 Subprograma (función) que busca el último nodo de una lista simplemente ligada

RECIBE:

L = Cabeza de la lista a recorrer RETORNA: Ultimo = Dirección del Ultimo Nodo. Si Ultimo = Null, es

porque la lista está Vacia. Subprograma Ultimo_Lista (L) Apuntador Ultimo Ultimo = L MIENTRAS ( Liga(Ultimo) <> Null) Haga Ultimo = Liga(Ultimo) Fin Mientras Retorne (Ultimo) Fin (Ultimo_lista)


3.1.7 Subprograma que busca un dato en una lista simplemente ligada (no ordenada)

RECIBE:

L = Cabeza de la lista a recorrer d = Dato buscado RETORNA:

Y = Dirección del Nodo inmediatamente anterior al que se busca. Si Y = Null, es porque el dato buscado es el primero de la lista.

X = Dirección del Nodo que se busca. Si X = Null, es

porque el dato buscado no existe en la lista. Subprograma Buscar_dato_lista(L,d,X,Y)

X = L Y = Null MIENTRAS (X <> Null AND Dato(X) <> d) Haga Y = X X = Liga(X)

Fin MIENTRAS Fin (Buscar_dato_lista)

3.1.8 Subprograma que borra un dato de una lista simplemente ligada.

RECIBE: L = Cabeza de la lista a recorrer d = Dato a borrar RETORNA: Nada Subprograma Borrar_lista(L,d) Apuntador X,Y Buscar_dato_lista(L,d,X,Y) Ver NOTA_4. Si (X = Null) Entonces Imprima “Dato a Borrar no existe” Returne () Fin si Si (Y = Null) Entonces L = Liga(L) Sino Liga(y) = liga(x) Fin si Liberar (X) Ver NOTA_5. Fin(borrar_Lista)


3.2 LISTAS SIMPLEMENTE LIGADAS CIRCULARES

3.2.1 Subprograma que recorre una lista simplemente ligada circular

RECIBE: L = Cabeza de la lista a recorrer RETORNA: Nada Subprograma Recorre_lista_Circular(L) Apuntador P P = L Repita Escriba dato(p) Ver NOTA_1. P = liga(P) MIENTRAS (P <> L) Fin (recorre_Lista_Circular)

3.2.2 Subprograma que inserta en una lista simplemente ligada circular ordenada (manteniendo el orden)



RETORNA: Nada Subprograma Insertar_Lista_Circular(L,d) Apuntador X, Y, U X = New_Nodo( ) Ver NOTA_2. Dato(X) = d Si (L = Null) Entonces L = X

Liga(X) = X SiNo

Y = Buscar_donde_Insertar(L,d) Ver NOTA_3. Si (Y = Null) Entonces U = Ultimo_Lista(L) Ver 3.1.6. Liga(X) = L Liga(U) = X L = X Sino


Liga(X) = Liga(Y) Liga(Y) = X Fin si

Fin Si Fin (Insertar_Lista_Circular)

3.2.3 Subprograma (función) que busca donde insertar en una lista simplemente ligada circular (ordenada)

RECIBE:



Subprograma Buscar_Insertar_lista_circular(L,d) Apuntador P, Y P = L Y = Null MIENTRAS (P <> L and Dato(P) < d) Haga Y = P P = Liga(P) Fin MIENTRAS Retorne (Y) Fin (Buscar_Insertar_lista_circular)


3.3 LISTAS SIMPLEMENTE LIGADAS CIRCULARES CON REGISTRO CABEZA

3.3.1 Subprograma que recorre una lista simplemente ligada circular con registro cabeza

RECIBE: L = Cabeza de la lista a recorrer RETORNA: Nada Subprograma Recorre_lista(L) Apuntador P P = L MIENTRAS (P <> Null) haga Escriba dato(p) Ver NOTA_1. P = liga(P) Fin MIENTRAS Fin (recorre_Lista)

3.3.2 Subprograma que inserta en una lista simplemente ligada circular con registro cabeza, ordenada (manteniendo el orden)



RETORNA: Nada Subprograma Insertar_Lista(L,d) Apuntador X, Y X = New_Nodo( ) Ver NOTA_2. Dato(X) = d Y = Buscar_donde_Insertar(L,d) Ver NOTA_3.

Liga(X) = Liga(Y) Liga(Y) = X Fin (Insertar_Lista)


3.3.3 Subprograma (función) que busca donde insertar en una lista simplemente ligada circular con registro cabeza (ordenada)

RECIBE:


Y = Dirección del Nodo inmediatamente anterior al que se va a insertar.

Subprograma Buscar_Insertar_lista(L,d) Apuntador P, Y P = Liga(L) Y = L MIENTRAS (P <> L and Dato(P) < d) Haga Y = P P = Liga(P) Fin MIENTRAS Retorne (Y) Fin (Buscar_Insertar_lista)

3.3.4 Subprograma que busca un dato en una lista simplemente ligada (no ordenada)

RECIBE:


Y = Dirección del Nodo inmediatamente anterior al que se busca.

X = Dirección del Nodo que se busca. Si X = L, es


X = Liga(L) Y = L MIENTRAS (X <> L AND Dato(X) <> d) Haga Y = X X = Liga(X)



3.3.5 Subprograma que borra un dato de una lista simplemente ligada circular con registro cabeza

RECIBE: L = Cabeza de la lista a recorrer d = Dato a borrar RETORNA: Nada Subprograma Borrar_lista(L,d) Apuntador X,Y Buscar_dato_lista(L,d,X,Y) Ver NOTA_4. Si (X = L) Entonces Imprima “Dato a Borrar no existe” Retorne () Fin si Liga(y) = liga(x) Liberar (X) Ver NOTA_5. Fin(borrar_Lista)


3.4 LISTAS DOBLEMENTE LIGADAS

3.4.1 Subprograma que recorre una lista doblemente ligada de izquierda a derecha

RECIBE: L = Cabeza de la lista a recorrer RETORNA: Nada Subprograma Recorre_lista(L) Apuntador P P = L MIENTRAS (P <> Null) haga Escriba dato(p) Ver NOTA_1. P = LD(P) Fin MIENTRAS Fin (recorre_Lista)

3.4.2 Subprograma que recorre una lista doblemente ligada de derecha a izquierda

RECIBE: L = Cabeza de la lista a recorrer RETORNA: Nada Subprograma Recorre_lista(L) Apuntador P P = Ultimo(L) Ver NOTA_7. MIENTRAS (P <> Null) haga Escriba dato(p) Ver NOTA_1. P = LI(P) Fin MIENTRAS Fin (recorre_Lista)

3.4.3 Subprograma que inserta en una lista doblemente ligada ordenada (manteniendo el orden)




RETORNA: Nada Subprograma Insertar_Lista(L,d) Apuntador X, Y X = New_Nodo( ) Ver NOTA_2. Dato(X) = d Y = Buscar_donde_Insertar(L,d) Ver NOTA_3. Si (Y = Null) Entonces Liga(X) = L L = X Sino Liga(X) = Liga(Y) Liga(Y) = X Fin si Fin (Insertar_Lista)

3.4.4 Subprograma (función) que busca donde insertar en una lista doblemente ligada (ordenada)

RECIBE:



Subprograma Buscar_Insertar_lista(L,d) Apuntador P, Y P = L Y = Null MIENTRAS (P <> Null and Dato(P) < d) Haga Y = P P = Liga(P) Fin MIENTRAS Retorne (Y) Fin (Buscar_Insertar_lista)


3.4.5 Subprograma que inserta en una lista doblemente ligada siempre al principio.

RECIBE: L = Cabeza de la lista a recorrer d = Dato a Insertar RETORNA: Nada Subprograma Insertar_Lista_Inicio(L,d) Apuntador X X = New_Nodo( ) Ver NOTA_2. Dato(X) = d Si (L = Null) Entonces Liga(X) = Null Sino Liga(X) = L Fin si L = X Fin (Insertar_Lista_Inicio)

3.4.6 Subprograma que inserta en una lista doblemente ligada siempre al final.

RECIBE: L = Cabeza de la lista a recorrer d = Dato a Insertar RETORNA: Nada Subprograma Insertar_Lista_Final(L,d) Ver NOTA_8. Apuntador X, Ultimo X = New_Nodo( ) Ver NOTA_2. Dato(X) = d Liga(X) = Null Si (L = Null) Entonces L = X SiNO

Ultimo = Buscar_Ultimo(L) Ver NOTA_7. Liga(Ultimo) = X Fin si Fin (Insertar_Lista_Final)


3.4.7 Subprograma (función) que busca el último nodo de una lista doblemente ligada

RECIBE:

L = Cabeza de la lista a recorrer RETORNA: Ultimo = Dirección del Ultimo Nodo. Si Ultimo = Null, es

porque la lista está Vacia. Subprograma Ultimo_Lista (L) Apuntador Ultimo Ultimo = L MIENTRAS ( Liga(Ultimo) <> Null) Haga Ultimo = Liga(Ultimo) Fin Mientras Retorne (Ultimo) Fin (Ultimo_lista)

3.4.8 Subprograma que busca un dato en una lista doblemente ligada (no ordenada)

RECIBE:


Y = Dirección del Nodo inmediatamente anterior al que se busca. Si Y = Null, es porque el dato buscado es el primero de la lista.

X = Dirección del Nodo que se busca. Si X = Null, es


X = L Y = Null MIENTRAS (X <> Null AND Dato(X) <> d) Haga Y = X X = Liga(X)



3.4.9 Subprograma que borra un dato de una lista doblemente ligada.

RECIBE: L = Cabeza de la lista a recorrer d = Dato a borrar RETORNA: Nada Subprograma Borrar_lista(L,d) Apuntador X,Y Buscar_dato_lista(L,d,X,Y) Ver NOTA_4. Si (X = Null) Entonces Imprima “Dato a Borrar no existe” Returne () Fin si Si (Y = Null) Entonces L = Liga(L) Sino Liga(y) = liga(x) Fin si Liberar (X) Ver NOTA_5. Fin(borrar_Lista)


3.5 LISTAS DOBLEMENTE LIGADAS CIRCULARES

3.5.1 Subprograma que recorre una lista doblemente ligada circular izquierda a derecha

RECIBE: L = Cabeza de la lista a recorrer RETORNA: Nada Subprograma Recorre_lista_Circular(L) Apuntador P P = L Repita Escriba Dato(p) Ver NOTA_1. P = LD(P) MIENTRAS (P <> L) Fin (recorre_Lista_Circular)

3.5.2 Subprograma que recorre una lista doblemente ligada circular derecha a izquierda

RECIBE: L = Cabeza de la lista a recorrer RETORNA: Nada Subprograma Recorre_lista_Circular(L) Apuntador P P = LI(L) Repita Escriba Dato(p) Ver NOTA_1. P = LI(P) MIENTRAS (P <> L) Fin (recorre_Lista_Circular)

3.5.3 Subprograma que inserta en una lista doblemente ligada circular ordenada (manteniendo el orden)




RETORNA: Nada Subprograma Insertar_Lista_Circular(L,d) Apuntador X, Y, U X = New_Nodo( ) Ver NOTA_2. Dato(X) = d Si (L = Null) Entonces L = X

LI(X) = X LD(X) = X

SiNo Y = Buscar_donde_Insertar(L,d) Ver NOTA_3. Si (Y = Null) Entonces LD(X) = L LI(X) = LI(L) LD(LI(L)) = X

LI(L) = X L = X Sino LD(X) = LD(Y) LI(X) = Y LI(LD(Y)) = X LD(Y) = X Fin si

Fin Si Fin (Insertar_Lista_Circular)

3.5.4 Subprograma (función) que busca donde insertar en una lista doblemente ligada circular (ordenada)

RECIBE:




Subprograma Buscar_Insertar_lista_circular(L,d) Apuntador P, Y Si (d < dato(L) ) ent return(Null) Fin Si P = LD(L) Y = L MIENTRAS (P <> L and Dato(P) < d) Haga Y = P P = LD(P) Fin MIENTRAS Retorne (Y) Fin (Buscar_Insertar_lista_circular)


3.6 LISTAS DOBLEMENTE LIGADAS CIRCULARES CON REGISTRO CABEZA

3.6.1 Subprograma que recorre una lista doblemente ligada circular con registro cabeza de izquierda a derecha

RECIBE: L = Cabeza de la lista a recorrer RETORNA: Nada Subprograma Recorre_lista(L) Apuntador P P = LD(L) MIENTRAS (P <> L) haga Escriba dato(p) Ver NOTA_1. P = LD(P) Fin MIENTRAS Fin (recorre_Lista)

3.6.2 Subprograma que recorre una lista doblemente ligada circular con registro cabeza de derecha a izquierda

RECIBE: L = Cabeza de la lista a recorrer RETORNA: Nada Subprograma Recorre_lista(L) Apuntador P P = LI(L) MIENTRAS (P <> L) haga Escriba dato(p) Ver NOTA_1. P = LI(P) Fin MIENTRAS Fin (recorre_Lista)

3.6.3 Subprograma que inserta en una lista doblemente ligada circular con registro cabeza, ordenada (manteniendo el orden)



RETORNA: Nada Subprograma Insertar_Lista(L,d) Apuntador X, Y X = New_Nodo( ) Ver NOTA_2. Dato(X) = d Y = Buscar_donde_Insertar(L,d) Ver NOTA_3. LD(X) = LD(Y) LI(X) = Y LI(LD(X)) = X LD(Y) = X Fin (Insertar_Lista)

3.6.4 Subprograma (función) que busca donde insertar en una lista doblemente ligada circular con registro cabeza (ordenada)

RECIBE:


Y = Dirección del Nodo inmediatamente anterior al que se va a insertar.

Subprograma Buscar_Insertar_lista(L,d) Apuntador P, Y

P = LD(L) Y = L MIENTRAS (P <> L and Dato(P) < d) Haga Y = P P = LD(P) Fin MIENTRAS Retorne (Y) Fin (Buscar_Insertar_lista)

3.6.5 Subprograma que busca un dato en una lista doblemente ligada (no ordenada)

RECIBE:



X = Dirección del Nodo que se busca. Si X = L, es porque el dato buscado no existe en la lista.

Subprograma Buscar_dato_lista(L,d) X = LD(L) MIENTRAS (X <> L AND Dato(X) <> d) Haga X = LD(X)

Fin MIENTRAS Retorne (X) Fin (Buscar_dato_lista)

3.6.6 Subprograma que borra un dato de una lista doblemente ligada circular con registro cabeza

RECIBE: L = Cabeza de la lista a recorrer d = Dato a borrar RETORNA: Nada Subprograma Borrar_lista(L,d) Apuntador X,Y X = Buscar_dato_lista(L,d) Ver NOTA_4. Si (X = L) Entonces Imprima “Dato a Borrar no existe” Returne () Fin si LD(LI(X)) = LD(X) LI(LD(X)) = LI(X) Liberar (X) Ver NOTA_5. Fin(borrar_Lista)


4 NOTAS

NOTA_1: Esta instrucción puede reemplazarse por la que se necesite, por ejemplo un contador, un acumulador, una comparación, entre otras. Para este caso el subprograma recorre una lista e imprime los datos almacenados en cada nodo. NOTA_2: Esta instrucción invoca un subprograma que interactúa con el Sistema Operativo solicitándole un registro (una copia de la estructura NODO definida) y almacenando la dirección en memoria de dicho registro en la variable tipo Apuntador de nombre X . NOTA_3: Esta instrucción invoca una función que retorna la dirección donde se debe almacenar el nuevo NODO.

NOTA_4: Esta instrucción invoca un subprograma que busca en la lista cuya cabeza es L, un dato d, y recibe en X la dirección del Nodo buscado (Null si no existe) y en Y la dirección del Nodo inmediatamente anterior (Null si el Nodo es el primero de la lista).

NOTA_5: Esta instrucción invoca un subprograma que interactúa con el Sistema Operativo solicitándole elimine de la memoria un registro (NODO) el cual se encuentra en la dirección de memoria X .

NOTA_6: Esta instrucción invoca una función que retorna la dirección donde se debe almacenar el nuevo NODO.. NOTA_7: Esta instrucción invoca una función que retorna la dirección donde se encuentra el Ultimo NODO de la Lista.

NOTA_8: Si sabemos que todos los registros a insertar serán siempre al final, es mas eficiente y práctico utilizar una variable auxiliar tipo apuntador, que siempre apunte al último registro (NODO) de la lista. Y las instrucciones para insertar un registro (NODO) son: Apuntador X, Ultimo X = New_Nodo( ) Dato(X) = d Liga(X) = Null Liga(Ultimo) = X Ultimo = x Se elimina la Función Ultimo_Lista()


5 RECURSIVIDAD

Definición:

La recursividad es un concepto fundamental en matemáticas y en computación. Una definición recursiva dice cómo obtener conceptos nuevos empleando el mismo concepto que intenta describir. En toda situación en la cual la respuesta pueda ser expresada como una secuencia de movimientos, pasos o transformaciones gobernadas por un conjunto de reglas no ambiguas, la fórmula recursiva es un buen candidado para resolver el problema. Los razonamientos recursivos se encuentran en la base misma de las matemáticas porque son necesarios para describir conceptos centrales como el de número

EJEMPLOS DE ALGORITMOS RECURSIVOS: Factorial Definición: factorial (n) = n! si n > 0 factorial (n) = n*n-1*n-2* ... * 1 si n > 0 el valor de 0! se define como factorial (0) = 1 Su definición recursiva es: factorial (n) = 1 si n = 0 factorial (n) = n* factorial (n-1) si n > 0 así para calcular el factorial de 4: factorial (4) = 4 * factorial (3) = 4 * 6 = 24 factorial (3) = 3 * factorial (2) = 3 *2 = 6 factorial (2) = 2 * factorial (1) = 2 * 1 = 2 factorial (1) = 1 * factorial (0) = 1 * 1 = 1


FACTORIAL UTILIZANDO CICLOS: Entero FactorialCiclos(entero n) InicioMetodo entero fac = 1; para (i = 1 hasta n) InicioPara Fac = fac * i FinPara Retornar fac FinMetodo FACTORIAL RECURSIVO: Entero FactorialRecursivo(entero n){ Si (n = 0) Verdadero Retornar 1; Falso Retornar FactorialRecursivo(n - 1) * n Fin-Si } Las definiciones recursivas de funciones en matemáticas que tienen como argumentos números enteros, se llaman relaciones de recurrencia. Forma de una ecuación de recurrencia: coar +c1ar-1 + c2ar-2 + ....+ ckar-k = f(r) función matemática discreta donde ci son constantes, es llamada una ecuación de recurrencia de coeficientes constantes de orden k, condicionada a que c0 y ck = 0. Una definición recursiva dice cómo obtener conceptos nuevos empleando el mismo concepto que intenta definir. El poder de la recursividad es que los procedimientos o conceptos complejos pueden expresarse de una forma simple. Un razonamiento recursivo tiene dos partes: la base y la regla recursiva de construcción. La base no es recursiva y es el punto tanto de partida como de terminación de la definición.


Ejemplo: Base: La secuenciación, iteración condicional y selección son estructuras válidas de control que pueden ser consideradas como enunciados. Regla recursiva: Las estructuras de control que se pueden formar combinando de manera válida la secuenciación iteración condicional y selección también son válidos. Un conjunto de objetos está definido recursivamente siempre que: (B) algunos elementos del conjunto se especifican explícitamente (R) el resto de los elementos del conjunto se definen en términos de los elementos ya definidos donde (B) se llama base (R) se llama cláusula recursiva Observaciones: 1. El procedimiento se llama a si mismo 2. El problema se resuelve, resolviendo el mismo problema pero de tamaño menor 3. La manera en la cual el tamaño del problema disminuye asegura que el caso base eventualmente se alcanzará La recursividad es un método poderoso usado en inteligencia artificial, su poder es que algunos conceptos complejos pueden expresarse en una forma simple. Una definición recursiva difiere de una definición circular en que tiene una forma de escapar de su expansión infinita. Este escape se encuentra en la definición o porción no recursiva o terminal de la definición. Las fórmulas recursivas pueden aplicarse a situaciones tales como prueba de teoremas, solución de problemas combinatorios, algunos acertijos, etc. Ejemplos:

5.1 Números de Fibonacci

Los números de Fibonacci se definen como: FN = FN-1 + FN-2 para N > 2 F0 = F1 = 1 que definen la secuencia:


1,1,2,3,5,8,13,21,34,55,89,144, ..... Por ejemplo, si quisiéramos encontrar Fibonacci de 5, entonces: Fibonacci (5) = Fibonacci (4) + Fibonacci (3) Fibonacci (4) = Fibonacci (3) + Fibonacci (2) Fibonacci (3) = Fibonacci (2) + Fibonacci (1) Fibonacci (2) = Fibonacci (1) + Fibonacci (0) De manera iterativa el algoritmo podría ser: estática int Fibonacci (int n) // versión iterativa comienza fibo [0] 1 fibo [1] 1 para i 1 hasta n fibo [i] fibo [i-1]+ fibo [i-2] regresa fibo [n] termina Resolviendo el mismo problema pero de manera recursiva, obtenemos: estática int Fibonacci (int n) //versión recursiva comienza si n < 1 entonces regresa 1 otro regresa Fibonacci (n-1) + Fibonacci (n-2) termina

5.2 Considere la siguiente ecuación recurrente:

an = an-1 + 2n a0 = 1 estática int a (int n) comienza si n = 0 entonces regresa1 otro regresa 2^n + a (n-1) termina


Los valores de los términos de una sucesión pueden darse de manera explícita mediante fórmulas como: Sn = n4 - 3n3 - 2n pero también pueden definirse por medio de descripciones que involucren otros términos que les anteceden en la sucesión.

5.3 Considere las siguientes sucesiones:

a) Sum (n) = 1

0 ii

i n

!

b) Sum (0) = 1 Sum (n+1) = Sum (n) + 1/(1/(n+1)!) c) Seq (0) = 1 Seq (n+1) = (n+1) / Seq(n) d) T (1) = 1 T (n) = 2T (n div 2)

e)

ni

ai

n

ai

in

i

in < a si

a = i si 1

por ejemplo:

ii

i n

11

i i i i ii

i

i

i

i

i

i

i

i

i

5 5 4 5 4 3 5 4 3 2 5 4 3 2 1 151

1

1

2

2

3

2

4

2

5

estática int suma (int i, int n) comienza si i = n entonces regresa i otro regresa n + suma (i,n-1) termina


5.4 Definición recursiva para elevar un número a una potencia:

Un número elevado a la potencia cero produce la unidad; la potencia de un número se obtiene multiplicándolo por sí mismo elevando a la potencia menos uno. Por ejemplo: 32 = 3*(31) = 3*(3*30) = 3*(3*1)= 3*(3) = 9 estática int potencia (int n, int k) comienza si k=0 entonces regresa 1 otro regresa n * potencia (n,k-1) termina

5.5 Número de Combinaciones

Recursivamente, podemos definir el número de combinaciones de m objetos tomados de n, denotado (n,m) para n> 1 y 0 < m < n por: (n,m) = 1 si m = 0 ó m = n ó n = 1 (n,m) = (n-1, m) + (n-1,m-1) en otro caso estática int combinaciones (int n, int m) comienza si m = 0 o m = n o n = 1 entonces regresa 1 otro regresa combinaciones (n-1,m) + combinaciones (n-1,m-1) termina

5.6 Algoritmo de Euclides

Este algoritmo es considerado el más viejo no trivial. El paso esencial que garantiza la validez del algoritmo consiste en mostrar que el máximo común divisor (mcd) de a y b, (a > b > 0), es igual a a si b es cero, en otro caso es igual al mcd de b y el remanente de a dividido por b, si b > 0.


estática int mcd (int a,b) comienza si b = 0 regresa a otro regresa mcd (b, a mod b) termina Ejemplos: mcd (25, 5) = mcd (5,0) = 5 mcd (18,6) = mcd (6,0) = 6 mcd (57, 23) = mcd (23, 1) = mcd (1,0) = 1 mcd (35, 16) = mcd (16,3) = mcd (3, 1) = mcd (1, 0) = 1 Definición: Cuando una llamada recursiva es la última posición ejecutada del procedimiento se llama recursividad de cola, recursividad de extremo final o recursión de extremo de cola. Definición: Cuando un procedimiento incluye una llamada a si mismo se conoce como recursión directa. Definición: Cuando un procedimiento llama a otro procedimiento y este causa que el procedimiento original sea invocado, se conoce como recursión indirecta. Al principio algunas personas se sienten un poco incómodas con la recursividad, tal vez porque da la impresión de ser un ciclo infinito, pero en realidad es menos peligrosa una recursión infinita que un ciclo infinito, ya que una recursividad infinita pronto se queda sin espacio y termina el programa, mientras que la iteración infinita puede continuar mientras no se termine en forma manual. Cuando un procedimiento recursivo se llama recursivamente a si mismo varias veces, para cada llamada se crean copias independientes de las variables declaradas en el procedimiento.

5.7 Técnica de diseño “dividir para vencer”

Muchas veces es posible dividir un problema en subproblemas más pequeños, generalmente del mismo tamaño, resolver los subproblemas y entonces combinar sus soluciones para obtener la solución del problema original. Como los subproblemas obtenidos generalmente son del mismo tipo que el problema original, la estrategia “dividir para vencer” generalmente se implementa como un algoritmo recursivo. Solución DPV (Problema T)


comienza si T < pequeño entonces regresa soluciónTrivial (T) otro comienza divide (T,T1,T2, ..., Ta) para i 1 hasta a Solucióni a DPV (Ti) regresa combina (Solución1, Solución2, ... , Solucióna) termina termina Dividir para vencer es una técnica natural para las estructuras de datos, ya que por definición están compuestas por piezas. Cuando una estructura de tamaño finito se divide, las últimas piezas ya no podrán ser divididas. Ejemplos: 1. Encontrar el número mayor de un arreglo de enteros: estática int mayor1 (objeto [ ] A, int limIzq, int limDer) comienza si limIzq = limDer entonces regresa A[limIzq] otro comienza m (limIzq + limDer) div 2 mayorIzq mayor1 (A,limIzq,m) mayorDer mayor1 (A, m +1, limDer) si mayorIzq > mayorDer entonces mayor1 mayorIzq otro regresa mayorDer termina termina Otra forma de resolver este problema es la siguiente:


estática int mayor1 (objeto [ ] A, int limIzq, int limDer) //versión 2 comienza si limIzq = limDer entonces regresa A[limIzq] otro comienza m (limIzq + limDer) div 2 mayorIzq mayor1 (A, limIzq, m) mayorDer mayor1 (A, m +1, limDer) si mayorIzq > mayorDer entonces regresa mayorIzq otro regresa mayorDer termina termina estática int mayor2 (objeto [ ] A, int limIzq) comienza limDer = A.longitud-1 si limIzq = limDer entonces regresa A[limIzq] otro si limDer-limIzq = 1 entonces si A[limDer] > A[limIzq] entonces regresa A[limDer] otro regresa A[limIzq] otro comienza m mayor2 (A,limIzq+1) si A[limIzq] > m entonces regresa A[limIzq] otro regresa m termina termina 2. Inversión de una cadena estática Cad invierte (Cad cadena, int limIzq, int limDer) comienza si limDer = limIzq entonces regresa cadena otro regresa invierte (cadena, limDer,limIzq+1) + cadena [limIzq] termina


3. Cadenas de la forma anbn La notación anbn se utiliza para denotar cadenas que consisten de n a’s consecutivas seguidas de n b’s consecutivas. Es decir denota al lenguaje: L = {w| w es de la forma anbn para n > 0 } La gramática es parecida a la de los palíndromes. Debemos checar que la primera sea una a y la última una b. <palabraLegal> := cadena vacía | a<palabraLegal>b El algoritmo para reconocer cadenas de esta forma, podría ser: estática bool reconocer (Cad w, int limIzq, int limDer) comienza si limIzq > limDer entonces regresa verdadero otro si w[limIzq] = ‘a’ & w[limDer] = ‘b’ entonces regresa reconocer (w, limIzq+1, limDer-1) otro regresa falso termina 4. Palindromes Un palindrome es una cadena que se lee (escribe, en este caso) igual de izquierda a derecha que de derecha a izquierda. Escribir una función que determine cuando una cadena es o no un palindrome. estática bool palindrome (Cad c, int limIzq) comienza si limIzq > c.longitud entonces regresa verdadero otro si c [limIzq] = c [limDer] entonces regresa palindrome (c, limIzq+1) otro regresa falso termina


5. Búsqueda binaria estática bool busbin (objeto [ ] A, int limIzq, int limDer, objeto valor) comienza si limIzq = limDer entonces regresa A [limDer].igual (valor) otro comienza m (limIzq + limDer) div 2 si A [m].igual (valor) entonces regresa verdadero otro si valor.mayor(A [m]) entonces regresa BusBin (A,m+1,limDer, valor) otro regresa BusBin (A,limIzq,m-1, valor) termina termina 6. MergeSort Suponga dos arreglos ordenados A[1..n] y B[1..m] que se desean juntar en un solo arreglo ordenado C[1..n+m] estática void Merge (Objeto [ ] A, Objeto [ ] B, Objeto [ ] C) comienza i 1; j 1; k 1; mientras i < n & j < m comienza si A[i] < B[j] entonces C[k] A[i]; i++ otro C[k] B[j]; j++ k++ termina Copia (C,k,A,i) Copia (C,k,B,j) termina


void MergeSort (Objeto [] A, int limIzq, int limDer) comienza si limIzq < limDer entonces comienza i (limIzq+limDer) div 2 MergeSort (A, limIzq, i) MergeSort (A, i+1, limDer) Merge (A,A,A) termina termina 7. Fractal cuadrado Dibujar una figura complicada con absoluto realismo empleando una computadora puede resultar en un trabajo bastante complicado para cualquier programador o artista. En 1975, un matemático francés llamado Bernoit Mandelbrot terminó una serie de investigaciones que duraron cerca de 20 años. Mandelbrot llamó al resultado de sus investigaciones Geometría Fractal. Un fractal es un dibujo formado por una geometría igual que la del dibujo pero de un tamaño menor. Un fractal se crea por cálculos repetitivos similares que los que se necesitaron para efectuar la parte inicial del dibujo. El fractal debe de seguir cierto orden para que no se produzcan dibujos que al final resultarían en un amontonamiento de líneas. Utilizando este método se pueden llegar a producir dibujos de una gran calidad y similitud con la realidad. estática void cuadrado (int x,int y,int r) comienza si r > 0 entonces comienza pintaCuadrado (x,y,r) cuadrado (x-r,y+r, r div 2) cuadrado (x+r,y+r, r div 2) cuadrado (x-r,y-r, r div 2) cuadrado (x+r,y-r, r div 2) termina termina 8. Dibujar recursivamente las marcas de una regla:


estática void regla (int ini, int fin, int n) comienza si n > 0 entonces comienza m (ini+fin) div 2 marca (m,n) regla (ini, m, n-1) regla (m, fin, n-1) termina termina regla (0,4,2) marca (2,2) regla (0,2,1) marca (1,1) regla (0,1,0) regla (1,2,0) regla (2,4,1) marca (3,1) regla (2,3,0) regla (3,4,0) 10. Torres de Hanoi estática void hanoi (Torre A, Torre B, Torre C, int n) // se desean mover n discos de la torre A a la B utilizando a C como auxiliar comienza si n = 1 entonces A --> B //se mueve un disco de A a B otro comienza hanoi (A,C,B,n-1) A --> B hanoi (C,A,B,n-1) termina termina Ejercicios: 1. Desarrolle una función para calcular recursivamente el número de ocurrencias del elemento elem en el vector A. 2. Desarrolle una función recursiva para saber si un carácter dado se encuentra presente en una cadena de caracteres. 3. Escriba una función recursiva para indicar si una cadena st1 ocurre dentro de una cadena st2.


4. Desarrolle una función recursiva para determinar si dos vectores son iguales. 5. Escriba el algortimo para la función de Ackermann, que está definida como: A(0,n) = n+1 para n > 0 A(m,0) = A(m-1, 1) para m > 0 A(m,n) = A(m-1, A(m,n-1)) para m > 0 y n > 0 6. Suponiendo que solo existe una rutina escribeDigito para escribir en la pantalla un dígito (0-9) pasado como parámetro, desarrolle un procedimiento recursivo que imprima un entero de cualquier cantidad de dígitos. 7. Multiplicación de números naturales. El producto de a*b donde a y b son enteros positivos, se puede definir como a sumando a sí mismo un número de veces igual a b. a*b = a si b = 1 a*b = a*(b-1) + a si b > 1 8. Considere un arreglo de enteros. Escriba algoritmos recursivos para calcular: (a) la suma de los elementos del arreglo (b) el producto de los elementos del arreglo (c) el promedio de los elementos del arreglo 9. Determine qué calcula la siguiente función recursiva y escriba una función iterativa que realice lo mismo: estática int f (int n) comienza si n= 0 regresa 0 otro regresa n + f (n-1) termina

listas pilas colas recursividad

Documents