jeffery.info

This is an question from the midterm exam of my Data Structures and Algorithms. A 10 marks question but I only got 5 with an incompleted answer.

——

“An evil king has n bottles of expensive wines, and his guards have just caught a spy tring to poison the king’s wine. Fortunately, the guards caught the spy after he succeeded in poisoning only one bottle. Unfortunately, they don’t know which one. The poison works slowly, it takes a full month for the person to die.”

Design an algorithm that allows the evil king to determine exactly which one of his wine bottles was poisoned in just one month’s time while expending at most O(log n) of his taste testers. Present your algorithm as a pseudo-code. If you want, you may further explain your algorithm by writing and English description or diagrams.

——

Few months after the exam, I got a better solution in dream. Interested person, think about it and I will share with you later.

• I teach you in a maths way
• Is formal education important?
• Can I be your friend? Can you be my friend?
• 無事不打三寶電