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