leecode第1227题：飞机座位分配概率

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

剩下的乘客将会：

• 如果他们自己的座位还空着，就坐到自己的座位上，
• 当他们自己的座位被占用时，随机选择其他座位

第n位乘客坐在自己的座位上的概率是多少？

原题链接

解题思路：

• 通过计算n=1，n=2，n=3，n=4可以发现，当n>1时，f(n)=0.5。直观上可以这样来理解：第一个人随机选择一个位置坐下；第二个人进来，如果发现自己的位置被占了，就把他赶走，然后坐在自己的位置上，这等价于第一个人刚开始坐在别的位置上，而第二个人的位置没有被占。到第n个人进来的时候，只会有位置被占或者不被占两种情况，因此概率为0.5。
• 将前面n-1人看成一个整体，n-1个人会占去n-1个位置，这n-1个位置中包含最后一个位置的概率是0.5。
  代码：

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