|
La moneda falsa
Se tienen 3^n monedas de oro, es decir, el número de monedas es potencia de 3, con n>=1.
Ejemplo: 3, 9, 27, 51, ...
Una de ellas es una moneda falsa, la moneda falsa pesa menos que las otras.
Para descubrir cuál de ellas es falsa, se cuenta con una balanza.
La idea es pesar las monedas en la balanza para compararlas hasta descubrir cuál de ellas pesa menos y entonces esa será la moneda falsa.
El reto consiste en diseñar un algoritmo que nos permita determinar cuál es la moneda falsa comparando pesos y que minimíze el número de veces que utilizamos la balanza.
Se puede supononer que los platos de la balanza soportan infinitas monedas, no hay límite en este sentido, la idea es utilizar lo menos posible la balanza.
En resumen:
¿Cuántas veces tendrías que utilizar la balanza en tu algoritmo para localizar la moneda falsa si el total de monedas es 3^n?
Saludos
|
24-11-2005
Modo Hilado