算法设计与分析作业.doc

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

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

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

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

4、main(){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、MAX;f_x=func(x);if(y0)cnt++;if(y<0&&y>f_x)cnt--;}cout<<36.0*cnt/n<

6、[H(n)]=nI，D[H(n)]=nI(1-I)，利用切比雪夫不等式：由于，则，因此．5．用上述算法，估计整数子集1~n的大小，并分析n对估计值的影响。解：运行代码：#include#include#include#include#includeusingnamespacestd;#defineN#definePI3.intmain(){random_devicerd;uniform_int_distribution

7、<>dist(1,N);longlongnumber=dist(rd);doublecount=0;setmyset;for(inti=0;i<50;i++){do{myset.insert(number);count++;number=dist(rd);}while(myset.find(number)==myset.end());myset.clear();}count/=50;longlongresult=(longlong)(2.0*count*count/PI);cout<<

8、result<