很经典的芯片测试题,当智力测试做一做吧.芯片测试：有2k块芯片,已知好芯片比坏芯片多．请设计算法从其中找出一片 好芯片,说明你所用的比较次数上限.其中：好芯片和其它芯片比较时,能正确给出另一块芯片是好还是坏． 坏芯片和其它芯片比较时,会随机的给出好或是坏.善良的本人已经找来答案了：两块芯片比较,结果可能是（好好）,（好坏）,（坏坏）.如果结果是（好好）,则可能是两块好芯片,也可能是两块坏芯片.如果结果是（好坏）或者（坏坏）,则两块芯片中至少有一块是坏的.1. 将2k块芯片分成k组,每组两个比较.如果结果是
2019-04-19
很经典的芯片测试题,当智力测试做一做吧.
芯片测试：有2k块芯片,已知好芯片比坏芯片多．请设计算法从其中找出一片
好芯片,说明你所用的比较次数上限.
其中：好芯片和其它芯片比较时,能正确给出另一块芯片是好还是坏．
坏芯片和其它芯片比较时,会随机的给出好或是坏.
善良的本人已经找来答案了：
两块芯片比较,结果可能是（好好）,（好坏）,（坏坏）.如果结果是（好好）,则可能是两块好芯片,也可能是两块坏芯片.如果结果是（好坏）或者（坏坏）,则两块芯片中至少有一块是坏的.
1. 将2k块芯片分成k组,每组两个比较.如果结果是（好坏）或者（坏坏）,则把两块芯片都去掉；如果结果是（好好）,则任选其中一块去掉.可以保证剩下好芯片比坏芯片多.
2. 如果剩下1个或2个,则可以判断这些是好芯片.
3. 如果剩下偶数个,则回到第1步.
4. 如果剩下奇数个,则任取一个和其它所有芯片比较,如果有一半将此芯片判为好芯片,则说明此芯片为好芯片,测试结束；否则,说明此芯片为坏芯片,去掉此芯片（当然还可以去掉将此芯片判为好芯片的芯片）后总芯片数为偶数,回到第1步.
考虑最坏的情况：
第1次,进行k次比较,可以使芯片数减半；
第2次,k为奇数,则需要进行k-1次比较,使芯片数减为k-1.
第3次,通过（k-1）/ 2次比较可以使芯片数减为 （k-1）/2.
第4次,（k-1）/2为奇数,需要（k-1）/2 - 1次比较
第5次,需要 （（k-1）/2 - 1）/2次比较
..
所以最多4k次比较.
下面,求解释.有哪位能帮俺解释清楚?以上解答是正确的吗?几乎步步欠推导啊!
优质解答
感觉答案没问题呀 LZ哪里不清楚?
解释下答案第一步 所做之后为什么好芯片依旧比坏芯片多吧：
假设有m个好芯片 n个坏芯片 （m>n）
两两比较只有三种情况 好好比较 好坏比较 坏坏比较
假设有a个好芯片与a个坏芯片进行的好坏比较 那么剩下的芯片都是好好 或 坏坏比较：
好坏比较的结果不是 好坏 就是 坏坏 肯定这2a个芯片都被弃掉了
好好比较的芯片弃掉了一半 则好芯片剩余个数：m'=(m-a)/2
坏坏比较的芯片至少弃掉一半（根据规则 2个芯片比较要么弃掉1个 要么弃掉2个）
所以坏芯片剩余个数：n'
感觉答案没问题呀 LZ哪里不清楚?
解释下答案第一步 所做之后为什么好芯片依旧比坏芯片多吧：
假设有m个好芯片 n个坏芯片 （m>n）
两两比较只有三种情况 好好比较 好坏比较 坏坏比较
假设有a个好芯片与a个坏芯片进行的好坏比较 那么剩下的芯片都是好好 或 坏坏比较：
好坏比较的结果不是 好坏 就是 坏坏 肯定这2a个芯片都被弃掉了
好好比较的芯片弃掉了一半 则好芯片剩余个数：m'=(m-a)/2
坏坏比较的芯片至少弃掉一半（根据规则 2个芯片比较要么弃掉1个 要么弃掉2个）
所以坏芯片剩余个数：n'