π的计算算法(已修改)

《π的计算算法(已修改)》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、π的计算算法与分析刘良凯13010199019算法一：基于割圆术单位圆的半周长π用内接正n边形的半周长πn来逼近。an是正n边形的边长，a2n是正2n边形的边长，由勾股定理得递推公式：a2n=2-4-an2n>=6a6=1计算结果如下：nanπn613122-33.105828541242-2+33.132628613482-2+2+33.139350203962-2+2+2+33.1410319511922-2+2+2+2+33.141451472时间复杂度为O(n),但收敛速度较慢程序：#include#include#i

2、nclude#includeintmain(){longdoublea;clock_tbegin,end;longdoublecost;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("%lfseconds",cost);printf("%.9f",96*a);system("pause");return0;}

3、结果：算法二：基于蒙特卡洛法在一个2×2的方格内进行随机投点，记下点落在半径为1的圆内的次数n0以及总的投点次数n，π=4n0/n。代码：#include#include#include#defineRAND_MAX0x7fffintmain(){clock_tbegin,end;doublecost;doublen=0;inti=0;doublex;doubley;begin=clock();for(i=0;i<=1000000;i++){x=rand()/(RAND_MAX+2.0);y=rand()/

4、(RAND_MAX+2.0);if(x*x+y*y<=1)n++;}end=clock();cost=(double)(end-begin)/CLOCKS_PER_SEC;printf("%lfseconds",cost);printf("pai=%lf",4*n/i);system("pause");return0;}此算法的时间复杂度为O（n），并且由于rand（）函数产生的只是伪随机数，因此结果误差会较大。输出结果：投点次数n模拟出的π值1003.20792110003.112887100003.1144891000003.13780910000

5、003.139545100000003.141338算法三：数值积分法以单位圆的圆心为原点建立直角坐标系，则单位圆在第一象限内的部分G是一个扇形，由曲线y=11+x2(x∈[0,1])及两条坐标轴围线，它的面积S＝π/4，算出S的近似值,它的4倍就是π的近似值。用一组平行于y的直线x＝xi（1>=i<=n－1，0=x0

6、［1］）/2）/n；//梯形公式Print［｛N［s1，20］，N［Pi，30］｝］s2=（y［0］＋y［1］＋2*Sum［y［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．14159248692313算法四：泰勒级数法arctanx=x-x33+x55-…+(-1)nx2k-12k-1+…π4=arctan12+arctan13π=16arctan15-4arctan1239程序：T［x＿，n＿］：＝Sum［（－1)^k*x^

7、（2k＋1）/（2k＋1），｛k，0，n｝］;Print［N［4*（T［1/2，260］＋T［1/3，170］），20］］；结果：3．14159265358979323846通过观察arctanx=x-x33+x55-…+(-1)nx2k-12k-1+…式子发现，当x的绝对值小于1，最好是远比1小的时候，泰勒级数就会快速收敛，而当n的值越大时，得到的π值也就越精准。算法五：基于级数的快速收敛公式π=1∞(-1)i-12i-1×(48182i-1+32572i-1-202392i-1)这是目前发现的计算π值收敛速度最快的级数形式的计算公式。π不仅能表示成无穷级数

8、和无穷乘积的形式，还可以写成级数和乘积