2014腾讯实习生笔试——蒙特卡洛算法求圆周率

这是2014腾讯实习生笔试（西安，武汉站）的第26题。给出二个函数，让你去理解其含义。答案是：第一个函数式用来产生（a,b）之间的随机小数。第二个函数式用蒙特卡洛概率算法求近似圆周率。

先介绍一下该方法（蒙特卡洛算法）：

以概率和统计理论方法为基础的一种计算方法。将所求解的问题同一定的概率模型相联系，用计算机实现统计模拟或抽样，以获得问题的近似解。比方，给定 x=a ，和 x=b ，你要求某一曲线 f 和这两竖线，及 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单位正方形的一部分。仅仅要能求出扇形面积 S1 在正方形面积 S 中占的比例 K=S1/S 就马上能得到 S1 ，从而得到 Pi 的值。如何求出扇形面积在正方形面积中占的比例 K 呢？一个办法是在正方形中随机投入非常多点，使所投的点落在正方形中每个位置的机会相等看当中有多少个点落在扇形内。将落在扇形内的点数 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，经过实測无误。