算法合集之信息學(xué)競賽中概率問題求解初探(已修改)
2025-10-25 18:36 本頁面
【正文】 1 22 走進(jìn)概率的世界 ——信息學(xué)競賽中概率問題求解初探 安徽省合肥一中 梅詩珂 2 22 引言 ?算法設(shè)計(jì)中很多問題的解決都用到了概率分析 ?一個(gè)大家熟知的例子是，快速排序中通過隨機(jī)選擇劃分點(diǎn)而使極端情況出現(xiàn)的概率大大減小 ?在信息學(xué)競賽中，與概率有關(guān)的問題占據(jù)著相當(dāng)?shù)姆至? ?在 05， 06， 08年的 NOI中都出現(xiàn)了與概率有關(guān)的試題 3 22 全文總覽 樣本空間 隨機(jī)變量 離散型隨機(jī)變量 連續(xù)型隨機(jī)變量 UVA Randomness SRM 349 LastMarble SPOJ RNG SGU Random Shooting 4 22 要用到的定義 ?連續(xù)型隨機(jī)變量的概率分布 ? 設(shè)有隨機(jī)變量 X， 稱 F(x) =P(X≤x) 為 X的概率分布函數(shù)，如果有非負(fù)可積函數(shù) f(x) 使 成立，則稱 f(x) 是 X的概率密度函數(shù) ?均勻分布 ?若隨機(jī)變量 X 在 [a,b]上等概率地取每個(gè)值，稱 X 在[a,b]上均勻分布，由概率密度的定義知 ? ??? x dttfxF )()(abxf ??1)( )( bxa ??5 22 SPOJ RNG ? 題目大意 ?有 N個(gè)隨機(jī)數(shù)生成器，第 i個(gè)等概率地返回 [0,Ri]中的一個(gè)實(shí)數(shù) (1 ≤ i ≤ N) ?問所有隨機(jī)生成數(shù)的和小于等于 b的概率是多少 ?約束條件 ? N、 Ri都是范圍在 1到 10內(nèi)的正整數(shù) (1 ≤ i ≤ N) 6 22 題意分析 ?第 i個(gè)隨機(jī)數(shù)生成器返回的值是一個(gè)在[0,Ri]中均勻分布的連續(xù)型隨機(jī)變量 ?不妨設(shè)為 Xi，顯然這 N 個(gè)隨機(jī)變量是互相獨(dú)立的 (1≤i≤N ) ?它們的和，即 X1+X2+… +XN，也是一個(gè)隨機(jī)變量，不妨設(shè)為 S ?那么 S≤b 的概率
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1