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