算法设计和分析作业

算法设计与分析

徐班

SA18011072

一、概率算法部分

1.求“近似值的算法：若将y-uniforms,1)改为y-x,则上述的算法估计的值是什么？

解：改为y-x,最终值为4Xt=2a.

2.在机器上用41广淳dx估计n值，给出不同的n值及精度。

解：运行代码：

#include<ctime>

#include<cstdlib>

#include<cmath>

#include<iostream>

#defineN1000000

usingnamespacestd;

voidHitorMiss()

(

doublex,y,Jx;

intent=0;

srand((unsigned)time(NULL));

for(inti=0;i<N;i++)

(

x=(double)rand()/RAND_MAX;

y=(double)rand()/RAND_MAX;

f_x=sqrt(1-x*x);

if(y<Lx)cnt++;

}

cout«4.0*cnt/N«endl;

)

intmain()

HitorMiss();

systemCpause");

return0;

)

运行结果为:

n值结果精度

100003.17362

1000003.136763

10000003.141613

100000003.141084

1000000003.141634

10000000003.141575

3.设a,b,c和d是实数，且251）,©8£1,£忸,0一©田是一个连续函数，写一概率算法计算积

分:/（x）dx-

解：运行代码：

#include<ctime>

#include<cstdlib>

#include<cmath>

#include<iostream>

usingnamespacestd;

//MC积分函数

voidMC(doublea,doubleb,doublec,doubled,double(*func)(double));

//测试函数

doubletest(doublex);

intmain()

(

MC(0,4,-1,8,test);

system(npause");

return0;

)

voidMC(doublea,doubleb,doublec,doubled,double(*func)(double))

intent=0,n=100000000;

doublex,y,f_x;

srand((unsigned)time(NULL));

for(inti=0;i<n;i++)

(

x=a+(b-a)*(double)rand()/RAND_MAX;

y=c+(d-c)*(double)rand()/RAND_MAX;

Jx=func(x);

if(y<f_x&&y>0)cnt++;

if(y<0&&y>f_x)ent—;

)

cout«36.0*cnt/n«endl;

)

doubletest(doublex)

(

returnx*x-2*x;

)

运行结果为:

n值结果精度

100005.5081

1000005.296682

10000005.316122

100000005.335963

1000000005.336883

10000000005.333944

4.若I是的正确值，h是由HitorMiss算法返回的值，则当n2甯时，有：

Prob[|h-I|<e]>1—6.

解:任取n>空出,设H(n)为n次命中的次数,则H(n)=nh为一个二项分布E[H(n)]=nLD[H(n)]

=nl(l-l),利用切比雪夫不等式：

