讨论一个面试题:零件配对
有一种AB对零件,如果某一对零件中有一个坏掉了,那么AB配对的时候会发出声响,如果两个都坏了,可能发出声响也可能不会发出声响,如果两个都是好的,不会发出声响。现在有50对这样的零件(分散的),但已知有一对是坏的,怎样才能最快找到这一对坏掉的零件?
?
这个题目我有两种思路,但比较难具体描述:
思路一:拿任意一个B部件跟A配对,
???1.当听到两次响声时,可以证明这个B部件是坏的;再拿任意一个剩余的B部件跟A配对,发出响声的A部件是坏的,over
???2.若配对完后,只听到一次响声,那么发出响声的A部件是坏的;此时再用剩余的任意一个A部件跟剩余的B配对,若没有响声,则最初的B部件是坏的,over;若发出响声,则对应的B部件是坏的,over
?
思路二:50个零件两两配对:
?? 1.当听到两次响声时,说明两个坏部件就在对应的两对零件中,然后从中找到坏掉的两个部件;
???2.如果从始至终只听到一次响声,那么响的那一对零件就是坏掉的那一对
?? 3.如果没有听到响声,那么说坏的零件已经配对,那么此时拿任意一个B部件跟A配对
???? 3.1 当听到一次响声时,证明AB中至少有一个坏的,若A是坏的,才与A配对的B是坏的,反之亦然;
?