算法设计与分析

算法设计与分析作业-周徐达-SA130110422.1值计算EX1.若将y←uniform(0,1)改为y←x,则上述的算法估计的值是什么？若将y←uniform(0,1)改为y←x，则2.2数字积分EX2.在机器上用估计π值，给出不同的n值及精度。实验代码#includectime#includestdio.h#includecstdlib#includemath.h#defineN1000000voidHitorMiss(){doublex,y,f_x;inti,k=0;for(i=0;iN;i++){x=(double)rand()/(double)(RAND_MAX);y=(double)rand()/(double)(RAND_MAX);f_x=sqrt(1-x*x);if(yf_x)k++;}printf(%6f\n,4*(double)k/N);}P=4∗=212√2‾‾√4dx∫101−x2‾‾‾‾‾‾√intmain(){srand(time(NULL));HitorMiss();system(pause);}实验结果n结果结果精度精度10000003.1423483位位100000003.1412094位位1000000003.1413714位位10000000003.1415305位位EX3设设a,b,c和和d是实数，且是实数，且a≤b,c≤d,f:[a,b]→[c,d]是一个连续函数，写一概率算法计算是一个连续函数，写一概率算法计算积分积分注意，函数的参数是注意，函数的参数是a,b,c,d,n和和f,其中其中f用函数指针实现，请选一连续函数做实验，并给用函数指针实现，请选一连续函数做实验，并给出实验结果。出实验结果。实验代码#includectime#includeiostream#includecstdlib#includemath.husingnamespacestd;/*MC积分函数*/voidMC(doublea,doubleb,doublec,doubled,double(*func)(double));/*测试函数1*/doubletest1(doublex);/*测试函数2*/doubletest2(doublex);intmain(){srand(time(NULL));MC(0,4,-1,8,test1);f(x)dx∫baMC(-1,1,-1,1,test2);system(pause);}voidMC(doublea,doubleb,doublec,doubled,double(*func)(double)){inti,k=0,n=1000000;doublex,y,f_x;for(i=0;in;i++){x=a+(b-a)*(double)rand()/(double)(RAND_MAX);y=c+(d-c)*(double)rand()/(double)(RAND_MAX);f_x=func(x);if(yf_x&&y0)k++;if(y0&&yf_x)k--;}printf(%6f\n,(double)k*36/n);}doubletest1(doublex){return(x*x-2*x);}doubletest2(doublex){return(x);}实验结果：ntest1结果结果test2结果结果精度精度100000005.329416-0.03484821000000005.3325340.001925310000000003.333830.0000914EX4.若是的正确值，是由HitorMiss算法返回的值，则当时有:解答过程If(x)dx∫10hn≥I(1−I)/δε2Prob[h−Iε]≥1–δ∣∣∣∣证明证明:任取任取,表示表示次命中的次数，则次命中的次数，则为一个二项分布为一个二项分布,由切比雪夫不等式由切比雪夫不等式因为因为所以所以所以所以2.3概率算法EX.用上述算法，估计整数子集1~n的大小，并分析n对估计值的影响。实验代码#includeiostream#includecstdlib#includeset#includerandomusingnamespacestd;#defineN1000000#definepi3.1415926intmain(){random_devicerd;mt19937engine(rd);uniform_int_distributiondist(1,N);inti=0,number=dist(engine);doublecount=0;setintmyset;for(i=0;i50;i++){do{myset.insert(number);count++;number=dist(engine);n≥I(1−I)/δε2H(n)nH(n)=nhE[H(n)]=nID[H(n)]=nI(1−I)Prob[h−Iε]=Prob[−E()ε]∣∣∣∣∣∣H(n)nH(n)n∣∣≥1−=1−=1−=1−D()H(n)nε2D(H(n)ε2n2nI(1−I)ε2n2I(1−I)nε2n≥I(1−I)δε2≤δI(1−I)nε2Prob[h−Iε]≥1–δ∣∣∣∣}while(myset.find(number)==myset.end());myset.clear();}count/=50;printf(%f\n,2.0*count*count/pi);system(pause);}实验结果n估计值估计值误差误差1000098451.2%1000001079267.9%10000009265987.4%10000000102369092.3%1000000001037062003.7%结论算法在算法在N较大时效果更加明显，误差更加小，性能更加优越较大时效果更加明显，误差更加小，性能更加优越3.2随机数的预处理EX.分析dlogRH的工作原理，指出该算法相应的u和v解：解：dlogRH采用了采用了Sherwood算法进行随机化的预处理算法进行随机化的预处理dlogRH(g,a,p){//Sherwood算法r←uniform(0..p-2);b←ModularExponent(g,r,p);//求幂模b=grmodp，随机取出一个元素c←bamodp;//((grmodp)(gxmodp))modp=gr+xmodp=c,将实例X转化为实例Yy←logg,pc;//使用确定性算法求logp,gc,y=r+xreturn(y-r)mod(p-1);//将解变为X的实例}算法的算法的u为为算法的算法的v为为((modp)(modp))modp=modp=cgrgxgr+x(lo(st)modp)=(los+lot)mod(p−1)gp,ggp,ggp,g3.3搜索有序表Ex.写一Sherwood算法C，与算法A,B,D比较，给出实验结果。实验代码#includeiostream#includecmath#includerandom#includecstdlibusingnamespacestd;#definetarget1intn=15,head=7;intval[15]={2,5,10,7,4,14,8,1,9,6,11,13,12,15,3};intptr[15]={14,9,10,6,1,13,8,0,2,3,12,5,11,100,4};intsearch(intx,inti);intA(intx);//确定性O(n)算法intB(intx);//时间为O(√n)的确定性算法intC(intx);//在算法B基础上改进的sherwood算法intD(intx);//时间为O(n)的概率算法intmain(){coutA(target)endl;coutB(target)endl;coutC(target)endl;coutD(target)endl;system(pause);}intsearch(intx,inti){intcount=0;while(xval[i]){count++;i=ptr[i];}returncount;}intA(intx){returnsearch(x,head);}intB(intx){inti=head;intmax=val[i];inty;for(intj=0;jsqrt(float(n));j++){y=val[j];if(maxy&&y=x){max=y;i=j;}}return(search(x,i)+(int)sqrt((float)n));}intC(intx){random_devicerd;mt19937engine(rd);uniform_int_distributiondist(0,n-1);inti=dist(engine);intmax=val[i];inty;for(intj=0;jsqrt(float(n));j++){inttemp=dist(engine);y=val[temp];if(maxy&&y=x){max=y;i=temp;}}returnsearch(x,i)+(int)sqrt((float)n);}intD(intx){random_devicerd;mt19937engine(rd);uniform_int_distributiondist(0,n-1);inti=dist(engine);inty=val[i];if(xy)returnsearch(x,head);elseif(xy)returnsearch(x,ptr[i]);elsereturni;}实验结果查找对象查找对象A算法比较次数算法比较次数B算法比较次数算法比较次数C算法比较次数算法比较次数D算法比较次数算法比较次数103302133132431435535433465430763368743798538109333111044101211546131263914137341514859均值均值74.534.24.67结论：性能方面结论：性能方面CBDA4.1八皇后问题Ex.证明：当放置（k+1)th皇后时，若有多个位置是开放的,则算法QueensLV选中其中任一位置的概率相等。证明：假设放置证明：假设放置(k+1)个皇后时，有个皇后时，有nb个位置是开放，分别记为个位置是开放，分别记为a,b…i…nb那么第那么第a个位置被选到的概率为个位置被选到的概率为第第b个位置被选到的概率为个位置被选到的概率为第第i个位置被选到的概率为个位置被选到的概率为第第nb个位置被选到的概率为个位置被选到的概率为所以算法所以算法QueensLV选中其中任一位置的概率相等，均为选中其中任一位置的概率相等，均为Ex.写一算法，求n=12~20时最优的StepVegas值。代码部分#includestdio.h#includecmath#includecstdlib#includerandom#includetime.husingnamespacestd;#defineN12#defineRUN_TIME100intx[N+1]={0};boolplace(intk);//ÅжϵÚK¸ö»ÊºóÊÇ·ñ·ÅÖÃÕýÈ·voidbacktrace(intstep);//»ØËÝ·¨intQueenLv(intStepVegas);//LVËã·¨intmain(void){intStepVegas,time_now,time_end;for(StepVegas=1;StepVegas=N;StepVegas++){inti,j=0,sucess=0;time_now=clock();do{while(!QueenLv(StepVegas));backtrace(StepVegas+1);if(x[N]!=0