Java Búsqueda de elementos pares en un vector o array con Divide y Vencerás DyV

[++c]

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

[Ogramar]

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]

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;
}