π的计算算法已修改.doc

1、的计算算法与分析刘良凯算法一：基于割圆术单位圆的半周长 用内接正 n 边形的半周长 ?来逼近。 ?是正 n边形的边长， ?2?是正 2n 边形的边长，由勾股定理得递推公式：计算结果如下：n612244896192=2n=6?2? 2 - 4- ?6=1?132- 32- 2+ 32- 2+ 2+ 32- 2+ 2+ 2+ 33.1414514722- 2+ 2+ 2+ 2+ 3时间复杂度为O(n), 但收敛速度较慢程序：#include #include #include #include int main()longdouble a;clock_tbegin,end;longdouble c

2、ost;begin=clock();a=sqrt(2-sqrt(2+sqrt(2+sqrt(2+sqrt(2+sqrt(3.0);end=clock();cost=( longdouble )(end-begin)/CLOCKS_PER_SEC;printf(%lfsecondsn,cost);printf(%.9fn,96*a);system( pause );return 0;结果：算法二：基于蒙特卡洛法在一个22的方格内进行随机投点，记下点落在半径为1 的圆内的次数 ?0以及总的投点次数n， =4?0/n。代码：#include #include #include #define RAN

3、D_MAX0x7fffint main()clock_tbegin,end;double cost;double n=0;int i=0;double x;double y;begin=clock();for (i=0;i=1000000;i+)x=rand()/(RAND_MAX+2.0);y=rand()/(RAND_MAX+2.0);if (x*x+y*y=i=n 1，0=x x x - ? 01 ?x =1）将曲边梯形1?T分成 n个小曲边梯形，总面积 S分成这些小曲边梯形的面积总和。=411 2dx0 1+ ?程序：n=5000；y x： 4/ （ 1 x*x ）；s1=（ Sum

4、y k/n ，k， 1， n 1（ y 0 y 1） /2 ） /n ； / 梯形公式Print N s1， 20， N Pi ， 30s2=（ y0 y 1 2*Sumy k/n ，k，1， n 1 4*Sum y k 1/2 ） /n ， k， 1，n） / （ 6*n ）； / 辛普森公式Print N s1， 20， N Pi ， 30结果： 3算法四：泰勒级数法35?2?- 1arctanx=x-?- +(- 1)?+3+52- 1?4 =arctan 12+arctan 13 =16arctan 1-4arctan15239程序：T x， n： Sum（ 1)k*x （ 2k 1）

5、 / （ 2k 1），k， 0，n;Print N 4* （ T1/2 ，260 T 1/3 ， 170）， 20；结果： 335?2?- 1通过观察 arctanx=x-?+?- +(- 1)?352 - 1 + 式子发现， 当 x的绝对值?小于 1，最好是远比 1小的时候，泰勒级数就会快速收敛，而当n的值越大时，得到的值也就越精准。算法五：基于级数的快速收敛公式?- 1483220(- 1) (+- =1-12?- 12?- 12?- 1)18572392?这是目前发现的计算值收敛速度最快的级数形式的计算公式。不仅能表示成无穷级数和无穷乘积的形式，还可以写成级数和乘积相结合的形式 : =2

6、+13(2+ 25 (2 + 37 ( 2 + ? + 2?+ 1) )程序：#include #include #include long n=16366,i,p,d16367;int main()clock_tbegin,end;double cost;begin=clock();while (n-i)d+i=2000;for (;n;n-=14)for (p=0,i=n;i;i-)p=p*i+di*10000;di=p%(2*i-1);p/=2*i-1;printf(%.4d ,d0+p/10000);d0=p%10000;end=clock();cost=( double )(end-begin)/CLOCKS_PER_SEC;printf(n%lfsecondsn,cost);system( pause );return 0;输出结果：运行时间是 0.274000s此算法的时间复杂度最低，且最终得到的值准确度最高。总结：机器运行时间时间复杂空间复杂输出举算法评价(s)度度例基于割圆0.000000(timeO(n)O(1)算法的复术函数的算法的杂度不运行时间最低高，运行为 1ms，低于 1ms时间也不均为零 )长，精度不高基于蒙特0.736000O(1)O(1)3.141338算法复杂卡洛法度低，运行时间较长，精度较低基于积分0.000000O(n)O(n)3算法复