模擬+數學遞推+直覺來思考Leetcode飛機座位分配概率

首發於公眾號MyEncyclopedia，定期發布AI，算法，工程類深度和前沿文章。學習本文的最佳姿勢為收藏本文，發送本文連結到桌面版瀏覽器，打開文末閱讀原文，敲入代碼運行。

Leetcode 1227 是一道有意思的概率題，本篇將從多個角度來討論這道題。題目如下

有 n 位乘客即將登機，飛機正好有 n 個座位。第一位乘客的票丟了，他隨便選了一個座位坐下。剩下的乘客將會：如果他們自己的座位還空著，就坐到自己的座位上， 當他們自己的座位被佔用時，隨機選擇其他座位，第 n 位乘客坐在自己的座位上的概率是多少？

示例 1：輸入：n = 1 輸出：1.00000 解釋：第一個人只會坐在自己的位置上。

示例 2：輸入: n = 2 輸出: 0.50000 解釋：在第一個人選好座位坐下後，第二個人坐在自己的座位上的概率是 0.5。

提示：1 <= n <= 10^5

假設規模為n時答案為f(n)，一般來說，這種遞推問題在數學形式上可能有關於n的簡單數學表達式（closed form），或者肯定有f(n)關於f(n-k)的遞推表達式。工程上，我們可以通過通過多次模擬即蒙特卡羅模擬來算得近似的數值解。

Monte Carlo 模擬發現規律

首先，我們先來看看如何高效的用代碼來模擬。根據題意的描述過程，直接可以寫出下面代碼。seats為n大小的bool 數組，每個位置表示此位置是否已經被佔據。然後依次給第i個人按題意分配座位。注意，每次位置隨機數範圍在[0,n-1]，因此，會出現已經被佔據的情況，此時需要再次隨機，直至分配到空位。

暴力直接模擬

def simulate_bruteforce(n: int) -> bool:    &34;&34;&34;    seats = [False for _ in range(n)]    for i in range(n-1):        if i == 0:   i-th has his seat                seats[i] = True            else:                while True:                    rnd = random.randint(0, n - 1) 34;&34;    Simulates one round of complexity O(N).    :param n: total number of seats    :return: True if last one has last seat, otherwise False    &34;& for each person, the seats array idx available are [i, n-1]    for i in range(n-1):        if i == 0:   i-th still has his seat                pass            else:                rnd = random.randint(i, n - 1)  34;&34;    Simulates one round of complexity O(N).    :param n: total number of seats    :return: True if last one has last seat, otherwise False    &34;& for each person, the seats array idx available are [i, n-1]    for i in range(n-1):        if i == 0:   i-th still has his seat                seats[i] = True            else:                # 0 must not be available, now we have 0 and [i+1, n-1],                rnd = random.randint(i, n - 1)                if rnd == i:                    seats[0] = True                else:                    seats[rnd] = True    return not seats[n-1]

---

著作權歸作者所有。商業轉載請聯繫作者獲得授權，非商業轉載請註明出處。