ALGORITMOS COMPUTACIONALES U3

ALGORITMOS RECURSIVOS
ALGORITMOS RECURSIVOS.
Un algoritmo recursivo es un algoritmo que expresa la solución de un problema en términos de una llamada a sí mismo. La llamada a sí mismo se conoce como llamada recursiva o recurrente.
FUNCIÓN Factorial(n)
VAR resultado: Entero

SI (n<2) ENTONCES
resultado = 1;
SINO
resultado = n * Factorial(n-1);
FSI

RETORNAresultado;
FIN FUNCIÓN

Generalmente, si la primera llamada al subprograma se plantea sobre un problema de tamaño u orden N, cada nueva ejecución recurrente del mismo se planteará sobre problemas, de igual naturaleza que el original, pero de un tamaño menor que N. De esta forma, al ir reduciendo progresivamente la complejidad del problema a resolver, llegará un momento en que su resolución sea más omenos trivial (o, al menos, suficientemente manejable como para resolverlo de forma no recursiva). En esa situación diremos que estamos ante un caso base de la recursividad.
Las claves para construir un subprograma recurrente son:
Cada llamada recurrente se debería definir sobre un problema de menor complejidad (algo más fácil de resolver).
Ha de existir al menos un caso base para evitar que larecurrencia sea infinita.
Es frecuente que los algoritmos recurrentes sean más ineficientes en tiempo que los iterativos aunque suelen ser mucho más breves en espacio.
COLAS.
Una cola, es una estructura en la cual se almacenan elementos (en orden de llegada), es decir que, se ingresan los elementos por la parte final de la estructura y se eliminan (o se sirven) por la parte del frente.

Comopuede observarse, ésta estructura cuenta con dos apuntadores, uno que apunta al último elemento y otro que apunta hacia el primer elemento (o el elemento del frente).
Se debe tener en cuenta que, una cola, almacena los datos en ella, manteniendo cierto orden, ya que sus elementos se añaden por el final de la cola y se extraen o se eliminan por la parte de frente.
El lector dispersará el por que lainsistencia de ello, pero cuando uno inicia este estudio, al momento de programar, se confunde fácilmente, por que las sentencias de las funciones son muy parecidas a la de una pila, y en algunas ocasiones me pasaba que empezaba programando una cola, pero terminaba funcionando como pila.

Las operaciones con las colas son:
-insert (q, x) Inserta el elemento x en la parte posterior de la cola q-remove(q) Suprime el elemento delantero de la cola q
-empty(q) Retorna True o false, si la cola tiene elementos o no.

Las colas pueden implementarse, al igual que las pilas, mediante dos formas:
Arreglos
Memoria Dinámica
Algoritmo Para Añadir elementos en la cola
Si la cola está vacía:
1. Puntero primero y puntero último deben apuntar a NULL.
2. Creamos el nuevo nodo (con ayuda de malloc() )
3.Luego la parte siguiente del nuevo nodo, debe apuntar a NULL
4. Tanto, primero y ultimo deben apuntar, al nuevo nodo.

Si la cola, tiene elementos:
Creamos el nuevo nodo, ya sea en la misma función o con ayuda de otra función .
Hacemos que la parte siguiente del nodo apunte a NULL.
Luego, la parte siguiente de ultimo, deba apuntar al nodo.
Y ultimo, ahora debe apuntar al nodo.
Algoritmo Paraeliminar
Guardar el elemento dato nodo en una variable temporal
colocar un apuntador temporal hacia el nodo primero de la cola
cambiar el puntero (hacia el nodo) primero, hacia el nodo hacia el cual apunta el nodo, que estaba al frente de la cola
si después de eso el apuntador primero es NULL entonces no hay más datos en la cola y el apuntador ultimo también debe apuntar a NULL
Liberar memoriaapuntada por el apuntador temporal
devolver el valor guardado en la variable temporal

Ejemplo 11.1
Se desea almacenar cierto número de enteros en una estructura de tipo Cola, diseñe una solución que permita, leer, eliminar datos de la cola.
#include
#include
#include
 
/*declaracion de la cola*/
struct nodo
{
int elemento;
struct nodo *siguiente;
};
typedef...

Leer documento completo

Regístrate para leer el documento completo.