π的計算算法已修改.doc

1、的計算算法與分析劉良凱算法一：基于割圓術(shù)單位圓的半周長 用內(nèi)接正 n 邊形的半周長 ?來逼近。 ?是正 n邊形的邊長， ?2?是正 2n 邊形的邊長，由勾股定理得遞推公式：計算結(jié)果如下：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時間復(fù)雜度為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;結(jié)果：算法二：基于蒙特卡洛法在一個22的方格內(nèi)進行隨機投點，記下點落在半徑為1 的圓內(nèi)的次數(shù) ?0以及總的投點次數(shù)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結(jié)果： 3算法四：泰勒級數(shù)法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；結(jié)果： 335?2?- 1通過觀察 arctanx=x-?+?- +(- 1)?352 - 1 + 式子發(fā)現(xiàn)， 當(dāng) x的絕對值?小于 1，最好是遠比 1小的時候，泰勒級數(shù)就會快速收斂，而當(dāng)n的值越大時，得到的值也就越精準(zhǔn)。算法五：基于級數(shù)的快速收斂公式?- 1483220(- 1) (+- =1-12?- 12?- 12?- 1)18572392?這是目前發(fā)現(xiàn)的計算值收斂速度最快的級數(shù)形式的計算公式。不僅能表示成無窮級數(shù)和無窮乘積的形式，還可以寫成級數(shù)和乘積相結(jié)合的形式 : =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;輸出結(jié)果：運行時間是 0.274000s此算法的時間復(fù)雜度最低，且最終得到的值準(zhǔn)確度最高。總結(jié)：機器運行時間時間復(fù)雜空間復(fù)雜輸出舉算法評價(s)度度例基于割圓0.000000(timeO(n)O(1)算法的復(fù)術(shù)函數(shù)的算法的雜度不運行時間最低高，運行為 1ms，低于 1ms時間也不均為零 )長，精度不高基于蒙特0.736000O(1)O(1)3.141338算法復(fù)雜卡洛法度低，運行時間較長，精度較低基于積分0.000000O(n)O(n)3算法復(fù)