资源描述：
《算法设计——概率算法作业》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、算法设计——概率算法作业一．概率算法二．源代码——概率算法三．近似算法一.概率算法Ex1.若将y←uniform(0,1)改为y←x,则上述的算法估计的值是什么？答：k/n表示飞镖进入某一个区域内的概率，返回的值为4k/n。因为：x←uniform(0,1)，y←x，在x和y满足x2+y2≤1时k++所以：当x<=√2/2时k++。k/n表示在总的n次中k自加的概率，这个概率就等价为x<=√2/2的概率。而x在[0,1]之间→x<=√2/2的概率就为√2/2，即k/n=√2/2。所以：此时返回值4k/n=2√2
2、。Ex2.在机器上用估计π值，给出不同的n值及精度。原理：f(x)=√(1-x^2)，先使用概率算法求数字积分，之后将积分结果乘以4即为PI值。输入：实验要使用的取值在[0,1]范围内的总点数执行结果截图：Ex3.设a,b,c和d是实数，且a≤b,c≤d,f:[a,b]→[c,d]是一个连续函数，写一概率算法计算积分：注意，函数的参数是a,b,c,d,n和f,其中f用函数指针实现，请选一连续函数做实验，并给出实验结果。算法使用的连续函数为：f(x)=x+4.0输入：横坐标的范围[4,8]，纵坐标的范围[0,12
3、]（产生的点的纵坐标是[0,12]，函数值域为[8,12]）。执行结果截图：EX4.用上述算法，估计整数子集1~n的大小，并分析n对估计值的影响。算法分析：不断从X={1,2,3，……n}中有放回的随机抽样，直到首次抽出重复元素为止，此时已经抽到的元素数目为K，则集合X的大小为：2K^2/PI。算法的执行结果：分析：在理论上当集合n越大时，估计集合大小的误差应该越小。但是可能是由于随机函数性能的问题，试验结果是随着n的增大，误差却越来越大。Ex5.分析dlogRH的工作原理，指出该算法相应的u和v解：算法首先使
4、用函数u(a,b)将a随机化为c，之后使用确定性算法dlog(g,p,c)计算出随机化后的输入实例的计算结果y，最后使用函数v(y,r)将y恢复为以a为输入实例的计算结果。Steps：1.产生一个随机值b2.u(a,b)=bamodp=c3.dlog(g,p,c)=logg,p(c)=y4.v(y,r)=(y-r)mod(p-1)=ss即为dlog(g,p,a)的值。原理解释：因为logg,p(c)=logg,p(abmodp)=[logg,p(a)+logg,p(b)]mod(p-1)y=[logg,p(a)
5、+logg,p(g^rmodp)]mod(p-1)y=[logg,p(a)+r)]mod(p-1)(0<=r<=p-2)logg,p(a)为输入实例为a的确定性算法的结果（即s）：s=logg,p(a)=(y-r)mod(p-1)，而(y-r)mod(p-1)即为函数v(y,r)。使用u(a,b)=bamodp将a随机化为c，之后使用v(y,r)=(y-r)mod(p-1)可以将y恢复为s，所以v和u可以实现：将输入实例a随机化为c之后，把以c为输入的确定性算法的结果恢复为以a为输入时确定性算法的结果。Ex6.
6、写一Sherwood算法C，与算法A,B,D比较，给出实验结果。算法C：由于算法B是一个确定性算法（在[1,√n]中找小于等于x的最大的y），所以将算法B修改为一个随机算法。修改方法为：将从确定的区间[1,√n]中找y，更改为在[1,n]中随机取出√n个值，在这√n值中找y。之后再使用确定性算法Search(x,y)查找x。修改方法的正确性说明：因为“若将val[1..n]中的n个整数看作是均匀随机分布的，则在val[1..L]中求y值就相当于：在n个整数中，随机地取L个整数，求这L个整数中不大于x的最大整数y
7、。”所以在数组val的子区间[1,√n]中寻找一个y就等价于在整个[1,n]中先选出√n个值、再在这些值中找一y。因此将算法B中的在[1,√n]中找y--->在[1,n]中随机取出√n个整数，在这√n个整数中找y，是正确的。算法设计：在一个已知的静态链表（其中每一个表项的含义是{data,rank}）array[NUM]={{5,1},{7,8},{3,4},{0,2},{4,0},{11,7},{17,9},{14,6},{9,5},{20,10},{21,12},{25,13},{23,11},{30,15
8、},{34,-1},{31,14}}中，分别使用A、B、C、D算法查找11的位置。算法的执行结果：Ex7.证明：当放置（k+1)th皇后时，若有多个位置是开放的,则算法QueensLV选中其中任一位置的概率相等。证：设k+1行皇后共找到M个open位置，则最后放入Mth位置的p=1/M；最后放入（M-1）的p为：在Mth不取到1&&在(M-1)th取到1，p=1/(M-1)*(1-1/
