Question

C++数字游戏求思路 不要代码

Answer 1

目前没想到更好的方法，先说说当前的思路：
1. 首先暴力破解也不困难，一共1w个数，全部尝试一遍，如果结果只有一个数字满足所有的条件，那么就输出这个数，如果有多个满足的，直接输出Not Sure。当然，可以设想肯定有更好的解法。所以继续思考。
2. 设答案是X。每行的第二个数字是猜对的位数，如果把4位数看成无序的数字集合，这个位数相当于本数字和X的交集元素。第三个数字是猜对的位置数，这个显然意味着有序的排列和X的交集位数。
3. 继续分析，如果1W以内所有的数字都不分顺序，仅仅看成集合，那么一共有多少这样的集合呢？不分顺序，意味着1234和4321是相同的集合，1234共有4！=24种排列方式，所以1W以内可以估算大概有10000/4! = 416个这种集合，实际数字应该略大于416，因为有2222这种数字。所以就估500。也就是说10000个数中，有尝试价值的总共只有500个数。而且这500个数用循环很容易得到。
4. 500个数字暴力破解起来就相当容易了，比起1W个，性能高了20倍。让这500个数字先去试探第二个数字，OK的再去试探第三个数字。
5. 因为每个条件严格程度不同，比如8585 3 3这个条件就比4815 2 1这个条件严格的多，第一轮淘汰的元素也更多，从性能角度讲，应该吧这个条件排前面。
6. 我看时间限制是1s，这个复杂度应该满足要求了。后面想到更好的方法再更新。