算法設(shè)計(jì)和分析作業(yè)

算法設(shè)計(jì)與分析

徐班

SA18011072

一、概率算法部分

1.求“近似值的算法：若將y-uniforms,1)改為y-x,則上述的算法估計(jì)的值是什么？

解：改為y-x,最終值為4Xt=2a.

2.在機(jī)器上用41廣淳dx估計(jì)n值，給出不同的n值及精度。

解：運(yù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;

)

運(yùn)行結(jié)果為:

n值結(jié)果精度

100003.17362

1000003.136763

10000003.141613

100000003.141084

1000000003.141634

10000000003.141575

3.設(shè)a,b,c和d是實(shí)數(shù)，且251）,?8￡1,￡忸,0一?田是一個(gè)連續(xù)函數(shù)，寫一概率算法計(jì)算積

分:/（x）dx-

解：運(yùn)行代碼：

#include<ctime>

#include<cstdlib>

#include<cmath>

#include<iostream>

usingnamespacestd;

//MC積分函數(shù)

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

//測(cè)試函數(shù)

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;

)

運(yùn)行結(jié)果為:

n值結(jié)果精度

100005.5081

1000005.296682

10000005.316122

100000005.335963

1000000005.336883

10000000005.333944

4.若I是的正確值，h是由HitorMiss算法返回的值，則當(dāng)n2甯時(shí)，有：

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

解:任取n>空出,設(shè)H(n)為n次命中的次數(shù),則H(n)=nh為一個(gè)二項(xiàng)分布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.用上述算法，估計(jì)整數(shù)子集1~11的大小，并分析n對(duì)估計(jì)值的影響。

解：運(yù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;

運(yùn)行結(jié)果為:

n值估計(jì)值誤差

1000096373.63%

10000011771017.71%

100000089498310.50%

1000000095605264.39%

1000000001070118497.01%

6.分析dlogRH的工作原理，指出該算法相應(yīng)的u和v

解：dlogRH采用了SherWood算法進(jìn)行隨機(jī)化的預(yù)處理

該算法的C代碼為：

intdlogRH(intg,inta,intp)

{

r=uniform(0..p-2);

b=ModularExponent(g,r,p);//^<g=brmodp,隨機(jī)取其中一個(gè)元素

c=mod(b*a,p);//((grmodp)(gxmodp))modp=gr+xmodp=c,將實(shí)例x轉(zhuǎn)化為實(shí)例y

y=logg,pc;〃實(shí)驗(yàn)確定性算法求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比較，給出實(shí)驗(yàn)結(jié)果。

解：運(yùn)行代碼：

#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(shè)(n)算法

intB(intx);〃確定性為O(W)的確定性算法

intC(intx);〃在算法B基礎(chǔ)上改進(jìn)的SherWood算法

intD(intx);〃時(shí)間為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;

運(yùn)行結(jié)果為:

查找對(duì)象A算法比較次數(shù)B算法比較次數(shù)C算法比較次數(shù)D算法比較次數(shù)

10330

21331

32431

43553

54334

65430

76336

87437

98538

109333

11104410

1211546

1312639

1413734

1514859

均值74.46673.44.7333

8.證明：當(dāng)放置（k+l）th皇后時(shí)，若有多個(gè)位置是開放的,則算法QueensLV選中其中任一位

置的概率相等。

證明：假設(shè)放置k+1個(gè)皇后時(shí)，有nb個(gè)位置是開放的，分別極為a,b...i...nb

那么第a個(gè)位置被選到的概率為1*；*9…*匕*…*號(hào)=白

23Inbnb

第b個(gè)位置被選中的概率為；*|*...*—*...*獨(dú)廠二白

23Inbnb

第i個(gè)位置被選中的概率為工*3*…*號(hào)=2

I1+1nbnb

第nb個(gè)位置被選到的概率為々

nb

所以算法QueensLV選中其中任一位置的概率為

9.寫一算法，求n=12?20時(shí)最優(yōu)的StepVegas值。

解：運(yùn)行代碼：

#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;

運(yùn)行結(jié)果為:

N=12時(shí)，

StepVegas運(yùn)行時(shí)間/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

從運(yùn)行結(jié)果來看，當(dāng)StepVegas=5,6時(shí)運(yùn)行時(shí)間最少，且正確率較高。

N=13時(shí),

StepVegas運(yùn)行時(shí)間/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

從運(yùn)行結(jié)果來看，當(dāng)StepVegas=6時(shí)運(yùn)行時(shí)間最少，且正確率較高。

N=14時(shí),

StepVegas運(yùn)行時(shí)間/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

從運(yùn)行結(jié)果來看，當(dāng)StepVegas=7時(shí)運(yùn)行時(shí)間最少，且正確率較高。

N=15時(shí),

StepVegas運(yùn)行時(shí)間/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

從運(yùn)行結(jié)果來看，當(dāng)StepVegas=7,8時(shí)運(yùn)行時(shí)間最少，為7時(shí)正確率較高。

當(dāng)N大于15,運(yùn)行時(shí)間較長(zhǎng)，從上面幾個(gè)可以看出，當(dāng)StepVegas=N/4~N/2范圍內(nèi)，效果較

好。

10.PrintPrimes{//打印1萬以內(nèi)的素?cái)?shù)

print2,3；

n—5；

repeat

ifRepeatMillRab(n,)thenprintn;

n<—n+2;

untiln=10000;

)

與確定性算法相比較，并給出10070000以內(nèi)錯(cuò)誤的比例。

解：運(yùn)行代碼：

#include<set>

#include<random>

#include<cmath>

#include<cstdlib>

#include<iostream>

usingnamespacestd;

#defineN100

#definePI3.1415926

boolBeast(inta,intn);〃判斷強(qiáng)偽素?cái)?shù)

boolMiller_Rabin(intn);//MR算法

boolRepeat_Miller_Rabin(intk,intn);//MR算法重復(fù)K次

boolsimple(intn);//簡(jiǎn)單確定算法

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?“不是素?cái)?shù)”<<endl;

myset.erase(i);

)

)

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

else

(

set<int>::iteratorit;

cout?”MR算法沒有找到的素?cái)?shù)：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;