金慶的專欄

有難度的算法筆試題

摘自：http://community.csdn.net/Expert/TopicView3.asp?id=5764920

3）芯片測試：

有2k塊芯片，已知好芯片比壞芯片多。請設計算法從其中找出一片好芯片，說明你所用的比較次數上限。
其中：
好芯片和其它芯片比較時，能正確給出另一塊芯片是好還是壞。
壞芯片和其它芯片比較時，會隨機的給出好或是壞。 

Vitin(衛亭) ( )：

試著回答一下第三題,不保證最快效率:
1.對N個芯片,在保證好芯片比壞芯片多的情況下,取出一塊芯片(為敘述方便,設為芯片X),與其他所有芯片做測試,記錄相互間的結果.
2.按照芯片X對其他芯片的結果,將其他芯片分成兩組:GOOD組和BAD組.
3.如果GOOD組的數目<BAD的數目,則X為壞芯片,跳到5.
4. 如果GOOD組的數目>=BAD組的數目,并且GOOD組對X的測試為good(認為X好芯片),則X確實是好芯片,算法結束(因為在N-1中,至 少半數的芯片認為X為不是壞芯片,考慮到"好芯片比壞芯片多",可歸謬證明);否則,只要有一個GOOD組芯片對X的測試為bad,則X為壞芯片,繼續.
5.X為壞芯片,故去除X,將所有芯片分成兩組:對X的測試為bad的保留,對X的測試為good的去除.考慮到所有的好芯片都保留了(它們對X的測試必為bad),所以仍然滿足"好芯片比壞芯片多"的條件.跳到1,繼續.

以上算法保證可以結束.因為如果測試出X是壞的,那么每次N至少減一.并且,因為"好芯片比壞芯片多",算法必定是在第4步結束.而不會出現芯片降到1的情況(只要初始的芯片數>=2)

題目中,初始N=2k.其復雜度在最壞的情況下測試次數(假設一次測試同時出現相互的結果,否則次數*2)為: k + (k+1) + ... + (2k-1) = 1/2 * k(3k-1) = O(k^2)


xlfddlfd(樓主請點我加分^_^不用客氣) ( ) ：

下面兩個結論比較有用，先列出來。

任意拿兩片芯片互相測試，則有
1）結果都為真，則說明兩片都為真，或者都為假。
2）其他結果，則最少有一為假。

在任意偶數多的芯片里，如果好芯片多于壞芯片，將所有芯片兩兩分組，根據抽屜原理，則有
1）必有兩個好芯片分在一組。
2）同為好芯片的組數一定多于同為壞芯片的組數。

測試流程
1）將芯片兩兩分組，比如1和2，3和4。。。。2k-1和2k?；ハ鄿y試，則必有結果同為真的組。
2）保留結果同為真的組，丟棄其他組。必有好芯片組多于壞芯片組。（所以當只有兩組或者一組同為真時，則必為真，測試結束）
3）結果同為真的組芯片必定同好或者同壞，所以可以丟棄一半。從所有同真組中任意取出一個丟棄另一個，組成新的測試組，繼續兩兩分組，直到同真組只有2個或者1個測試結束，堅持到最后的就是好芯片。

說 明：同真組可能會變成奇數個，當為奇數組時，任意選一組取其中一個（假設為A），在剩余組中各取一個來測試A，如果測試結果A為好芯片過半或者等于一半， 則A為好芯片，測試結束。否則A為壞芯片，判定A為好芯片的必為壞芯片，剔除后剩余部分形成新的測試組，繼續兩兩分組。。。

總的原理和淘 金差不多，剛開始好的芯片多，在每次剔除芯片時一定要保證剔除的壞芯片數量一定要多于或者等于好芯片的數量，這樣就能保證在剩余的芯片中好的一定多于壞 的。當組數為奇數時采用投票制，多于半數的投票有效（等于也有效，因為好的多于壞的，相等則被測試的一定為好的）。

因為每次最少剔除一半的芯片，所以最壞情況出現在每次只能剔除一半芯片的時候，按等比數列遞減。當有N個芯片時，測試次數為n+(n/2)+(n/4)...=2n（實際上當為奇數組時，次數會更多，不過算不過來了，省略^_^ ）


Vitin(衛亭) ( ) ：

xlfddlfd 的算法很好,學習一下.

這個算法比我之前的算法要快得多.
當 最壞情況是,每次都是奇數,并且每次都是壞芯片 時,測試次數(lg是以2為底的對數,N = 2k)約為 2(k + k/2 + k/4+...)-slgk = 4k - slgk = O(k),仍然是線性算法(此處的s為不大的常數(但大于1),因為在每次為奇數的情況下,實際的數目要比 k/2, k/4 之類的小,可以認為這個誤差是lgk的倍數,此外壞芯片的比較數是每次總個數-1,所以要減少大約一個lgk).