國家集訓隊20xx論文集-侯啟明(參考版)
2025-07-28 03:36本頁面
【正文】 謝謝大家 ! 。它可以為我們的解法提供強有力的理論依據(jù)，更可以通過估計上下界來指導解法的構造。 總結 細心的讀者應該會注意到，本文中的例題不用信息論的知識都可以解決。 最后的構造 構造完畢！ 問題的解決 就這樣，在信息論的幫助下，這個困擾了我兩年的問題終于解決了。 稍加分析不難得出后面的步驟。而原來那枚好硬幣，為了保持天平兩邊硬幣數(shù)相等，也只好換到另一側。 最后的構造 因為這三種情況出現(xiàn)的概率相同且必居其一。 ?和第一次比較不同 說明兩次比較中壞硬幣在天平異側。 既然這樣，我們不妨來看看這次比較可能得到的三種結果都意味著什么。 最后的構造 但假如比較結果是“不平衡”呢？此時，壞硬幣編號的熵為 log3k1，如果要在 k1次比較內找出壞硬幣，那么此后每一次比較結果的熵都得是 log3。由于這個數(shù)是奇數(shù)，所以只好把唯一一枚沒有嫌疑的硬幣也放上天平，這樣就確定了第一次比較的方案。 “放大”后的問題解決了，那么原問題呢？我們可以猜想，一個好硬幣和無窮多個好硬幣是等效的，也就是說，如果設在有一個已知的好硬幣的情況下， k次比較最多從 f(k)個硬幣中找出一個壞硬幣，那么f(k)≡g(k)。 ?好球較重：與上一種情況類似，不再贅述。 此時可以確定壞硬幣在上了天平的g(k)t個硬幣中，同樣，根據(jù)結論 1，得到g(k)t=3k1，故 g(k)=g(k1)+3k1: 進一步的分析 現(xiàn)在通過構造來證明 g(k)=g(k1)+ 3k1： 第一次比較第 1到 3k1號硬幣和 3k1個好硬幣，分以下情況討論： ?平衡：說明壞硬幣在剩下的 g(k1)個硬幣中，由 g的定義，可以在 k1步內找出。 由于可以通過剩下的 k1次比較把壞硬幣從這 t個硬幣中找出來，所以 t=g(k1)。 信息論不行的時候，枚舉也是必要的。 進一步的分析 設在有無窮枚好硬幣時， k次比較最多從g(k)個硬幣中找出一個壞硬幣。 請看進一步的分析： 進一步的分析 通過轉化，發(fā)現(xiàn)只要計算出給出一枚好硬幣， k次比較最多在多少枚硬幣（ 不 包括給出的好硬幣）中找出一枚壞硬幣，就可以解決原問題。 初步分析 雖然這樣，但是在原題的條件下，這個信息論下
公司管理相關推薦
鄂ICP備17016276號-1