算法设计与分析作业.docx

《算法设计与分析作业.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法设计与分析徐玥SA一、概率算法部分1.求π近似值的算法：若将y←uniform(0,1)改为y←x,则上述的算法估计的值是什么？解：改为y←x，最终值为4×12=22.2.在机器上用4011-x2dx估计π值，给出不同的n值及精度。解：运行代码：#include#include#include#include#defineNusingnamespacestd;voidHitorMiss(){doublex,y,f_x;intcnt

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

3、43.1416343.1415753．设a,b,c和d是实数，且a≤b,c≤d,f:[a,b]→[c,d]是一个连续函数，写一概率算法计算积分：abfxdx．解：运行代码：#include#include#include#includeusingnamespacestd;//MC积分函数voidMC(doublea,doubleb,doublec,doubled,double(*func)(double));//测试函数doublet

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

5、e)rand()/RAND_MAX;f_x=func(x);if(y0)cnt++;if(y<0&&y>f_x)cnt--;}cout<<36.0*cnt/n<

6、<ε≥1-δ．解：任取n≥I(1-I)ε2δ，设H(n)为n次命中的次数，则H(n)=nh为一个二项分布E[H(n)]=nI，D[H(n)]=nI(1-I)，利用切比雪夫不等式：Probh-I<ε=ProbHnn-EHnn<ε≥1-DHnnε2=1-DHnε2n2=1-I(1-I)nε2由于n≥I(1-I)ε2δ，则I(1-I)nε2≤δ，因此Probh-I<ϵ≥1-δ．5．用上述算法，估计整数子集1~n的大小，并分析n对估计值的影响。解：运行代码：#include#include

7、et>#include#include#includeusingnamespacestd;#defineN#definePI3.intmain(){random_devicerd;uniform_int_distribution<>dist(1,N);longlongnumber=dist(rd);doublecount=0;setmyset;for(inti=0;i<50;i++){do{myset.insert(number);co

8、unt++;number=dist(rd);}while(myset.find(number)==myset.end());myset.clear();}count/=50;longlongresult=(longlong)(2.0*count*count/PI);cout<