資源描述：
《稱球問題一般解法.doc》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。
1、稱球問題一般會有以下3種變形：1、n個(gè)球，其中有一個(gè)壞的，知道是輕還是重，用天平稱出壞球來。2、n個(gè)球，其中有一個(gè)壞的，不知是輕還是重，用天平稱出壞球來。3、n個(gè)球，其中有一個(gè)壞的，不知是輕還是重，用天平稱出壞球來，并告知壞球是輕還是重。對于上面3種情況，稱量n次，最多可以在幾個(gè)球中找出壞球來？答案：分別為：3^n,(3^n-1)/2,(3^n-3)/2.稱法體現(xiàn)在下面的證明中：一、天平稱重，有兩個(gè)托盤比較輕重，加上托盤外面，也就是每次稱重有3個(gè)結(jié)果，就是ln3/ln2比特信息。n個(gè)球要知道其中一個(gè)不同的球，如果
2、知道那個(gè)不同重量的球是輕還是重，找出來的話那就是n個(gè)結(jié)果中的一種，就是有l(wèi)n(n)/ln2比特信息，假設(shè)我們要稱k次，根據(jù)信息理論：k*ln3/ln2>=ln(n)/ln2,解得k>=ln(n)/ln3這是得到下限，可以很輕易證明滿足條件的最小正整數(shù)k就是所求。比如稱3次知道輕重可以從3^3=27個(gè)球中找出不同的球出來。具體稱法就是：每次再待定的n個(gè)球中取[(n+2)/3]個(gè)球，放在天平左邊；[(n+2)/3]個(gè)球放在天平右邊。（注：[x]表示不大于x的最大整數(shù)。）二、對于N(m)=(3^m-1)/2個(gè)小球，現(xiàn)在
3、我們來尋求m次的解法。首先，對于m=2的情況，相當(dāng)于四個(gè)小球來稱兩次的情況，這個(gè)已經(jīng)討論過多次了，也很簡單，在此略去其次，若m<=k-1時(shí)，假定對于N(k-1)=(3^(k-1)-1)/2個(gè)球的情況我們都有解法?，F(xiàn)在來考慮m=k的情況。第一次稱取[3^(k-1)-1]個(gè)球放在天平天平兩端，則：如果平衡，獲得[3^(k-1)-1]個(gè)標(biāo)準(zhǔn)球，壞球在剩下的[3^(k-1)+1]/2個(gè)中。由于[3^(k-1)-1]>=[3^(k-1)+1]/2，（k>=2),即已知的標(biāo)準(zhǔn)球數(shù)不小于未知球數(shù);所以在以后的測量中就相當(dāng)于任意
4、給定標(biāo)準(zhǔn)球的情況，由前面的引理二可知對于[3^(k-1)+1]/2的情況(k-1)次可解。如果不平衡，大的那方記做A,小的那方記作B。標(biāo)準(zhǔn)球記做C.則現(xiàn)在我們有[3^(k-1)-1]/2個(gè)A球和B球，有[3^(k-1)+1]/2個(gè)C球。第二次用3^(k-2)個(gè)A球加[3^(k-2)-1]/2個(gè)B球放左邊;3^(k-2)個(gè)C球加[3^(k-2)-1]/2個(gè)A球放右邊。如果左邊大于右邊，則說明是在左邊的3^(k-2)個(gè)A球中質(zhì)量大的為壞球；如果左邊等于右邊，則說明是在第二次稱時(shí)沒用的3^(k-2)個(gè)B球中質(zhì)量輕的為壞
5、球。以上兩種情況都可以再用三分法(k-2)次解決，加上前兩次共k次解決。如果左邊小于右邊，則壞球在左邊的[3^(k-2)-1]/2個(gè)B球中或在右邊的同樣數(shù)目的A球中。此時(shí)的情況和第二次開始時(shí)類似（只不過是k-1變成k-2).用相同的辦法一直往下追溯到一個(gè)A球和一個(gè)B球一次區(qū)分的情況，這時(shí)只需拿A球和標(biāo)準(zhǔn)球比較以下就行了。因此在這種情況下也是可以最終用k次解決的。由以上兩步加上數(shù)學(xué)歸納法知，對于N(m)=(3^m-1)/2的情況，稱m次是可以稱出來的。由這個(gè)解法加上前面所給出的上界Nmax(m)<=(3^m-1)/
6、2，知稱m次能解決的最大的小球數(shù)Nmax(m)=(3^m-1)/2。有興趣的人可以驗(yàn)證一下m=3,N=13的情況----該情況已經(jīng)被反復(fù)拿出來討論過了。--------------------------------------------------------------------大家好，我們來繼續(xù)昨天的問題?，F(xiàn)在我要給出通解啦。為了簡化下面的過程，我們假設(shè)小球的個(gè)數(shù)正好是(3t-3)/2。首先我們把小球分成數(shù)量相等的三組A1～An
7、B1～Bn
8、C1～Cn，其中n=(3t-1-1)/2。第一次使用天平的時(shí)候
9、，不妨把A組和B組分別放在天平左右盤。如果天平左低右高，那么有可能因?yàn)樽筮卬個(gè)小球之一較重，也可能因?yàn)橛疫卬個(gè)小球之一較輕。反過來也是一樣。這種時(shí)候，轉(zhuǎn)到下面的情況(1)處理。而天平平衡的時(shí)候，則壞球一定在剩下n個(gè)小球中，(2)討論了這種問題。【情況1】這時(shí)的條件是：已知A1～An中一個(gè)球較重，或者B1～Bn中一個(gè)球較輕，其中n=(3t-1-1)/2。我們把可以在C中任意拿出一個(gè)好球（C中的都是好球嘛）放到B中去。然后由情況(3)討論接下來的處理方法。【情況2】這時(shí)的條件是：已知壞球C1～Cn中，且不知輕重關(guān)系，
10、其中n=(3t-1-1)/2。我們把C分作三組a1～am
11、b1～bm
12、c1～cm+1，其中m=(3t-2-1)/2。注意看啦，c組要比a，b兩組多出一個(gè)。怎么？我們昨天不是說這種情況沒辦法完成嗎？但是，我們現(xiàn)在多了一項(xiàng)武器－－好球。對，我們可以從已經(jīng)判斷為一定是好球的A，B組中任意拿出一個(gè)好球，和a一起放到天平左盤，把c組放到天平右盤，如果天平左低右高，那么一定是a組中m
