題目鏈接：點(diǎn)擊查看

題目大意：朵哈要坐飛機(jī)去旅游，出發(fā)的時候包括朵哈在內(nèi)一共有n個人要上飛機(jī)，這班飛機(jī)有n個座位，第i個人的座位號是i，朵哈的座位號是1。

現(xiàn)在n個人按照座位號是從1到n的順序上飛機(jī)，但朵哈忘了自己的座位，于是她就等概率隨機(jī)選了一個位置坐下了，而其余人都記得自己的位置，如果他們中的一個人上飛機(jī)之后發(fā)現(xiàn)自己的位置被占了，則會在剩下的位置中等概率隨機(jī)選一個坐下，如果沒被占，則會直接坐到自己的位置上。

你需要計(jì)算最后一個上飛機(jī)的人坐到了自己位置上的概率。

朵哈返程的時候，包括她在內(nèi)的m個人會按照一個隨機(jī)的座位號上飛機(jī)。

這班飛機(jī)有m個座位，朵哈的座位號還是1。但是朵哈又一次忘記了自己的座位，并且還是只有她忘記了自己的座位?，F(xiàn)在所有人找座位的規(guī)則和出發(fā)時完全相同，朵哈或任何一個發(fā)現(xiàn)自己座位已經(jīng)被占了的人會等概率隨機(jī)選一個沒被占的座位坐下。

你需要計(jì)算最后一個上飛機(jī)的人坐到了自己位置上的概率。

題目分析：

我們先來分析第一問，按照順序上飛機(jī)，很容易知道，當(dāng)n=1時，答案時1，當(dāng)n=2時，答案是0.5，那么我們來分析一下n大于等于3的情況，我們設(shè)f(i)為飛機(jī)上一共有i個人時的概率

當(dāng)朵哈坐在1號位，那么剩下n-1個人包括最后一個人在內(nèi)，肯定都能坐到自己的位置，所以此時概率為1

當(dāng)朵哈坐在n號位，那么第n個人最后上飛機(jī)，肯定坐不到自己的位置了，所以此時概率為0

當(dāng)朵哈坐在第k號位，那么第2~k-1個人可以坐在自己的位置上，輪到第k個人時會開始隨機(jī)坐，那么我們不妨將第k個人視為朵哈，將剩余的n-k個空位，視為新的n，以此類推，這樣遞推關(guān)系就很清晰了：f(n)=(1+f(2)+f(3)+……+f(n-2)+f(n-1))/n

其實(shí)自己在紙上畫一畫n=3和n=4的情況，應(yīng)該一下子也能確定第一問的概率當(dāng)n大于等于2時時恒等于0.5的了。。

接下來我們在第一問的基礎(chǔ)上討論第二問：

如果朵哈第1個上飛機(jī)，那么問題就轉(zhuǎn)化成了求f(m)

如果朵哈第2個上飛機(jī)，因?yàn)榈谝粋€人肯定坐在了自己的位置上，那么就是求f(m-1)

如果朵哈第3個上飛機(jī)，因?yàn)榍皟蓚€人肯定坐在了自己的位置上，那么就是求f(m-2)

如果朵哈第k個上飛機(jī)，因?yàn)榍発-1個人肯定坐在了自己的座位上，那么就是求f(m-k+1)

如果朵哈最后一個上飛機(jī)，那概率肯定時1

又因?yàn)閒(2)=f(3)=f(4)=……=f(n-1)=f(n)=0.5，

所以我們分兩種情況即可：

如果朵哈最后一個上飛機(jī)，概率為1

如果朵哈不是最后一個上飛機(jī)，概率為0.5

而朵哈上飛機(jī)的順序是隨機(jī)的，所以朵哈最后一個上飛機(jī)的概率為1/m，所以第二問的公式也就推出來了：

f(m)=(1/m)*1+(m-1/m)*0.5=(m+1)/(2*m)，n==1時也適用

上代碼：

#include<iostream> #include<cstdio> #include<string> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<cmath> #include<set> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e6+100;int main() { // freopen("input.txt","r",stdin);int w;cin>>w;int kase=0; while(w--){int n,m;scanf("%d%d",&n,&m);printf("Case #%d: ",++kase);if(n==1)printf("%.6f",1.0);elseprintf("%.6f",0.5);printf(" %.6f\n",((m+1)*1.0)/(2*m*1.0));}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的2019ICPC(银川) - Take Your Seat(概率公式)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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