哎呀我做的好复杂，肯定是多绕了很多圈子，就是死算 (聊天灌水)  264次阅读

作者: 白沙纱 , 发表于: 2015-05-15 (3484天前) @ 剑剑风流

假定f(n)是指一共有n个人时，最后一个人(第n个人）坐到最后一个座位（第n个座位）的概率。f(100)就是题目。

则有
f(n)=sum(p(i)*f(n|i): i=1..n) ----(a)

其中
f(n|i)是第一个人选择第i个座位时，最后一个人（n)能坐在最后一个座位(n)的条件概率。
p(i)是第一个人选择第i个座位的概率，p(i)=1/n, for i=1..n

------------------------

然后就是简化理解f(n|i), 对于n>1:

当i=1的时候，也就是第一个人坐在第1个座位，后面全正确了，所以f(n|1)=1；
当i=n的时候，第n个人位置被第一个人占了（实际上最后那人肯定得坐在第一个座位，但读者此时不需要知道这个）， 所以f(n|n)=0；

当i=2时，也就是第一个人坐了第二个座位， 那第二个人就有（n-2+1)种选择了： 第一个座位和3..n的座位。
从第二个人选择的情况， 和最初一共有（n-2+1)个人然后从第一个人开始选择的情况是等价的。这句话表达不清楚，就举个例子把：

假如n=5, i=2, 求f(5|2)
此时，第二个人可以选择1，3，4，5四个座位， 第五个人坐在第5个座位的概率，就等价于
有1，2，3，4四个座位，从第一个人开始选择算起，求第四个人坐在第4个座位的概率（这个概率是f(4)哈)。
f(5|2)=f(4)
推广到n, 就是f(n|2)=f(n-2+1)

同理，当i>2时，也即第一个人坐了第i个座位，那1和i之间的人（不包括1和i)都会坐自己正确的位置，原本应该坐在i位置的人（如前记做第i个人） 就面临（n-i+1)种选择， 从他开始的情况就和f(n-i+1)等价。

则f(n|i)=f(n-i+1) ,对 2<=i

带入(a)
又已知f(1)=1

就可以得到递推公式了。
f(n)=(1/n)*(f(n|1) + sum(f(n|i) : i=2..n-1) + f(n|n))

=>f(n)=(1/n)*(1 + sum(f(n-i+1): i=2..n-1) + 0)

=>f(n)=(1/n)*(1+sum(f(i): i=2..n-1))

初始值
f(2)=0.5
然后就可以用程序递归了。

当然也可以手算做几个就知道都一样不用继续做下去了。