domingo, 28 de noviembre de 2010

Elemento mayoritario (divide y vencerás)

Ya hemos hablado antes del problema del elemento mayoritario de un vector. Primero presentamos la descripción del problema y una solución lineal que no funcionaba muy bien xD Ver:

http://alguienenlafisi.blogspot.com/2010/10/elemento-mayoritario-solucion-lineal.html

Luego se presentó una solución correcta de orden lineal que funciona para todos los casos:

http://alguienenlafisi.blogspot.com/2010/11/elemento-mayoritario-solucion-lineal.html

La solución que presentare ahora usa la técnica "Divide y Vencerás" para escoger el candidato a elemento mayoritario y luego realiza un verificación lineal. La técnica Divide y Vencerás (DYV) consiste en resolver un problema a partir de las soluciones parciales de problemas más pequeños derivados del original. Esta técnica se implementa usualmente con algoritmos recursivos que van partiendo un problema en subproblemas cada vez hasta llegar a un caso frontera donde la solución es trivial. En general, los algoritmos DYV suelen ser más eficientes.

El algoritmo de búsqueda del candidato se basa en la observación de que si un vector tiene un elemento mayoritario entonces ese elemento también será mayoritario de alguna de las mitades del vector. Por ello podemos partir en vector en dos mitades y buscar el elemento mayoritario en ambas de forma recursiva. El caso frontera se da cuando una mitad contiene un único elemento, entonces ese elemento es mayoritario.

La complejidad de este algoritmo es de orden lineal.

#include <stdio.h>
#include <stdlib.h>

int buscar(int *v, int i, int f, int *may) {
 if(f-i == 0) {
  *may = v[i];
  return 1;
 }
 int m = (i+f)/2, m1, m2, c1, c2;
 c1 = buscar(v, i, m, &m1);
 c2 = buscar(v, m+1, f, &m2);
 if(m1 == m2) {
  *may = m1;
  return c1 + c2;
 } else {
  if(c1 > c2) {
   *may = m1;
   return c1-c2;
  } else {
   *may = m2;
   return c2-c1;
  }
 }
}

bool verificar(int *v, int n, int may) {
 int c=0;
 for(int i=0; i<n; i++) {
  if(v[i] == may) {
   c++;
  }
 }
 return (c > n/2);
}

int main() {
 int *v, n;
 scanf("%d", &n);
 v = new int [n];
 for(int i=0; i<n; i++) {
  scanf("%d", &v[i]);
 } 
 int may, c;
 if(buscar(v, 0, n-1, &may) > 0) {
  if(verificar(v, n, may)) {
   printf("El elemento mayoritario es %d", may);
  } else {
   printf("No existe un elemento mayoritario");
  }
 } else {
  printf("No existe un elemento mayoritario");
 } 
 return 0;
}

Saludos.

2 comentarios:

  1. Inicialmente cuanto vale m1 y m2?

    ResponderEliminar
  2. m1 y m2 son variables de retorno (por eso se pasan como puntero) la idea es recibir en m1 el elemento mayoritario de la primera mitad y en m2 el de la segunda mitad.

    ResponderEliminar