算法设计与分析

算法设计与分析姓名：方国庆学号：SA13011096Ex.1若将y←uniform(0,1)改为y←x,则上述的算法估计的值是什么？因为𝑘𝑛=1√2，所以4𝑘𝑛=4√2=2√2Ex2.在机器上用𝟒∫√𝟏−𝒙𝟐𝟏𝟎dx估计π值，给出不同的n值及精度。SourceCode:#includestdio.h#includestdlib.h#includetime.hintmain(){srand((unsigned)time(NULL));intcount,I;longn;for(n=100;n=10e8;n*=10){for(i=1,count=0;i=n;i++){floatx=(float)rand()/RAND_MAX;floaty=(float)rand()/RAND_MAX;if((x*x+y*y)1)count++;}printf(n=%d\nPi=%f\n,n,4*count/(float)n);}return0;}由上图可知，不同n值与Pi精度的关系如下表：n10e210e310e410e510e610e710e8Pi精度10.10.10.010.0010.0010.0001Ex3.设a,b,c和d是实数，且a≤b,c≤d,f:[a,b]→[c,d]是一个连续函数，写一概率算法计算积分：∫𝑓(𝑥)𝑑𝑥𝑏𝑎注意，函数的参数是a,b,c,d,n和f,其中f用函数指针实现，请选一连续函数做实验，并给出实验结果。SourceCode:#includestdio.h#includestdlib.h#includetime.h#defineN10000000doublefunction(doublex){return(x-2)*(x-2)-1;}doubleGenRandom(doublex,doubley){return((double)rand()/RAND_MAX)*(y-x)+x;}doublecaller(double(*f)(double),doublea,doubleb,doublec,doubled){inti,count;for(i=count=0;iN;++i){doublex=GenRandom(a,b);doubley=GenRandom(c,d);doubley0=function(x);if((0=y)&&(y=y0))count++;if((y0=y)&&(y=0))count--;}c=(c0)?0:c;d=(d0)?0:d;returncount*(d-c)*(b-a)/N;}intmain(){srand((unsigned)time(NULL));doublea,b,c,d;a=0;b=4;c=-1;d=3;doubleS=caller(function,a,b,c,d);printf(所求积分为：%lf.\n,S);return0;}设计算法时，考虑到由c,d取值与0的关系导致的四种可能状况。最后通过c=(c0)?0:c;d=(d0)?0:d;进行统一化处理，使得最后的代码准确而且简洁。本例中，使用函数f(x)=(x−2)2−1运行结果如下：所得结果在N=10e7时为1.333269，与实际值4/3误差不足为0.001%。*Ex4.设ε,δ是(0,1)之间的常数，证明：若I是∫𝑓(𝑥)𝑑𝑥10的正确值，h是由HitorMiss算法返回的值，则当n≥I(1-I)/ε2δ时有：Prob[|h-I|ε]≥1–δ上述的意义告诉我们：Prob[|h-I|≥ε]≤δ,即：当n≥I(1-I)/ε2δ时，算法的计算结果的绝对误差超过ε的概率不超过δ，因此我们根据给定ε和δ可以确定算法迭代的次数。解此问题时可用切比雪夫不等式，将I看作是数学期望。证明：I=∫𝑓(𝑥)𝑑𝑥10为点落在1/4圆内的概率记随机变量X为n个点中落在1/4圆内的点数量，则X~B(n,I),所以有:EX=n*IDX=n*I(1-I)EX.(ch2.3)用上述算法，估计整数子集1~n的大小，并分析n对估计值的影响。SourceCode:/*RandomlygetanelementfromsetintS*/intuniform(setintX){intm=rand()%X.size();setint::iteratoriter=X.begin();for(inti=0;im;iter++,i++);return*iter;}/*EstimatethesizeofsetintX*/intSetCount(setintX){setintS;inta;while(S.find(a=uniform(X))==S.end())S.insert(a);return(int)(2*S.size()*S.size()/Pi);}intmain(intargc,char*argv[]){setintX;srand((unsigned)time(NULL));/*InitializethesetintS*/for(inti=0;iSizeX;++i)X.insert(i);intN;for(N=10;N=1000;N*=10){/*CallSetCount(X)Ntimesanduseitsaverage*/intSum=0;for(inti=0;iN;++i)Sum+=SetCount(X);printf(N=%dXsize=%d\n,N,(Sum/N));}return0;}运行结果如下：由可见当n取值增大时，估计的集合大小与真实值越来越接近。Ex.(Ch3.2随机的预处理)分析dlogRH的工作原理,指出该算法相应的u和v该算法中的u是引入r将任意输入实例p随机化成实例c的部分,即程序中的b=ModularExponent(g,r,p)和c=bamodp;该算法重的v是由随机化后的输入实例c求出y后,利用y计算得到x的部分,即(y-r)mod(p-1)Ex.(Ch3.3搜索有序表)写一Sherwood算法C，与算法A,B,D比较，给出实验结果。SourceCode:#includestdio.h#includestdlib.h#includestring.h#includetime.h#includesys/time.h#includemath.h#defineREAPT_TIMES128#definen120000intval[n+1],ptr[n+1];intcount,head=4;intx=n/2;intSearch(intx,inti){count=1;while(xval[i]){i=ptr[i];count++;}returni;}intA(intx){returnSearch(x,head);}intD(intx){inti=rand()%n+1;inty=val[i];if(xy)returnSearch(x,head);if(xy)returnSearch(x,ptr[i]);returni;}intC(intx){inty,i=head;intmax=val[i];for(intj=1;j=n/6;j++){y=val[j];if(maxy&&y=x){i=j;max=y;}}returnSearch(x,i);}intB(intx){inty,i=head;intmax=val[i];for(intj=1;jsqrt(n);j++){y=val[j];if(maxy&&y=x){i=j;max=y;}}returnSearch(x,i);}voidGen_Data(){intindex,pre;head=(index=rand()%n+1);val[pre=head]=1;for(inti=2;i=n;){index=rand()%n+1;if(0==val[index]){val[index]=i;ptr[pre]=index;pre=index;i++;}}ptr[index]=0;}intmain(){srand((unsigned)time(NULL));memset(val,0,sizeof(val));Gen_Data();longlongcountA,countB,countC,countD;countA=countB=countC=countD=0;for(inti=1;i=REAPT_TIMES;i++){A(x);countA+=count;}for(inti=1;i=REAPT_TIMES;i++){D(x);countD+=count;}for(inti=1;i=REAPT_TIMES;i++){B(x);countB+=count;}for(inti=1;i=REAPT_TIMES;i++){C(x);countC+=count;}printf(countA=%lld\n,countA/REAPT_TIMES);printf(countD=%lld\n,countD/REAPT_TIMES);printf(countB=%lld\n,countB/REAPT_TIMES+(longlong)sqrt(n));printf(countC=%lld\n,countC/REAPT_TIMES+n/6);return0;}实验结果如下所示：实验中同样采用的多次计算取平均值的方法，以尽量减少偶然误差。从实验结果来看，使用概率算法所需的比较次数要明显少于其他各种算法。我使用的算法C是将原来B算法中的√𝑛改为n/6,所得比较次数要低于只比较一次的算法D，但不如比较√𝑛次的算法B。由此可见选取一个合理的比较次数对于提升算法性能十分重要。实验中的√𝑛被证明是能使算法性能最优的比较次数。Ex.(4.18后问题)证明：当放置（k+1)th皇后时，若有多个位置是开放的,则算法QueensLV选中其中任一位置的概率相等。证明：设第i个位置被选中的概率为P(i).由于第i个位置被选中表示在第i次判断ifuniform(1..nb)=1结果为真，并且对于∀m次(mi),都有该判断为假。则P(i)=1𝑖×(1−1𝑖+1)×(1−1𝑖+2)×…×(1−1𝑛𝑏)=1𝑖×𝑖𝑖+1×𝑖+1𝑖+2×𝑖+2𝑖+3×…×𝑛𝑏−2𝑛𝑏−1×𝑛𝑏−1𝑛𝑏=1𝑛𝑏因此，则算法QueensLV选中其中任一位置的概率相等。Ex.(4.18后问题)写一算法,求n=12~20时最优的StepVegas值。SourceCode:#includestdio.h#includestdlib.h#includetime.h#includesys/time.h#includestack#defineCHESS_SIZE18#defineREAPT_TIMES64usingnamespacestd;intchess[CHESS_SIZE+1];intstepVegas;stackintst;boolis_legal(introw,intcol);boolbacktrace(intk);boolQueenLV();voidPrint_ChessBoard(int,int);/*Checkifthecurrentpostionislegal*/boolis_legal(introw,intcol){if(row=2)for(intm=1;mrow;m++)if((col+row)==(chess[m]+m)||(col-row)==(chess[m]-m)||(col==chess[m]))returnfalse;returntrue;}/*tranditionalwaytosolveCHESS_SIZEqueensproblem*/boolbacktrace(intk){inti=k+1;int