1：题目描述

有 n 位乘客即将登机，飞机正好有 n 个座位。第一位乘客的票丢了，他随便选了一个座位坐下。

剩下的乘客将会：

如果他们自己的座位还空着，就坐到自己的座位上，

当他们自己的座位被占用时，随机选择其他座位
第 n 位乘客坐在自己的座位上的概率是多少？

2：解题思路

1：先从简单的开始分析，如果n=1，则P(n)=1.0

2：如果n=2,则P(n)=0.5，若第一个人选了自己的位置，则第二个人可以坐到自己位置(符合)；若第一个人坐到了第二个人的位置，则第二个人就坐不到自己的位置(不符合)。所以P(2)=0.5；

3：如果n=3，先看总的情况数(情况数以若字分割):若第一个人选了自己的位置(概率为1/3)，则后续的人都可以做到自己的位置(符合)；若第一个人选了第3个人的位置(概率为1/3)，则第2个人是没有影响的，依旧可以坐到自己位置，但第3个人是坐不到自己位置的(不符合)；若第一个人选了第2个人的位置(概率为1/3)，第二个人会随机选位置（其实这里可以看做第二个人的位置应该是第一个人的位置，但他没票只能随机坐，这样就又转化为了第2点说到的情况）。P(3)=1/3+(1/3)*P(2)=(1/3)*(1+P(2))。

4：我们推广到n，由3的分析，我们可以看出第一个人的选择分为三大种情况：选到自己位置；选到n的(最后一人位置);选到除了这俩个位置之外的位置(设这个位置为第i个人的位置，1<i<n)，其实就又转化为了P(i)的问题。得出公式：

因为求和总数(n-1)-2+1必须大于等于0，上述公式必须要求n>=2;

3:代码

 

double nthPersonGetsNthSeat(int n){
    double p[n+1];
    double Sum; 
    p[1]=1.0;
    for(int i=2;i<=n;i++)
    {
        Sum=0;
        for(int j=2;j<=i-1;j++)
        {
            Sum+=p[j];
        }
        p[i]=1.0/i*(1+Sum);
    }
    return p[n];
}

但这种方法是会超时的。我们可以对递推公式进行优化。

4：公式优化

对于这种递推公式后面是求和的，可以写出n-1的递推公式，通过四则运算消去求和号，最终得到

P(n)=P(n-1)（n>=3），因为P(2)=0.5所以有:

double nthPersonGetsNthSeat(int n){
   return n==1?1.0:0.5;
}