MTP 2: Práctica 1

MTP 2

1 Especificaciones y Análisis 1.1 Especificaciones La práctica se centra en dominar los conceptos más elementales de C (Bucles, Vectores, Ficheros, Funciones con argumentos por valor y referencia, creación de todos estos elementos mediante prototipos separados del programa principal), para su uso posterior en practicas futuras.

1.1.1 Especificaciones Particulares Ejercicio 1 El primer ejercicio pide generar una rutina que genere un numero aleatorio equiprobable entre dos valores (MAX,MIN) que se le pasan a la función. La forma de resolución de este programa reside en encontrar una formula que permita dar números aleatorios por igual: return iP + (int) ( ( (double) (iU-iP+1) * rand() ) / (RAND_MAX+1.0) ); Con esta ecuación obtenemos valores aleatorios equiprobables entre iU e iP, la explicación es bien sencilla, al restar el Max-Min y sumarle uno obtenemos el rango de posibles valores, si multiplicamos por rand() y dividimos por el valor máximo de rand() + 1 el resultado, como máximo va a ser iU-iP y como mínimo va a ser cero, por lo que al sumar el Min siempre va a dar un numero entre ambos valores.

1.1.2 Especificaciones Particulares Ejercicio 2 Este ejercicio nos pide una rutina que genere permutaciones aleatorias entre 0 y N, para generar dicha rutina se nos facilita el siguiente pseudocódigo: para i de 1 a N: perm[i] = i; para i de 1 a N: intercambiar perm[i] con perm[aleator(i, N)];

1.1.3 Especificaciones Particulares Ejercicio 3 El tercer programa nos pide generar una rutina que llame a la rutina del ejercicio 2, pasándole a la rutina del ejercicio 2, el valor M, nos generara tantas permutaciones como veces se la llame mediante el parámetro N.

1.1.4 Especificaciones Particulares Ejercicio 4 Éste apartado nos pide dar el código de una rutina que ordene las permutaciones generadas por los ejercicios anteriores.

1.1.5 Especificaciones Particulares Ejercicio 5 Éste programa tiene como finalidad determinar experimentalmente el tiempo medio de ejecución por inserción sobre tablas de diferentes tamaños, para ello la rutina recurre a las rutinas generadas en los ejercicios anteriores para generar las permutaciones y ordenarlas, además de la rutina Driver_Ordena, en este ejercicio se pide generar una

2

MTP 2 rutina que escriba en un fichero el tiempo medio de ejecución del algoritmo de ordenación para n_perms.

1.2 Análisis 1.2.1 Análisis Particular Ejercicio 1 Para realizar el histograma, se nos planteo la posibilidad de hacerlo mediante el Gnuplot, los datos se los podíamos pasar de dos maneras generando en la propia función un fichero donde guardar los valores y las veces que se repiten, o mediante la siguiente línea de código en Linux vamos metiendo en un fichero las veces que se repite cada numero: “Grep numero salida.txt | wc –l >>distribución.txt”, se generaba el fichero, esta segunda forma es la que hemos usado para generar las graficas en el Gnuplot y de esta forma no modificar la función.

1.2.2 Análisis Particular Ejercicio 2 En este ejercicio no se encontraba dificultad aparente si el primer ejercicio poseía un algoritmo correcto.

1.2.3 Análisis Particular Ejercicio 3 El trabajo con punteros es el elemento principal de éste ejercicio. Lo más importante es cubrir los casos para errores en la reserva de memoria y su posterior liberación.

1.2.4 Análisis Particular Ejercicio 4 En este ejercicio la principal dificultad se podía encontrar en el diseño del código de ordenación.

1.2.5 Análisis Particular Ejercicio 5 La principal característica de este ejercicio es la medición del tiempo de ejecución de un método, teniendo claro los ejercicios anteriores este ejercicio solo planteaba la dificultad de medir el tiempo que se solucionaba mediante la instrucción clock() .

2 Diseño 2.1 Estructuras y Tipos Abstractos de Datos Estructura de ordena.h typedef int (*pfunc_pivote) (int, int); typedef int (*pfunc_ordena) (int *, int, int, pfunc_pivote); int aleator(int iP,int iU); int *genera_perm(int n); int **driver(int N,int M); int InsertSort(int *tabla,int P,int U,pfunc_pivote pivote); double Driver_Ordena(pfunc_ordena metodo, pfunc_pivote pivote, int n_perms, int tamanio);

3

MTP 2 int Time_Ordena(pfunc_ordena metodo, pfunc_pivote pivote, char *fichero, int num_min, int num_max, int incr, int n_perms); short GuardaTabla_double(char *fichero, double *tiempo, int *tamanio, int N);

2.2 Algoritmo A continuación adjuntamos el código de las funciones con los algoritmos Fichero “ordenar.c” /*FUNCIÓN: aleator*/ int aleator(int iP,int iU) { return iP + (int) ( ( (double) (iU-iP+1) * rand() ) / (RAND_MAX+1.0) ); } /*FUNCIÓN: genera_perm*/ int *genera_perm(int n) { int i, aleat, temp; int *perm = NULL; if(n