Prob[|h—I|<e]=Prob--------E(-------I<£>1-------------=1------——=1------------

n\n九£/

由于则爷因此Prob[|h-I]<旬二1一3.

5.用上述算法，估计整数子集1~11的大小，并分析n对估计值的影响。

解：运行代码：

#include<ctime>

#include<set>

#include<random>

#include<cstdlib>

#include<iostream>

usingnamespacestd;

#defineN1000000

#definePl3.1415926

intmain()

{

random_devicerd;

uniform_int_distribution<>dist(l,N);

longlongnumber=dist(rd);

doublecount=0;

set<int>myset;

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«result«endl;

cout«"err:\t"«1.0*abs(N-result)/N«endl;

system(Hpausen);

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转化为实例y

y=logg,pc;〃实验确定性算法求logp,gc,y=r+x

return(y-r)mod(p-1);

)

在该算法中u为：((grmodp){gxmodp))modp=gr+xmodp=c

V为：(logp,g(st)modp)=(logp,gS+logpgt)mod(p-1)

7.写一Sherwood算法C,与算法A,B,D比较，给出实验结果。

解：运行代码：

#include<iostream>

#include<cmath>

#include<random>

#include<cstdlib>

#include<iostream>

usingnamespacestd;

#definetarget1

intn=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(W)的确定性算法

intC(intx);〃在算法B基础上改进的SherWood算法

intD(intx);〃时间为O(n)的概率算法

intmain()

(

cout«A(target)«endl;

cout«B(target)«endl;

cout«C(target)«endl;

cout«D(target)«endl;

systemCpause");

return0;

)

intsearch(intx,inti)

(

return0;

)

intA(intx)

{

returnsearch(x,head);

)

intB(intx)

(

inti二head;

intmax=val[i];

inty;

for(intj=0;j<sqrt(float(n));j++)

(

y=val[j];

if(max<y&&y<=x)

(

max=y;

i=j；

)

return(search(x,i)+(int)sqrt((float)n));

intC(intx)

random_devicerd;

uniform_int_distribution<>dist(O,n-1);

inti=dist(rd);

intmax=val[i];

inty;

for(intj=0;j<sqrt(float(n));j++)

(

inttemp=dist(rd);

y=val[temp];

if(max<y&&y<=x)

(

max=y;

i=temp;

)

)

returnsearch(x,i)+(int)sqrt((float)n);

)

intD(intx)

(

random_devicerd;

uniform_int_distribution<>dist(0,n-1);

inti=dist(rd);

inty=val[i];

if(x<y)

returnsearch(x,head);

elseif(x>y)

returnsearch(x,ptr[i]);

else

returni;

运行结果为:

查找对象A算法比较次数B算法比较次数C算法比较次数D算法比较次数

10330

21331

32431

43553

54334

65430

76336

87437

98538

109333

11104410

1211546

1312639

1413734

1514859

均值74.46673.44.7333

8.证明：当放置（k+l）th皇后时，若有多个位置是开放的,则算法QueensLV选中其中任一位

置的概率相等。

证明：假设放置k+1个皇后时，有nb个位置是开放的，分别极为a,b...i...nb

那么第a个位置被选到的概率为1*；*9…*匕*…*号=白

23Inbnb

第b个位置被选中的概率为；*|*...*—*...*独厂二白

23Inbnb

第i个位置被选中的概率为工*3*…*号=2

I1+1nbnb

第nb个位置被选到的概率为々

nb

所以算法QueensLV选中其中任一位置的概率为

9.写一算法，求n=12〜20时最优的StepVegas值。

解：运行代码：

#include<cmath>

#include<random>

#include<ctime>

#include<cstdlib>

#include<iostream>

usingnamespacestd;

#defineN12

#defineRUN_TIME100

intx[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++;

//cout«"sucess="«sucess«endl;

for(inti=1;i<=N;i++)

x[i]=0;

)

j++；

}while(j<RUN.TIME);

cout«"-------------StepVegas="«StepVegas«---------------"«endl;

cout«“Run”<<RUN.TIME«"times；';

cout«”sucess"«sucess«"times!,n;

cout«"sucessrateisn«100.0*sucess/RUN_TIME«end);

time_end=clock();

cout«"Ittakes"«(time_end-time_now)*1000/CLOCKS_PER_SEC/sucess;

cout«”tosolvethisproblem"«endl;

)

system("pausen);

return0;

)

boolplace(intk)

(

fbr(intj=l;j<k;j++)

{

if((abs(k-j)==abs(x[j]-x[k]))||x[j]==x[k])

returnfalse;

returntrue;

)

voidbacktrace(intstep)

(

if(step>N)return;

for(inti=1;i<=N;i++)

(

x[step]=i;

if(place(step))

backtrace(step+1);

)

)

intQueenLV(intStepVeags)

{

random_devicerd;

intline=1,nb=1,j=0;

while((line<=StepVeags)&&(nb>0))

(

nb=0;

j=0;

for(inti=1;i<=N;i++)

(

x[line]=i;

if(place(line))

(

nb++;

uniform_int_distribution<>dist(l,nb);

if(dist(rd)==l)j=i；

)

}

if(nb>0)x[line++]=j;

)

if(nb>0)

returntrue;

else

returnfalse;

运行结果为:

N=12时，

StepVegas运行时间/ms正确率

162.51100

26.82100

31.07100

40.2755198

50.16867583

60.16923165

70.2536

80.38461526

90.45161331

100.4418643

110.43100

121.54100

从运行结果来看，当StepVegas=5,6时运行时间最少，且正确率较高。

N=13时,

StepVegas运行时间/ms正确率

1352.19100

235.27100

34.63100

40.8100

50.2608792

60.15853782

70.2244949

80.33333333

90.41935531

100.38888936

110.57540

120.59100

131.9100

从运行结果来看，当StepVegas=6时运行时间最少，且正确率较高。

N=14时,

StepVegas运行时间/ms正确率

12044.94100

2187.77100

321.84100

43.099199

50.65656699

60.2790786

70.21126871

80.28571442

90.46428628

100.51612931

110.7225

120.85714342

130.58100

142.65100

从运行结果来看，当StepVegas=7时运行时间最少，且正确率较高。

N=15时,

StepVegas运行时间/ms正确率

113645.8100

21122.44100

3112.77100

416.03100

52.53100

60.61702194

70.27586287

80.28070257

90.435

100.61538526

110.56666730

120.61290331

130.71153852

140.75100

153.18100

从运行结果来看，当StepVegas=7,8时运行时间最少，为7时正确率较高。

当N大于15,运行时间较长，从上面几个可以看出，当StepVegas=N/4~N/2范围内，效果较

好。

10.PrintPrimes{//打印1万以内的素数

print2,3；

n—5；

repeat

ifRepeatMillRab(n,)thenprintn;

n<—n+2;

untiln=10000;

)

与确定性算法相比较，并给出10070000以内错误的比例。

解：运行代码：

#include<set>

#include<random>

#include<cmath>

#include<cstdlib>

#include<iostream>

usingnamespacestd;

#defineN100

#definePI3.1415926

boolBeast(inta,intn);〃判断强伪素数

boolMiller_Rabin(intn);//MR算法

boolRepeat_Miller_Rabin(intk,intn);//MR算法重复K次

boolsimple(intn);//简单确定算法

intmain()

(

set<int>myset;

for(inti=101;i<10000;i+=2)

(

if(simple(i))

myset.insert(i);

)

for(inti=101;i<10000;i+=2)

(

if(Repeat_Miller_Rabin((int)log((float)i),i))

{

if(myset.find(i)==myset.end())

cout«"MR算法找到的“wi«“不是素数”<<endl;

myset.erase(i);

)

)

if(myset.size()==0)cout«"MR算法完全正确!”<vendl;

else

(

set<int>::iteratorit;

cout«”MR算法没有找到的素数：n«endl;

for(it=myset.begin();it!=myset.end();it++)

cout«*it«n\t";

cout«endl;

)

system("pausen);

return0;

boolBeast(inta,intn)

ints=0,t=n-1,x=1;

do

(

S++；

t/=2;

}while(t%2==0);

for(inti=0;i<t;i++)

x=x*a%n;

if(x==1||x==n-1)

returntrue;