viernes, 17 de mayo de 2013

Búsqueda del valor máximo

Uno de los problemas académicos más comunes es el de la búsqueda del valor máximo o mínimo dentro de una lista. Una aplicación que podríamos darle a este problema sería por ejemplo con fines estadísticos, calcular para una muestra de datos: el máximo, el mínimo y el valor medio.

Antes de plantear el problema vamos a intentar "pensar en cámara lenta" y preguntarnos qué haría nuestra cabeza si tuviésemos que encontrar el valor máximo de una muestra de datos. Suponemos la siguiente muestra de datos:

2, 5, 10, 1, 7

A simple vista diríamos que el máximo es 10, pero ¿Cómo es que lo hemos determinado? si lo vemos en cámara lenta nos daríamos cuenta que:

1. Comparamos el 2 y el 5, como el 5 es mayor, nos quedamos con el 5 y descartamos el 2.
2. Comparamos el 5 con el 10, como el 10 es mayor, nos quedamos con el 10 y descartamos el 5.
3. Comparamos el 10 con el 1, como el 10 es mayor, nos quedamos con el 10 y descartamos el 1.
4. Comparamos el 10 con el 7, como el 10 es mayor, nos quedamos con el 10 y descartamos el 7.

Finalmente el último con el que nos quedamos fue el 10, por tanto, es el 10 el valor máximo.

Si analizamos cada uno de los pasos, vemos que en cada uno de ellos se compara un elemento de la lista con el valor con el que nos hemos quedado en el paso anterior. Si llevamos esto a lenguaje de programación  se puede plantear como un recorrido por todos los elementos de una lista en la que cada iteración realza una comparación entre el valor actual con el máximo de la iteración anterior, por tanto sabemos que debemos tener una estructura así:

//creamos la muestra de datos
int listaNumeros [5]; 
listaNumeros[0] = 2;
listaNumeros[1] = 5;
listaNumeros[2] = 10;
listaNumeros[3] = 1;
listaNumeros[4] = 7;

//tenemos un recorrido de la muestra
for(int i=0; i<5;i++)
{
  //comparamos el valor actual con el resultado de la iteración anterior
  if (listaNumeros[i] > valor_maximo)
  {
    //esta linea representa el "nos quedamos con" de cada paso
    valor_maximo = listaNumeros[i]; 
  }
}

Hasta aquí tenemos la estructura básica del algoritmo, ahora le hacemos algunos ajustes, teniendo en cuenta que la variable valor_maximo no la hemos inicializado.
Si la inicializaramos con 0, nos corremos el riesgo de que para otra muestra tengamos valores negativos y en ese caso el máximo siempre sería 0, lo mejor es tomar como máximo algún valor de la muestra, por ejemplo el primero.

//inicializamos el valor máximo con el primer elemento de la muestra
int valor_maximo = listaNumeros[0];

//tenemos un recorrido de la muestra
for(int i=0; i<5;i++)
{
  //comparamos el valor actual con el resultado de la iteración anterior
  if (listaNumeros[i] > valor_maximo)
  {
    //esta linea representa el "nos quedamos con" de cada paso
    valor_maximo = listaNumeros[i]; 
  }
}

Ahora que nos aseguramos que el valor_maximo de la muestra sea uno de los elementos de la muestra, vemos que la primera iteración comparará listaNumeros[0] y valor_maximo y que siempre serán iguales en la primera iteración, por tanto el código que está dentro del if núnca se ejecutará en la primera iteración, así que podemos aplicar una optimización haciendo que empiece la iteración a partir del segundo elemento, de la siguiente forma.


//inicializamos el valor máximo con el primer elemento de la muestra
int valor_maximo = listaNumeros[0];

//el recorrido se inicia en el segundo elemento
for(int i=1; i<5;i++)
{
  //comparamos el valor actual con el resultado de la iteración anterior
  if (listaNumeros[i] > valor_maximo)
  {
    //esta linea representa el "nos quedamos con" de cada paso
    valor_maximo = listaNumeros[i]; 
  }
}

Finalmente, aprovecharemos el mismo recorrido para calcular el máximo, el mínimo y la media:

//creamos la muestra de datos
int listaNumeros [5]; 
listaNumeros[0] = 2;
listaNumeros[1] = 5;
listaNumeros[2] = 10;
listaNumeros[3] = 1;
listaNumeros[4] = 7;

int valor_maximo = listaNumeros[0];
int valor_minimo = listaNumeros[0];
int media = listaNumeros[0];

for(int i=1; i<5;i++)
{
  //Búsqueda del máximo
  if (listaNumeros[i] > valor_maximo)
  {
    valor_maximo = listaNumeros[i];
  }

  
  //Búsqueda del mínimo
  if (listaNumeros[i] < valor_minimo)
  {
    valor_minimo = listaNumeros[i] ;
  }

  //cálculo de media
  media +=  listaNumeros[i] ;

}

//al terminar el recorrido la variable media contiene la suma de todos los elementos
//dividimos entre el número de elementos para calcular la media
media = media/5;

//En este punto tenemos calculado los tres valores estadísticos de la muestra, los imprimimos en pantalla
printf("valor_maximo: ", valor_maximo);
printf("valor_minimo: ", valor_minimo);
printf("media: ", media);



1 comentario: