算法设计与分析作业

算法设计与分析徐玥SA18011072一、概率算法部分1.求π近似值的算法：若将y←uniform(0,1)改为y←x,则上述的算法估计的值是什么？解：改为y←x，最终值为4×1√2=2√2.2.在机器上用4∫√1−𝑥2𝑑𝑥10估计π值，给出不同的n值及精度。解：运行代码：#includectime#includecstdlib#includecmath#includeiostream#defineN1000000usingnamespacestd;voidHitorMiss(){doublex,y,f_x;intcnt=0;srand((unsigned)time(NULL));for(inti=0;iN;i++){x=(double)rand()/RAND_MAX;y=(double)rand()/RAND_MAX;f_x=sqrt(1-x*x);if(yf_x)cnt++;}cout4.0*cnt/Nendl;}intmain(){HitorMiss();system(pause);return0;}运行结果为：n值结果精度100003.173621000003.13676310000003.141613100000003.1410841000000003.14163410000000003.1415753．设a,b,c和d是实数，且a≤b,c≤d,f:[a,b]→[c,d]是一个连续函数，写一概率算法计算积分：∫𝑓(𝑥)𝑑𝑥𝑏𝑎．解：运行代码：#includectime#includecstdlib#includecmath#includeiostreamusingnamespacestd;//MC积分函数voidMC(doublea,doubleb,doublec,doubled,double(*func)(double));//测试函数doubletest(doublex);intmain(){MC(0,4,-1,8,test);system(pause);return0;}voidMC(doublea,doubleb,doublec,doubled,double(*func)(double)){intcnt=0,n=100000000;doublex,y,f_x;srand((unsigned)time(NULL));for(inti=0;in;i++){x=a+(b-a)*(double)rand()/RAND_MAX;y=c+(d-c)*(double)rand()/RAND_MAX;f_x=func(x);if(yf_x&&y0)cnt++;if(y0&&yf_x)cnt--;}cout36.0*cnt/nendl;}doubletest(doublex){returnx*x-2*x;}运行结果为：n值结果精度100005.50811000005.29668210000005.316122100000005.3359631000000005.33688310000000005.3339444．若I是∫𝑓(𝑥)𝑑𝑥10的正确值，h是由HitorMiss算法返回的值，则当n≥𝐼(1−𝐼)𝘀2𝛿时，有：Prob[|h−I|ε]≥1−δ．解：任取n≥𝐼(1−𝐼)𝘀2𝛿，设H(n)为n次命中的次数，则H(n)=nh为一个二项分布E[H(n)]=nI，D[H(n)]=nI(1-I)，利用切比雪夫不等式：Prob[|h−I|ε]=Prob[|𝐻(𝑛)𝑛−E(𝐻(𝑛)𝑛)|ε]≥1−𝐷(𝐻(𝑛)𝑛)𝘀2=1−𝐷(𝐻(𝑛))𝘀2𝑛2=1−𝐼(1−𝐼)𝑛𝘀2由于n≥𝐼(1−𝐼)𝘀2𝛿，则𝐼(1−𝐼)𝑛𝘀2≤𝛿，因此Prob[|h−I|ϵ]≥1−δ．5．用上述算法，估计整数子集1~n的大小，并分析n对估计值的影响。解：运行代码：#includectime#includeset#includerandom#includecstdlib#includeiostreamusingnamespacestd;#defineN1000000#definePI3.1415926intmain(){random_devicerd;uniform_int_distributiondist(1,N);longlongnumber=dist(rd);doublecount=0;setintmyset;for(inti=0;i50;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);coutresultendl;couterr:\t1.0*abs(N-result)/Nendl;system(pause);return0;}运行结果为：n值估计值误差1000096373.63%10000011771017.71%100000089498310.50%1000000095605264.39%1000000001070118497.01%6．分析dlogRH的工作原理，指出该算法相应的u和v解：dlogRH采用了SherWood算法进行随机化的预处理该算法的C代码为：intdlogRH(intg,inta,intp){r=uniform(0..p-2);b=ModularExponent(g,r,p);//求g=brmodp,随机取其中一个元素c=mod(b*a,p);//((grmodp)(gxmodp))modp=gr+xmodp=c,将实例x转化为实例yy=logg,pc;//实验确定性算法求logp,gc,y=r+xreturn(y-r)mod(p-1);}在该算法中u为：((𝑔𝑟𝑚𝑜𝑑𝑝)(𝑔𝑥𝑚𝑜𝑑𝑝))𝑚𝑜𝑑𝑝=𝑔𝑟+𝑥𝑚𝑜𝑑𝑝=𝑐v为：(𝑙𝑜𝑔𝑝,𝑔(𝑠𝑡)𝑚𝑜𝑑𝑝)=(𝑙𝑜𝑔𝑝,𝑔𝑠+𝑙𝑜𝑔𝑝,𝑔𝑡)𝑚𝑜𝑑(𝑝−1)7．写一Sherwood算法C，与算法A，B，D比较，给出实验结果。解：运行代码：#includeiostream#includecmath#includerandom#includecstdlib#includeiostreamusingnamespacestd;#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);return0;}intsearch(intx,inti){return0;}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;uniform_int_distributiondist(0,n-1);inti=dist(rd);intmax=val[i];inty;for(intj=0;jsqrt(float(n));j++){inttemp=dist(rd);y=val[temp];if(maxy&&y=x){max=y;i=temp;}}returnsearch(x,i)+(int)sqrt((float)n);}intD(intx){random_devicerd;uniform_int_distributiondist(0,n-1);inti=dist(rd);inty=val[i];if(xy)returnsearch(x,head);elseif(xy)returnsearch(x,ptr[i]);elsereturni;}运行结果为：查找对象A算法比较次数B算法比较次数C算法比较次数D算法比较次数103302133132431435535433465430763368743798538109333111044101211546131263914137341514859均值74.46673.44.73338．证明：当放置（k+1)th皇后时，若有多个位置是开放的,则算法QueensLV选中其中任一位置的概率相等。证明：假设放置k+1个皇后时，有nb个位置是开放的，分别极为a,b…i…nb那么第a个位置被选到的概率为1∗12∗23∗…∗𝑖−1𝑖∗…∗𝑛𝑏−1𝑛𝑏=1𝑛𝑏第b个位置被选中的概率为12∗23∗…∗𝑖−1𝑖∗…∗𝑛𝑏−1𝑛𝑏=1𝑛𝑏第i个位置被选中的概率为1𝑖∗𝑖𝑖+1∗…∗𝑛𝑏−1𝑛𝑏=1𝑛𝑏第nb个位置被选到的概率为1𝑛𝑏所以算法QueensLV选中其中任一位置的概率为1𝑛𝑏．9．写一算法，求n=12~20时最优的StepVegas值。解：运行代码：#includecmath#includerandom#includectime#includecstdlib#includeiostreamusingnamespacestd;#defineN12#defineRUN_TIME100intx[N+1]={0};boolplace(intk);voidbacktrace(intstep);intQueenLV(intStepVegas);intmain(){intStepVegas,time_now,time_end;for(StepVegas=1;StepVegas=N;StepVegas++){intj=0,sucess=0;time_now=clock();do{while(!QueenLV(StepVegas));backtrace(StepVegas+1);if(x[N]!=0){sucess++;//coutsucess=sucessendl;for(inti=1;i=N;i++)x[i]=0;}j++;}while(jRUN_TIME);cout-------------StepVegas=StepVegas-------------endl;coutRunRUN_TIMEtimes,;coutsucesssucesstimes!,;coutsucessrateis100.0*sucess/RUN_TIMEendl;time_end=clock();coutIttakes(time_end-time_now)*1000/CLOCKS_PER_SEC/s