算法设计与分析.doc

.Ex.1(p20) 若将y uniform(0, 1) 改为 y x, 则上述的算法估计的值是什么？解：若将y uniform(0, 1) 改为 y x，此时有2x21，则k+，即x(0,22，此时k+，由于此时x uniform(0, 1)，所以k/n=22，则此时4k/n=22。所以上述算法估计的值为22。Ex.2(p23) 在机器上用4011-x2dx估计值，给出不同的n值及精度。解：由ppt上p21可知，011-x2dx的大小s=kn，其中k为落入圆内的数目，n为总数，且=4011-x2dx，即需要计算4k/n。我们先令x uniform(0, 1)，y uniform(0, 1)。计算x2+y2的值，如果小于等于1，那么此时k+。最后计算4k/n的值即可估计此时的值。代码的主要部分为：执行结果为：结果分析：随着N的取值不断地增加，得到的值也就越来越精确。Ex.3(p23) 设a, b, c和d是实数，且a b, c d, f:a, b c, d是一个连续函数，写一概率算法计算积分：abfxdx注意，函数的参数是a, b, c, d, n和f, 其中f用函数指针实现，请选一连续函数做实验，并给出实验结果。解：abfxdx的值为y= fx，y=0，x=a，x=b围成的面积。根据之前的例子我们可以知道abfxdx = k(b-a)d/n。其中k是落在函数y= fx，x=a，x=b以及y=0所包围区间内的个数。代码的主要部分为：运行结果为：结果分析：随着N的取值不断地增加，得到的积分值越来越精确。Ex4(p24). 设,是(0,1)之间的常数，证明：若I是01f(x)dx的正确值，h是由HitorMiss算法返回的值，则当n I(1-I)/2时有：Prob|h-I| 1 上述的意义告诉我们：Prob|h-I| , 即：当n I(1-I)/ 2时，算法的计算结果的绝对误差超过的概率不超过，因此我们根据给定和可以确定算法迭代的次数 (I(1-I)14)解此问题时可用切比雪夫不等式，将I看作是数学期望。证明：由切比雪夫不等式可知：P( | X - E(X) | i，都有uniform(1,j)=0。且P(uniform(1,i)=1) = 1/i。P(uniform(1,j)=0) = (j-1)/j所以：Pi = (1/i * i/i+1 * * n-1/n) = 1/n即选择位置Si的概率为1/n，所以算法选中其中任意位置的概率相等。Ex9(p83). 写一算法，求n=1220时最优的StepVegas值。解：对于每个N，当stepVegas从1取到N，对于每一个stepVegas我们重复计算100次，使用一百次的平均成功率以及平均执行时间来描述此stepVegas的性能。算法的主要代码如下图所示：分别取N=12,13,14,20，对于每一个N，具体的执行结果如下图所示：当N=12时，结果如下如所示，从图中我们可以看出此时的最优stepVegas为4：当N=13时，结果如下如所示，从图中我们可以看出此时的最优stepVegas为4：当N=14时，结果如下如所示，从图中我们可以看出此时的最优stepVegas为4：当N=15时，结果如下如所示，从图中我们可以看出此时的最优stepVegas为5：当N=16时，结果如下如所示，从图中我们可以看出此时的最优stepVegas为6：当N=17时，结果如下如所示，从图中我们可以看出此时的最优stepVegas为6：当N=18时，结果如下如所示，从图中我们可以看出此时的最优stepVegas为7：当N=19时，结果如下如所示，从图中我们可以看出此时的最优stepVegas为7：当N=20时，结果如下如所示，从图中我们可以看出此时的最优stepVegas为8：结果分析：从结果中我们可以看出，当stepVegas取N的一半还小一点时，此时得到最优的stepVegas。此外，当N很大时，单独的使用回溯法虽然一定能够找到一个合法解，但是此时算法的执行时间较长，如果单独的使用概率算法来寻求一个合法解，此时算法的成功率很低，需要执行很多次才能找到一个合法解。为了解决这两种算法的弊端，我们采用将回溯法和概率算法结合起来的方式来避免这两种算法的弊端，实验结果也证明了这种结合的方法时高效的。Ex10(p147).PrintPrimes /打印1万以内的素数print 2，3；n 5；repeatif RepeatMillRab(n, lgn) then print n;n n+2;until n=10000;与确定性算法相比较，并给出10010000以内错误的比例。解：通过执行Miller Rabin算法来判定一个数是否为合数还是强伪素数或者素数，多次重复执行Miller Rabin算法可以大概率排除强伪素数的可能。具体的代码如下所示：当N取不同值时，即可计算出从1N之间的素数个数。当N=100