π的计算算法(已修改).docx

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

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

2、oublea;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;}结果：算法二：基于蒙特卡洛法在一个2×2的方格内进行随机投点，记下点落在半径

3、为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<=;i++){x=rand()/(RAND_MAX+2.0);y=rand()/(RAND_MAX+2.0);if(x*x+y*y<=1)n++;}en

4、d=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.10003.100003.3.3.3.算法三：数值积分法以单位圆的圆心为原点建立直角坐标系，则单位圆在第一象限内的部分G是一个扇形，由曲线y=11+x2(

5、x∈[0,1])及两条坐标轴围线，它的面积S＝π/4，算出S的近似值,它的4倍就是π的近似值。用一组平行于y的直线x＝xi（1>=i<=n－1，0=x0

6、－1｝］＋4*Sum［y［k－1/2）/n］，｛k，1，n｝］）/（6*n）；//辛普森公式Print［｛N［s1，20］，N［Pi，30］｝］结果：π＝3．313算法四：泰勒级数法arctanx=x-x33+x55-…+(-1)nx2k-12k-1+…π4=arctan12+arctan13π=16arctan15-4arctan1239程序：T［x＿，n＿］：＝Sum［（－1)^k*x^（2k＋1）/（2k＋1），｛k，0，n｝］;Print［N［4*（T［1/2，260］＋T［1/3，170］），20］］；结果：3．通过观察arctan

7、x=x-x33+x55-…+(-1)nx2k-12k-1+…式子发现，当x的绝对值小于1，最好是远比1小的时候，泰勒级数就会快速收敛，而当n的值越大时，得到的π值也就越精准。算法五：基于级数的快速收敛公式π=1∞(-1)i-12i-1×(48182i-1+32572i-1-i-1)这是目前发现的计算π值收敛速度最快的级数形式的计算公式。π不仅能表示成无穷级数和无穷乘积的形式，还可以写成级数和乘积相结合的形式:π=2+13(2+25(2+37(2+…+i2i+1)))程序：#include#include#

8、includelongn=16366,i,p,d[16367];intmain(){clock_tbegin,end;doublecost;begi