芯片測試問題

有n片芯片，已知其中好芯片比壞芯片至少多1片。現在需要通過測試從中找出1片好芯片。測試的方法是：將2片芯片放到測試臺上，2片芯片互相測試并報告測試結果：”好”或者”壞”。假定好芯片的報告是正確的，壞芯片的報告是不可靠的(可能是對的，也可能是錯的)。請設計一個算法，使用最少的測試次數來找出1片好芯片。

由于好芯片至少比壞芯片多1片，對1片芯片來說，如果有?n/2?片芯片都報告它是”好的”，那么這片芯片一定是好的（因為如果該芯片的所有報告都是壞芯片產生的，則說明已經有?n/2?個壞芯片，又因為好芯片比壞芯片多，所以當前芯片一定是好的；而如果并非所有報告都是壞芯片產生的，那么有些報告是好芯片產生的，所以當前芯片一定是好的）。一個蠻力算法就是任取1片芯片，然后用其余所有芯片來測試它，直到找到1片好芯片為止。這個算法最壞情況下Θ(n^2)次測試。

下面嘗試一下分治策略。

初始的想法就是：將n片芯片兩兩一組分成?n/2?組，每組測試1次。就像體育比賽的淘汰賽一樣，通過第一輪的?n/2?次測試淘汰一部分芯片，剩下的芯片構成一個規模較小的子問題進入第二輪。如果測試的芯片不超過3片(即子問題規模小于等于3)，并且好芯片比壞芯片至少多1片，那么只要測試1次就可以找出好芯片。剩下需要考慮的一個問題是：采取什么樣的淘汰規則，能夠保證進入下一輪的好芯片比壞芯片至少多一片，換句話說，每輪測試丟棄的壞芯片數至少和丟棄的好芯片數一樣多。這涉及算法的正確性。另一個問題是：每輪測試淘汰的芯片數占測試芯片數的比例是多少。這涉及子問題規模縮小得有多快，它決定了算法的效率。

先分析一下不同的測試報告究竟給出了什么信息。假設放到測試臺上的芯片是A和B，表1列出了可能的結果。

• 如果測試結果是情況1，那么A、B中留1片，任意丟掉1片（實際上A、B都好或A、B都壞）；
• 如果是后三種情況，則把A和B全部丟掉（實際上因為至少有一片是好的，因此最差的情況是好壞芯片同歸于盡，但至少沒有多丟掉好芯片）。

命題 1 當n是偶數時，在上述規則下，經過一輪淘汰，剩下的好芯片比壞芯片至少多1片。
證 設A、B都是好芯片的有i組，A、B一好一壞有j組，A、B都壞的有k組，那么

經過淘汰后，剩下好芯片數為i，壞芯片數為k，滿足i>k。

但是當n是奇數，沒被分組而輪空的是1片壞芯片時，可能淘汰后剩下的好芯片與壞芯片數相等。比如n=7，有4片好芯片，3片壞芯片。如果分組為：{好，好}，{好，好}，{壞，壞}，1片壞芯片輪空，那么淘汰后的4片芯片恰好2好2壞。對于奇數的情況，可以增加一輪特殊處理，即把這個輪空的芯片與每1片其他芯片都測一遍。根據前面的分析，通過這些測試可以判斷這片芯片的好壞。如果它是好的，算法結束；如果它是壞的，丟棄它。這些額外工作需要O(n)次測試，而這輪分組內的測試也需要O(n)次(精確說應該是?n/2?次)，因此不論是偶數還是奇數，歸約為子問題的工作量都是O(n)。

下面考慮第二個問題。

命題2 因為每組至少需要丟掉1片芯片，因此經過一輪測試后，剩下的芯片數至多為n/2。算法的偽碼描述如下：

根據前面關于遞推方程的分析結果，可以得到 。不難看出，比起蠻力算法，分治算法在效率上有明顯的提高。

---

選擇問題

1、同時選最大和最小算法

該算法的基本思想是：首先將L中的元素兩兩一組，分成?n/2?組(當n是奇數時有一個元素輪空)。每組中的兩個數通過1次比較確定本組的”較大”和”較小”。把至多?n/2?+1(當n為奇數時，需要把被輪空的元素加進來)個小組”較大”放到一起，運行Findmax算法找出其中的最大元素，它就是L中的最大元素。類似地，再把至多?n/2?+1(當n為奇數時，需要把輪空的元素加進來)個小組”較小”放到一起，運行Findmin算法找出其中的最小元素，它就是L中的最小元素。

該算法的偽碼描述如下：

2、找第二大元素的算法

顯然兩次調用Findmax算法可以得到第二大元素，先用Findmax算法找出最大元素，然后從L中刪除max，再調用Findmax找出剩下元素的最大元素，就是輸入L的第二大元素Second。不難看出該算法的時間復雜度是：

下面嘗試錦標賽算法。該算法的基本思想是：將L中的元素兩兩一組，分成?n/2?組(如果n是奇數時可能有1個元素輪空)。每組內進行比較，將較小的元素淘汰，每組中較大的元素和輪空的元素(如果存在的話)進入下一輪。進入下一輪的元素應該有?n/2?個。在下一輪中，繼續進行同樣的分組淘汰，勝者再進入下一輪，直到產生”冠軍”，即最大元素為止。到此算法總計淘汰了n-1個元素，每次比較恰好淘汰1個元素，因此算法已經做了n-1次比較。但是，我們的任務還沒有完成，怎樣找第二大元素Second呢? 如果還是再次調用找最大算法，那么算法還需要n-2次比較。這就和剛才的兩次調用Findmax的算法在時間上一樣了。我們的想法是：利用第一階段競爭冠軍時比較運算的結果信息，以減少第二階段的比較次數。這是可能的。首先觀察到，第二大元素只能在與最大元素max直接比較所淘汰的元素中產生。如果一個元素被其他元素淘汰，而那個元素本身不是冠軍，那么該元素至多只能排在第三名之后。這樣，我們在找第二大元素時只需關心那些被max淘汰的元素即可。需要考慮的是在第一階段中，被max淘汰的元素有多少，又是哪些元素。在max沒產生之前，算法并不知道誰是最后的冠軍，我們必須要求每個元素把被自己淘汰掉的元素全部記錄下來。為此，在比賽之前為每個元素設定一個指針，指向一個鏈表。如果該元素在比較中把其他元素淘汰了，就把那個元素記錄在自己的鏈表里。到max產生的時候，我們只需要檢查max的鏈表，在上面調用Findmax 算法就可以找到第二大元素了。算法的偽碼描述如下：

這個算法的時間復雜度是多少? 算法所做的比較次數分成兩部分，第一部分是找最大元素max過程中的比較次數，第二部分是在產生max后在其鏈表中找最大所需要的比較次數。在第一部分，每次比較正好淘汰1個元素，淘汰n-1個元素的比較次數就等于n-1。在第二部分，比較次數恰好等于max 鏈表中的元素個數減1，只要估計出max 所淘汰掉的元素個數就可以得到這部分的工作量。

我們有下面的命題：

總結

以上是生活随笔為你收集整理的算法设计与分析：芯片测试问题、选择问题详解的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。