有关概率和期望问题的研究

《有关概率和期望问题的研究》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、有关概率和期望问题的研究河北唐山一中鬲融摘要在各类信息学竞赛中（尤其是ACM竞赛中），经常出现一些与概率和期望有关的题目。这类题目需要较高的数学水平和一定的算法技巧，必须经过仔细分析，选择合适的数学模型和算法才能顺利的解决问题。本文就对这类题目的一些常见方法进行了研究。数学基础这里写的数学基础是有关概率和期望的一点简单的计算法则，虽然我们都很熟悉，但是有时也可能会忘记使用，所以在这里列出来，也作为以后内容的基础。概率的运算Ø两个互斥事件，发生任一个的概率等于两个事件的概率和Ø对于不相关的事件或者分步进行的事件，可以使用乘法原则。Ø对于一般情况p(A+B)=p(A)+

2、p(B)-p(AB)期望的运算ØE(φ)=ΣφiPi，这是期望的定义，其中φi是一个取值，而Pi是取这个值的概率Ø期望有“线性”，也就是说对于不相关的两个随机变量φ和ξ，E(φ±ξ)=E(φ)±E(ξ)；E(φξ)=E(φ)E(ξ)；E(φ/ξ)=E(φ)/E(ξ)Ø在某些情况下，期望可以表示成一个无穷的等比数列，然后利用极限的思想来求。当然，这些只是最基础的知识，要解决好概率和期望的问题，还需要掌握一些组合数学的知识。常用方法方法1直接计算这种方法说起来很简单，就是推导出一个数学公式，然后通过程序来计算这个式子的值。这样的题目在与概率和期望有关的题目中比例不小，但

3、是由于它们大都需要一定的组合数学基础，而一旦推导出公式，对算法的要求并不太高，而时间复杂度往往也比较低，所以这类问题不是本文的重点。有关内容可以在任何一本组合数学书中学到。例一百事世界杯之旅题目来源SHTSC2002Day1Prob2“……在2003年6月之前购买的百事任何饮料的瓶盖上都会有一个百事球星的名字。只要凑齐所有百事球星的名字，就可以参加百事世界杯之旅的抽奖活动，获取球星背包、随身听，更可以赴日韩观看世界杯。还不赶快行动！……”你关上电视，心想：假设有n个不同球星的名字，每个名字出现的概率相同，平均需要买几瓶饮料才能凑齐所有的名字呢？输入输出要求输入一个数

4、字n，2≤n≤33，表示不同球星名字的个数。输出凑齐所有的名字平均需要购买的饮料瓶数。如果是一个整数则直接输出。否则就用下面样例中的格式分别输出整数部分和小数部分。分数必须是不可约的。样例输入和输出输入输出235511—121734046358------720720分析这是一道比较简单的概率和期望问题。只要确定好计算方法，就可以很容易的得到公式。如果单独考虑每一名球星，那么就中了命题人的圈套。因为考虑单独的一个球星的时候所买的“没用”的饮料在考虑其他球星的时候可能会变成有用的。正确的思路是，假设现在已经有k个球星的名字，那么要使球星的名字达到k+1个平均需要买多少

5、瓶饮料？这是很容易计算的，是。所以我们从没有球星的名字开始，直到把所有的球星名字都凑齐，平均需要的饮料数(E)就可以计算出来：由于题目的数据规模并不大，所以可以直接使用PASCAL的Comp或Int64(C/C++的longlong)进行计算。而题目要求得到即约分数，只要在计算的时候使用分数并注意约分就可以了。方法2动态规划动态规划是一种应用范围很广的方法，由于概率和期望具有前面提到过的一些性质（特别是期望的定义以及期望的“线性”性质），使我们可以在概率和期望之间建立一定的递推关系，这样就可以通过动态规划来解决一些概率问题。与其他方面的动态规划一样，合理的选择状态以

6、及高效的状态转移方程是应用这种方法的关键，而状态的选择在这类问题中尤为重要。选择合适的状态不仅可以提高效率，而且可以保证动态规划所必须的无后效性。而动态规划的各种优化方法也可以应用。概率和期望的最值问题也往往使用动态规划的方法来解决。例二多米诺骨牌题目来源UVA10529你试图把一些多米诺骨牌排成直线，然后推倒它们。但是如果你在放骨牌的时候不小心把刚放的骨牌碰倒了，它就会把相临的一串骨牌全都碰倒，而你的工作也被部分的破坏了。比如你已经把骨牌摆成了DD__DxDDD_D的形状，而想要在x这个位置再放一块骨牌。它可能会把左边的一块骨牌或右边的三块骨牌碰倒，而你将不得不重

7、新摆放这些骨牌。这种失误是无法避免的，但是你可以应用一种特殊的放骨牌方法来使骨牌更多的向一个方向倒下。给出你要摆放的骨牌数目，以及放骨牌时它向左和向右倒的概率，计算你为完成任务摆放的骨牌数目的平均数。假设你使用了最佳的摆放策略。输入将包含至多100个测试点，每个测试点占一行，包含需要摆放的骨牌数目n(1≤n≤1000)，以及两个非负实数Pl,Pr，表示骨牌向左和向右倒的概率。保证1＜Pl+Pr≤0.5。最后一个测试点包含一个数0。对于每个测试点输出题目要求的数目，保留两位小数。分析首先应该明确怎样找到最佳的摆放策略。我们可以考虑在位置i放最后一块骨牌。显然，i前