算法學習筆記：17.蒙特卡洛算法 ——從原理到實戰，涵蓋 LeetCode 與考研 408 例題

在計算機科學和數學領域，蒙特卡洛算法（Monte Carlo Algorithm）以其獨特的隨機抽樣思想，成為解決復雜問題的有力工具。從圓周率的計算到金融風險評估，從物理模擬到人工智能，蒙特卡洛算法都發揮著不可替代的作用。本文將深入剖析蒙特卡洛算法的思想、解題思路，結合實際應用場景與 Java 代碼實現，并融入考研 408 的相關考點，穿插圖片輔助理解，幫助你全面掌握這一重要算法。

蒙特卡洛算法的基本概念

蒙特卡洛算法得名于摩納哥的著名賭城蒙特卡洛，因其核心思想與賭博中的隨機事件概率計算相似而得名。它是一種通過隨機抽樣來求解數學問題的數值方法，通過大量重復的隨機試驗，利用概率統計規律估計問題的解。

例如，在計算圓周率 π 時，蒙特卡洛算法的思路如下：

在一個邊長為 2 的正方形內，有一個半徑為 1 的內切圓（圓心與正方形中心重合）。
向正方形內隨機投擲大量點，記錄落在圓內的點的數量。
由于圓的面積與正方形面積之比為 π/4，因此通過 “圓內點數 / 總點數≈π/4” 可估算出 π 的值。

蒙特卡洛算法的關鍵特性包括：

隨機性：依賴隨機抽樣生成試驗數據，每次運行的結果可能不同。

概率性：結果是對真實解的概率估計，隨著試驗次數增加，估計值逐漸逼近真實解。

普適性：適用于難以用解析方法求解的復雜問題（如高維積分、復雜系統模擬等）。

效率與精度的權衡：試驗次數越多，結果精度越高，但計算成本也越高。

蒙特卡洛算法的思想

蒙特卡洛算法的核心思想是 **“以隨機模擬替代確定性計算，以概率估計逼近真實解”**，其基本流程可概括為：

問題建模：將實際問題轉化為可通過隨機抽樣求解的概率模型，明確需要估計的目標值（如 π、積分值、系統故障率等）。
隨機抽樣：根據問題模型生成符合特定概率分布的隨機樣本（如均勻分布、正態分布等）。
試驗與統計：對每個樣本進行試驗（如判斷點是否在圓內、模擬系統運行狀態等），記錄試驗結果。
估計求解：根據大量試驗的統計結果，計算目標值的估計值（如通過頻率估計概率）。
精度分析：通過增加試驗次數，降低估計值的誤差，直到結果滿足精度要求。

蒙特卡洛算法的數學基礎是大數定律：當隨機試驗的次數足夠多時，事件發生的頻率會穩定在其概率附近。因此，通過足夠多的抽樣試驗，蒙特卡洛算法的估計值會逐漸收斂到真實解。

蒙特卡洛算法的解題思路

使用蒙特卡洛算法解決實際問題時，通常遵循以下步驟：

明確問題目標：確定需要求解的量（如積分值、概率、最優解等）。
構建概率模型：將目標量與某個隨機事件的概率關聯起來，使目標量可通過該事件的頻率估計。
設計抽樣方案：確定隨機變量的概率分布（如均勻分布、正態分布），生成符合分布的隨機樣本。
執行隨機試驗：對每個樣本進行試驗，記錄試驗結果（如成功 / 失敗、數值大小等）。
統計與計算：根據試驗結果計算目標量的估計值，并分析誤差（如標準差、置信區間）。
優化與迭代：若結果精度不足，增加試驗次數后重復步驟 4-5，直至滿足要求。

例如，在計算定積分∫??f (x) dx（其中 0≤f (x)≤M）時，蒙特卡洛算法的步驟為：

