Tag: 猜数字

如果你不了解猜数字，可以来这里玩玩。简单归纳一下就是，4个位置，放0-9，互不相同。你可以一次次地猜测是哪四个数字，直到猜对为止。每次猜测，都会得到一个结果，形如XAXB，比如0A1B。A代表你的猜测中有一个数字的位置跟答案中相同，B代表有一个数字答案中有，但你猜得位置不对。 最早玩这个是在文曲星上，当时觉得这个游戏简直难得一逼，跟文曲星上别的游戏简直不是一个数量级（更重要的原因是错误提示画面非常之恐怖）。但最近觉得这个游戏没有道理这么难，遂决定琢磨一下算法。 首先从信息论的角度分析一下，题目相当于说从P(10,4)个可能性中找出那唯一的一个，也就是说，必须拿到log(P(10,4))这么多信息量。这是多少呢？我们算一下大概就是12.3bit（原来只有这么点。。。），也就是说，如果每次砍掉一半，那么砍13次就能找到这个组合了。据说正常人平均7次能猜出一道猜数字的答案，文曲星上的期限是10次以内(反正我是经常猜不出来……)，我们就按10次来算，这意味着每次XAXB的结果能给我们带来1bit以上，2bit未满的信息。 4A0B的可能性是多少？1/P(10,4) = 1/10*9*8*7。3A0B呢？4个空可以换，每个空还有10-4=6个选择，也就是24/P(10,4)  ——是的，请注意不存在3A1B……。2A时b的情况就多了，我刚才在这里列了几个式子，发现很不简洁，于是作罢。0A0B呢？P(6,4)/P(10,4)=6*5*4*3/10*9*8*7，是4A的360倍，多得一塌糊涂。容易发现，由于位置数比可能性的总数要小得多，想得到一个A或者B更高的结果，概率是相当低的。换句话说得到结果越准确，得到的信息量就越大。 OK。那么我们初始化时构造一个可能性集合，每次给出一个尽量准确的结果，然后在每次猜测后根据得到的结果，将不匹配的可能性剔除，如此进行直至得出结果。这个“尽量准确”难倒了我，于是我的第一个实现就只是给出集合中的第一个解，近似于随机给出——STL的set是用红黑树实现的。 没想到的是，这样实现的结果已经足够好……随机生成10000个谜题，平均解题所需要尝试的次数在5.4841。这也就意味着，平均每次猜测可以提供超过2bit的信息量。要知道A的取值不过是0 1 2 3 4而B更仅仅是从0到4-A而已，这两个数字就是完全随机也不过能提供4bit不到的信息量。这个效率好得实在超出想象(求哪位给一个数学上清晰的解释)。 那么我对“尽量准确”能带来的改善就不抱太大希望了。我用的方法是统计每次现存的可能性集合中每个位置上每个数字的出现概率（其实用出现次数即可，反正都是成正比的），对于每一个可能性，四个位置上的数字概率之积最大的，就是“尽量准确”的。测试的结果，平均改善0.05次尝试。 我改测试5个位置填0-9，也是差不多0.05次的改善。 位置数继续增长时，第一次构造集合的尺寸就指数增长，可能性数增长时，就幂函数增长，都不是善茬。试了几次太慢，我也就懒得测试了…… 代码共享在： https://github.com/duduzhu/Guess 老实说，这还真是挺丢脸一个作品，我觉得也就是个数据结构小作业的水平，连大作业都算不上。 不过，真上数据结构的时候，我在用网页实现猜数字……不是策略……而是猜数字本身……弱智到要命。而且因为对网页UI畅想太好，到底没弄好。 丢人。