Hola quisiera que me ayudaran con la siguiente asignacion: Dada una matriz NxN(n es par) de nros enteros, desarrollar un programa para determinar la submatriz cuyas suma de valores sea la mayor. Utilice la estrategia divide y venceras. La salida se debe mostrar por pantalla con la matriz original, la submatriz correspondiente y y el maximo valor de la suma de sus elementos. Si existiese mas de una solucion, estas deben mostrarse. Les agradeceria mucho que me ayudaran
Bueno tengo un code basado en esa estrategia, es el metodo de ordenamiento mas avanzado, el quicksort... Aqui esta, en C, pero puedes tomar la idea e implementarla en Java...
Ordenamiento de arreglos por el método rápido (quicksort)
PROG0021 - C/C++ (Codigo)
El método rápido o quicksort, es el algoritmo para ordenamiento de arreglos más rápido que existe. Además, es matemáticamente demostrable, que no puede existir un método mejor. Se basa en el principio "divide y vencerás". Su implementación sin embargo, reviste complejidad, ya que se trata de un algoritmo recursivo por naturaleza.
El método rápido o quicksort, es el algoritmo para ordenamiento de arreglos más rápido que existe. Además, es matemáticamente demostrable, que no puede existir un método mejor. Se basa en el principio "divide y vencerás". Su implementación sin embargo, reviste complejidad, ya que se trata de un algoritmo recursivo por naturaleza.
void SortArray (int array[],int first,int last)
{
int i,j,p,t;
// i se hace igual al índice del primer elemento
i= first;
// y j igual al índice del último elemento
j= last;
// p se hace igual al elemento pivote del arreglo
p= array[(first+last)/2];
do {
// se hace la partición del arreglo
while (array[i]<p) i++;
while (p<array[j]) j--;
if (i<=j)
{
// se intercambian los elementos i-esimo y j-esimo del arreglo
t= array[i];
array[i]= array[j];
array[j]= t;
i++;
j--;
}
} while (i<=j);
if (first<j) SortArray(array,first,j);
if (i<last) SortArray(array,i,last);
}
Saludos y espero te sirva para lo que necesitas...
Autor
En línea
