Revision: 46839
Initial Code
Initial URL
Initial Description
Initial Title
Initial Tags
Initial Language
at May 26, 2011 14:14 by josepino
Initial Code
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]) ); } } }
Initial URL
Initial Description
Initial Title
Encontrar la moda en un array - Find the element that is repeated
Initial Tags
Initial Language
Java