《算法合集之《浅析竞赛中一类数学期望问题的解决方法》》由会员分享，可在线阅读，更多相关《算法合集之《浅析竞赛中一类数学期望问题的解决方法》（17页珍藏版）》请在金锄头文库上搜索。
1、浅析竞赛中一类数学期望问题的浅析竞赛中一类数学期望问题的解决解决方法方法 福建省福州第八中学 汤可因 摘要摘要 期望在我们生活中有着十分广泛的应用， 而对于我们信息学奥赛也出现了不少求解期望值的问题。 本文对于竞赛中涉及求离散型随机变量的数学期望的题目所使用的常用方法归纳成为两大类，并进行了总结与分析。 关键字关键字 期望 递推 动态规划 方程组 目录目录 引言 . 3 预备知识 . 3 一、期望的数学定义 . 3 二、期望的线性性质 . 3 三、全概率公式 . 4 四、条件期望与全期望公式 . 4 一、利用递推或动态规划解决 . 4 例题一：聪聪与可可 . 5 分析 . 5 小结 . 6 例
2、题二：Highlander . 6 分析 . 6 小结 . 8 例题三：RedIsGood . 8 分析 . 8 小结 . 9 二、建立线性方程组解决 . 10 引入 . 10 分析 . 10 需要注意的地方 . 12 例题四：First Knight . 12 分析 . 12 例题五：Mario . 15 分析 . 15 总结 . 16 参考文献 . 17 引言引言 数学期望亦称为期望，期望值等，在概率论和统计学中，一个离散型随机变量的期望值是试验中每次可能结果的概率乘以其结果的总和。 而期望在我们生活中有着十分广泛的应用。例如要设计一个彩票或赌博游戏，目标为赢利，那么计算能得到的钱以及需要
3、付出的钱的期望，它们的差则需要大于 0。又例如对于是否进行一项投资的决策，可以通过分析总结得出可能的结果并估算出其概率，得到一个期望值而决定是否进行。期望也许与每一个结果都不相等，但是却是我们评估一个事情好坏的一种直观的表达。 正因为期望在生活中有如此之多的应用， 对于我们信息学奥赛也出现了不少求解期望值的问题。而其中大多数又均为求离散型随机变量的数学期望。 本文对于这类题目所会涉及到的常用方法进行了归纳，总结与分析。 预备知识预备知识 一、一、期望的期望的数学定义数学定义 如果 X 是一个离散的随机变量，输出值为 x1, x2, .， 和输出值相应的概率为 p1, p2, . （概率和为 1
4、）, 那么期望值 iiixpXE)(。 例如投掷一枚骰子，X 表示掷出的点数，P(X=1)，P(X=2)，P(X=6)均为61，那么5 . 36654321 616615614613612611)(XE。 二、期望的线性性质二、期望的线性性质 对于任意随机变量 X 和 Y 以及常量 a 和 b，有 E(aX + bY) = aE(X) + bE(Y) 当两个随机变量 X 和 Y 独立且各自都有一个已定义的期望时，有 E(XY) = E(X)E(Y) 三三、全概率公式、全概率公式 假设 Bn | n = 1, 2, 3, . 是一个概率空间的有限或者可数无限的分割， 且每个集合 Bn是一个可测集
5、合，则对任意事件 A 有全概率公式： nnnBPBAPAP)()|()( 其中 P(A | B)是 B 发生后 A 的条件概率 四四、条件期望与条件期望与全期望公式全期望公式 )21()(，jiyYxXPpjiij当 X=xi时，随机变量 Y 的条件数学期望以 E(Y | X=xi)表示。 全期望公式： )()|()()|(YEpyppypppypxXYExXPXYEEikikkikiik kiikiik kiiii 所以iiixXYExXPXYEEYE)|()()|()( 例如，一项工作由甲一个人完成，平均需要 4 小时，而乙有 0.4 的概率来帮忙，两个人完成平均只需要 3 小时。若用 X
6、 表示完成这项工作的人数，而 Y 表示完成的这项工作的期望时间（单位小时） ，由于这项工作要么由一个人完成，要么由两个人完成，那么这项工作完成的期望时间 E(Y) = P(X = 1)E(Y | X = 1) + P(X = 2)E(Y | X = 2) = (10.4)40.43 = 3.6。 一、利用一、利用递推递推或动态规划解决或动态规划解决 递推作为一种基础的算法，相信所有人都不会陌生。而对于一部分期望问题而言， 递推则为一种快速有效的方法。 我们不需要将所有可能的情况都枚举出来，而是根据已经求出的期望推出其它状态的期望， 亦或根据一些特点和结果相同的情况，求出其概率。 例题例题一一：聪聪：聪聪与与可可可可1 在一个魔法森林里，住着一只聪明的小猫聪聪和一
