Scribd
Cargar
453 vistas3 páginas

Aplicación de Divide y Vencerás

Este documento contiene 3 problemas y sus posibles soluciones con complejidad O(nlogn). El primer problema involucra encontrar la suma máxima de celdas consecutivas en un array y una solución directa es O(m+(n-m)) mientras que divide y conquista no es conveniente. El segundo problema empareja tornillos y tuercas mediante comparaciones y la solución itera en O(nlogn). El tercer problema determina si la suma de dos elementos de un vector es un número S y la solución recorre el vector dos veces en O(nlogn

Cargado por

Odetth Guerrero
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como DOCX, PDF, TXT o lee en línea desde Scribd
453 vistas3 páginas

Aplicación de Divide y Vencerás

Este documento contiene 3 problemas y sus posibles soluciones con complejidad O(nlogn). El primer problema involucra encontrar la suma máxima de celdas consecutivas en un array y una solución directa es O(m+(n-m)) mientras que divide y conquista no es conveniente. El segundo problema empareja tornillos y tuercas mediante comparaciones y la solución itera en O(nlogn). El tercer problema determina si la suma de dos elementos de un vector es un número S y la solución recorre el vector dos veces en O(nlogn

Cargado por

Odetth Guerrero
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como DOCX, PDF, TXT o lee en línea desde Scribd

NOMBRES

1 EDUARDO DE LA HOZ

2 EMIL BARRIOS

3 JAIRO BONETH

Divide y Vencerás

1. Considere la aplicación de la técnica divide y conquistar sobre el siguiente problema.


Dado un array de n números enteros, buscamos la cadena de m celdas consecutivas
en este array cuya suma sea máxima, puede haber números negativos (obviamente
m<n). ¿Cómo sería una resolución directa del problema?, su complejidad. ¿Es
conveniente aplicar divide y vencerás en este caso? Calcule su complejidad.

int sumaMax(int[] array, int p, int h) {


int SumaMayor = 0;
for (int i = 0; i < h; i++) {
SumaMayor += array[i];
}

int tope =h;


int sumanueva = SumaMayor;
int ultimo = 0;

while(tope < p) {
sumanueva -= array[ultimo];
sumanueva += array[tope];

if (sumanueva > SumaMayor) {


SumaMayor = sumanueva;
}

tope ++;
ultimo ++;
}

return SumaMayor;
}

// la complejidad algorítmica es de O(m+(n-m)), el utilizar divide y vencerás no es de


lógica conveniencia ya que tendría que resolver muchas más operaciones.
2. En una habitación oscura se tienen dos cajones en uno de los cuales hay n
tornillos de varios tamaños, y en el otro las correspondientes n tuercas. Es
necesario emparejar cada tornillo con su tuerca correspondiente, pero debido
a la oscuridad no se pueden comparar tornillos con tornillos ni tuercas con
tuercas, y la única comparación posible es la de intentar enroscar una tuerca
en un tornillo para comprobar si es demasiado grande, demasiado pequeña,
o se ajusta perfectamente al tornillo.

Desarrollar un algoritmo para emparejar los tornillos con las tuercas que use
O(nlogn) comparaciones en promedio.

void tornillosTuercas(int[] tornillos, int[] tuercas) {

for (int i = 0; i < [Link]; i++) {

boolean igual = false;


int j = 0;

while(!igual) {
igual = tornillos[i] == tuercas[j];

j++;
}
if (igual) {
[Link]("la tuerca del tornillo ha sido
encontrada#"+(i+1));
}
}
}

//el ciclo para representa el n y el ciclo while puede acabar antes de n,


dando una representacion de logn
3. Dado un vector C[1..n] de números enteros distintos, y un número entero S,
se pide: Diseñar un algoritmo de complejidad O(nlogn) que determine si
existen o no dos elementos de C tales que su suma sea exactamente S.

boolean IgualCS(int[] vector, int s) {


boolean existe = false;
int i = 0;

while(i < [Link]-1 && !existe) {

int j = i+1;
while (!existe && j < [Link]) {
existe = vector[i]+vector[j] == s;
j++;
}

i++;
}

return existe;
}

También podría gustarte