有 n 位乘客即將登機(jī)，飛機(jī)正好有 n 個(gè)座位。第一位乘客的票丟了，他隨便選了一個(gè)座位坐下。
剩下的乘客將會(huì)：
如果他們自己的座位還空著，就坐到自己的座位上，
當(dāng)他們自己的座位被占用時(shí)，隨機(jī)選擇其他座位
第 n 位乘客坐在自己的座位上的概率是多少？
來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/airplane-seat-assignment-probability
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

乍一看應(yīng)該想到：對(duì)于第一個(gè)人有三種可能：

①坐上自己的座位，那么之后每一個(gè)人都能坐到自己的座位上

②坐上2~n-1內(nèi)的座位上（假設(shè)為x號(hào)），那么x之前的所有人都能坐上自己的座位，x號(hào)隨機(jī)坐，此時(shí)轉(zhuǎn)化為N=n-x+1的問(wèn)題

③直接坐上n的位置，n沒(méi)有位置坐

因此，我們可以從n=2開(kāi)始計(jì)算，存儲(chǔ)之前所有答案即可

要注意的是，雖然n=1時(shí)答案為1，但是存儲(chǔ)的答案應(yīng)該為0，因?yàn)槌薾號(hào)外的人坐上座位都會(huì)使得n號(hào)坐不上n座位

對(duì)于n=2，顯然概率為1/2

對(duì)于n=n呢？ 概率應(yīng)該為 (1/n)*1 (坐上自己位置)+(1/n)*P(n-1) (坐上2號(hào)位置，變成n-1人問(wèn)題)+(1/n)*P(n-2) (坐上2號(hào)位置，變成n-2人問(wèn)題) …+(1/n)*0 (坐上n號(hào)位置，直接gg)

即P(n)=(1/n)*1+(1/n)(P(n-1)+P(n-2)…+P(1))

有思路了就，寫(xiě)！

等等！

稍微算了兩個(gè)，在P(1)=0,P(2)=1/2的情況下，P(3)P(4)也都等于1/2

是不是，除了P(1)都等于1/2呢？

用數(shù)學(xué)歸納法其實(shí)很好證明，

在2~n-1時(shí)P等于1/2 1時(shí)P等于0的前提下，帶入以上通式可以得到P(n)就正好等于1/2!!!

而P(1)=0,P(2)=1/2

class Solution {public double nthPersonGetsNthSeat(int n) {if(n==1){return 1;}else{return 0.5;}} }

說(shuō)好的一行呢？

class Solution {public double nthPersonGetsNthSeat(int n) {return n==1?1:0.5;} }

總結(jié)

以上是生活随笔為你收集整理的【Java】LeetCode 1227. 飞机座位分配概率——数学好一行解决的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。