算法设计和分析作业.doc

《算法设计和分析作业.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、算法设计与分析徐坍SA18011072概率算法部分1.求兀近似值的算法：若将y—uniform(0,1)改为y—x,则上述的算法估计的值是什么？解：改为y-x,最终值为4x寺=2712.在机器上用4^7?二予〃尢估计n值，给出不同的门值及精度。解：运行代码：#include#include#include#include#defineN1000000usingnamespacestd;voidHitorMiss(){doublex,y,fix;intent=0;

2、srand((unsigned)time(NULL));for(inti=0;i

3、841000000003.14163410000000003.1415751.设a,b,c和d是实数，且a#include#include#includeusingnamespacestd;//MC积分函数voidMC(doublea,doubleb,doublec,doubled,double(*func)(double));//测试函数doubletest(

4、doublex);intmain(){MC(0,4,-1,8,test);system(MpauseH);return0;}voidMC(doublea,doubleb,doublec,doubled,double(*func)(double)){intent=0,n=100000000;doublex,y,fix;srand((unsigned)time(NULL));for(inti=0;i

5、AND_MAX;fix=func(x);if(y0)cnt++;if(y<0&&y>fLx)ent—;)cout«36-0*cnt/n«endl;}doubletest(doublex){returnx*x・2*x;}运行结果为:n值结果精度100005.50811000005.29668210000005.316122100000005.3359631000000005.33688310000000005.3339441.若I是J；f(x)dx的正确值，h是由HitorMiss算法返冋的值，则当nn芈尹时，有

6、:Prob[

7、h-111-6・解:任取n>罟，设H(n)为n次命中的次数，则H(n)二nh为一个二项分布E[H(n)]=nI,D[H(n)]=nl(l-I),利用切比雪夫不等式：Prob[

8、h—I

9、^,则罟S6,因此Prob[

10、h-I

11、1-5.1.用上述算法，估计整数子集1〜n的大小，并分析n对估计值的影响。解：运行代码：#include#include#include#include

12、ib>#includeusingnamespacestd;#defineN1000000#definePI3.1415926intmain(){random_devicerd;uniform_int_distributionv>dist(l,N);longlongnumber=dist(rd);doublecount=0;setmyset;for(inti=0;i<50;i++){do{myset.insert(number);count++;number=dist(rd);}while(myse

13、t.find(number)==myset.end());myset.clear();)count/=50;longlongresult=(longlong)(2.0*count*count/PI);cout«result«endl;cout«"err:t"«1.0*abs