Too*_*ool 0 algorithm tree huffman-code
"设计一种策略,最大限度地减少在下面的游戏[Gar94],#52中提出的预期问题数量.你有一副牌,其中包括一个黑桃王牌,两个黑桃牌,三个三分球,以及最多九个牌9,总共制作45张牌.有人从洗牌甲板上取出一张牌,你必须通过询问是否回答问题来识别.
这是算法的设计和分析练习.
我想到的是两种解决方法:
它是9吗？不:是8岁吗？不:这是7吗？... 等等.
卡> 5？不是:卡> 2？... 等等.
哪种方法正确？
欢迎任何帮助.
编辑:我应该使用贪婪的方法.
这些都不是最好的方法.您可以进一步概括您要求的问题,例如:"所选卡片是1,4,7还是8？".
要确定要问哪个问题,您需要构建一个包含数字的霍夫曼树.然后你会问:"所选卡片是否是左子树中的数字之一？" 如果是,请向下移动到左子树并重复.否则,移到右侧子树并重复.