Sesión 9 complemento

Vista previa del material en texto

UPN, PASIÓN POR
TRANSFORMAR VIDAS
SESIÓN 9: Divide y vencerás
Ing. Mitchell Blancas
ANALISIS DE ALGORITMOS Y ESTRATEGIAS DE PROGRAMACION
LOGRO DE LA SESIÓN
Al término de la sesión el estudiante aplica divide y vencerás en la solución de problemas propuestos y los representa a través de algoritmos.
¡Pregunta!
¿Cómo ordenar datos usando divide y vencerás?
QuickSort
void Quicksort (int *v, int Izq, int Der){
 int i=Izq, j=Der, aux;
 int Pivote=v[(Izq + Der)/2];
 do{
 while (v[i] < Pivote) i++;
 while (v[j] > Pivote) j--;	
	 if (i<=j){
 	 aux=v[i];
	 v[i]=v[j];
	 v[j]=aux;
	 i++;
	 j--;
	 }	
 }while(i<=j);
 if(j>Izq) Quicksort (v, Izq,j);
 if(i<Der) Quicksort (v, i, Der);
}
#include <iostream>
using namespace std;
int main(){
	int vec[5]={6,4,3,8,1};
	Quicksort(vec,0,4);
	for(int k=0;k<5;k++)
		cout<< vec[k] << " ";
}
Imprime: 1,3,4,6,8
Realizar la prueba de escritorio
#include <iostream>
using namespace std;
int main(){
	int vec[5]={7,1,3,12,10};
	Mergesort(vec,0,4);
	for(int k=0;k<5;k++)
		cout<< vec[k] <<" ";
}
MergeSort
Imprime: 1,3,7,10,12
Realizar la prueba de escritorio
void Mergesort (int *v, int primero, int ultimo){
	int central;
	if(primero < ultimo ){
		central = (primero + ultimo)/2;
		Mergesort(v,primero,central);
		Mergesort(v,central+1,ultimo);
		mezcla(v,primero,ultimo,central);
	}
}
MergeSort
void mezcla(int *v, int izq,int dcha, int centro)
{	int x=izq,y=centro+1,z=x;
	//Vector auxiliar para realizar la mezcla
	int aux[100]; 
	while (x <= centro && y <= dcha){
		if(v[x]<v[y]) { aux[z]= v[x]; x++;}
		else { aux[z]= v[y]; y++;}
		z++;
	}
 //Terminar de pasar elementos faltantes
 while (x<=centro){ aux[z]=v[x]; x++;z++;}
 while (y<=dcha){ aux[z]=v[y]; y++;z++;}
 //Copiar aux en v
 for(x=izq; x<=dcha;x++)
 v[x] = aux[x];
}
BUSQUEDA
Métodos DyV:
Búsqueda binaria
Búsqueda ternaria
Búsqueda por interpolación
Búsqueda Binaria
	Si el conjunto de elementos es grande, el tiempo de búsqueda en dicho conjunto se puede reducir utilizando el siguiente algoritmo de tipo divide y venceras:
	PASOS:
Ordenar el registro.
Se divide el registro en 2 partes. 
Se determina la parte donde esta contenida el elemento buscado.
Se repite el proceso en esa parte hasta encontrar el elemento buscado.
Si al finalizar todo el proceso, no se llego a encontrar dicho elemento, se devuelve un indicador de no_éxito.
int bBR(int izq, int der, int n, int x[ ], int t){ 
 if (izq<=der){
 int mitad=(izq+der)/2;
 if (t>x[mitad]) 
		bBR(mitad+1, der, n, x, t);
 else if(t<x[mitad]) 
		bBR(izq, mitad-1, n, x, t);
 else 
		return mitad;
 }
 else return -1;
}
Código
 Búsqueda por Interpolación 
Consiste en tratar de acertar en qué parte del intervalo está el elemento que se esta buscando en lugar de ciegamente dividir el arreglo a la mitad. Para ello se utiliza la siguiente proporción.
t
X[izq]
X[der]
izq
pos
der
Arreglo x[]
 pos – izq der – izq
