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