#include <iostream.h>
#include <stdlib.h>
#include <time.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);
int main()
{
int i, x, aux, coste, talla;
int opcion;
int impar = -1;
bool salir = false;
Vector v;
coste = 0;
for (i=0; i<MAX-1; i++) // generacion del vector de impares
{
v[i] = impar + 2;
impar+=2;
};
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 << "** Programa de prueba de los algoritmos de busqueda **"<< endl;
cout << "******************************************************"<< endl;
cout << endl << endl;
do
{
cout << " Menu de opciones:" << endl << endl;
cout << " 1.- Busqueda lineal "<< endl;
cout << " 2.- Busqueda Binaria de 3 vias" << endl;
cout << " 3.- Busqueda Binaria de 2 vias" << endl;
cout << " 4.- Salir" << endl;
do
{
cout << " Indique el numero de la opcion que desea realizar -> ";
cin >> opcion;
cout << endl;
}
while (opcion < 1 || opcion > 4); // repetiremos la toma de opcion hasta que tengamos una correcta
if (opcion != 4) // si la opcion es la 4 es para salir y entonces no tenemos que tomar estos datos
{
cout << " Dame el valor que debemos buscar en el vector de impares -> " ;
cin >> x;
cout << endl;
do
{
cout << endl;
cout << " Dame la talla que quieres para el vector entre 1 y "<< MAX << " -> " ;
cin >> talla;
}
while (talla > MAX || talla < 1); // la talla siempre estara entre 1 y MAX
}
switch (opcion)
{
case 1:
aux = Lineal (v, talla, x, coste);
break;
case 2:
aux = Binaria3 (v, talla, x, coste);
break;
case 3:
aux = Binaria2 (v, talla, x, coste);
break;
case 4:
salir = true;
break;
}
if (opcion != 4)
{
if (aux == talla) // Si el indice devuelto es igual a la talla es que no hemos encontrado el elemento
cout << endl << " No se ha encontrado el elemento y el coste ha sido de " << coste << endl;
else
cout << endl << " Hemos encontrado el elemento " << v[aux] << " en la posicion " << aux << " coste = "<< coste << endl;
}
else
cout << " El programa ha terminado " << endl << endl;
}
while (!salir);
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;
}