比较简单的题目,我的思路大概是这样的.
先假设f(n)为有 n 个人时,第 n 个人坐到自己位置的概率.
首先,第 1 个人随机选位置的时候,可能有三种情况:
选到了自己的位置,那么后面就不会有人发现自己座位被做了,此时第 n 个人一定会坐到自己的位置.
选到了第 n 个人的位置,这时第 n 个人就会坐到第 1 个人的位置上.
选到了第 k 个人位置,这时,第 k 个人前面的(除了第一个人)都坐到了自己的位置,直到第 k 个人时,问题转化求解f(n-k+1).
因此递推公式可以写成:
我们将一些值代入到公式中可以发现这样一个事情:
因此递推公式进一步简化成: