/******************************************************/
/*************** Isidro Pastor Jorda ******************/
/************** Noemi Ruth Moya Hinojo ****************/
/******************************************************/
/****************** Telematica ************************/
/******************************************************/
/************* Practica 1 cost.cpp ********************/
/******************************************************/
#include <iostream.h>
#include <stdlib.h>
#include <cstdlib> // include para usar la funcion rand()
#include <string>
#include <fstream.h>
const int MAX = 10000;
typedef int Vector[MAX-1];
int Lineal (Vector v, int talla, int x, int & coste);
int Binaria3 (Vector v, int talla, int x, int & coste);
int Binaria2 (Vector v, int talla, int x, int & coste);
void Escribir(string fichero,int costemedio,int talla);
int main()
{
int i, x;
int coste, talla, costemedio;
int busq; // indice que usaremos para contar las busquedas que hacemos y que llegaran hasta 5*talla
Vector v;
coste = 0;
talla = 10;
x = 0;
int impar = -1;
cout << "******************************************************"<< endl;
cout << "*************** Isidro Pastor Jorda ******************"<< endl;
cout << "************** Noemi Ruth Moya Hinojo ****************"<< endl;
cout << "******************************************************"<< endl;
cout << "****************** Telematica ************************"<< endl;
cout << "***********Funtamentos de Programacion II ************"<< endl;
cout << "****************** Practica 1 ************************"<< endl;
cout << "******************************************************"<< endl;
cout << endl << endl;
cout << "Generando ficheros de costes de algoritmos " ;
for (i=0; i<MAX-1; i++) // generacion del vector de impares
{
v[i] = impar + 2;
impar+=2;
}
for (talla = 10; talla <= 10000; talla=talla*3/2) // Bucle para ir modificando la talla del vector
{
/********************************************************************
** Comenzamos a realizar las busquedas con probabilidad del 50% al *
** hacerlo generando un elemento aleatorio que puede estar o no en *
** el vector ya que pueden ser numeros pares o impares generados *
*********************************************************************/
/* Busqueda Lineal */
coste=0; // Inicializamoso el contador de costes
for(busq = 1; busq<=5*talla; busq++) // Repetiremos busquedas hasta un total de 5*talla
{
x = rand()%(2*talla); // Obtenemos un valor aleatorio para x entre 0 y 2*talla
Lineal (v, talla, x, coste); // Realizamos la busqueda de ese numero aleatorio
}
costemedio = coste / busq; // Una vez fuera del bucle calculamos el coste medio de comparaciones
Escribir("lin-50.dat", costemedio, talla); // y escribimos los datos obtenidos en el fichero correspondiente
/* Repetimos este esquema de operaciones para cada algoritmo de busqueda*/
/* Busqueda Binaria de 3 vias */
coste=0;
for(busq = 1; busq<=5*talla; busq++)
{
x = rand()%(2*talla);
Binaria3 (v, talla, x, coste);
}
costemedio = coste / busq;
Escribir("bin-50.dat", costemedio, talla);
/* Busqueda Binaria de 2 vias */
coste=0;
for(busq = 1; busq<=5*talla; busq++)
{
x = rand()%(2*talla);
Binaria2 (v, talla, x, coste);
}
costemedio = coste / busq;
Escribir("bim-50.dat", costemedio, talla);
/********************************************************************
** Comenzamos a realizar las busquedas con probabilidad del 100% al *
** hacerlo generando un indice aleatorio que usaremos para almacenar*
** en x un elemento que si esta contenido dentro del vector *
*********************************************************************/
coste=0; // Inicializamoso el contador de costes
for(busq = 1; busq<=5*talla; busq++) // Bucle para realizar hasta 5*talla busquedas
{
i = rand()%(talla-1); // Generamos el indice aleatorio entre 0 y talla-1
x = v[i]; // Almacenamos en x el valor contenido en el vector con indice i
Lineal (v, talla, x, coste); // Llamamos a la funcion de busqueda con el valor x
}
costemedio = coste / busq; // Una vez fuera del bucle calculamos el coste medio de comparaciones
Escribir("lin-100.dat", costemedio, talla); // y escribimos los datos obtenidos en el fichero correspondiente
/* Repetimos este esquema de operaciones para cada algoritmo de busqueda*/
/* Busqueda Binaria de 3 vias */
coste=0;
for(busq = 1; busq<=5*talla; busq++)
{
i = rand()%(talla-1);
x = v[i];
Binaria3 (v, talla, x, coste);
}
costemedio = coste / busq;
Escribir("bin-100.dat", costemedio, talla);
/* Busqueda Binaria de 2 vias */
coste=0;
for(busq = 1; busq<=5*talla; busq++)
{
i = rand()%(talla-1);
x = v[i];
Binaria2 (v, talla, x, coste);
}
costemedio = coste / busq;
Escribir("bim-100.dat", costemedio, talla);
cout << "." ; // Pintaremos un punto en pantalla cada vez que terminemos el analisis de una talla
}
cout << endl;
cout << endl << "Ficheros de costes de algoritmos generados ....." << endl;
cout << endl << "Recuerda que si has compilado cost.cpp con dev-c++ tendras los ficheros en el directorio del programa"<< endl;
cout << endl ;
system("PAUSE");
return 0;
}
/******************************************************************************
* Funcion: Lineal
* Descripcion: Funcion que realiza una busqueda lineal de un elemento
* en un vector.
*
* Parametros:
*
* Nombre E/S Descripcion
* ------ ----- -----------
* v E Vector sobre el que trabajaremos
* talla E Talla del vector
* x E Elemento que buscamos
* coste E/S coste de las comparaciones de elementos del vector
*
* Valor devuelto:
* Devuelve un entero que sera el indice del vector donde se encuentra
* el elemento que buscamos, devuelve como indice la talla del vector
* si no encontramos el elemento dentro del vector
******************************************************************************/
int Lineal (Vector v, int talla, int x, int & coste)
{
int i;
int aux = talla;
i=0;
while(i<talla)
{
if (v[i]==x)
aux = i;
coste++;
i++;
}
return (aux);
}
/******************************************************************************
* Funcion: Binaria3
* Descripcion: Funcion que realiza una busqueda Binaria de 3 vias
* de un elemento en un vector.
*
* Parametros:
*
* Nombre E/S Descripcion
* ------ ----- -----------
* v E Vector sobre el que trabajaremos
* talla E Talla del vector
* x E Elemento que buscamos
* coste E/S coste de las comparaciones de elementos del vector
*
* Valor devuelto:
* Devuelve un entero que sera el indice del vector donde se encuentra
* el elemento que buscamos, devuelve como indice la talla del vector
* si no encontramos el elemento dentro del vector
*******************************************************************************/
int Binaria3 (Vector v, int talla, int x, int & coste)
{
int izq, der, cen, aux;
izq = 0;
der = talla -1;
cen = (izq + der)/2;
while (( izq < der) && (v[cen] != x)) // Repetiremos el bucle mientras no se crucen los indices y no encontremos x
{
if (v[cen] > x) // si el central es mayor que x cogeremos la parte de la izquierda
der = cen -1; // por lo que el nuevo indice derecho sera la posicion del centro menos 1
else // en caso contrario x sera mas grande que el central y cogemos el derecho
izq = cen +1; // por lo que el indice izquierdo sera ahora el central mas 1
cen = (izq + der)/2; // Calculamos el nuevo centro de nuestro subvector
coste = coste + 2; // como hacemos dos comparaciones aumentamos el coste en dos
}
coste++; // Añadimos un coste mas motivado por la comparacion de salida del bucle while
if (v[cen] == x) // Si hemos salido sera porque hemos encontrado x en el vector o cruzado indices
aux = cen; // Si el central es el buscado almacenamos el indice central en aux
else
aux = talla; // en caso contrario se han cruzado los indices sin encontrar el valor
coste++; // Esto produce una comparacion mas de elementos del vector
return aux; // Devolvemos el indice donde hemos encontrado el valor
}
/***************************************************************************
* Funcion: Binaria2
* Descripcion: Funcion que realiza una busqueda Binaria de 2 vias
* de un elemento en un vector (Dicotomica modificada).
*
* Parametros:
*
* Nombre E/S Descripcion
* ------ ----- -----------
* v E Vector sobre el que trabajaremos
* talla E Talla del vector
* x E Elemento que buscamos
* coste E/S coste de las comparaciones de elementos del vector
*
* Valor devuelto:
* Devuelve un entero que sera el indice del vector donde se encuentra
* el elemento que buscamos, devuelve como indice la talla del vector
* si no encontramos el elemento dentro del vector
****************************************************************************/
int Binaria2 (Vector v, int talla, int x, int & coste)
{
int izq, der, cen, aux;
izq = 0;
der = talla -1;
cen = (izq + der)/2;
while ( izq+1 <= der-1) // Antes de entrar en el bucle miramos que tenemos mas de dos elementos
{
if (v[cen] > x) // Si el elemento central es mas grande que x, buscaremos a la izquierda del central
der = cen -1; // por lo tanto nuestro nuevo elemento derecho sera el inmediato anterior al central
else // En caso de ser el elemento x mayor o igual al central cogeremos la seccion derecha
izq = cen; // por lo que haremos el indice izquierdo igual a nuestro indice central
cen = (izq + der)/2; // Calculamos el nuevo centro de nuestra seccion de vector a comprobar
coste++; // incrementamos el coste cada vez que se ejecuta el bucle
}
if (v[izq] == x) // Si hemos salido es porque nos quedan solamente dos elementos, comparamos el izquierdo
aux = izq; // si es el que buscamos entonces almacenamos su posicion en aux
else // en caso contrario comprobaremos si el que buscamos es el derecho
{
if (v[der] == x) // si lo es almacenamos en aux su posicion
aux = der;
else
aux = talla; // en caso de no ser ninguno de los dos no hemos encontrado el valor y devolvemos la talla
coste++;
}
coste++;
return aux;
}
/*****************************************************************************
* Funcion: Escribir
* Descripcion: Funcion que añade a un fichero los valores de talla y
* coste medio
*
*
* Parametros:
*
* Nombre E/S Descripcion
* ------ ----- -----------
* fichero E Nombre del fichero donde añadir los datos
* costemedio E Valor del coste medio
* talla E Talla del vector con el que hemos calculado el coste
*
* Valor devuelto:
* void, la matriz no devuelve nada pero modifica el fichero que le pasamos
*****************************************************************************/
void Escribir(string fichero, int costemedio, int talla)
{
ofstream f;
f.open (fichero.c_str(), ios::app); // abrimos el fichero en modo append
if (!f)
cout << " Error abriendo el fichero "<< fichero << " para grabar datos " << endl;
else
{
f << talla << " " << costemedio << endl; // añadimos en el fichero la talla y el coste medio
f.close();
}
return;
}