import java.util.Random;
 
//////////////////////////////////////////////////////////////////////////////////////////////////////////
/*
 * TECNICA DE DISEÑOS DE ALGORITMOS
 * Author: JOSE PINO - SANTIAGO TORTORA
 * 
 * 
 * Aplicando la técnica DyV encontrar la moda en un vector de N elementos. La moda es el valor que  
 * más repite. Luego indicar la fórmula de recurrencia de la solución hallando su costo asintótico. 
 
 * 
 */
//////////////////////////////////////////////////////////////////////////////////////////////////////////
 
 
 
 
/**
 * Encontrar la moda en un vector de N elementos
 * 
 * Para hallar la moda se utiliza la tecnica Divide y Venceras, en donde basicamente
 * se calcula la frecuencia con la que aparece cada uno de los elementos del vector y se escoge
 * aquel que se repite mas veces
 * 
 * 
 * Esta implementacion considera un vector de arreglos cargados aleatoriamente.
 * 
 * Existen otras versiones en donde el vector puede estar ordenado (eficientemente) lo que hace
 * que se pueda calcular la moda recorriendo el vector solamente una vez. En dicho caso la complejidad
 * estaria en O(n) pero como es necesario ordenar el vector antes, la complejidad seria O(nlogn).
 * 
 * Una solucion mas compleja pero eficiente asegurando una complejidad mejor que O(nlogn) y aplicando 
 * la misma tecnica de Divide y Venceras se encuenta
 * en Gaston H. Gonnet y R. Baeza-Yates "Handbook of Algorithms and Data Structures". 
 * 
 * La ecuación de recurrencia es la siguiente:
 *  		 |
 *  T(n) <=  | O (1) si n =1   				//if (prim == ult) return a[prim];
 * 			 | T(n/2) + O(n)
 * 			 |
 * 
 * La complejidad de la funcion Frecuencia es O(n), entonces la complejidad para calcular la moda
 * esta en orden de O(n^2)
 */
public class Tarea8 {
 
	public static void main (String [] args) {
 
		System.out.println ("BUSQUEDA DE LA MODA EN UN VECTOR DE N ELEMENTOS\n");
		System.out.println ("TECNICA DE DIVIDE Y VENCERAS\n");
		System.out.println ("================================================================\n");	
 
		int N = 50;										//Define el tamnho del vector
 
		int [] elVector = new int [N]; 					//elVector es un arreglo de N elementos de tipo enteros
 
		cargarVector(elVector);							//Cargamos el vector con valores aleatorios
		imprimirVector(elVector);						//Imprimimos los valores del vector
 
 
		/*Llamamos al metodo hallarModa e imprimimos el valor devuelto*/
		System.out.println ("\n\nEL VALOR QUE MAS SE REPITE ES: " + hallarModa (elVector, 0 , elVector.length-1));
 
 
	}
 
 
 
 
 
 
 
 
	/**
	 * Metodo para hallar la moda en un vector de enteros
	 * Utilizando la tecnica Divide y Venceras
	 * @param a
	 * @param prim
	 * @param ult
	 * @return
	 */
	public static int hallarModa (int a[], int prim, int ult) {
		int i, frec, maxfrec, moda;
		if (prim == ult) return a[prim];
		moda = a[prim];
		maxfrec = Frecuencia(a, a[prim], prim, ult);
		for (i = prim + 1; i<=ult; i++) {
			frec = Frecuencia (a, a[i], i, ult);
			if (frec > maxfrec) {
				maxfrec = frec;
				moda = a[i];
			}
		}
 
		return moda;
 
 
	}
 
 
 
 
 
	/**
	 * Metodo para calcular el numero de veces que se repite un elemento
	 * Utilizado por el metodo hallarModa
	 * @param a
	 * @param p
	 * @param prim
	 * @param ult
	 * @return
	 */
	public static int Frecuencia (int a[], int p, int prim, int ult) {
		int i, suma;
		if (prim > ult) return 0;
		suma = 0;
		for (i = prim; i<= ult; i++)
			if(a[i] == p)
				suma++;
 
		return suma;
 
	}
 
 
 
 
	/**
	 * Metodo para cargar el vector con valores int aleatorios
	 * @param a
	 */
	public static void cargarVector (int a[]) {
		Random r = new Random();						//Variable para el numero generado aleatoriamente
		for (int i = 0; i< a.length; i++){		//Cargamos el vector con valores aleatorios
			a [i] = (r.nextInt(100));   		//Genera y carga valores aleatorios en elVector
		}
	}
 
 
 
 
	/**
	 * Metodo para imprimir el vector
	 * @param a
	 */
	public static void imprimirVector (int a[]) {
		System.out.println("\nEl vector es:");
		for (int i = 0; i < a.length; i++) {
			System.out.printf( "%d " , (a[i]) );
		}
	}
 
 
 
 
}