| Asignatura: Fundamentos de Informática | |
|
| Especialidad: Electrónica - UPV/EHU | ||
| Curso académico: 2013-2014 | ||
| Profesor: Ismael Etxeberria Agiriano |
Se pueden consultar ejercicios similares al presente en formato de presentación.
Diseña y codifique un programa que genere un vector de números reales aleatorios del 0 al 10 (ambos inclusives) con un decimal y los ordene crecientemente.
Habrá que generar, por ejemplo, una lista de 10 números aleatorios, como se muestra en la Figura 12.1.
Tras ordenarlo, el resultado aplicado al ejemplo debería ser el mostrado en la Figura 12.2.
Para la resolución del ejercicio propuesto vamos a necesitar la
función (o macro) random definida en la
stdlib.h, que tiene la forma siguiente:
int random (int n);
La macro
random
devuelve un número de una serie pseudo-aleatoria de distribución uniforme
entre 0 y n - 1.
Para inicializar el primer valor (semilla) utilizaremos el reloj del sistema
con la función (o macro)
randomize
(que requiere la inclusión del fichero time.h) de la forma:
void randomize (void);
En DevC++ no vienen definidas estas macros por lo que habrá que hacerlo a mano, despues de incluir stdio.h:
#include <stdlib.h> #if !defined(randomize) #define randomize() srand((unsigned)time(NULL)) #endif #if !defined(random) #define random(num)(int)(((long)rand()*(num))/(RAND_MAX+1)) #endif
En este apartado vamos a acometer el problema de generar el vector de números aleatorios y mostrarlo en pantalla.
Vamos a dividir el problema definiendo una función que genere genere un vector v de números n aleatorios:
void GenerarAleatorios (double v[], int n);
Una definición equivalente de esa función será:
void GenerarAleatorios (double *v, int n);
Es muy importante entender que aquella parte del programa que llame a esta función ha de disponer de un espacio reservado de al menos n elementos a partir de la dirección v. Además, dentro de esta función no sabemos cuántos elementos están reservados.
Definiremos similarmente una función para mostrar los n primeros elementos de un vector v en pantalla:
void MostrarVector (double *v, int n);
El programa principal que inicializa la semilla de números aleatorios, genera la lista de números aleatorios y los muestra en pantalla puede ser:
#include <stdlib.h>
#include <time.h>
void GenerarAleatorios (double v[], int n);
void MostrarVector (double v[], int n);
void main (void)
{
double vector[10];
randomize ();
GenerarAleatorios (vector, 10);
MostrarVector (vector, 10);
}
Para generar la lista de n números aleatorios entre 0 y 10 con un
decimal podemos obtener números del 0 al 100 y dividirlos entre 10.
Para ello llamaremos a la macro random con 101 como
parámetro.
void GenerarAleatorios (double v[], int n)
{
int i;
for (i = 0; i < n; i++)
v[i] = (double) random (101) / 10.0;
}
Hemos utilizado el cast (double) que convierte el número
entero devuelto por random a real
y obtener el resultado real deseado,
evitándose divisiones enteras.
En realidad esto no es necesario ya que al especificar 10.0 el mismo
compilador va a llevar a cabo esta conversión.
La función MostrarVector es sencilla:
#include <stdio.h>
void MostrarVector (double v[], int n)
{
int i;
for (i = 0; i < n; i++)
printf (" %4.1f", v[i]);
printf ("\n");
}
La función de ordenación recibe un vector y lo ordena. Su prototipo puede ser:
void OrdenarVector (double v[], int n);
El programa principal que genere la lista de números aleatorios, los muestre, los ordene y los vuelva a mostrar puede ser:
#include <stdlib.h>
#include <time.h>
void GenerarAleatorios (double v[], int n);
void MostrarVector (double v[], int n);
void OrdenarVector (double v[], int n);
void main (void)
{
double vector[10];
randomize ();
GenerarAleatorios (vector, 10);
MostrarVector (vector, 10);
OrdenarVector (vector, 10);
MostrarVector (vector, 10);
}
Se puede observar que lo único que hemos añadido al programa principal
del apartado anterior es la especificación del prototipo de la función
de ordenación OrdenarVector,
su llamada en el programa principal y
el volver a mostrar en pantalla el vector, esta vez ordenado.
Para describir el algoritmo de ordenación que vamos a utilizar retomaremos el ejemplo al principio de este capítulo.
El algoritmo consistirá en colocar en primera posición el elemento más pequeño intercambiando con el actual, y así sucesivamente hasta ordenar todo el vector. No vamos a utilizar diagramas de flujo, sino que podemos decir, mediante pseudo-código:
Para i De 0 A n-2 Hacer
j = índice del elemento más pequeño de i a n-1
Si i ≠ j Entonces
Intercambiar contenido de las celdas i y j
En la Figura 12.4 se muestra el estado del vector durante el proceso de ordenación.
El primer vector contiene los elementos tal y como se muestran en la Figura 12.3. El elemento menor del vector es 0.9 y el índice j de este elemento es el 3. Por lo tanto tendremos que intercambiar el elemento en la posición 0, 5.2, con el elemento en la posición 3, 0.9.
Consideraremos que este primer elemento está ordenado y abordaremos el algoritmo para el subvector de la posición 1 hasta la 9.
La codificación de esta función de ordenación puede ser:
int IndiceMenor (double v[], int n);
void Intercambia (double *n1, double *n2);
void OrdenarVector (double v[], int n)
{
int i, j;
for (i = 0; i < n - 1; i++) { /* Para i de 0 a n - 2 */
j = IndiceMenor (&v[i], n-i) + i;
if (j != i)
Intercambia (&v[i], &v[j]);
}
}
La obtención del índice con el elemento menor de
i a n-1
se hace mediante la función IndiceMenor a la que se le
pasa el subvector que comienza en la posición i
y tiene n-i elementos.
Para obtener el índice del vector original tendremos que añadirle a la
posición en el subvector el comienzo.
Veamoslo con un ejemplo.
En la figura 12.5 se puede ver el estado de la ordenación para i = 5, es decir, ya hemos ordenado todos los elementos anteriores.
Buscaremos el índice del elemento menor del subvector que resta por ordenar, que obtendremos indicando la dirección de la celda i-ésima, como se muestra en la Figura 12.6.
La función nos devolverá que el índice del elemento menor es el 1, pero en términos del vector original tendremos que sumarle i es decir, 5 por lo que j será 6.
Podemos definir una función que nos devuelva el índice del menor elemento de un vector de entre n:
int IndiceMenor (double v[], int n)
{
int i, m;
m = 0; /* Inicializamos el primer elemento como el menor */
for (i = 1; i < n; i++)
if (v[i] < v[m])
m = i;
return m;
}
El algoritmo para intercambiar el contenido de dos variables es conocido. Podemos codificar la función correspondiente:
void Intercambia (double *n1, double *n2)
{
double t;
t = *n1;
*n1 = *n2;
*n2 = t;
}