本文共 603 字，大约阅读时间需要 2 分钟。

有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次比较。

转载地址：http://qjkqb.baihongyu.com/