“设计一个策略，尽量减少在以下游戏 [Gar94]，#52 中提出的预期问题数量。你有一副牌，其中包括一张黑桃 A、两张黑桃 2、三个三，以及最多九个九，总共制作 45 张牌。有人从洗牌牌中抽出一张牌，你必须通过询问可以回答是或否的问题来识别它。
这是算法设计和分析的练习。
我想到的是两种解决方法：
是9吗？不：是 8 吗？不：是 7 吗？... 等等。
卡 > 5？否：卡 > 2？... 等等。
哪个是正确的方法？
欢迎任何帮助。
编辑：我应该使用贪婪的方法。
问问题
1010 次
1 回答
5
Neither of those is the best approach. You can generalize the questions you ask further, to be something like: "Is the chosen card one of 1, 4, 7, or 8?".
To decide which question to ask, you'd build a Huffman tree containing the numbers. Then you'd ask: "Is the chosen card one of the numbers in the left subtree?" If it is, move down to the left subtree and repeat. Otherwise, move to the right subtree and repeat.
于 2012-10-21T16:00:54.567 回答