如果有9個球，其中如果1個球的重量不同，則需要至少2個重量才能找到奇數球。 如果有27個球，它需要3次機會。尋找不同重量球所需的最小重量是多少？
9 - > 3 pow 2 - > 2 chances。
27 - > 3 pow 3 - > 3的機率。
問題：什麼需要如果給
3 POW 45發現奇數球暈死的最小數目 - 3 POW 40個球
？
不能使用計算器。我認爲，需要推導出一些方程/公式。
任何人都可以破解這個難題嗎？
如果3^x = N球和x -- number of weighs,x = log3(N);
3^x = 3^45 - 3^40;
3^x = 3^40 * (3^5 - 1);
x = log3(3^40) + log3(3^5 - 1) = 40 + log3(242);
real_x = ceil(x);
嗯，根據3^2 - > 2和3^3 - > 3的第一個假設是真實的，證明我錯了。如果是這樣，x（N）= log3（N）函數。並且沒有必要計算x（a^alpha - b^beta），因爲如果beta小於alpha，b^beta = o（a^alpha），所以我們可以放棄它。而且我可以犯一個錯誤。 – Violette 2010-11-13 08:18:24
要完成：4 =日誌（3^4）<日誌（3^5-1）<日誌（3^5）= 5，從而小區（日誌（3^5-1））= 5，所以結果是45 – sdcvvc 2010-11-13 12:00:29
+1：完美。謝謝。也感謝sdcwc。 – bjskishore123 2010-11-13 14:16:39
根據您的例子中，我們可以推斷，不同重量的球要麼已知較重的或已知較輕。爲了簡單起見，我認爲它更重。
首先讓我們來看看爲什麼在45次稱重中可以做到這一點：對於3n個球，可以稱n與n，剩下n不稱重，並減少到n個球。做40次，減少到一批（3^45-3^40）/ 3^40 = 3^5-1 = 242球。重球在那裏。添加一個已知的正常球，所以你有243（3次冪），並繼續五次稱重，之後你會有重球。
接下來讓我們來看看它爲什麼不能在44個稱量或更少來完成：每次稱重爲您提供了一條信息，這可以被認爲是數字0，1，或2 0爲「重球在左邊「，1爲」重球在右邊「，2爲」重球在未被稱量的批次「。無論有多少球與相同數量的球進行稱重，情況都是如此。因此，任何44個稱量的結果都可以看作是44個數字的序列 - 0,1，和2。有3^44個可能的結果任何策略使用44個稱量。但是你有超過3^44個球，所以你不能保證使用只產生3^44個不同答案的實驗過程找到合適的球。從信息論的角度來看，「正確答案」中有更多的信息比44次稱量所能產生的更多。
當使用秤的傳統稱重方法時，我們不必推斷任何東西，順便說一句。 – user268396 2010-11-13 14:53:50
另一種直觀的方式來得到的答案是問自己這樣一個問題：
多少個球最多可以由一個權重進行檢查？
答案是3.原因是因爲如果你比較三個球中的兩個球，你要麼立即找到不同重量的球（無論重量還是重量較輕），要麼你發現他們的重量是相同的，消除導致第三個球具有不同的重量。
因此，人們可以將N個球分成3個組加上一個M的餘數組（其中0 < = M < 3）。每組3個應用一個這樣的權重將消除所有球的2/3。這意味着您剩下一組新的球，您需要從中找到不同重量的球，此組中球的數量等於球場（N/3）+ M.
通過應用相同對於這個縮小的球組，您可以在一般情況下在最高限度（log（N）/ log（3））步驟中找到具有不同重量的球。最高限額（）聲明的原因是，您最終可能會用完3個組，並留下一組2個球，並且需要額外的1個權重。 （如果最後一組只有1個球你不必權衡推斷它必須是不同的權重的一個球。更精確地配製成最多地板（日誌（N）/日誌appearst需要權重的數量（3） ）+ 1;從那裏簡單的觀察到，如果log（N）/ log（3）是整數，則不需要額外的加權，從而導致更高精度的上限值（log（N）/ log（3））。）
的密切票是不是因爲做重複，而是因爲你的問題是題外話，因爲它不直接相關的節目。您可能在http://math.stackexchange.com/上有更多的運氣。 – 2010-11-13 14:20:39