––––––––– = –––––––––––
 t – x[izq] x[der] – x[izq]
despejando pos, tendremos: 
pos = izq + (der - izq) * (t - x[izq]) / ( x[der] - x[izq] ) 
int BInterpolacion(int n, int x[ ], int t) { 
 int pos, izq, der; 
 izq = 0; // primer elemento
 der = n-1; // ultimo elemento
 while( izq<=der ) { 
 pos = izq + (der - izq) * ( t - x[izq] ) / ( x[der] - x[izq] ); 
 if ( t<x[pos] ) der = pos-1;
 else izq = pos+1;	 
 if ( t==x[pos] ) return pos;
 } 
 return -1;
}
Código
int BInterpolacion(int n, int x[ ], int t) { 
 int pos, izq, der; 
 izq = 0; // primer elemento
 der = n-1; // ultimo elemento
 while( izq<=der ) { 
 pos = izq + (der - izq) * ( t - x[izq] ) / ( x[der] - x[izq] ); 
 if ( t<x[pos] ) der = pos-1;
 else izq = pos+1;	 
 if ( t==x[pos] ) return pos;
 } 
 return -1;
}
Código
Realice la implementación DyV (recursiva) de la búsqueda por interpolacion
PROBLEMA DE LA BALANZA
Se tiene una balanza de 2 platos y n bolitas donde n-1 bolitas tienen el mismo peso y una un peso mayor, se pide usando la menor cantidad de pesadas encontrar la posición inicial de la bolita de mayor peso. 
4
5
6
7
1
2
3
0
Bolita de mayor peso
4
5
6
7
1
2
3
0
PROBLEMA DE LA BALANZA: Ejemplo
4
5
6
7
1
2
3
0
PROBLEMA DE LA BALANZA: Ejemplo
4
5
6
7
2
3
1
0
PROBLEMA DE LA BALANZA: Ejemplo
1
0
4
5
6
7
2
3
PROBLEMA DE LA BALANZA: Ejemplo
Solución:
#include <iostream.h>
#include <stdlib.h>
#include <conio.h>
#include <iomanip.h>
int suma(int, int, int[ ]);
void impPlato(int, int, int [ ]);
int main (){ 
 int x[ ] = { 1, 1, 1, 1, 1, 1, 2, 1, 1};
 int n, a, b, mitad, sIzq, sDer, vez; 
 n = sizeof(x) / sizeof(int);
 vez=0; a= 0; b= n-1;
 cout<<"Tengo "<< n <<" Bolitas"<<endl;
 while(a<b) {
 vez++;
 cout << endl << "------Pesada " << vez << "------" << endl;
 if ( (b-a+1)% 2 != 0 ) {
	 	cout << "Fuera de la balanza \t " << "x [ " << b << "]= " << x[b]<<endl;
 b = b - 1;
 }
 mitad = (a+b) / 2;
 impPlato ( a, mitad, x );
 sIzq = suma ( a, mitad, x );
 cout << " \t Peso Plato Izq = " << sIzq << endl;
 impPlato ( mitad+1, b, x );
 sDer = suma ( mitad+1, b, x );
 cout<<" \t Peso Plato Der = " << sDer << endl;
 if ( sIzq > sDer ) b=mitad;
 else if ( sIzq < sDer ) a = mitad+1;
 else a = b+1; // lo encontré fuera de la balanza
 getch( );
 } // fin while
 cout<<endl<<"\t\t\tlo encontre en subindice:" << a << endl; 
 getch();
} // fin main( )
int suma(int ini,int fin, int x[]) {
 int s=0;
 for ( int i=ini; i<=fin; i++ )
 s = s + x[i];
 return s;
}
void impPlato(int ini, int fin, int x[]) {
 int i;
 cout<<endl;
 for ( i=ini; i<=fin; i++ )
 cout << setw(3) << "x[" << i << "]";
 cout<<endl;
 for ( i=ini; i<=fin; i++)
 cout << setw(5) << x[i];
}
BackTracking
¡Gracias por su atención!