零件区分

l4m2

有n个原件，好的比坏的多。好原件可以判断另一个原件是好的还是坏的，而坏零件在被要求判断时，会随机回答。
1.要得到一个好原件，几步能保证得到？
2.要判断所有原件的情况，需要几步？（小于等于上题答案+n-1）
3.如果每次判断都是互相判断（即每次能同时获得A原件对B原件的判断和B原件对A原件的判断）呢？
注：若好的和坏的一样多，如1好1坏，当双方互相判定为坏时，无法得知哪个好哪个坏。

whbns

说一个思路吧，未必是最佳的。

如果两个零件互相判定，结果都是好，那么两个可能同为好，也可能同为坏。
如果结果为两个是一好一坏的话，被判为坏的一定是坏的，另一个可能是好的，也可能是坏的。
如果结果都为坏，那么至少有一个是坏的，也可能都是坏的。

可以看出无论哪种情况都不能直接确定某个元件是好的，所以必须利用“好的比坏的多”这个条件。
我的方法是这样的：
先把所有的零件两两一组，互相判定，如果结果为“好坏”或“坏坏”则把两个都放到一边，因为这两个里面至少有一个坏的，所以剩下的一定还是好的比坏的多。
剩下的就是“好好”的组。这时在每组中取走一个就可以让剩下的零件数减半了。
但是有一种特殊情况，如果总零件是奇数个，且“好好”组也是奇数个。这时有可能好零件组比坏零件组多一组，而最后一个单个的是坏的。如果每组去掉一个，剩下的好坏零件就一样多了。所以如果有偶数组，则每组去掉一个零件，但不在组里的零件留下。如果有奇数组，则每组去掉一个，同时去掉多出来的那个。
这样只需要n/2次相互判定就可以将总零件数至少减半。
重复上面的步骤，最终剩下一个或两个就一定是好的了。总共最多需要大约n次相互判定。

mathe

我们知道两个好零件判断其它零件的结果总是相同的，而且互判是好的。而总零件数目充分多时，坏零件判断其它零件的结果几乎总有不同的结果。

mathe

所以我们可以先随机选择两个互判为真的零件，让它们依次判断其它零件，如果全部相同，就认为结果得出，不然两者必有一假，再替换一个用同样策略下去，从概率上很快就会找到结果

hujunhua

8月14日的一个公众微信号上也有类似的问题，题目叫做“人与鬼”。
显然，微信号上的情境设定更好。

hujunhua

靠，手机的拷屏咋这么大？怎么设定图片大小@gxqcn？