PI day - Ước lượng số PI bằng phương pháp Monte Carlo

Ý tưởng chính

• Vẽ một hình vuông \(ABCD\) có cạnh là \(d\) tùy ý

• Vẽ một hình tròn \(O\) đồng tâm với hình vuông có bán kính là \(r = d/2\)

• Giả lập chấm \(n\) điểm ngẫu nhiên vào hình vuông, đếm số lượng các điểm \(k\) rơi vào trong hình tròn.

• Khi \(n\) càng lớn (tiến về vô cùng) thì tỷ số \(\displaystyle \frac k n\) sẽ dần tiến về tỷ số của diện tích của hình tròn \(O\) và diện tích hình vuông \(ABCD\):

$$\lim_{n \to \infty} \frac k n = \displaystyle \frac {S_O} {S_{ABCD}} = \frac {\pi r^2}{d^2} = \frac {\pi r^2}{(2r)^2} =\boxed { \frac {\pi} 4 }$$

Vậy \(\displaystyle 4\frac k n \approx \pi\).

Tính khoảng cách Euclide

Một điểm nằm trong hình tròn khi khoảng cách của nó đến tâm \(O\) bé hơn \(r\) và ngược lại. Theo hình vẽ trên, \(P\) nằm trong nên \(OP < r\) và \(Q\) nằm ngoài nên \(OQ > r\).

Dùng công thức tính khoảng cách Euclide để tính khoảng cách một điểm \(P\) đến \(O\):

$$|OP| = \sqrt{(P_x - O_x)^2 + (P_y - O_y)^2}$$

Demo