Ejercicio introductorio
Escribe una función en notación algorítmica que devuelva el factorial de un número natural introducido como parámetro
funcion factorial(n:entero) devuelve entero
{Pre: n>0}
Variables
resultado:entero;
indice:entero;
Principio
resultado:=1;
para indice:=2;indice menor que n;indice++
resultado=resultado*indice;
devuelve resultado
Fin
¿Otra manera?
¿Existe otra manera cualitativamente distinta de hacer lo que nos han pedido, que suponga al mismo tiempo una forma distinta de pensar en algoritmo para dar solución a problemas?
Sí, existe otra forma, que además es más intuitiva, y hace que podamos resolver problemas con algoritmos que nos resultan más sencillos de pensar.
Solución recursiva
funcion factorial (n:entero) devuelve entero
{Pre: n>0}
Principio
si n=1
entonces
devolver(1);
si no
devolver (n*factorial(n-1);
fsi
Fin
Hasta ahora conocíamos violaciones de segmento, ahora podemos generar desbordamiento de pila (por cierto, nombre de un muy buen foro de programación: http://stackoverflow.com )
Llamadas recursivas
n*factorial(n-1);
(n-1)*factorial(n-1);
(n-1)*factorial(n-2);
(n-1)*factorial(n-3);
…
3*factorial(2);
2*factorial(1);
1;
Ejercicio.
Escribe una función que calcule el máximo común divisor (mcd) de dos números naturales, a y b, sabiendo que mcd(a,b)=mcd(b, a MOD b) si a>=b, y en caso contrario, mcd(a, b)=mcd(a, b MOD a). Da una solución recursiva.
Ejemplo à mcd(60, 45) = mcd(45, 15) = mcd(15,0)
Solución:
funcion mcd(a, b:entero) devuelve entero
{ Pre: a>=0, b>=0}
Principio
si a=0
entonces devolver(b);
si no
si b=0
entonces devolver(a)
si no
si a>b
entonces devolver (mcd(b,a MOD b));
si no devolver (mcd(a,b MOD a));
fsi
fsi
fsi
fin
Un algoritmo recursivo debe tener:
- Un tratamiento de todos los casos triviales que puedan darse en el problema a resolver. Dicho tratamiento no puede hacer llamadas recursivas y sí tiene que dar una solución inmediata a esos casos triviales.
- Un tratamiento del(los) casos no trivial(es). Dicho tratamiento hará uso de una ley de recurrencia que mediante una fórmula o conjunto de acciones u operaciones resolverá el caso no trivial mediante llamadas a la propia función (o procedimiento) con parámetros “más pequeños” que converjan a uno de los casos triviales.
Para que el caso sea válido y funcione, cada llamada recursiva debe de hacer que la siguiente llamada se aproxime más a un caso trivial de forma que al final se llegue a dicho caso.
Lineales. Cada invocación genera una nueva invocación y sólo una (excepto la última, claro). Un ejemplo es el anterior ejercicio del factorial.
- Final. Lo último que hace el algoritmo es precisamente esa invocación.
- No final. Tras la invocación aún hay que hacer algún cálculo en el resultado de la invocación. El ejercicio de factorial sería no lineal, ya que tras la invocación hay que hacer la multiplicación
Múltiples. Una misma invocación puede generar más de una invocación, por ejemplo, un ejercicio de calcular Fibonacci.
En general las soluciones recursivas son:
- Menos eficientes que las iterativas
- Más claras y sencillas que las iterativas
Lo bueno es pensar en recursivo e implementar en iterativo.
Podemos transformas en muchos casos los algoritmos recursivos en iterativos con más o menos dificultad.
Gracias Inazio Claver por cubrirme!!
Oh bueno, no he perdido mucha teoría solo horas y horas para adelantar trabajos, ya voy dos hojas de ejercicios retrasada :_(Punteros en C
Los punteros es algo que cada lenguaje de programación trata de una forma especifica, aunque lo que se puede hacer en uno, normalmente se suele poder hacer en otro de una u otra manera.
Es por ello, que al ser algo especifico de programación, que vamos a verlo para el caso especifico de C, aunque algunas cosas podrían ser generalizables a otros lenguajes (pero muchas no).
Variables estáticas y dinámicas
En general, al programar, puedo hacer uso de dos tipos de variables:
- estáticas: La memoria que utilizan se reserva en tiempo de compilación. Ventaja: sencillez.
int matriz[5][5];
- dinámicas: La memoria se reserva en tiempo de ejecución. Ventajas: flexibilidad (estoy definiendo una matriz de cualquier tamaño) y permiten la creación de estructuras de datos dinámicas ( que es un mecanismo más complejo que el visto ahora con las estructuras estáticas).
int*mariz;
...
matriz=malloc(sizeof(int)*5*5);
Para utilizar variables dinámicas es preciso disponer de un mecanismo para acceder a la memoria del ordenador. Ese mecanismo es precisamente el uso de punteros.
Concepto de puntero
Cuando tengo una variable, hay tres datos que están relacionados en ella:
- Tipo: Directamente relacionado con el tamaño del espacio que se reserva en memoria para ella.
- Valor que contiene.
- Dirección: Ubicación en memoria.
Un puntero es una variable que almacena la dirección de memoria de otra variable.
Es como una flecha que apunta a otra variable.
Punteros: dos operadores
Operador dirección (&): Nos devuelve la dirección de una variable.
Operador contenido o indirección (*): Nos permite acceder al contenido de una variable a la que está apuntando un puntero.
Declaración de punteros
Hay que indicar el tipo de la variable a la que apuntara, el nombre del puntero, y utilizar el símbolo * para indicar que es un puntero.
Ejemplo:
int valor;
int *puntero;
puntero=&valor;
valor=5;
*puntero=5; /*Las dos instrucciones hacen lo mismo*/
valor: 5
puntero: *
Más sobre punteros
¿Cuál es la diferencia?
- punteros=5; (Modificado a dónde apunta el puntero)
- *puntero=5; (Modifico el valor de la variable a la que apunta el puntero)
Hay que inicializar los punteros para que apunten a una dirección de memoria antes de utilizarlos.
- int *puntero;
*puntero=7;
- ¿Dónde apunta el puntero? ¿Qué estoy modificando? Exacto, no lo sé ni yo, así que esto al Sistema Operativo no le va a gustar y seguro que se enfada (abortándome el programa).
Valor NULL: es un valor que se usa para indicar que un puntero no apunta a ningún sitio.
- int *puntero=NULL;
¿Qué operaciones puedo hacer datos apuntados? Las mismas que con el correspondiente tipo de datos.
Operaciones básicas con punteros
Asignación
- Hacer que el puntero apunte a una dirección de memoria.
- p1=p2; ojo, p1 pasa a contener la dirección de memoria contenida en p2.
- implicaciones:
* Los vectores hay que copiarlos componente a componente.
* Si copiamos el puntero, no hemos copiado la variable.
Comparación
- Ver si dos punteros apuntan al mismo lugar.
- p1==p2 no es lo mismo que *p1==*p2
Suma, resta
- Se utilizan para recorrer estructuradas de datos.
- p1++ (apuntará al siguiente carácter de una cadena)
Inicialización del valor de un puntero
Tengo dos opciones:
- Asignar la dirección de otra variable del programa:
int valor;
int *puntero;
puntero=&valor;
- Pedir al sistema memoria para una variable nueva.
* Es precisamente la opción empleada para utilizar variables dinámicas.
* C ofrece funciones para obtener memoria del Sistema Operativo de forma dinámica y liberarla cuando ya no es necesaria.
Generación y destrucción de variables dinámicas
#include <stdlib.h> /*necesario para asignación dinámica de memoria*/
...
struct fecha {
int dia;
int mes;
int agno;
};
struct fecha *pFecha;
...
pFecha=(struct fecha *) malloc (sizeof(struct fecha));
if (pFecha==NULL){
printf("No hay suficiente memoria\n");
}
else {
...
free (pFecha):
...
}
...
malloc y free
pFecha=(struct fecha *) malloc (sizeof(struct fecha));
- malloc reserva los bytes que indiquemos en el parámetro que le pasamos (Precisamente para ello usamos la función sizeof pasándole como parámetro el tipo correspondiente. Así reservamos espacio justo para una variable de ese tipo).
- malloc devuelve un puntero genérico ( o NULL si no hay memoria suficiente).
- Tras llamar a malloc hay que hacer una conversión explícita de tipos para convertir ese puntero genérico en un puntero específico al tipo de datos que estamos manejando (en este caso en un puntero a struct fecha).
free(pFecha)
- free libera la memoria a la que apunta el puntero que le pasamos como parámetro.
- liberará más o menos memoria en función del tipo de datos del que sea el puntero que le pasamos.
Paso de parámetros por referencia a una función
Los punteros entre otras cosas dan soporte ara poder pasar parámetros por referencia a una función:
...
float perim, área;
circulo(radio, &perim, &área);
...
void circulo (float r, float *p, float *a){
*p=2*Pl*r;
*a=Pl*r*r;
}
Si la función llamara a otra función y hubiera que pasar de nuevo "a" por referencia, no habría que poner "&" delante de "a", ya que "a" es ya un puntero y por tanto una dirección.
Punteros y vectores
char *p, c, v[5]; /*Definimos un puntero a carácter, un carácter, y un vector de 5 caracteres*/
c=*p; /* Asigno a c lo apuntqado por p*/
p=&c; /* Asigno a p la dirección de c*/
/* Al definir un vector v[5] se queda guardada la dirección inicial del vector en la constante v*/
p=v;
p=&v[0]; /* Esta línea y la anterior son equivalentes*/
/* Del mismo modo p+4 es exactamente lo mismo que &p[4]*/
/* Y *(v+4) equivale a v]*/
Recorriendo vectores con punteros
* Le estaríamos sumando a p 1:
char*p;
p=p+1;
* Le estaríamos sumando a p 4:
int *9;
p=p+1 /* si, uno vale por cuatro*/
Aclarando un poco las cosas
int vector[4]
El compilador reserva cuatro enteros consecutivos en memorial.
Almacena en la variable vector la dirección del primer elemento del vector.
Acceso a los elementos:
vector [0] *(vector)
vector [1] *(vector+1)
vector [2] *(vector+2)
vector [3] *(vector+3)
La variable vector es como un puntero, con la única diferencia de que se ha reservado además espacio para sus componentes.
Paso de vectores como parámetros
Cuando pasamos un vector a una función, lo estamos pasando implícitamente por referencia, ya que un vector y un puntero, a fin de cuentas, son lo mismo (o casi).
Como parámetro actual ponemos la variable vector (que como acabamos de ver no es más que un puntero).
Como parámetro formal, hasta ahora hemos hecho apaños ya que no sabíamos muy bien lo que eran los punteros ni su relación con los vectores, pero a partir de ahora basta con poner un puntero al tipo del que sean las componentes del vector. Dentro de la función podré acceder a las 2componentes de ese puntero" sin ningún problema.
Recordar que al ser un paso por referencia y al estar pasando punteros, todos los cambios que haga el vector quedarán hechos en el vector original.
Recordar además que existe un motivo importante para que un vector se pase siempre por referencia, y es que de hacerse por valor se estarían duplicando las necesidades de memoria.
Paso de parámetros: Ejemplo
main(){
char cadena[50];
char nueva[50];
...
QuitaEspacios (cadena, nueva);
/* cadena y nueva son ya direcciones*/
...
}
void QuitarEspacios (char *origen, char *destino){
...
destino[3]=origen[7];
...
}
0 comentarios:
Publicar un comentario