Posted By

josepino on 05/26/11


Tagged

and Vector divide moda conquer


Versions (?)

Encontrar la moda en un array - Find the element that is repeated


 / Published in: Java
 

  1. import java.util.Random;
  2.  
  3. //////////////////////////////////////////////////////////////////////////////////////////////////////////
  4. /*
  5.  * TECNICA DE DISEÑOS DE ALGORITMOS
  6.  * Author: JOSE PINO - SANTIAGO TORTORA
  7.  *
  8.  *
  9.  * Aplicando la técnica DyV encontrar la moda en un vector de N elementos. La moda es el valor que
  10.  * más repite. Luego indicar la fórmula de recurrencia de la solución hallando su costo asintótico.
  11.  
  12.  *
  13.  */
  14. //////////////////////////////////////////////////////////////////////////////////////////////////////////
  15.  
  16.  
  17.  
  18.  
  19. /**
  20.  * Encontrar la moda en un vector de N elementos
  21.  *
  22.  * Para hallar la moda se utiliza la tecnica Divide y Venceras, en donde basicamente
  23.  * se calcula la frecuencia con la que aparece cada uno de los elementos del vector y se escoge
  24.  * aquel que se repite mas veces
  25.  *
  26.  *
  27.  * Esta implementacion considera un vector de arreglos cargados aleatoriamente.
  28.  *
  29.  * Existen otras versiones en donde el vector puede estar ordenado (eficientemente) lo que hace
  30.  * que se pueda calcular la moda recorriendo el vector solamente una vez. En dicho caso la complejidad
  31.  * estaria en O(n) pero como es necesario ordenar el vector antes, la complejidad seria O(nlogn).
  32.  *
  33.  * Una solucion mas compleja pero eficiente asegurando una complejidad mejor que O(nlogn) y aplicando
  34.  * la misma tecnica de Divide y Venceras se encuenta
  35.  * en Gaston H. Gonnet y R. Baeza-Yates "Handbook of Algorithms and Data Structures".
  36.  *
  37.  * La ecuación de recurrencia es la siguiente:
  38.  * |
  39.  * T(n) <= | O (1) si n =1 //if (prim == ult) return a[prim];
  40.  * | T(n/2) + O(n)
  41.  * |
  42.  *
  43.  * La complejidad de la funcion Frecuencia es O(n), entonces la complejidad para calcular la moda
  44.  * esta en orden de O(n^2)
  45.  */
  46. public class Tarea8 {
  47.  
  48. public static void main (String [] args) {
  49.  
  50. System.out.println ("BUSQUEDA DE LA MODA EN UN VECTOR DE N ELEMENTOS\n");
  51. System.out.println ("TECNICA DE DIVIDE Y VENCERAS\n");
  52. System.out.println ("================================================================\n");
  53.  
  54. int N = 50; //Define el tamnho del vector
  55.  
  56. int [] elVector = new int [N]; //elVector es un arreglo de N elementos de tipo enteros
  57.  
  58. cargarVector(elVector); //Cargamos el vector con valores aleatorios
  59. imprimirVector(elVector); //Imprimimos los valores del vector
  60.  
  61.  
  62. /*Llamamos al metodo hallarModa e imprimimos el valor devuelto*/
  63. System.out.println ("\n\nEL VALOR QUE MAS SE REPITE ES: " + hallarModa (elVector, 0 , elVector.length-1));
  64.  
  65.  
  66. }
  67.  
  68.  
  69.  
  70.  
  71.  
  72.  
  73.  
  74.  
  75. /**
  76. * Metodo para hallar la moda en un vector de enteros
  77. * Utilizando la tecnica Divide y Venceras
  78. * @param a
  79. * @param prim
  80. * @param ult
  81. * @return
  82. */
  83. public static int hallarModa (int a[], int prim, int ult) {
  84. int i, frec, maxfrec, moda;
  85. if (prim == ult) return a[prim];
  86. moda = a[prim];
  87. maxfrec = Frecuencia(a, a[prim], prim, ult);
  88. for (i = prim + 1; i<=ult; i++) {
  89. frec = Frecuencia (a, a[i], i, ult);
  90. if (frec > maxfrec) {
  91. maxfrec = frec;
  92. moda = a[i];
  93. }
  94. }
  95.  
  96. return moda;
  97.  
  98.  
  99. }
  100.  
  101.  
  102.  
  103.  
  104.  
  105. /**
  106. * Metodo para calcular el numero de veces que se repite un elemento
  107. * Utilizado por el metodo hallarModa
  108. * @param a
  109. * @param p
  110. * @param prim
  111. * @param ult
  112. * @return
  113. */
  114. public static int Frecuencia (int a[], int p, int prim, int ult) {
  115. int i, suma;
  116. if (prim > ult) return 0;
  117. suma = 0;
  118. for (i = prim; i<= ult; i++)
  119. if(a[i] == p)
  120. suma++;
  121.  
  122. return suma;
  123.  
  124. }
  125.  
  126.  
  127.  
  128.  
  129. /**
  130. * Metodo para cargar el vector con valores int aleatorios
  131. * @param a
  132. */
  133. public static void cargarVector (int a[]) {
  134. Random r = new Random(); //Variable para el numero generado aleatoriamente
  135. for (int i = 0; i< a.length; i++){ //Cargamos el vector con valores aleatorios
  136. a [i] = (r.nextInt(100)); //Genera y carga valores aleatorios en elVector
  137. }
  138. }
  139.  
  140.  
  141.  
  142.  
  143. /**
  144. * Metodo para imprimir el vector
  145. * @param a
  146. */
  147. public static void imprimirVector (int a[]) {
  148. System.out.println("\nEl vector es:");
  149. for (int i = 0; i < a.length; i++) {
  150. System.out.printf( "%d " , (a[i]) );
  151. }
  152. }
  153.  
  154.  
  155.  
  156.  
  157. }

Report this snippet  

You need to login to post a comment.