算法合集之信息論在信息學(xué)競(jìng)賽中的簡(jiǎn)單應(yīng)用-文庫(kù)吧在線文庫(kù)
【正文】 態(tài)共有 8種可能情況，假設(shè)它們是等概率的。 ?通過(guò)它可以很方便地得到某些交互式問(wèn)題的一個(gè)較好的步數(shù)下界 (“ 信息論下界” ) 讓我們先來(lái)看一些信息論的基本理論 理論基礎(chǔ) ?定義：如果一個(gè)隨機(jī)變量 x共有 n種取值，概率分別為 p0,p2,......,pn，則其熵為H(x)=f(p0,p2,......,pn)=∑Cpilogpi ?定理 1：在得到關(guān)于隨機(jī)變量 x的一個(gè)熵為 h的信息后， x的熵將會(huì)減少 h。(x)是多少？ 解答 3： 此時(shí)貓的只數(shù)為 0,1,2,3的四種情況的概率依次是 (1/8,3/8,3/8,1/8)，而每種情況的熵分別為(0,log3,log3,0)，所以此時(shí) H39。 圖 1 例 2： Rods(IOI2021) 兩個(gè) Rod可能有公共方格，比如在圖 1中，方格（ 4， 4）無(wú)法確定是僅屬于 1個(gè) Rod還是同時(shí)屬于兩個(gè) Rod。 例 2： Rods(IOI2021) 圖 1 比賽時(shí)我很快想到了一個(gè)最多調(diào)用 rect函數(shù) 6log2n+C（某個(gè)常數(shù)）次的方法，但是因?yàn)檫@個(gè)數(shù)差不多剛好達(dá)到 100，所以我在這時(shí)就開(kāi)始試圖優(yōu)化上式中 log2n的系數(shù)，結(jié)果徒勞無(wú)功，反而耽誤了時(shí)間。 輸入 n和 k，如果能在 k此比較中找到 n枚硬幣中的哪枚為壞的，就輸出 39。 現(xiàn)在，有了信息論的武器，這個(gè)遺憾終于得到了解決 ! ？ 初步分析 首先，對(duì)硬幣用 1到 n進(jìn)行編號(hào)，設(shè)壞硬幣的編號(hào)為 x。 不過(guò)，轉(zhuǎn)化之后的問(wèn)題仍然難以解決，一枚好硬幣實(shí)在太少，因此，不妨先將原問(wèn)題“放大”一下，考慮一下有無(wú)窮枚好硬幣的情形。 ?好球較輕：說(shuō)明壞硬幣就在這些硬幣中，且較重，由上文結(jié)論，可以在 k1步內(nèi)找出。所以，這次比較得到三種結(jié)果的概率必須相等。這樣，第二次比較的方案也被唯一確定了。綜上所述，信息論在信息學(xué)競(jìng)賽中是大有用武之地的。雖然這道題的重點(diǎn)在構(gòu)造而不是信息論，但信息論在證明解法的最優(yōu)性時(shí)是十分必要的，而且，信息論的分析也在本題如理亂麻的構(gòu)造過(guò)程中起著關(guān)鍵性的指導(dǎo)作用。 ?平衡 說(shuō)明第二次比較中壞硬幣沒(méi)上天平。 下面進(jìn)行構(gòu)造證明 最后的構(gòu)造 根據(jù)計(jì)算 g(k)時(shí)的推理，第一次比較應(yīng)該有 3k1枚“有嫌疑”的硬幣上天平。 當(dāng) k1時(shí)：考慮第一次比較，設(shè) t為這次沒(méi)上天平的尚未確定好壞的硬幣的個(gè)數(shù)，下
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1