2014テンセント実習生の筆記試験--モンテカルロアルゴリズムは円周率を求めます

1795 ワード

これは2014テンセント実習生の筆記試験(西安、武漢駅)の26番目の問題です.2つの関数を与えて、その意味を理解させます.答えは、最初の関数式が(a,b)間のランダム小数を生成するために使用されます.第2の関数式はモンテカルロ確率アルゴリズムを用いて近似円周率を求める.
まず、この方法(モンテカルロアルゴリズム)を紹介します.
確率と統計理論法に基づいた計算方法.解いた問題を一定の確率モデルと結びつけ,計算機を用いて統計シミュレーションまたはサンプリングを実現し,問題の近似解を得た.例えば、x=aとx=bを与えると、ある曲線fとこの2つの縦線、およびx軸で囲まれた面積を求めることができ、y軸の横線y=cの中でc>=f(a)and c>=f(b)を起定することができ、非常にeasyであり、y=c、x=a、x=b、およびx軸で囲まれた矩形面積を求めることができ、その後、ランダムにこの矩形範囲のような点を大量に生成することができる.現在の曲線上部の点数と現在の曲線下部の点数を統計し、doteUpCount,nodeDownCountと表記し、要求される面積はdoteDownCountsが占める割合*矩形面積に近似することができる.
では、この問題の解法分析は以下のようになります.
数値積分法では、単位円の1/4の面積を求めてPi/4を求めてPiを得る.単位円の1/4面積は扇形で、辺長が1単位正方形の一部です.扇形面積S 1が正方形面積Sに占める割合K=S 1/Sを求めるだけですぐにS 1が得られ、Piの値が得られる.扇形面積が正方形面積に占める割合Kをどのように求めますか?1つの方法は、正方形に非常に多くの点をランダムに投入し、投げた点を正方形の各位置に落とす機会を等しくして、中に扇形内にどれだけの点が落ちているかを見ることです.扇形内に落ちた点数mと投げた点の総数nとの比m/nをkの近似値とする.Pが扇形内に落ちる要件はx^2+y^2<=1である.

#include < iostream > 
 #include < cmath > 
 #include < ctime > 
 #define  COUNT 500000  //        
 
 using   namespace  std;
 
 bool  InCircle( double  x, double  y) //    1/4      
 {
      if ((x * x + y * y) <= 1 ) return   true ;
      return   false ;
 } 
 void  main()
 {
      double  x,y;
      int  num = 0 ;
      int  i;
 
     srand((unsigned)time(NULL));
      for (i = 0 ;i < COUNT;i ++ )
      {
         x = rand() * 1.0 / RAND_MAX;
         y = rand() * 1.0 / RAND_MAX;
          if (InCircle(x,y)) num ++ ;
     } 
     cout << " PI: " << (num * 4.0 ) / COUNT << endl;
 }

結果:テスト

5
次の結果が表示されます.

3.13958
,

3.14041
,

3.13729
,

3.13859
,

3.14186.
プログラムソース:http://blog.csdn.net/nomad2/article/details/6307824ああ、実測しても間違いない.

いっしょにtalk C栗(第百三十五回:C言語例--execシリーズ関数一)

アルゴリズムの再帰(3)-チェーンテーブル操作