Autor Tema: Java Búsqueda de elementos pares en un vector o array con Divide y Vencerás DyV  (Leído 3606 veces)

++c

  • Sin experiencia
  • *
  • APR2.COM
  • Mensajes: 1
    • Ver Perfil
Hola amigos,

estoy ensayando con la técnica divide y vencerás. Concretamente quiero realizar la búsqueda de dígitos pares en un vector con la técnica que comentaba antes.

No se si voy bien encaminado... Me gustaría una mano para terminar de entenderlo e interpretar la idea que busco. Coloco el codigo:

Código: [Seleccionar]
public static int cuentaPares(int a[], int primero, int ultimo){
        int vectorIzq;
        int vectorDer;
        if(primero>ultimo)
            return primero;
        int mitad = (primero+ultimo)/2;
        vectorIzq=cuentaPares(a, primero, mitad-1);
        vectorDer=cuentaPares(a, mitad+1, ultimo);
        if(vectorIzq%2==0)
            contador++;
        if(vectorDer%2==0)
            contador++;
        return contador;
    }
   
    public static void main(String[] args) {
       
         int v[]={1,3,5,6,7,8};
         int numero=cuentaPares(v, 0, v.length-1);
         if(numero!=0)
            System.out.println("Existen "+numero+ " número/s pares en el vector");
         else
             System.out.println("No existen números pares en el vector");
    }   
}

Saludos y muchas gracias
« Última modificación: 12 de Julio 2015, 13:15 por Ogramar »

Ogramar

  • Moderador Global
  • Experto
  • *******
  • Mensajes: 2628
    • Ver Perfil
Re:Búsqueda de elementos pares en un vector con DyV
« Respuesta #1 en: 12 de Julio 2015, 13:13 »
Hola, divide y vencerás es un término amplio pero en este caso nos referiríamos a la estrategia algorítmica basada en subdividir un problema en partes más pequeñas que se resuelven recursivamente hasta llegar a un caso base y obtener la solución directamente o combinando las diferentes soluciones parciales obtenidas.

Además de la lógica estos problemas tienen la complicación de la recursión, que suele ser difícil de aplicar y de plantear adecuadamente.

La lógica general es esta:

funcion DivideyVenceras (problema)

   si caso_base (problema)
      devolver solucion_simple
   sino
      descomponer el problema en n problemas
      para cada problema pi
         solucion si <- DivideyVenceras(pi)
      fpara
   fsi
   combinar si procede en la solución final (s1, s2..., sn)

finFuncion


Divide y vencerás se puede aplicar a casi cualquier problema, pero no siempre será un método interesante de aplicar ya que en algunos casos puede ser poco eficiente.

En el código que tú has puesto no acabo de entender cuál es la lógica que aplicas. Veo que vas subdiviendo el array pero no veo qué sentido tiene esta instrucción:

if(primero>ultimo)
            return primero;

¿Cuál es la intención de esta instrucción? ¿Cual sería su utilidad?

Salu2

Ogramar

  • Moderador Global
  • Experto
  • *******
  • Mensajes: 2628
    • Ver Perfil
Aquí hay un modelo de lógica que se puede emplear, aunque no utiliza divide y vencerás:


Algorithm: segregateEvenOdd()
1) Initialize two index variables left and right: 
left = 0,  right = size -1
2) Keep incrementing left index until we see an odd number.
3) Keep decrementing right index until we see an even number.
4) If left < right then swap arr[ left ] and arr[ right ]


Código en C:

Código: [Seleccionar]
#include<stdio.h>
 
/* Function to swap *a and *b */
void swap(int *a, int *b);
 
void segregateEvenOdd(int arr[], int size)
{
  /* Initialize left and right indexes */
  int left = 0, right = size-1;
  while(left < right)
  {
     /* Increment left index while we see 0 at left */
     while(arr[left]%2 == 0 && left < right)
        left++;
 
     /* Decrement right index while we see 1 at right */
     while(arr[right]%2 == 1 && left < right)
        right--;
 
     if(left < right)
     {
       /* Swap arr[left] and arr[right]*/
       swap(&arr[left], &arr[right]);
       left++;
       right--;
     }
  }
}   
 
/* UTILITY FUNCTIONS */
void swap(int *a, int *b)
{
  int temp = *a;
  *a = *b;
  *b = temp;
}     
 
/* driver program to test */
int main()
{
  int arr[] = {12, 34, 45, 9, 8, 90, 3};
  int arr_size = 7, i = 0;
 
  segregateEvenOdd(arr, arr_size);
 
  printf("array after segregation ");
  for(i = 0; i < arr_size; i++)
    printf("%d ", arr[i]);
 
  getchar();
  return 0;
}

 

Sobre la educación, sólo puedo decir que es el tema más importante en el que nosotros, como pueblo, debemos involucrarnos.

Abraham Lincoln (1808-1865) Presidente estadounidense.

aprenderaprogramar.com: Desde 2006 comprometidos con la didáctica y divulgación de la programación

Preguntas y respuestas

¿Cómo establecer o cambiar la imagen asociada (avatar) de usuario?
  1. Inicia sesión con tu nombre de usuario y contraseña.
  2. Pulsa en perfil --> perfil del foro
  3. Elige la imagen personalizada que quieras usar. Puedes escogerla de una galería de imágenes o subirla desde tu ordenador.
  4. En la parte final de la página pulsa el botón "cambiar perfil".