前言

This Series aritcles are all based on the book 《经典算法大全》; 对于该书的所有案例进行一个探究和拓展，并且用python和C++进行实现; 目的是熟悉常用算法过程中的技巧和逻辑拓展。

提出问题

14.Algorithm Gossip:求 蒙地卡罗法求 PI 送分算法题， 非常简单， 就是一个正方形，里面内切一个比例， 随机描点，问在圆里面的点的比例 得到一个值 k (面积比)。 那么我们可以知道 (k = PI /4 ). 所以 PI = 4*k;

分析和解释

代码

#include <stdio.h> #include <stdlib.h> #include <time.h> #define N 50000 int main(void) { int i, sum = 0; double x, y; srand(time(NULL)); for(i = 1; i < N;i++) { x = (double)rand()/ RAND_MAX; y = (double)rand()/ RAND_MAX; if((x * x + y * y) < 1) sum++; } printf("PI = %f\n", (double)4 * sum / N); return 0; }

拓展和关联

Buffon 投针试验

布丰投针试验和这个原理类似， 有兴趣可以看看， 也是测算 PI

后记

参考书籍

《经典算法大全》维基百科