Estructuras de Datos II: Ejercicios Prácticos de Métodos de Búsqueda y Ordenamiento en C/C++


Dado un vector numérico entero de 22 elementos introducidos de forma aleatoria con valores positivos y ordenados de forma ascendente. Pedir por teclado el valor a buscar en el vector y realizar una búsqueda dicotómica. Antes de finalizar se visualizará el vector y si el elemento se encontró la posición que ocupa y en caso contrario se visualizará mediante un mensaje adecuado que el elemento no se encontró en el vector.

Para la resolución de este ejercicio, hemos utilizado la búsqueda dicotómica, dado que podemos acceder a un array ordenado y buscar un dato concreto, de una forma muy sencilla. Además, éste método reduce el tiempo de búsqueda considerablemente, ya que disminuye exponencialmente el número de iteraciones necesarias.


#include <stdio.h>
#include<conio.h>
int main (){
//crear vector con 22 elementos
int a[22]= {1,3,5,7,9,11,13,15,17,19,21,23,25,27,29,31,33,35,37,39,41,43};

//crear variables
int dato; //valor ingresado a buscar por el usuario
int inf; // lado izquierdo del vector
int sup; //lado derecho del vector
int mitad; //centro del vector
int posicion; //lugar del dato en el vector
char band='F'; //valor para determinar si el dato fue encontrado

//solicitar a usuario valor a buscar
printf("\n Ingrese un nro a buscar entre 0 y 45: ");
scanf("%i",&dato);

//Búsqueda Dicotómica
inf=0;
sup=22;

while (inf <=sup)
{
mitad =(inf + sup)/2;
if (a[mitad]==dato){
band='V';
break;
}
if (a[mitad]>dato){
sup=mitad;
mitad=(inf+sup)/2;
}
if (a[mitad]<dato){
inf=mitad;
mitad - (inf+sup)/2;
}
}
if (band=='F'){
printf("El valor buscado no esta dentro del vector");
}
else if (band=='V')
{
posicion=mitad + 1;
printf("El valor buscado esta en la posicion: %i",posicion);
}

getch();
return 0;
}


Dado un vector numérico entero de 20 ordenar los números enteros contenidos en el array a través del método de la burbuja.

Hemos utilizado el método burbuja dado que es uno de los procedimientos más comunes y útiles en el procesamiento de datos, es la ordenación de los mismos. Se considera ordenar al proceso de reorganizar un conjunto dado de objetos en una secuencia determinada (patrón de arreglo). El objetivo de este proceso generalmente es facilitar la búsqueda de uno o más elementos pertenecientes a un conjunto; en nuestro caso, al vector numérico.

#include “iostream.h”
#include “conio.h”

//metodo para imprimir al vector
int num[20],n;
void muestra_vector(){
for (int t; t=0; t<n; t++)
{
cout<<num[t]<<” ”;
}
}

//metodo de ordenacion burbuja
void ordenar_burbuja(){
int temp;
for (int i =0; i<n; i ++)
{
for (int k=n-1; k>0; k--)
{
if (num[k]<num[k-1]){
temp=num[k];
num[k]=num[k-1];
num[k-1]=temp;
}
}
}

//parte principal del programa
main(){

//asignacion del los elementos del vector
vector<int> num(8,10,13,4,5,6,7,9,15,20,11,2,30,31,25,26,24,28,19,17);

//impresion del vector desordenado
cout<<”Antes de ordenar: ”<<endl;
for (int j=0;j<n; j++)
{
cout <<num[j] << “ ”;
}

//llamado al metodo burbuja para que ordene el vector
ordenar_burbuja();

//impresion del vector ordenado
cout <<”Ordenamiento Metodo Burbuja: ”<<endl;
muestra_vector();

getch();
}
 


Comentarios