搜索
π的计算算法与分析刘良凯13010199019算法一：基于割圆术单位圆的半周长π用内接正n边形的半周长𝜋𝑛来逼近。𝑎𝑛是正n边形的边长，𝑎2𝑛是正2n边形的边长，由勾股定理得递推公式：𝑎2𝑛=√2−√4−𝑎𝑛2n=6𝑎6=1计算结果如下：n𝒂𝒏𝝅𝒏61312√2−√33.10582854124√2−√2+√33.13262861348√2−√2+√2+√33.13935020396√2−√2+√2+√2+√33.141031951192√2−√2+√2+√2+√2+√33.141451472时间复杂度为O(n),但收敛速度较慢程序：#includestdio.h#includemath.h#includestdlib.h#includetime.hintmain(){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\n,cost);printf(%.9f\n,96*a);system(pause);return0;}结果：算法二：基于蒙特卡洛法在一个2×2的方格内进行随机投点，记下点落在半径为1的圆内的次数𝑛0以及总的投点次数n，π=4𝑛0/n。代码：#includestdio.h#includestdlib.h#includetime.h#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()/(RAND_MAX+2.0);if(x*x+y*y=1)n++;}end=clock();cost=(double)(end-begin)/CLOCKS_PER_SEC;printf(%lfseconds\n,cost);printf(pai=%lf\n,4*n/i);system(pause);return0;}此算法的时间复杂度为O（n），并且由于rand（）函数产生的只是伪随机数，因此结果误差会较大。输出结果：投点次数n模拟出的π值1003.20792110003.112887100003.1144891000003.13780910000003.139545100000003.141338算法三：数值积分法以单位圆的圆心为原点建立直角坐标系，则单位圆在第一象限内的部分G是一个扇形，由曲线y=11+𝑥2(x∈[0,1])及两条坐标轴围线，它的面积S＝π/4，算出S的近似值,它的4倍就是π的近似值。用一组平行于y的直线x＝x𝑖（1=i=n－1，0=x0x1…x𝑛−1x𝑛=1）将曲边梯形T分成n个小曲边梯形，总面积S分成这些小曲边梯形的面积总和。π=4∫11+𝑥210dx程序：n=5000；y［x＿］：＝4/（1＋x*x）；s1=（Sum［y［k/n］，｛k，1，n－1｝］＋（y［0］＋y［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-𝑥33+𝑥55-…+(−1)𝑛𝑥2𝑘−12𝑘−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．14159265358979323846通过观察arctanx=x-𝑥33+𝑥55-…+(−1)𝑛𝑥2𝑘−12𝑘−1+…式子发现，当x的绝对值小于1，最好是远比1小的时候，泰勒级数就会快速收敛，而当n的值越大时，得到的π值也就越精准。算法五：基于级数的快速收敛公式π=∑(−1)𝑖−12𝑖−1∞1×(48182𝑖−1+32572𝑖−1−202392𝑖−1)这是目前发现的计算π值收敛速度最快的级数形式的计算公式。π不仅能表示成无穷级数和无穷乘积的形式，还可以写成级数和乘积相结合的形式:π=2+13(2+25(2+37(2+⋯+𝑖2𝑖+1)))程序：#includestdio.h#includestdlib.h#includetime.hlongn=16366,i,p,d[16367];intmain(){clock_tbegin,end;doublecost;begin=clock();while(n-i)d[++i]=2000;for(;n;n-=14){for(p=0,i=n;i;i--){p=p*i+d[i]*10000;d[i]=p%(2*i-1);p/=2*i-1;}printf(%.4d,d[0]+p/10000);d[0]=p%10000;}end=clock();cost=(double)(end-begin)/CLOCKS_PER_SEC;printf(\n%lfseconds\n,cost);system(pause);return0;}输出结果：运行时间是0.274000s此算法的时间复杂度最低，且最终得到的值准确度最高。总结：机器运行时间(s)时间复杂度空间复杂度输出举例算法评价基于割圆术0.000000(time函数的算法的运行时间最低为1ms，低于1ms均为零)O(n)O(1)3.141452472算法的复杂度不高，运行时间也不长，精度不高基于蒙特卡洛法0.736000O(1)O(1)3.141338算法复杂度低，运行时间较长，精度较低基于积分法0.000000O(n)O(n)3．14159248692313算法复杂度较高，精度也较高，运行时间短基于级数0.000000O(n)O(n)3．14159265358979323846算法复杂度较高，精度也较高，运行时间短基于级数的快速收敛公式0.274000O(n2)O(n)精度有几千位算法复杂度高，运行时间适中，精度很高