¿Cuál es la solución a este problema?

Suponga que su N es una potencia de 3.
Divide tu pila de monedas en 3 partes iguales.
1) Ahora péselos en la balanza de dos en dos.
2) La pila que es más ligera en 2 de las 3 comparaciones es la pila que tiene la moneda falsa. Deseche los otros dos, considere el peso más ligero.
3) Si la pila tiene más de 1 moneda, Goto 1 más felicitaciones.

Aquí, aunque tiene más número de comparaciones (que búsqueda binaria) en el paso 2, está descartando 2/3 de la pila en cada ronda. Por lo tanto, el tiempo de ejecución es: log (base 3) N

Divida las monedas en tres pilas de n / 3 cada una (redondee hacia abajo para las dos primeras pilas si n no es un múltiplo de 3). Pese las dos primeras pilas una contra la otra. Si no se equilibran, el grupo más ligero contiene el falso. Si lo hacen, está en la pila restante.

Una vez que identifique cuál de los 3 grupos que contienen la moneda falsa, repita el procesamiento dividiéndolo en 3 pilas nuevamente, y así. De esta manera, siempre aislarás la moneda a un grupo 1/3 del tamaño de la moneda anterior hasta alcanzar una sola moneda. Por lo tanto, se necesitan aproximadamente ponderaciones log-3 (n) para reducirlo.

Si no estuviera seguro de que la moneda falsa es más liviana en lugar de más pesada que el resto, este método no funcionaría.

Esfuérzate y haz lo que puedas para aprobar el examen. Si no funciona, regístrese para la repetición en 2 meses.

Entrena con un amigo. Apuesta a aprobar el examen, quizás solo necesites algún incentivo.

¿Cuál es la pregunta?