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