Monte Carlo Method
Monte Carlo methods vary, but tend to follow a particular pattern:
- Define a domain of possible inputs.
- Generate inputs randomly from a probability distribution over the domain.
- Perform a deterministic computation on the inputs.
- Aggregate the results.
For example, consider a circle inscribed in a unit square. Given that the circle and the square have a ratio of areas that isπ/4, the value of π can be approximated using a Monte Carlo method:
- Draw a square, then inscribe a circle within it.
- Uniformly scatter objects of uniform size over the square.
- Count the number of objects inside the circle and the total number of objects.
- The ratio of the two counts is an estimate of the ratio of the two areas, which is π/4. Multiply the result by 4 to estimate π.
蒙特卡罗（Monte Carlo）算法计算圆周率的主要思想：给定边长为R的正方形，画其内切圆，然后在正方形内随机打点，设点落在圆内的概为P，则根据概率学原理：
$$P = 圆面积 / 正方形面积 ＝ PI R R / 2R * 2R = PI / 4。$$ 即 $$PI=4P$$。这样，当随机打点足够多时，统计出来的概率就非常接近于$$PI$$的四分之一了。
#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
int main()
{
const int MAX_TIMES = 2000000; // sample nunmber
srand(time(0));
int inside = 0;
for(int i = 0; i < MAX_TIMES; ++i) {
double x = (double)(rand())/ RAND_MAX;
double y = (double)(rand())/RAND_MAX;
if(x * x + y * y <= 1.0) ++inside;
// if(i % (MAX_TIMES / 100) == 0) cout << '.';
}
double pi = 4.0 * inside / MAX_TIMES;
cout << "/nPI = " << pi << endl;
return 0;
}