算法的基本设计方法--数字模拟法

数字模拟法也称数字仿真。
　　在自然界和日常生活中，许多现象带有不确定的性质，有此问题甚至很难建立数学模型。寻这类实际问题很难建立列举、递推、递归或回溯等算法，通常采用模拟法。通过采用模拟法。通过编制程序，利用数字计算机进行模拟。在对实际问题中的随机现象进行数字模拟时，通常用计算机产生的随机数来表示。由于计算机产生的随机数总是要受有效数字位数的限制，其随机的意义要比实际问题中真实有随机变量差一些。因此，计算机产生的随机数称为伪随机数。
　　产生随机数最常用的方法是在区间[0,1]上生成均匀分布的随机数，然后利用这种分布再产生模拟其它分布(如正态分布、指数分布等)的随机数。而产生均匀分布的随机数通常用线性同余法，其计算公式为
　　　x=mod(j*x+k,m)
其中x取值于0--(m-1)之部。m越大，其随机性质越好，且x取不同的初值，就可以产生不同的随机数序列。如果要产生0--1之间的随机数，则只要令y=x/m即可。例如，在上述公式中的参数可取j=2053,k=13849,m=2∧16。下在是产生0--1之间均匀分布的随机数的算法。
　　算法一：产生0--1之间均匀分布的随机数。
　　输入：x为随机数种子。第一次调用过程给出初值，以后由过程自动返回循环使用。
　　输出：0--1之间的一个随机数y，循环使用的种子值x。
　　PROCEDURE　ARND(x,y)
x←mod(2503*x+13849,2∧16)
y←x/2∧16
RETURN
下面的例子是利用随机数计算定积分。
　　例：用蒙特卡洛(Monte Carlo)法计算定积分
　　　　S＝∫f(x)d(x)
不失一般性，假设a<b,0<f(x)<d,其中d max[f(x)],x [a,b],如图所示。
蒙特卡洛法计算定积分的基本思想是：产生n(n足够大)个均匀分布的长方形ABCD上的随机数点(x1,y1),其中x1为均匀分布在区间[a,b]上的随机数，y1为均匀分布在区间[0,d]上的随机数。设其中落中曲边梯形ABEF上的随机数点数为m，则曲边梯形的面积(即定积分值S)为
S=(m/n)(b-a)d
　　其算法如下。
　　算法二：蒙特卡洛法计算定积分。
　　输入：积分上、下限b、a;d≥max[f(x)];随机数点个数n。
　　输出：定积分值S。
　　PROCEDURE　AMONCAR(z,b,d,n,S)
m←0;i=1
FOR i=1 TO n DO
{ ARND(t,x);x←a+(b-a)*x
ARND(t,y);y←d*y
IF y<f(x) THEN m←m+1
}
S←Dm*(b-a)*d/n
OUTPUT S
RETURN
在算法二中，需要调用由算法一提供的产生01之间均匀分布的随机数的过程ARND。只要n足够大，用蒙卡洛法计算得到的定积分近似值的近似程度是比较好的。而且，这种方法特别适用于计算多重积分。