構建一個矩形區域：x∈[a,b]，y∈[0,M]。
向矩形內隨機投擲 N 個點，統計落在曲線 y=f (x) 下方的點的數量 K。
積分值≈(b-a)×M×(K/N)（矩形面積 × 頻率）。

實際應用場景與 Java 代碼實現

場景 1：估算圓周率 π

解題思路

如前文所述，通過向正方形內隨機投點，利用圓內點數與總點數的比例估算 π。

代碼實現

import java.util.Random;public class MonteCarloPi {public static double estimatePi(int numTrials) {Random random = new Random();int inCircle = 0;for (int i = 0; i < numTrials; i++) {// 生成[-1,1)范圍內的隨機點(x,y)double x = random.nextDouble() * 2 - 1;double y = random.nextDouble() * 2 - 1;// 判斷點是否在圓內（x2 + y2 ≤ 1）if (x * x + y * y <= 1) {inCircle++;}}// 估算πreturn 4.0 * inCircle / numTrials;}public static void main(String[] args) {int trials = 10000000; // 1000萬次試驗double pi = estimatePi(trials);System.out.println("估算的π值：" + pi); // 輸出約為3.1415（隨試驗次數增加更接近真實值）System.out.println("誤差：" + Math.abs(pi - Math.PI));}}

場景 2：計算定積分

問題描述

使用蒙特卡洛算法計算定積分∫?1x2dx（真實值為 1/3≈0.3333）。

解題思路

積分區間為 x∈[0,1]，被積函數 f (x)=x2 的最大值為 1（當 x=1 時），因此構建一個邊長為 1 的正方形（x∈[0,1]，y∈[0,1]）。
向正方形內隨機投點，統計落在曲線 y=x2 下方的點的數量 K。
積分值≈K/N（N 為總點數，因正方形面積為 1）。

代碼實現

import java.util.Random;public class MonteCarloIntegral {public static double estimateIntegral(int numTrials) {Random random = new Random();int inArea = 0;for (int i = 0; i < numTrials; i++) {// 生成[0,1)范圍內的隨機點(x,y)double x = random.nextDouble();double y = random.nextDouble();// 判斷點是否在曲線y=x2下方if (y <= x * x) {inArea++;}}// 估算積分值return (double) inArea / numTrials;}public static void main(String[] args) {int trials = 10000000;double integral = estimateIntegral(trials);System.out.println("估算的積分值：" + integral);System.out.println("真實值：0.3333...");System.out.println("誤差：" + Math.abs(integral - 1.0 / 3));}}

場景 3：LeetCode 中的概率問題（模擬場景）

問題描述

給定一個函數rand7()，它返回 1 到 7 之間的均勻隨機整數。請使用rand7()實現rand10()，即返回 1 到 10 之間的均勻隨機整數。

解題思路

這是一個典型的通過低范圍隨機數生成高范圍隨機數的問題，可使用蒙特卡洛算法的思想：

利用rand7()生成兩個隨機數 a 和 b，構造一個范圍為 1-49 的隨機數（(a-1)*7 + b）。
忽略大于 40 的數（確保剩余 40 個數均勻分布），將 1-40 的數映射到 1-10（(num-1)%10 + 1）。
若生成的數大于 40，則重新生成，直到得到有效數（接受 - 拒絕抽樣法）。

代碼實現

public class Rand10 {// 假設已有rand7()函數private int rand7() {return (int) (Math.random() * 7) + 1;}public int rand10() {int num;do {// 生成1-49的隨機數int a = rand7();int b = rand7();num = (a - 1) * 7 + b;} while (num > 40); // 只保留1-40// 映射到1-10return (num - 1) % 10 + 1;}public static void main(String[] args) {Rand10 solution = new Rand10();// 測試：統計100000次結果的分布int[] count = new int[11]; // 索引0-10，忽略0for (int i = 0; i < 100000; i++) {int num = solution.rand10();count[num]++;}for (int i = 1; i <= 10; i++) {System.out.println("數字" + i + "出現次數：" + count[i]);}}}