miércoles, 3 de noviembre de 2010

Elemento mayoritario (solucion lineal)

¡Esta vez me encontraron el error a mi! xD En un post anterior se explico en que consistía el problema del elemento mayoritario y se propuso una solución para vectores de longitud par. Pues bien dicha solución no es correcta porque falla para determinados casos. Ver:

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

No hace mucho un amigo de la facultad me hizo notar el error pasándome algunos casos en donde mi algoritmo no pudo determinar el elemento mayoritario a pesar que este existía. Pero además de ello me envío otro algoritmo que resuelve el problema en tiempo lineal. Veamos:

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

bool buscar(int *v, int n, int *may);

int main() {
 int *v, n;
 printf("n = ");
 scanf("%d", &n);
 v = new int[n];
 for(int i=0; i<n; i++) {
  printf("v[%d] = ", i);
  scanf("%d", &v[i]);
 }
 
 int may = 0;
 if(buscar(v, n, &may)) {
  printf("mayoritario = %d\n", may);
 } else {
  printf("no existe un elemento mayoritario\n");
 }
 return 0;
}

bool buscar(int *v, int n, int *may) {
 int rep = 1;
 *may = v[0];
 for(int i=1; i<n; i++) {
  if(v[i] == *may) {
   rep++;
  } else {
   rep--;
   if(rep == -1) {
    rep = 1;
    *may = v[i];
   }
  }
 }
 
 rep = 0;
 for(int i=0; i<n; i++) {
  if(*may == v[i]) {
   rep++;
  }
 }
 
 if(rep > n/2) {
  return true;
 }
 return false;
}


Gracias David, somos equipo para el concurso de programación eh! xD

Saludos.

1 comentario: