solution

Phương pháp Monte Carlo ước lượng các đại lượng hình học/xác suất bằng lấy mẫu ngẫu nhiên. Để bài toán có đáp số xác định (không phụ thuộc bộ sinh ngẫu nhiên thật), ta dùng bộ sinh số giả ngẫu nhiên cố định sau.

Bộ sinh số giả ngẫu nhiên (để kết quả tái lập được, không dùng random thật): Cho số nguyên seed $\ge 0$. Đặt $s_0=\text{seed}$. Với $i=1,2,3,\dots$: $s_i = (1103515245 \cdot s_{i-1} + 12345) \bmod 2^{31}.$ Số ngẫu nhiên thứ $i$ là $u_i = s_i / 2^{31} \in [0,1)$. Dãy $u_1,u_2,u_3,\dots$ được lấy theo ĐÚNG thứ tự này, dùng tuần tự trong suốt quá trình mô phỏng.

Bài toán: Cho bán kính $R$ (số nguyên dương) và số điểm cần sinh $N$. Với $i=1,\dots,N$, lấy hai số ngẫu nhiên kế tiếp $u_{2i-1}, u_{2i}$ để tạo điểm $(x_i,y_i) = (u_{2i-1}\cdot R,\ u_{2i}\cdot R)$ — điểm ngẫu nhiên đều trong hình vuông $[0,R]\times[0,R]$. Đếm số điểm $k$ thỏa $x_i^2+y_i^2 \le R^2$ (nằm trong một phần tư hình tròn tâm gốc tọa độ, bán kính $R$).

Vì diện tích một phần tư hình tròn chiếm tỉ lệ $\pi/4$ diện tích hình vuông, ước lượng diện tích của TOÀN BỘ hình tròn bán kính $R$ là $\hat A = 4R^2 \cdot \dfrac{k}{N}$ (quy ước $\hat A = 0$ nếu $N=0$).

In ra $k$ và $\hat A$ (làm tròn 6 chữ số thập phân).

Ví dụ: với $N=3,\ R=2,\ \text{seed}=1$, kết quả là 3 16.000000.