前情提要： 关于猜数字解法的讨论（以中阶规则为例）
由于月亮对初阶的最优次数究竟是不是5次产生了疑问，我抽了周一早八的时间写了个初阶猜数字的算法，并且跑了一下。万万没想到，写代码半小时，跑代码……我从早八下课早上十点跑到了今天凌晨五点半 心疼电脑。甚至我连 Gal 测评都没更新。
有一些中阶帖子里提到的内容我可能会略过不讲，感兴趣的请看前情提要。
一·算法设计
这次的问题针对的是初阶规则，与中阶不同的是，初阶规则是有重复数字的，由于只有 0-5，即一共有 6^4=1296 种组合。我们只需要将 1296 种可能的数字看作一个解的集合，通过一次次地猜测来缩小这个解集，最后可以把解集锁定在一个，那么这个解就是答案的数字。
猜数字的结果一共有 (0,0),(0,1),(0,2),(0,3),(0,4),(1,0),(1,1),(1,2),(1,3),(2,0),(2,1),(2,2),(3,0),(4,0) 14 种可能，要判断猜哪个数可以将解集缩到最小，只需要遍历 1296 个可能。在这里和中阶帖子里出现了算法设计的分歧，在选择猜数的策略上，中阶我们选择的是解集大小的期望重视，也就是说最后会倾向于解决问题的期望步数最少，另外有一个相近的算法是步数期望型，即不是进行直接加权平均而是对解集大小取对数（即需要缩小的步数）再加权平均。这两种方法会倾向于多次猜数字下的平均步数更少。而月亮的疑惑是最坏情况下的最少步数，所以我们改变策略，选出十四种可能里最大的一种可能，也就对应最坏情况。之后在遍历的所有解集数字里找出最坏情况下解集最小的一个，也就是最坏情况下的最优猜数。在这种情况下，可能平均步数不是最少，但尽量保证了考虑最坏情况。
二·代码实现
上次是用 python 实现的，这次考虑到性能的差距于是写了下 c++。
首先和上次的区别是因为存在可重复数字，所以不能用上次的向量来取巧，采用了遍历映射到数组来计数，具体可以参考leetcode 299.猜数字游戏
然后需要一个函数得出最能缩小解空间的解，按照算法设计中的步骤进行三层循环即可，上次为了省事只在解集内取猜数结果爆了两次最优解以外的情况，这次不敢偷懒了（结果时间几何倍数增长 ）
需要一个函数帮助缩小解空间，只需要遍历解空间，将 xAxB 与结果不符的剔除即可，这个函数不变
最后只需要从“0000”循环检验到“5555”统计最终结果即可。
三·问题与优化
采用了和中阶相同的优化方法，先跑一遍找出全集中的最优第一次猜数“0011”（评估相同取靠前的数），将所有结果对应的最优缩小数以及所对应的缩小后的解空间打表，省去了第一次猜数计算的时间，大大降低了时间复杂度。
将猜数的范围限制在解空间内是一个潜在的隐患，是否存在影响仍需要严格的数学证明，可惜我懒这次没有这个隐患了，但是我的电脑有隐患了，跑了整整一天。
优化后的最终代码部分见附图
四·统计结果
| 猜数次数 | 1 | 2 | 3 | 4 | 5 | | 出现次数 | 1 | 6 | 25 | 239 | 1025 |
期望约为 4.76 次，方差约为 0.26，最大值为 5 次
测试结果见附件
五·总结
遍历了整个可能的解空间，证明了在最坏情况重视的策略下，可以做到 5 次之内猜出数字。
期望在 4.76 次，1296 次里有超过 1000 次是在5次的情况下猜出来的，可见该策略考虑的较为极端，也因此面对最坏情况得到的结果与普通情况也较为平均。
高阶在有重复的情况下还多了数字，比初阶大了一个数量级左右，初阶我跑了一天，高阶？不可能去做了。 |
心疼电脑。甚至我连 Gal 测评都没更新。
