算法设计作业

Ex.1若将y-uniform（0,1）改为y-x,则上述算法估计的值是什么？

解：若令y-x,则原问题由平面投影到线段上了。随机产生的点都会落在线

段（0,0）-（V2,V2）上。所以k/n=l/V2,算法的输出为4k/n=2/七2.828。

故上述算法估计的值为2.828.

Ex.2在机器上用光估计n值，给出不同的n值及精度。

〃・，，

-#includelostream

Sinclude“math,h”

#include“time,h”

/include“stdlib.h"

usingnamespacestd;

臼voidmainO

(

doublex,y;

unsignedk,i,n;

n=10000;

for(j=0;j<5;j++)

(

n=n*10;

k=0;

srand((unsigned)time(0));

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

x=rand()*1.0/RAND_MAX;

y=rand0*1.0/RA1®_MAX;

if(y<=sqrt(1-x*x7)

k++;

)

cout«"n="«n«"时,"《"兀为"<4.0*k/

11

□X

C:\Windows\system32\cmd.exe

n=100000时，冗为3.14736

n=1000000时.兀为3.14021

n=10000000时.冗为3.1417

”100000000时，71^)3,14134

n=1000000000时，冗为3.1415

由截图可知:当n=100000时,精度(小数点后)为2位；当n=1000000时，

精度(小数点后)为2位；当n=10000000时，精度(小数点后)为3位；当

n=100000000时,精度(小数点后)为3位;当n=1000000000时,精度(小数

点后)为4位。

Ex3.设a,b,c和d是实数，且aWb,c<d,f:[a,b]—[c,d]是一个连续函

数，写一概率算法计算积分：「/(吟出(:注意，函数的参数是a,b,c,d,n和

f,其中f用函数指针实现，请选一连续函数做实验，并给出实验结果。

-^include“iostream”

#include"time,h”

^include*stdlib.h*

usingnamespacestd;

typedefdouble(*funcp)(double):

-doublef(doublex)

|(

returnx*x:|

-doubleuniform(doublem,doublen)

(

returnm-static_cast<double>(rand())/RAND_MAX*(n-m);

-doubleIntegral(doublea,doubleb,doublec,doubled,unsignedn,fimcpf)

|(

doublex.y:

unsignedi,k=0;

srand((unsigned)time(0))：

for(i=0:i<n:i++){

x=unifora(a,b):

y=unifcra(c,d):

if(y<=f(x))

k++:

)

return(b-a)*(d-c)*k/n+(b-a)*c;

L)

-voidmainO

{

doublea=1,b=2,c=1,d=4:

unsignedj,n：

n=100000;

funcppfun=f:

for(j=0;j<4:j++)

(

n=n♦10:

cout«*n=*«n«"时，"«"函数积分为为"«Integral(a,b,c,d,n,pfun)«*\n*:

)

图C:\Windows\system32\cmd.exe

=1000000时,函数积分为力2.3364

=10000000时，函数积分为为2.3335

=100000000时,函数积分为力2.33353

=1000000000时,函数枳分为为2.33333

'ressanykeytocontinue...

程序中我们设定的连续函数为KX）=",所求积分为/；%2热，理论值为

2.33333….由截图可知:当n=106时,精度（小数点后）为2位;当n=l（）7时,

精度（小数点后）为3位；当n=108时，精度（小数点后）为3位；当n=109时，

精度(小数点后)为5位。

EX5.用上述算法(SetCount),估计整数子集l~n的大小，并分析n对估计

值的影响。

-专include*iostream*

#includeh*

^include*stdlib.h*

usingnasespacestd：

-unsigneduniform(unsigneda,unsignedb)

return(rand()%/-a+1))+a：

[}

-doubleSetCount(unsignedn)

{.

unsignedk=0;

unsigned*s=newunsigned[n]：

for(unsignedi=0：i<n:i-)

s[i]=0;

srand((unsigned)tinie(0));

unsignedx-uniform(1,n):

do{

荒=1:

x=uniformd,n):

}while(s[x]=0);

delete[]s;

return2.0*k*k/3.1415926;

-voidmain()

unsignedn-500：

doublesum-0;

for(inti=0:i<5:i++)

,{

for(intj=0:j<5000:jl)

sum=sus-SetCount(n):

cout«"当n="«n«"时yUSetCountO运行5000次后取平均为YQg/5000«*\n\

..…*10;

国！C:\Windows\system32\cmd.exe

当n=500时SetCountC包亍1000次后取平均为399.887

当n=5000B^SetCountC包亍§000次后取平均为1269.42

当n=50000时SetCount<〉匈亍§000次后取平均力281.5.01

当n=500000时SetCount<〉闻亍§000次后取平均为41254.5

当n=5000000时SetCoimtC运行5000次后取平均为81291.3

Press