Geek
对[智力测验]的一种解题方法
# 兔子 投稿
因为评论中很多人对舞女的旋转是对应左脑还是右脑产生疑问，避免产生歧义，我重写了一下题目，将左右脑的背景完全剥除。为了让更多的人能看懂，我说的很啰嗦而且避开了很多统计学的用语。(实际情况是：假设检验是电焊老师教的，学的极烂不知道该怎么说)
题目：
有一数据集和一堆人。数据集分为2类好数据(M)和坏数据(N)。人分为3类ABC。对于一个坏数据，所有人都会给出一致的输出0或1。对于一个好数据，A类人给出0，B类人给出1，C类人以0.5概率给出0或1。尝试寻找一个方法，用数据划分人群成ABC三堆。使得划分出来的A类人群，“此人群全部都是A类人”的正确率超过95%。已知数据集足够大，ABC每类人群都不为空。
解题思路：
从数据集中抽一个数据，展示给所有人。若所有人给出一致输出，那么说明此数据为N数据，不能提供任何信息。那么舍弃此轮操作。
然后继续向人群展示一个新数据。经过几轮运气不好，一直抽到N数据后，直到碰到第一个M数据，此时根据人群给出的0和1 答案，将人群分类为A类和B类。为了与实际情况的ABC类，文字上有区别：以下，真实情况的A类人用“实际A类”或“真A类”表示，当前划分A类的一群人用“划分A类”表示，真实属于C类人但错分成A类用“假A类”表示。他们的关系是 “划分A类”肯定包含所有的“真A类”，但也混着一些“假A类”。
只对划分A类研究。剩下的思路，就是利用“对M数据输入，真A类会一直产生0，而假A类随机产生0或1”这一特性，如果一个人输入了M数据产生了1则一定是假A类，将其删除。不停的向划分A类输入M数据，直到去除掉了足够多的假A类。这个思路要解决2个问题：
如何判断一个数据是M类？
如何判断已经输入了足够的M类数据？
对划分A类输入数据：
当划分A类给出全1的时候，这是个N数据。
当划分A类给出全0的时候，此时再将这数据送往划分B类。若划分B类也给出全0，说明这是个N数据。若出现了1，则对同一数据，存在真A类给出了0且真B类给出了1，说明这是个M数据。这样我就对划分A类输入过1次M数据且知道了结果(全0)。这种情况就是“对划分A类输入M数据进行1轮检测”
当划分A类的输出0，1都有的情况，说明这是个M数据。真A类对数据输出了0，假A类中有人随机输出了1。这种情况是“对划分A类输入M数据进行1轮检测”。此种情况我也对划分A类输入了M数据且知道了结果(有0有1)
以上就是对划分A类输入数据，输出的全部可能。可以看到我既判断了数据是M类还是N类，也拿到了划分A类对M类数据的输出。第一问题解决。
划分A类中，真A类对M数据的输出永远是0，对于挑出假A类没有帮助，我们可以不去管他，只关注假A类。假设划分A类中只有1个假A类，在进行x轮测试中它每次都输出0的可能性是 0.5^x。这是x轮测试后没检出这个假A类，出错的可能。我们希望正确的划分有95%的把握，即：1 - .5^x > 0.95。解出这个x=5
对于1个假A类的情况，问题2也解决了。
只有1个假A类的情况解决了，可是现在不知道划分A类中有多少是错的。怎么办？思路就是：如果在最糟糕的情况下，我都能保证x轮检测后，正确的概率超过95%，那么其他情况下也能达到95%以上的正确率。很显然的,划分A类中的假A类越多，越需要更多轮的检测把它们一个不留的全检测出来。需要检测轮数与假A类的个数有关。最糟的情况，划分A类中只有1个是真的，其他全是假的。我们不知道划分A类中有多少假A类。但是划分A类有一共多少个人，可以查。假设目前划分A类中有r个人，最糟情况下r-1个都是假的。进行x轮检测，1个假A类时正确检出概率是1-.5 ^ x, 那么r-1个假A类全部检出的正确率就是(1 - 0.5^x) ^ (r-1)。 正确率超过95%意味着 (1 - 0.5^x) ^ (r-1) > 0.95。
因为划分A类总个数是有限的，则x轮检测也是有限步操作。
操作流程：
第一步：将数据一个一个发给所有人，直到输出出现有0有1的情况。将所有为0的结果程序称为“划分A类”，所有输出1的程序称为“划分B类”
第二步：查“划分A类”包含人数r，带入公式 (1 - 0.5**x) ** (r-1) > 0.95 ，求得最小正整数解 x。 设置当前检测次数 count = 0
第三步：向划分A类,输入下一个数据。若：
划分A类的程序给出全1输出，跳回第三步
划分A类的程序给出全0， 则将数据输入划分B类：若
划分B类输出全0，则跳回第三步
划分B类输出存在1，则 count 增1， 跳到第四步。
划分A类的输出有0有1，则将输出为1的程序全部删除出划分A类，count 增1。 跳到第四步。
第四步：检查count 是否等于 x，若
count == x， 则操作结束。
count < x, 则跳回第三步。 经第四步结束的划分A类，“此类中全部成员都是真A类”的论断，正确率超过95%。
实际数据测试：
若第一次得到的划分A类是30个人，解得: x>9.14434... 用10次M数据检测即可，
若划分A类是百人规模，则x>10.91481... 需要11次检测
划分A类是20000人规模，需要19次检测