一道有趣的电路板面试题,征求好的解法
一、试题
有N块电路板,每个电路板可以检测别的电路板是好还是坏,但不能检测自己。好的电路板能得出准确的结果,但坏的电路板得到的结果就有可能是错的。电路板中好的比坏的要多。
请用最少的检测次数,找出一块好的电路板的方法来,并说明的分析理由。
二、分析
1.假设用一块好的电路板检查另一块电路板
序号 |
测试结果 |
测试结果说明了要检测的电路板什么 |
1 |
好的 |
是好的 |
2 |
坏的 |
是坏的 |
换句话说:
序号 |
待检查的电路板本身就是 |
测试结果 |
1 |
好的 |
好的 |
2 |
坏的 |
坏的 |
2.
假设用一块坏的电路板检查另一块电路板
序号 |
待检查的电路板本身就是 |
测试结果 |
1 |
好的 |
好的 |
2 |
坏的 |
|
3 |
坏的 |
好的 |
4 |
坏的 |
3.两块电路板互相检查
3.1两块好的电路板互相检查结果是:
仅仅一种结果
序号 |
测试结果 |
1 |
好的,好的 |
3.2两块坏的电路板互相检查结果是:
下面四种结果中的一种:
序号 |
测试结果 |
1 |
坏的,坏的 |
2 |
坏的,好的 |
3 |
好的,坏的 |
4 |
好的,好的 |
3.3
一块好的电路板与一块坏的电话互相检查的结果:
序号 |
测试结果 |
1 |
好的,坏的 |
2 |
坏的,坏的 |
也就是说,不可能出现测试结果,两个都是好的情况。
3.4
两块电路板相互测试的结果:只有3种结果:
1.都是好的;
2.都是坏的;
3.一个好的,一个坏的;
三、推理
1.两块电路板互相测试,测试结果是都是好的
如果两块电板板互相检查,如果得到的结果正好都是两个好的,那么,我们可以推理出:
两块电路板,要么都是好的,要么都是坏的。
序号 |
两块电路的测试结果是 |
测试结果说明了什么 |
1 |
两个好的 |
两块电路板都是好的 |
2 |
两块电路板都是坏的 |
要么两块电路板要么全好,要么全坏。
2.
两块电路板互相测试,测试结果是一个好的,一个坏的
如果两块电板板互相检查,如果得到的结果是一个是好的,还有一个是坏的,那么,我们可以推理出:
序号 |
两块电路的测试结果是 |
测试结果说明了什么 |
1 |
一个好的,另一个是坏的 |
两块电路板都是坏的 |
2 |
两块电路板一个是好的,一个是坏的 |
说明至少有一块电路板是坏的。
3.
两块电路板互相测试,测试结果是两个都是坏的
如果两块电板板互相检查,如果得到的结果:两个都是坏的,那么,我们可以推理出:
序号 |
两块电路的测试结果是 |
测试结果说明了什么 |
1 |
两个都是坏的 |
两块电路板都是坏的 |
2 |
两块电路板一个是好的,一个是坏的 |
说明至少有一块电路板是坏的。
四、推理结果
1.
两块电路板互相测试,测试结果:两个都是好的
两块电路板要么都是好的,要么都是坏的。
4.
两块电路板互相测试,测试结果是只要有一个是坏的
至少有一块电路板是坏的。
五、解题思路
1第一步找出一块坏的电路板
用第一块电路板与余下的N-1块电路板,两两测试,一旦测试结果第一次出现了:
有一个是坏的,不管另一个测试结果是好,是坏。
将其记录下来;
一旦测试结果还出现了,有两次的测试结果都是好的,就停止测试。
注意:如果循环了一遍,结果都没有出现测试结果都是好的,说明第一块电路板,就是坏的。
先分别记录
测试结果是两个好的,两块电路板名称分别叫做A与B;
再分别记录
测试结果是一个好的,一个是坏,两块的电路板分别叫做C与D;
然后分别记录
另一组测试结果是两个好的,两块电路板名称分别叫做E与F;
接着A测试C,并且也测试D,
如果测试都为好的,可以断定A与B都是坏的;
B测试C,并且也测试D,如果测试都是好的,可以断定A与B都是坏的;
一旦确定了A与B都是坏的。
用E来测试A,
如果测试结果是好的,说明E也假的;
用E来测试B
如果测试结果是好的,说明E也假的;
用F来测试A,
如果测试结果是好的,说明F也假的;
用F来测试B,
如果测试结果是好的,说明F也假的;
注意:用E来测试A,
如果测试结果是坏的,并不能说明E就是好的电路板。
2.第二步用未知的电路板来检测这块坏的电路板
如果是结果是好的,可以肯定这块未知电路板是坏的,将他放到坏的电路板的一堆里,或者数字组里,或者叫添加到坏电路板的集合里;
如果测试结果是坏的,该块电路板好坏,不可确定,是未知;
然后用他来测试坏的电路板里集合里的每一块电路板,只要发现测试结果是好的,就可以肯定该电路板,是坏的,可以添加到坏的电路板集合中去。
六、征求问题解法
原来以为很Easy,偶想了好半天,太头疼了,都没有一个好的解法,特此征求CSDN朋友各路英雄豪杰,有什么好的算法。谢谢!
推荐扩展阅读: