Examen y respuestas Febrero 2017 Divide y Vencerás Problema 3 PDF

Preview

Summary

Examen y respuestas Febrero 2017 Divide y Vencerás Problema 3...

Description

Examen Febrero

ADDA/EDA

Curso 2016/2017

Ejercicio 3: DyV Se tienen n monedas de igual tamaño, todas ellas de igual peso salvo una menos pesada. Considere que dispone de una lista que almacena los objetos de tipo Moneda: List listaMonedas Se dispone de una balanza con dos platillos para comparar el peso de dos conjuntos de monedas. En cada pesada lo único que puede observar es si la balanza queda equilibrada, si pesan más los objetos del platillo de la derecha o si pesan más los de la izquierda. El siguiente método, de complejidad constante, permite hacer una pesada de las monedas: int pesada (List listaMonedas, int i_izq, int j_izq, int i_der, int j_der) 

Se colocan en el plato izquierdo las monedas de la listaMonedas del intervalo [i_izq, j_izq), y en el plato derecho las monedas del intervalo [i_der, j_der)



Devuelve un número positivo si las monedas del plato izquierdo pesan más que las del plato derecho, un cero si pesan igual ambos platos, y un número negativo si las monedas del plato derecho pesan más que las del plato izquierdo.

Diseñar una función basada en la técnica recursiva de Divide y Vencerás que permita determinar en qué posición de listaMonedas está la moneda menos pesada, con el mínimo número de pesadas posible (orden logarítmico). Dicha función debe devolver la posición de la lista original de monedas donde está la moneda menos pesada. int problemaMonedas(List listaMonedas) Ejemplo: Para la lista de monedas siguiente, la solución sería 2. Moneda 7

Moneda

Moneda

Moneda

Moneda

Moneda

Moneda

7

5

7

7

7

7

Se pide: 1. Rellene la ficha propuesta (partes marcadas como //TODO). 2. Implemente la función int problemaMonedas (List listaMonedas) en lenguaje Java. Puede añadir los parámetros que necesite o bien crear una función auxiliar recursiva con dichos parámetros. IMPORTANTE: Se prohíbe usar en la solución cualquier estructura de datos auxiliar.

Examen Febrero

ADDA/EDA

Curso 2016/2017

Ficha Examen Monedas Técnica: Divide y Vencerás sin Memoria Propiedades Compartidas:

listaMonedas: List

Propiedades Individuales:

// TODO i, int j, int

Solución: Posición de listaMonedas que almacena la moneda menos pesada Inicialización

problemaMonedas(listaMonedas) = problemaAux(0, listaMonedas.size())

TODO Generalización:

// TODO 𝑝𝑟𝑜𝑏𝑙𝑒𝑚𝑎𝐴𝑢𝑥(𝑖, 𝑗) =

𝑖 𝑗−𝑖 =1 𝑘 𝑝𝑒𝑠 = 0 𝑝𝑟𝑜𝑏𝑙𝑒𝑚𝑎𝐴𝑢𝑥(𝑖, 𝑘 ) 𝑝𝑒𝑠 < 0 𝑝𝑟𝑜𝑏𝑙𝑒𝑚𝑎𝐴𝑢𝑥(𝑘 + (𝑗 − 𝑖)%2, 𝑗) 𝑝𝑒𝑠 > 0

{ k = (i+j)/2 pes = pesada(listaMonedas, i, k, k + (j-i)%2, j) (j-i)%2 devuelve 1 si el intervalo [i,j) tiene un número impar de monedas y 0 si es par Total: 4,5 puntos por la ficha y 5,5 puntos por el código. int problemaAux(int i, int j){ int ret, pes; if (j - i == 1){ ret = i; }else{ int k = (i+j) / 2; if ((j-i)%2 == 0){ pes = pesada(listaMonedas, i, k, k, j); }else{ pes = pesada(listaMonedas, i, k, k + 1, j); } if (pes < 0){ ret = problemaAux(i, k); }else if(pes > 0){ if ((j-i)%2 == 0){ ret = problemaAux(k, j); }else{ ret = problemaAux(k + 1, j); } }else{ ret = k; } } return ret; }...