2. Demuestre que se requiere pesar al menos dos veces para resolver el problema del ejercicio 1.
3. Ocho monedas son idénticas en apariencia, pero una está defectuosa y es más pesada o más ligera que las otras, que pesan lo mismo. Dibuje un árbol de decisiones para proporcionar un algoritmo que identifique, cuando mucho en tres pesadas, la moneda defectuosa; y determine si es más pesada o más ligera que las otras usando sólo una balanza.
4. Doce monedas son idénticas en apariencia, pero una está defectuosa y es más pesada o más ligera que las otras, que pesan lo mismo. Dibuje un árbol de decisiones para proporcionar un algoritmo que identifique, cuando mucho en tres pesadas, la moneda defectuosa; y determine si es más pesada o más ligera que las otras usando sólo una balanza.
5. Diga qué está mal en el siguiente argumento que pretende demostrar que el acertijo de 12 monedas requiere al menos cuatro pesadas en el peor caso si se comienza por pesar cuatro monedas contra cuatro. Si se pesan cuatro monedas contra cuatro y están balanceadas, debemos detectar la moneda defectuosa de las cuatro restantes. Pero el análisis en esta sección demostró que detectar una moneda defectuosa entre cuatro requiere pesar al menos tres veces en el peor caso. Por lo tanto, en el peor caso, si se comienza pesando cuatro monedas contra otras cuatro, el acertijo de 12 monedas requiere al menos cuatro pesadas.
6. Trece monedas son idénticas en apariencia, pero una está defectuosa y es más pesada o más ligera que las otras, que pesan lo mismo. ¿Cuántas veces se requiere pesar en el peor caso para encontrar la moneda defectuosa y determinar si es más o menos pesada que las otras usando sólo una balanza? Pruebe su respuesta.
7. Resuelva el ejercicio 6 para el acertijo de 14 monedas.
8. (3n − 3)/2, n ≥ 2 monedas son idénticas en apariencia, pero una está defectuosa y es más pesada o más ligera que las otras, que pesan lo mismo. [Kurosaka] proporcionó un algoritmo para encontrar la moneda defectuosa y determinar, en n pesadas en el peor caso, si es más o menos pesada que las otras usando sólo una balanza. Pruebe que no es posible encontrar la moneda e identificar como más pesada o más ligera en menos de n pesadas.
9. Dé un algoritmo que ordene cuatro artículos usando cinco comparaciones en el peor caso.
10. Utilice árboles de decisiones para encontrar una cota inferior para el número de comparaciones requeridas para ordenar cinco artículos en el peor caso. Dé un algoritmo que use este número de comparaciones para ordenar cinco artículos en el peor caso.
11. Utilice árboles de decisiones para encontrar una cota inferior para el número de comparaciones requeridas para ordenar seis artículos en el peor caso. Dé un algoritmo que emplee este número de comparaciones para ordenar seis artículos en el peor caso.
s1, ..., s2k
para ordenar en orden no decreciente. Se construirá un árbol binario con vértices terminales etiquetados s1, . . . , s2k. Un ejemplo es el siguiente
Trabajando de derecha a izquierda, se crea un padre para cada par y se etiqueta con el máximo número de hijos. Se continúa de esta manera hasta llegar a la raíz. En este punto, se ha encontrado el valor más grande, m. Para encontrar el segundo valor más grande, primero se escoge un valor v menor que todos los elementos de la sucesión. Se sustituye el vértice terminal w que contiene a m por v. Se etiquetan otra vez los vértices siguiendo la trayectoria de w a la raíz, como se indica. En este punto se ha encontrado el segundo valor más grande. Continúe hasta que la sucesión quede ordenada.
12. ¿Por qué es adecuado el nombre de “torneo”?
13. Dibuje los dos árboles que se crearían después del árbol adyacente cuando se aplica el orden de torneo.
14. ¿Cuántas comparaciones requiere el orden de torneo para encontrar el elemento más grande?
15. Demuestre que cualquier algoritmo que encuentra el valor más grande entre n elementos requiere al menos n−1 comparaciones.
16. ¿Cuántas comparaciones requiere el orden de torneo para encontrar el segundo elemento más grande?
17. Escriba el orden de torneo como un algoritmo formal.
18. Demuestre que si n es una potencia de 2, el orden de torneo requiere (n lg n) comparaciones.
19. Dé un ejemplo de una situación real (como la de la figura 9.7.1) que se pueda modelar como un árbol de decisiones. Dibuje el árbol de decisión.
20. Dibuje un árbol de decisiones que se pueda usar para determinar quién debe entregar una declaración federal de impuestos.
21. Dibuje un árbol de decisiones que dé una estrategia razonable para jugar blackjack (vea, por ejemplo [Ainslie]).
