清华大学出版社 TSINGHUA UNIVERSITY PRESS 第7章概率算法
1 第7章 概率算法
清华大学出版社 随机数 VERSITY PRESS 随机数在概率算法设计中扮演着十分重要的角色。在现实计算机 上无法产生真正的随机数,因此在概率算法中使用的陌随机数都是 定程度上随机的,即伪随机数 线性同余法是产生伪随机数的最常用的方法。由线性同余法产生 的随机序列a,a1,an满足 an=(ba,- +c)mod m n=1, 2 其中b0,c≥0,d≤m。d称为该随机序列的种子。如何选取该 方法中的常数b、c和m直接关系到所产生的随机序列的随机性 能。这是随机性理论研究的内容,已超出本书讨论的范围。从 直观上看,m应取得充分大,因此可取m为机器大数,另外应 取gcd(m,b)=1,因此可取b为一素数。 2
2 随机数 随机数在概率算法设计中扮演着十分重要的角色。在现实计算机 上无法产生真正的随机数，因此在概率算法中使用的随机数都是 一定程度上随机的，即伪随机数。 线性同余法是产生伪随机数的最常用的方法。由线性同余法产生 的随机序列a0 ,a1 ,…,an满足 = + = = ( −1 )mod 1,2, 0 a ba c m n a d n n 其中b0，c0，dm。d称为该随机序列的种子。如何选取该 方法中的常数b、c和m直接关系到所产生的随机序列的随机性 能。这是随机性理论研究的内容，已超出本书讨论的范围。从 直观上看，m应取得充分大，因此可取m为机器大数，另外应 取gcd(m,b)=1，因此可取b为一素数
清华大学出版社 TSINGHUA UNIVERSITY PRESS 数值概率算法
3 数值概率算法
清华大学出版社 用随机投点法讦算元值 设有一半径为r的圆及其外切四边形。向该正方形随机地投掷n个 点。设落入圆内的点数为k。由于所投入的点在正方形上均匀分 布,因而所投入的点落入圆内的概率为=x。所以当n足够大 4k 时,k与n之比就逼近这一概率。从而丌 public static double darts(int n) ∥用随机投点法计算π值 int k=0 for(int i=1; i <=n; i++)i double dart. fRandomo double y=dart. fRandomO if((X*X+y*y)<=1k++; return 4 k/double)n 4
4 用随机投点法计算值 设有一半径为r的圆及其外切四边形。向该正方形随机地投掷n个 点。设落入圆内的点数为k。由于所投入的点在正方形上均匀分 布，因而所投入的点落入圆内的概率为 。所以当n足够大 时，k与n之比就逼近这一概率。从而 。 4 4 2 2 = r r n 4k public static double darts(int n) { // 用随机投点法计算值 int k=0; for (int i=1;i <=n;i++) { double x=dart.fRandom(); double y=dart.fRandom(); if ((x*x+y*y)<=1) k++; } return 4*k/(double)n; }
清华大学出版社 计算定积分 IY PRESS 设印(x)是[0,1上的连续函数,且0≤f(x)≤1。 需要计算的积分为/=「(x)积分等于图中的面积G 0 y=f(x) 在图所示单位正方形内均匀地作投点试验,则随机点落在曲线下 面的概率为 P{y≤f(x)=「∫dak=∫f(xk 假设向单位正方形内随机地投入n个点(x,y)。如果有m个点落入 G内,则随机点落入G内的概率Ⅰ≈
5 计算定积分 设f(x)是[0，1]上的连续函数，且0f(x)1。 需要计算的积分为 = ,积分I等于图中的面积G。 1 0 I f (x)dx 在图所示单位正方形内均匀地作投点试验，则随机点落在曲线下 面的概率为 假设向单位正方形内随机地投入n个点(xi,yi)。如果有m个点落入 G内，则随机点落入G内的概率 = = 1 0 ( ) 0 1 0 { ( )} ( ) f x Pr y f x dydx f x dx n m I