國家集訓隊20xx論文集-侯啟明-展示頁
2025-08-03 03:36本頁面
【正文】 是多少？ 解答 1： 由于 8種情況的概率相等，所以： H(x)=f(1/8,1/8,1/8,1/8,1/8,1/8,1/8,1/8)=log8 問題 2： 我看一眼所得到的信息 y的熵是多少？ 解答 2： 由于貓的只數(shù)共有 0,1,2,3四種情況，概率分別為 (1/8,3/8,3/8,1/8)，所以： H(y)=f(1/8,3/8,3/8,1/8)=log86log3/8 例 1：驗證一下定理 1 問題 3： 我看完之后， x的熵 H39。因此，三只貓的狀態(tài)共有 8種可能情況，假設它們是等概率的。在那一帶棲息著三只渾身雪白，有著一只藍眼睛和一只綠眼睛的 —— 例 1：驗證一下定理 1 貓 ！ A B C 例 1：驗證一下定理 1 在天冷的時候，它們喜歡趴在樓內的暖氣上。 ?定理 2：當一個隨機變量的各種取值概率相等時，它的熵最大。在信息學競賽中的簡單應用 侯啟明 信息論簡介 ?信息論是關于信息的本質和傳輸規(guī)律的科學的理論。 ?通過它可以很方便地得到某些交互式問題的一個較好的步數(shù)下界 (“信息論下界” ) 讓我們先來看一些信息論的基本理論 理論基礎 ?定義：如果一個隨機變量 x共有 n種取值，概率分別為 p0,p2,......,pn，則其熵為H(x)=f(p0,p2,......,pn)=∑Cpilogpi ?定理 1：在得到關于隨機變量 x的一個熵為 h的信息后， x的熵將會減少 h。 這些理論看上去和某些題目關系密切，不是嗎？ 那么，具體應該如何運用呢？讓我們來看一些例子： 我們宿舍二樓到三樓之間樓梯的窗戶外面是相鄰的一個平房的房頂。于是，每只貓就有了兩種狀態(tài)：在屋內和在屋外。 現(xiàn)在，我在一樓的小賣部。(x)是多少？ 解答 3： 此時貓的只數(shù)為 0,1,2,3的四種情況的概率依次是 (1/8,3/8,3/8,1/8)，而每種情況的熵分別為(0,log3,log3,0)，所以此時 H39。(x)=1/8*0+3/8*log3+3/8*log3+1/8*0=6log3/8 可以發(fā)現(xiàn) H(x)=H(y)+H39。 定理 1得到了驗證。在一個 N*N的方陣中，放了水平和豎直兩個 Rod。 圖 1 例 2： Rods(IOI2022) 兩個 Rod可能有公共方格，比如在圖 1中，方格（ 4， 4）無法確定是僅屬于 1個 Rod
公司管理相關推薦
鄂ICP備17016276號-1