金慶的專欄

有難度的算法筆試題

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

3）芯片測試：

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

Vitin(衛(wèi)亭) ( )：

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

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

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


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

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

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

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

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

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

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

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


Vitin(衛(wèi)亭) ( ) ：

xlfddlfd 的算法很好,學(xué)習(xí)一下.

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