找回密码
 欢迎注册
查看: 18592|回复: 7

[求助] 零件区分

[复制链接]
发表于 2016-8-18 11:05:38 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有账号?欢迎注册

×
有n个原件,好的比坏的多。好原件可以判断另一个原件是好的还是坏的,而坏零件在被要求判断时,会随机回答。
1.要得到一个好原件,几步能保证得到?
2.要判断所有原件的情况,需要几步?(小于等于上题答案+n-1)
3.如果每次判断都是互相判断(即每次能同时获得A原件对B原件的判断和B原件对A原件的判断)呢?
注:若好的和坏的一样多,如1好1坏,当双方互相判定为坏时,无法得知哪个好哪个坏。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2016-8-18 13:47:12 | 显示全部楼层
说一个思路吧,未必是最佳的。

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

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

点评

好方法  发表于 2016-8-18 13:58
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2016-8-18 17:52:14 来自手机 | 显示全部楼层
我们知道两个好零件判断其它零件的结果总是相同的,而且互判是好的。而总零件数目充分多时,坏零件判断其它零件的结果几乎总有不同的结果。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2016-8-18 17:56:27 来自手机 | 显示全部楼层
所以我们可以先随机选择两个互判为真的零件,让它们依次判断其它零件,如果全部相同,就认为结果得出,不然两者必有一假,再替换一个用同样策略下去,从概率上很快就会找到结果

点评

但是最坏情况呢  发表于 2016-8-18 23:01
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2016-8-20 14:03:44 | 显示全部楼层
8月14日的一个公众微信号上也有类似的问题,题目叫做“人与鬼”
显然,微信号上的情境设定更好。
Screenshot_2016-08-20-13-56-01-89.png
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2016-8-20 14:07:49 | 显示全部楼层
靠,手机的拷屏咋这么大?怎么设定图片大小@gxqcn?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-3-28 19:09 , Processed in 0.053302 second(s), 20 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表