算法合集之信息論在信息學(xué)競賽中的簡單應(yīng)用-資料下載頁
2024-10-16 03:11本頁面
【正文】 “放大”后的問題解決了，那么原問題呢？我們可以猜想，一個(gè)好硬幣和無窮多個(gè)好硬幣是等效的，也就是說，如果設(shè)在有一個(gè)已知的好硬幣的情況下， k次比較最多從 f(k)個(gè)硬幣中找出一個(gè)壞硬幣，那么f(k)≡g(k)。 下面進(jìn)行構(gòu)造證明 最后的構(gòu)造 根據(jù)計(jì)算 g(k)時(shí)的推理，第一次比較應(yīng)該有 3k1枚“有嫌疑”的硬幣上天平。由于這個(gè)數(shù)是奇數(shù)，所以只好把唯一一枚沒有嫌疑的硬幣也放上天平，這樣就確定了第一次比較的方案。 如果比較結(jié)果是“平衡”，那么我們就把嫌疑縮小到了 g(k1)個(gè)硬幣中，而且有了足夠的好硬幣，很容易通過 k1次比較把壞硬幣找出來。 最后的構(gòu)造 但假如比較結(jié)果是“不平衡”呢？此時(shí)，壞硬幣編號(hào)的熵為 log3k1，如果要在 k1次比較內(nèi)找出壞硬幣，那么此后每一次比較結(jié)果的熵都得是 log3。所以，這次比較得到三種結(jié)果的概率必須相等。 既然這樣，我們不妨來看看這次比較可能得到的三種結(jié)果都意味著什么。 最后的構(gòu)造 ?和第一次比較相同 說明兩次比較中壞硬幣在天平同側(cè)。 ?和第一次比較不同 說明兩次比較中壞硬幣在天平異側(cè)。 ?平衡 說明第二次比較中壞硬幣沒上天平。 最后的構(gòu)造 因?yàn)檫@三種情況出現(xiàn)的概率相同且必居其一。所以第二次比較時(shí)，相對(duì)于第一次比較，有 3k2枚嫌疑硬幣保持原位， 3k2枚嫌疑硬幣換到了另一側(cè)， 3k2枚嫌疑硬幣換成了好硬幣。而原來那枚好硬幣，為了保持天平兩邊硬幣數(shù)相等，也只好換到另一側(cè)。這樣，第二次比較的方案也被唯一確定了。 稍加分析不難得出后面的步驟。但由于整個(gè)過程的形式化描述過于繁瑣，故這里不再贅述。 最后的構(gòu)造 構(gòu)造完畢！ 問題的解決 就這樣，在信息論的幫助下，這個(gè)困擾了我兩年的問題終于解決了。雖然這道題的重點(diǎn)在構(gòu)造而不是信息論，但信息論在證明解法的最優(yōu)性時(shí)是十分必要的，而且，信息論的分析也在本題如理亂麻的構(gòu)造過程中起著關(guān)鍵性的指導(dǎo)作用。 總結(jié) 細(xì)心的讀者應(yīng)該會(huì)注意到，本文中的例題不用信息論的知識(shí)都可以解決。那么，信息論在這里的意義是什么呢？實(shí)際上，作為一種純粹的理論，信息論是一種可以用來對(duì)一類問題進(jìn)行分析的工具。它可以為我們的解法提供強(qiáng)有力的理論依據(jù)，更可以通過估計(jì)上下界來指導(dǎo)解法的構(gòu)造。綜上所述，信息論在信息學(xué)競賽中是大有用武之地的。 謝謝大家 !
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1